Algoritmi e Strutture Dati
Laurea in Informatica per il Management, Università di Bologna, AA 2020/2021
Avvisi
Salta al programma e libri di testo
- 30/9/2021
- Questa edizione del corso è terminata. Il conitenuto di questa pagina va considerato copia d'archivio.
Descrizione del corso, programma e libri di testo
Questa è la pagina del corso di Algoritmi e Strutture Dati moduli 2/3, corso di laurea in Informatica per il Management, AA 2020/2021, Università di Bologna.
Il modulo 2 è tenuto dal prof. Moreno Marzolla, mentre il modulo 3 è tenuto dal prof. Saverio Giallorenzo.
Programma:
- Complessità ammortizzata degli algoritmi
- Visite di grafi
- Algoritmi divide-et-impera
- Tecniche greedy
- Programmazione dinamica
- Minimum Spanning Tree
- Cammini minimi
- Fondamenti teorici della calcolabilità: macchine di Turing, asserzioni e invarianti
Testo adottato
-
Alan A. Bertossi, A. Montresor, Algoritmi e
strutture di dati (terza edizione), CittàStudi, 2014, ISBN:
9788825173956 [Errata Corrige]
Dispensa di esercizi svolti
-
Moreno Marzolla, Esercizi di Algoritmi e Strutture
Dati
[odt]
[PDF]
Questa dispensa contiene esercizi (con soluzione) relativi agli argomenti svolti nel corso. Per la maggior parte si tratta di esercizi tratti da vecchie prove d'esame. La dispensa è soggetta a revisioni, per cui si prega di fare sempre riferimento alla versione più recente.
La dispensa Esercizi di Algoritmi e Strutture Dati di Moreno Marzolla è distribuito con Licenza Creative Commons Attribuzione - Condividi allo stesso modo 4.0 Internazionale
Altri testi di consultazione
-
Jeff Erickson, Algorithms
(liberamente scaricabile in formato PDF)
Questo libro (in inglese) copre più o meno il programma che svolgeremo a lezione. L'autore lo ha reso liberamente disponibile in formato PDF sulla propria pagina web.
-
Camil Demetrescu, Irene Finocchi, Giuseppe F. Italiano, Algoritmi
e strutture dati 2/ed, McGraw-Hill, 2008, ISBN: 978 88 386
64687 [errata corrige]
Questo è un ottimo testo didattico sugli algoritmi e strutture dati, che tratta essenzialmente gli stessi argomenti del libro di Bertossi e Montresor.
-
Robert Sedgewick, Algoritmi in Java 3/Ed.,
Pearson. 2003. ISBN 9788871921693
Questo libro si distingue dagli altri perché descrive gli algoritmi usando Java anziché pseudocodice. Il libro contiene molte figure che facilitano la comprensione degli argomenti. Un limite di questo testo è che tratta gli aspetti legati ai costi asintotici in modo un po' superficiale.
-
Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, Clifford
Stein, Introduzione agli
Algoritmi e Strutture Dati 3/ed, McGraw-Hill, 2010, ISBN:
9788838665158
Questo è uno dei testi classici sugli algoritmi e le strutture dati. Offre una trattazione approfondita degli argomenti principali ma include molto più materiale rispetto a quanto verrà svolto a lezione. Di conseguenza lo consiglio a coloro che desiderano approfondire gli argomenti, o che cercano un testo autorevole da consultare anche in futuro.
-
Jon Bentley, Programming Pearls, 2nd edition,
Addison-Wesley, 2000, ISBN 0-201-65788-0.
Questo piccolo libro contiene numerosi esempi tratti da situazioni reali ed esercizi per imparare come sviluppare programmi efficienti. Lo consiglio a tutti coloro che desiderano vedere in che modo le tecniche algoritmiche viste a lezione possono essere usate per risolvere problemi reali.
Altro materiale
- Corso di Algoritmi e Strutture Dati, prof. Alberto Montresor, Università di Trento
- Free Online Algorithms and Data Structures Books
- Per chi desidera cimentarsi con esercizi più complicati suggerisco Cracking the Coding Interview
Modalità d'esame
Salta al calendario delle lezioni
L'esame finale consiste in un progetto individuale seguito da un esame orale.
Il progetto include di norma in 4-5 esercizi che richiedono di progettare e realizzare programmi Java efficienti per la risoluzione dei problemi assegnati.
Durante l'anno accademico verranno assegnati tre progetti: uno per la sessione estiva, uno per quella autunnale, e uno per quella invernale. I progetti andranno consegnati indicativamente circa 10 giorni prima del primo appello d'esame di quella sessione (verranno comunicate le date precise di volta in volta). Le specifiche dei progetti saranno rese disponibili circa un mese prima delle scadenze per la consegna.
I progetti sufficienti consentono di sostenere l'orale in uno degli appelli nella sessione d'esami per la quale sono stati consegnati. Ci saranno tre appelli orali nella sessione estiva (giugno/luglio 2021), uno in quella autunnale (settembre 2021) e due per quella invernale (gennaio/febbraio 2022). Nel caso di progetti insufficienti, sarà necessario attendere la sessione d'esami successiva e consegnare le soluzioni dei nuovi progetti che verranno proposti.
L'orale consiste nella discussione dei progetti e in una serie di domande su tutto il programma, in particolar modo gli argomenti di teoria visti a lezione. Potranno essere posti anche dei semplici esercizi sulla complessità o sulle strutture dati da svolgere sul momento. Il voto finale dipenderà in modo preponderante dal risultato della prova orale.
I docenti gestiranno con la massima intransigenza ogni irregolarità. L'esame è un momento ufficiale che va affrontato con la massima serietà. Il voto finale NON è negoziabile (può solo essere rifiutato).
Calendario delle lezioni
Nota: I lucidi non sostituiscono né il libro di testo né la frequenza alle lezioni. In particolare, studiare su un libro permette di chiarire dettagli che potrebbero essere solo accennati (o mancare del tutto) nei lucidi. I lucidi sono soggetti a modifiche frequenti.
I lucidi delle
lezioni sono distribuiti con licenza Creative Commons (l'esatta
versione della licenza applicata è indicata nella seconda
pagina di ciascuna serie di lucidi). L'autore dei lucidi è Moreno Marzolla; parte del
materiale è stato originariamente sviluppato e reso disponibile
dal prof. Alberto
Montresor.
- 23/02/2021
- Introduzione ai moduli 2/3
[ODP] [PDF] [Video parte 1] [Video parte 2] - 24/02/2021
- Esercitazione
[Virtuale] [Pagina prof. Giallorenzo] - 2/3/2021
- Visite di grafi
[ODP] [PDF] [Codice di esempio] [Video parte 1] [Video parte 2] - 3/3/2021
- Visite di grafi (cont.)
[Video parte 3] [Video parte 4] - 8/3/2021
- Implementazione Java BFS e ordinamento topologico
[Video]
Analisi ammortizzata
[ODP] [PDF] [Video] - 9/3/2021
- Esercitazione
[Virtuale] [Pagina prof. Giallorenzo] - 16/3/2021
- Analisi ammortizzata (cont.)
[Video] - 17/3/2021
- Divide-et-impera
[ODP] [PDF] [VecSumDI.java] [Video parte 1] [Video parte 2] - 23/3/2021
- Algoritmi Greedy
[ODP] [PDF] [Virtuale] [Video parte 1] [Video parte 2] - 24/3/2021
- Esercitazione
[Virtuale] [Pagina prof. Giallorenzo] - 30/3/2021
- Programmazione Dinamica
[ODP] [PDF] [Virtuale] [Codice di esempio] [Video parte 1] [Video parte 2] - 31/3/2021
- Programmazione Dinamica (cont.)
[Video parte 1] [Video parte 2] - 7/4/2021
- No lezione (vacanze di Pasqua)
- 8/4/2021
- Esercitazione
[Virtuale] [Pagina prof. Giallorenzo] - 13/4/2021
- Minimum Spanning Trees (Cap. 14.3 del libro di testo)
[ODP] [PDF] [Virtuale] [Codice di esempio]
[Video parte 1] [Sembra che il video della seconda parte della lezione non sia stato registrato correttamente (è un doppione della prima parte)] - 14/4/2021
- Minimum Spanning Trees (cont.)
[Virtuale] [Video parte 1] [Video parte 2] - 20/4/2021
- Cammini di costo minimo
[ODP] [PDF] [Virtuale] [Codice di esempio] [Video parte 1] [Video parte 2] - 21/4/2021
- Esercitazione
[Virtuale] [Pagina prof. Giallorenzo] - 27/4/2021
- Cammini di costo minimo (cont.)
[Virtuale] [Video parte 1] [Video parte 2] - 28/4/2021
- Asserzioni e invarianti
[ODP] [PDF] [Virtuale] [Video parte 1] [Video parte 2]
Per approfondire- Video-esercizio sulle invarianti (soluzione di un esercizio assegnato all'esame di fondamenti di informatica, ing. biomedica; questo argomento viene trattato in modo identico a quanto in questo corso)
- 4/5/2021
- Macchine di Turing e calcolabilità
[ODP] [PDF] [Virtuale] [Video parte 1] [Video parte 2]
Per approfondire- Simulatore di MdT che si può usare direttamente nel browser.
- Moreno Marzolla, Fondamenti di informatica (capitolo 7)
- 5/5/2021
- Esercitazione
[Virtuale] - 11/5/2021
- Conclusione
