Algoritmi e Strutture Dati
Laurea in Informatica per il Management, Università di Bologna, AA 2020/2021
Salta alle modalità d'esame
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
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
Torna in cima alla pagina.
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).
Torna in cima alla pagina.
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]
- 5/5/2021
- Esercitazione
[Virtuale]
- 11/5/2021
- Conclusione
Torna in cima alla pagina.