Algoritmi e Strutture Dati @ UniBO 2010/2011
Corso di Laurea in Informatica per il Management
Salta al programma 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.
Torna in cima alla pagina.
Salta alle modalità d'esame
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
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.
Torna in cima alla pagina.
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
Torna in cima alla pagina.
Salta ai lucidi delle lezioni
Orario del corso di Algoritmi e Strutture Dati, AA 2010/2011
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 |
Torna in cima alla pagina.
Salta ad altro materiale
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]
- 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]
- 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]
- 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]
- 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]
- 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
Torna in cima alla pagina.
Salta agli esami
Torna in cima alla pagina.
Appelli d'esame per il corso di Algoritmi e Strutture Dati, AA 2010/2011
|
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
|
Torna in cima alla pagina.