CODICE | 80306 |
---|---|
ANNO ACCADEMICO | 2020/2021 |
CFU |
|
SETTORE SCIENTIFICO DISCIPLINARE | INF/01 |
LINGUA | Italiano |
SEDE |
|
PERIODO | 2° Semestre |
MATERIALE DIDATTICO | AULAWEB |
L'obiettivo del corso è l'apprendimento e l'analisi dal punto di vista di
correttezza ed efficienza di strutture dati e algoritmi classici nella formazione
di un informatico, assumendo dal corso di Algoritmi e Strutture Dati le
nozioni base relative a complessità e strutture dati elementari.
Apprendere algoritmi e schemi algoritmici classici, saper analizzare correttezza ed efficienza di un algoritmo
Tradizionale.
Metodologie di analisi e progettazione di algoritmi: notazioni asintotiche e correttezza e complessità di algoritmi ricorsivi (approfondimenti da ASD), correttezza di algoritmi iterativi, analisi ammortizzata, divide-et-impera, programmazione dinamica e algoritmi greedy.
Algoritmi di ordinamento: algoritmi elementari e mergesort (richiami da ASD), quicksort, heapsort, delimitazione inferiore problema dell'ordinamento per confronti, algoritmi di ordinamento non per confronti.
Strutture dati avanzate: heap, strutture union-find.
Grafi: definizioni, rappresentazioni, visite, ordinamento topologico, componenti fortemente connesse, cammini minimi (algoritmo di Djikstra), minimo albero ricoprente (algoritmi di Prim e Kruskal).
Teoria della NP-completezza: classi di complessità, problemi NP-completi, algoritmi di approssimazione.
Note a cura del docente.
Per approfondimenti:
Algoritmi e strutture dati. Demetrescu, Finocchi, Italiano. McGraw Hill. Seconda edizione, 2008.
Introduzione agli algoritmi e strutture dati. Cormen, Leiserson, Rivest, Stein. McGraw Hill. Terza edizione, 2009.
Ricevimento: Su appuntamento.
Ricevimento: Su appuntamento via email
ELENA ZUCCA (Presidente)
PAOLA MAGILLO
ALESSANDRO VERRI (Presidente Supplente)
L'orario di tutti gli insegnamenti è consultabile su EasyAcademy.
Prova scritta e orale.
La prova scritta verifica la capacità dello studente di mettere in pratica le nozioni viste a lezione. La prova orale verifica la comprensione dei concetti e la capacità di illustrarli in modo appropriato.
Data | Ora | Luogo | Tipologia | Note |
---|---|---|---|---|
27/01/2021 | 09:00 | GENOVA | Scritto | aula 506 |
18/06/2021 | 09:00 | GENOVA | Scritto | aula 506 |
09/07/2021 | 09:00 | GENOVA | Scritto | aula 506 |
26/07/2021 | 09:00 | GENOVA | Scritto | aula 506 |
07/09/2021 | 09:00 | GENOVA | Scritto | aula 506 |
19/01/2022 | 09:00 | GENOVA | Scritto | aula 506 |