Algoritmi e Strutture Dati @ UniBO 2010/2011
Corso di Laurea in Informatica per il Management
Avvisi
Salta alla descrizione del corso
L'edizione 2010/2011 del corso è terminata. Nell'anno accademico 2011/2012 il corso di Algoritmi e Strutture dati rimane annuale, ma è diviso in due moduli. Il modulo A è tenuto dal prof. Luciano Bononi; il modulo B è tenuto da Moreno Marzolla.
- 7/2/2012
- I voti della prova scritta del 31/1/2012 sono pubblicati su AlmaEsami. Ricordo che il voto proposto è il voto finale, e include gli eventuali bonus ottenuti con le esercitazioni. È possibile visionare il compito il giorno venerdì 10/2/2012 (neve permettendo) alle ore 14:00 presso l'ufficio del docente. Chi intende accettare o rifiutare il voto deve inviarmi una mail entro la sera di martedì 14/2/2012. La mail deve provenire dal vostro indirizzo di posta istituzionale @studio.unibo.it. La mail deve contenere il vostro cognome, nome e numero di matricola; il corpo del messaggio deve essere ad esempio: "Accetto/Rifiuto il voto XX/30 conseguito nella prova scritta di Algoritmi e Strutture Dati del 31/1/2012.". Provvederò a registrare i voti senza la necessità della vostra presenza fisica.
- 2/2/2012
- Informo gli interessati che la pubblicazione dei voti della prova scritta del 31/2/2012 è rimandata alla prossima settimana.
- 11/1/2012
- I voti della prova scritta del 10/1/2012 sono pubblicati su AlmaEsami. Ricordo che il voto proposto è il voto finale, e include gli eventuali bonus ottenuti con le esercitazioni. È possibile visionare il compito il giorno martedì 17/1/2012 alle ore 14:00 presso l'ufficio del docente. Chi ha ottenuto almeno 18/30 può accettare o rifiutare il voto inviandomi una mail entro la sera di martedì 17/1/2012. La mail deve provenire dal vostro indirizzo di posta istituzionale @studio.unibo.it. La mail deve contenere il vostro cognome, nome e numero di matricola; il corpo del messaggio deve essere ad esempio: "Accetto/Rifiuto il voto XX/30 conseguito nella prova scritta di Algoritmi e Strutture Dati del 10/1/2012.". Provvederò a registrare i voti senza la necessità della vostra presenza fisica.
- 10/11/2011
- Pubblicate le date degli appelli d'esame della sessione invernale (gennaio-febbraio 2012). Le liste di iscrizione sono già aperte.
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] [Possibile soluzione]
- 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] [Possibile soluzione]
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, 1.5 MBs][.pdf, 1.1 MBs] Aggiornato 07/10/2010 - 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, 400.3 KBs] Aggiornato 19/10/2010Risorse- A. Montresor, Analisi di algoritmi (contiene numerose ulteriori dimostrazioni sulle proprietà delle notazioni asintotiche).
- 19/10/2010
- [Esercizi svolti]
- 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, 102.9 KBs][.pdf, 324.9 KBs] Aggiornato 28/10/2010Risorse- Codice sorgente della libreria Java ASDlab (in formato .zip, .tar.gz, dal sito di Giuseppe. F. Italiano).
- 02/11/2010
- [Esercizi svolti] (ultimo aggiornamento 3/11/2010)
- 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, 1.4 MBs][.pdf, 795.3 KBs] Aggiornato 11/11/2010Risorse- 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 svolti] [Bandiera.java] [Intervalli.java]
- 18/11/2010
- Statistiche (Libro di testo: Capitolo 5, esclusa la sezione 5.3
Selezione deterministica
).
[.odp, 235.3 KBs][.pdf, 1 MB] Aggiornato 23/11/2010 - 23/11/2010
- Alberi Binari di Ricerca (Libro di testo: Capitolo 6, escluse sezioni 6.3 e 6.6).
[.odp, 53.3 KBs][.pdf, 185.7 KBs] Aggiornato 23/11/2010 - 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, 290.5 KBs][.pdf, 629.5 KBs] Aggiornato 25/11/2010Risorse- 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 svolti]
- 9/12/2010, 14/12/2010
- Tabelle hash (Libro di testo: Capitolo 7).
[.odp, 1.4 MBs][.pdf, 951.2 KBs] Aggiornato 06/12/2010 - 16/12/2010
- Code con priorità (Libro di testo: Capitolo 8, solo sezione 8.1)
[.odp, 48.4 KBs][.pdf, 122.1 KBs] Aggiornato 23/02/2011 - 24/02/2011
- Union-find (Libro di testo: Capitolo 9, escluse sezioni 9.3, 9.4)
[.odp, 66.8 KBs][.pdf, 192.8 KBs] Aggiornato 24/02/2011 - 25/02/2011, 03/03/2011
- Tecniche Algoritmiche: Divide Et Impera (Libro di testo: Capitolo 10)
[.odp, 311.9 KBs][.pdf, 164.1 KBs] Aggiornato 24/02/2011 - 04/03/2011, 10/03/2011
- Tecniche Algoritmiche: Programmazione Dinamica (Libro di testo: Capitolo 10)
[.odp, 102.2 KBs][.pdf, 281.9 KBs] Aggiornato 10/03/2011Approfondimenti- 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 svolti su tecniche divide-et-impera
- 11/03/2010
- Tecniche Algoritmiche: Algoritmi greedy (Libro di testo: Capitolo 10)
[.odp, 58 KBs][.pdf, 187 KBs] Aggiornato 11/03/2011 - 17/03/2011
- Lezioni sospese per Festa per i 150 anni dell'unità nazionale
- 18/03/2011
- Il problema dello zaino
[.odp, 40.8 KBs][.pdf, 114.9 KBs] Aggiornato 18/03/2011 [Zaino.java] - 18/03/2010
- Esercizi risolti (CINA.java, Copiatutto.java) Aggiornato 18/03/2011
- 24/03/2011
- Grafi (Libro di testo: Capitolo 12, esclusa sezione 12.5.2)
[.odp, 949 KBs][.pdf, 701.4 KBs] Aggiornato 23/03/2011
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, 357 KBs][.pdf, 756.4 KBs] Aggiornato 23/03/2011 - 31/03/2011
- Minimo albero ricoprente (Minimum Spanning Tree) (Libro di testo: Capitolo 13, esclusa sezione 13.4)
[.odp, 85.6 KBs][.pdf, 378.3 KBs] Aggiornato 08/04/2011 - 01/04/2011
- Lezione annullata
- 07/04/2011
- Esercizi che verranno svolti in aula
Attenzione: la lezione si svolgerà in aula Ercolani 2 - 08/04/2011
- Cammini minimi (Libro di testo: Capitolo 14, esclusa sezione 14.4)
[.odp, 744.9 KBs][.pdf, 2.1 MBs] Aggiornato 08/04/2011
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
[.odp, 67.6 KBs][.pdf, 123.8 KBs] Aggiornato 14/04/2011
Esercizi e altro materiale
Esercizi svolti
- Esercizi sulla complessità asintotica
- Esercizi su strutture dati elementari
- Esercizi su ordinamento e heap
- Esercizi su alberi binari di ricerca
- Esercizi su algoritmi divide-et-impera
- Esercizi su programmazione dinamica
- Esercizi su visite di grafi
- Esercizi riepilogativi
Altri siti di interesse
- 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 [Testo con soluzioni] [Voti] |
| II | Secondo parziale: Venerdì 6 maggio 2011, ore 10:30, aula Ercolani 2 [Testo con soluzioni] [Voti verbalizzabili] |
| Prima Sessione | |
| I | Prova scritta: Venerdì 10 giugno 2011, ore 10:30, aula Ercolani 1 [Testo con soluzioni] |
| II | Prova scritta: Venerdì 8 luglio 2011, ore 10:30, aula Ercolani 1 [Testo con soluzioni] |
| Seconda Sessione | |
| I | Prova scritta: Lunedì 5 settembre 2011, ore 10:30, aula Ercolani 1 [Testo con soluzioni] |
| II | Prova scritta: Martedì 20 settembre 2011, ore 10:30, aula Ercolani 1 [Testo con soluzioni] |
| Terza Sessione | |
| I | Prova scritta: martedí 10/1/2012 ore 13:30, aula Ercolani 1 [Testo con soluzioni] |
| II | Prova scritta: martedí 31/1/2012 ore 10:30, aula Ercolani 1 [Testo con soluzioni] |
