Algoritmi e Strutture Dati @ UniBO 2010/2011
Corso di Laurea in Informatica per il Management
Avvisi
Salta alla descrizione del corso
Questa pagina si riferisce all'edizione 2010/2011 del corso. Vai alla pagina dell'edizione più recente.
Descrizione del corso
Questa è la pagina web del corso di Algoritmi e Strutture Dati (Anno Accademico 2010/2011), corso di laurea in Informatica per il Management, Università di Bologna. Il docente del corso è Moreno Marzolla.
Programma e libri di testo
Questo è il programma del corso
- Complessità asintotica degli algoritmi
- Strutture dati elementari (Liste, Pile, Code, Alberi...)
- Algoritmi di ordinamento e ricerca (Insertion Sort, Selection Sort, Bubble Sort, Merge Sort, Quick Sort, Heap Sort)
- Limite inferiore alla complessità del problema dell'ordinamento basato su confronti
- Algoritmi di ordinamento in tempo lineare (Counting Sort, Pigeonhole Sort, Radix Sort, Bucket Sort)
- Algoritmi di selezione (QuickSelect)
- Alberi binari di ricerca, alberi AVL
- B-Trees
- Tabelle Hash, analisi della risoluzione delle collisioni mediante indirizzamento aperto o concatenazione
- Code di priorità
- Strutture union-find; euristiche quick-union e quick-find
- Tecniche Algoritmiche: divide et impera, algoritmi greedy, programmazione dinamica
- Grafi e visite di grafi: visita in ampiezza e profondità
- Algoritmi su grafi: albero minimo di copertura, cammini minimi da singola sorgente (algoritmo di Dijkstra), distanze minime tra tutte le coppie di vertici
Testo adottato
- Camil Demetrescu, Irene Finocchi, Giuseppe F. Italiano, Algoritmi e strutture dati 2/ed, McGraw-Hill, 2008, ISBN: 978 88 386 64687
Testi di consultazione
- Alan A. Bertossi, A. Montresor, Algoritmi e strutture di dati, CittàStudi, 2010, ISBN: 9788825173567. Questo è un ottimo testo didattico sugli algoritmi e strutture dati. Esso copre essenzialmente gli stessi argomenti del libro di Demetrescu et al.
- Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, Clifford Stein, Introduzione agli algoritmi e strutture dati 2/ed, McGraw-Hill, 2005, ISBN: 9788838662515. Questo è uno dei testi classici sugli algoritmi, offre una trattazione piuttosto approfondita di tutti gli argomenti principali. Si noti che questo libro include molto più materiale rispetto a quanto verrà svolto a lezione, e richiede buone basi matematiche per comprendere le dimostrazioni. Questo libro è pertanto consigliato a coloro che desiderano approfondire gli argomenti svolti, oppure a chi sia particolarmente appassionato alla materia.
- Camil Demetrescu, Umberto Ferraro Petrillo, Irene Finocchi, Giuseppe F. Italiano, Progetto di Algoritmi e Strutture Dati in Java, McGraw-Hill, 2007, ISBN: 9788838663741. Questo libro è il complemento del testo adottato, poiché contiene la descrizione delle implementazioni Java degli algoritmi descritti tramite pseudocodice nel libro di Demetrescu et al. Attenzione: questo volume NON sostituisce il libro di Demetrescu, Finocchi, Italiano, perché non contiene la parte di teoria che vedremo a lezione.
Modalità d'esame
Salta all'orario delle lezioni
Nota: le modalità d'esame riportate in seguito valgono a partire dall'anno accademico 2010/2011. Chi sostiene le prove scritte negli ultimi due appelli dell'anno accademico precedente (ossia gli appelli regolari di gennaio-febbraio 2011) deve fare riferimento alle vecchie modalità d'esame, che prevedono la consegna obbligatoria del progetto entro il 28 febbraio 2011. Chi ha già sostenuto la prova scritta e non consegna il progetto entro il 28 febbraio 2011, dovrà risostenere l'esame con le nuove modalità.
L'esame finale consiste in una prova scritta: l'esame si considera superato se alla prova scritta si ottiene un voto di almeno 18/30. Non è previsto alcun orale: solo in casi particolari il docente si riserva la possibilità di richiedere un colloquio orale (ad esempio in situazioni di sospetta "copiatura" allo scritto).
Durante le prove scritte o i parziali non è consentito usare libri o appunti; sarà però distribuito assieme al testo del compito questo formulario contenente alcune formule utili.
Durante il corso sarà possibile sostenere due prove parziali (scritte), che si svolgeranno a metà e al termine del corso. Chi ottiene almeno 18/30 in entrambi i parziali ha superato l'esame con voto pari alla media dei voti ottenuti. Al termine del corso, durante il primo appello d'esame sarà possibile recuperare uno dei due parziali; le domande del parziale di recupero saranno ovviamente relative solo alla parte di programma del parziale da recuperare. Potrà sostenere la prova di recupero solo chi ha partecipato a entrambi i parziali durante il corso, ed è risultato insufficiente solo in una di essi.
Durante il corso verranno assegnate tre esercitazioni di programmazione da svolgere a casa. Le esercitazioni sono facoltative e devono essere svolte singolarmente. Ciascuna esercitazione dovrà essere consegnata entro la data che verrà comunicata di volta in volta (il testo e le scadenze delle esercitazioni saranno indicati in questa pagina). Una esercitazione positiva verrà valutata 1 punto, mentre una esercitazione insufficiente (o non consegnata) verrà valutata zero punti. I punti così ottenuti verranno sommati al voto della prova scritta (o alla media dei voti delle prove parziali) contribuendo quindi ad innalzare il voto finale.
Esercitazioni di programmazione
- Prima esercitazione: [Testo]
- Seconda esercitazione: [Testo]
- Terza esercitazione: [Testo] [Template Java] [test1.dat deve produrre come risultato circa 10.98] [test2.dat deve produrre come risultato circa 8.78]
Orario delle lezioni
| Primo Semestre | |
|---|---|
| Martedì | 11:30—13:30, aula Ercolani 1 |
| Giovedì | 10:30—13:30, aula Ercolani 1 |
| Secondo Semestre | |
| Giovedì | 14:30—16:30, aula Ercolani 1 |
| Venerdì | 10:30—13:30, aula Ercolani 1 |
Lucidi delle lezioni
I lucidi non sono da considerare come sostitutivi né dei testi di riferimento né della frequenza alle lezioni, che costituiscono importanti elementi per una buona preparazione dell'esame; i lucidi messi a disposizione costituiscono soltanto uno schema di parte delle lezioni. Non si garantisce la correttezza di quanto riportato nei lucidi: segnalazioni di errori sono ovviamente sempre ben gradite.
Copyright notice: I lucidi delle lezioni sono
distribuiti con licenza Creative
Commons attribution-noncommercial-share alike (l'esatta versione
della licenza applicata è indicata nella seconda pagina di
ciascuna serie di lucidi). L'autore dei lucidi è Moreno Marzolla; in alcuni
casi il materiale originario è stato sviluppato da Alberto Montresor che
l'ha reso disponibile
con la medesima licenza.
- 5/10/2010
- Introduzione al corso
[ODP] [PDF] - 7/10/2010, 12/10/2010, 14/10/2010
- Stima della complessità asintotica degli algoritmi; le notazioni asintotiche
(Libro di testo: Capitolo 2, escluso: dimostrazione del teorema fondamentale della ricorrenza, sezione 2.7.2 e 2.8).
[PDF]Risorse- A. Montresor, Analisi di algoritmi (contiene numerose ulteriori dimostrazioni sulle proprietà delle notazioni asintotiche).
- 19/10/2010
- Esercizi
- 21/10/2010
- Lezione annullata causa sessione di laurea
- 26/10/2010, 28/10/2010
- Strutture dati elementari: array, liste, code, alberi; visite di alberi (Libro di testo: Capitolo 3).
[ODP] [PDF 4up]Risorse- Codice sorgente della libreria Java ASDlab (in formato .zip, .tar.gz, dal sito di Giuseppe. F. Italiano).
- 02/11/2010
- Esercizi
- 04/11/2010, 09/11/2010. 11/11/2010
- Algoritmi di Ordinamento (Libro di testo: Capitolo 4; solo cenni della sezione 4.5.1
Analisi di QuickSort
).
[ODP] [PDF 4up]Risorse- Confronto grafico tra diversi algoritmi di ordinamento
- C. A. R. Hoare, Quicksort, The Computer Journal 1962 5(1):10-16; doi:10.1093/comjnl/5.1.10
- Robert Sedgewick, Implementing Quicksort programs, Comm. ACM, 21(10), 1978, pp. 847—857
- 16/11/2010
- Esercizi
- 18/11/2010
- Statistiche (Libro di testo: Capitolo 5, esclusa la sezione 5.3
Selezione deterministica
).
[ODP] [PDF 4up] - 23/11/2010
- Alberi Binari di Ricerca (Libro di testo: Capitolo 6, escluse sezioni 6.3 e 6.6).
[ODP] [PDF 4up] - 25/11/2010, 30/11/2010, 2/12/2010
- Alberi bilanciati di Ricerca (Libro di testo: Capitolo 6, escluse sezioni 6.3 e 6.6).
[ODP] [PDF 4up]Risorse- GNU libavl è una implementazione in C degli alberi AVL
- Implementazione Java della struttura dati AVLTree
- Comer, D. 1979. The Ubiquitous B-Tree. ACM Comput. Surv. 11, 2 (Jun. 1979), 121-137.
- 7/12/2010
- Esercizi
- 9/12/2010, 14/12/2010
- Tabelle hash (Libro di testo: Capitolo 7).
[ODP] [PDF 4up] - 16/12/2010
- Code con priorità (Libro di testo: Capitolo 8, solo sezione 8.1)
[ODP] [PDF 4up] - 24/02/2011
- Union-find (Libro di testo: Capitolo 9, escluse sezioni 9.3, 9.4)
[ODP] [PDF 4up] - 25/02/2011, 03/03/2011
- Tecniche Algoritmiche: Divide Et Impera (Libro di testo: Capitolo 10)
[ODP] [PDF 4up] - 04/03/2011, 10/03/2011
- Tecniche Algoritmiche: Programmazione Dinamica (Libro di testo: Capitolo 10)
[ODP] [PDF 4up]Approfondimenti- Notes on Dynamic Programming a cura di
Luca Trevisan contiene una spiegazione molto chiara del problema discusso nel problema 10.7
pag. 275 del libro di testo (problema del
Dottor Copiatutto
)
- Notes on Dynamic Programming a cura di
Luca Trevisan contiene una spiegazione molto chiara del problema discusso nel problema 10.7
pag. 275 del libro di testo (problema del
- 11/03/2011
- Esercizi
- 11/03/2010
- Tecniche Algoritmiche: Algoritmi greedy (Libro di testo: Capitolo 10)
[ODP] [PDF 4up] - 17/03/2011
- Lezioni sospese per Festa per i 150 anni dell'unità nazionale
- 18/03/2011
- Il problema dello zaino
[ODP] [PDF 4up] [Zaino.java] - 18/03/2010
- Esercizi
- 24/03/2011
- Grafi (Libro di testo: Capitolo 12, esclusa sezione 12.5.2)
[ODP] [PDF 4up]
Approfondimenti- A. Broder, R. Kumar, F. Maghoul, P. Raghavan, S. Rajagopalan, R. Stata, A. Tomkins, J. Wiener, Graph structure in the web
- 25/03/2011
- Algoritmi di visita di grafi (Libro di testo: Capitolo 12, esclusa sezione 12.5.2)
[ODP] [PDF 4up] - 31/03/2011
- Minimo albero ricoprente (Minimum Spanning Tree) (Libro di testo: Capitolo 13, esclusa sezione 13.4)
[ODP] [PDF 4up] - 01/04/2011
- Lezione annullata
- 07/04/2011
- Esercizi
Attenzione: la lezione si svolgerà in aula Ercolani 2 - 08/04/2011
- Cammini minimi (Libro di testo: Capitolo 14, esclusa sezione 14.4)
[ODP] [PDF 4up]
Attenzione: la lezione si svolgerà in aula Seminari 1, Piano Terra, Dipartimento di Scienze dell'Informazione. Verranno anche distribuiti i questionari di valutazione della didattica, per cui si raccomanda la presenza in aula. - 14/04/2011
- Esercizi
Approfondimenti
- Moreno Marzolla, Esercizi di Algoritmi e Strutture
Dati
[odt]
[PDF]
Documento distribuito in accordo con la licenza Creative Commons Attribution-ShareAlike 3.0 Unported (CC-BY-SA 3.0)
- Corso di Algoritmi e Strutture Dati, prof. Alberto Montresor, Università di Trento
- Corso di Algoritmi e Strutture Dati, prof. Giuseppe F. Italiano, Università di Roma
Tor Vergata
- The Stony Brook Algorithm Repository
- Programming Pearls
- Codice sorgente della libreria Java ASDlab (in formato .zip, .tar.gz, dal sito di Giuseppe. F. Italiano).
Esami
| Parziali | |
|---|---|
| I | Primo parziale: Lunedì 17 gennaio 2011, ore 10:30, aula Ercolani 2 |
| II | Secondo parziale: Venerdì 6 maggio 2011, ore 10:30, aula Ercolani 2 |
| Prima Sessione | |
| I | Prova scritta: Venerdì 10 giugno 2011, ore 10:30, aula Ercolani 1 |
| II | Prova scritta: Venerdì 8 luglio 2011, ore 10:30, aula Ercolani 1 |
| Seconda Sessione | |
| I | Prova scritta: Lunedì 5 settembre 2011, ore 10:30, aula Ercolani 1 |
| II | Prova scritta: Martedì 20 settembre 2011, ore 10:30, aula Ercolani 1 |
| Terza Sessione | |
| I | Prova scritta: martedí 10/1/2012 ore 13:30, aula Ercolani 1 |
| II | Prova scritta: martedí 31/1/2012 ore 10:30, aula Ercolani 1 |
