ANALISI E PROGETTAZIONE DI ALGORITMI

ANALISI E PROGETTAZIONE DI ALGORITMI

_
iten
Codice
80306
ANNO ACCADEMICO
2019/2020
CFU
9 cfu al 3° anno di 8759 INFORMATICA (L-31) GENOVA
SETTORE SCIENTIFICO DISCIPLINARE
INF/01
SEDE
GENOVA (INFORMATICA )
periodo
2° Semestre
materiale didattico

PRESENTAZIONE

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. 

 

OBIETTIVI E CONTENUTI

OBIETTIVI FORMATIVI

Apprendimento e analisi dal punto di vista di correttezza ed efficienza di strutture dati e algoritmi classici, assumendo da ASD nozioni base di algoritmi, complessità e strutture dati elementari. Gli argomenti includono tecniche avanzate di analisi e progettazione, algoritmi di ordinamento, strutture dati avanzate, algoritmi su grafi, teoria della NP-completezza.

Modalità didattiche

Tradizionale.

PROGRAMMA/CONTENUTO

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.

TESTI/BIBLIOGRAFIA

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.

DOCENTI E COMMISSIONI

Ricevimento: Su appuntamento.

Ricevimento: Su appuntamento.

Ricevimento: Su appuntamento via email

Commissione d'esame

ELENA ZUCCA (Presidente)

ALESSANDRO VERRI

PAOLA MAGILLO

GIORGIO DELZANNO

DAVIDE ANCONA

LEZIONI

Modalità didattiche

Tradizionale.

ORARI

L'orario di tutti gli insegnamenti è consultabile su EasyAcademy.

Vedi anche:

ANALISI E PROGETTAZIONE DI ALGORITMI

ESAMI

Modalità d'esame

Prova scritta e orale.

Modalità di accertamento

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.

Calendario appelli

Data Ora Luogo Tipologia Note
29/01/2020 09:00 GENOVA Scritto
19/06/2020 09:00 GENOVA Scritto
10/07/2020 09:00 GENOVA Scritto
27/07/2020 09:00 GENOVA Scritto
08/09/2020 09:00 GENOVA Scritto