Corso di: Algoritmi & Laboratorio (CFU 6+6)
Laurea in Informatica (ind. S.R.)
Anno accademico: 2002-2003
Docenti: Maddalena ZACCHI, Ugo DE'LIGUORO
INDICE
Obiettivi del corso
Il corso ha lo scopo di fornire gli strumenti metodologici di base per
il progetto, l'analisi ed il confronto di algoritmi e di introdurre
alcuni
algoritmi e strutture dati fondamentali.
Prerequisiti
Contenuti dei corsi di "Programmazione I & Laboratorio" e
"Programmazione
II & Laboratorio".
Modalità d'esame
L'esame si compone di due parti: una discussione del progetto di
laboratorio
e una verifica scritta sugli argomenti delle lezioni.
Per superare l'esame lo studente deve riportare una votazione
sufficiente
in entrambe le prove.
La votazione finale viene calcolata come media dei voti riportati nelle
due prove separatamente.
Libri di testo
-
T.H. Cormen, C.E. Leiserson, R.L. Rivest.
"Introduzione agli Algoritmi" (volumi 1, 2, e 3).
Jackson Libri.
Programma del corso
-
Strutture dati avanzate
-
Heap, code con priorità.
-
Alberi, grafi.
-
Insiemi disgiunti.
-
Introduzione alle tecniche di progetto e nozioni di
complessità
degli algoritmi.
-
Analisi nel caso peggiore e nel caso medio.
-
Ordine di grandezza delle funzioni.
-
Notazione asintotica.
-
Metodi per risolvere le equazioni di ricorrenza: metodo iterativo e
metodo
principale.
-
Correttezza degli algoritmi.
-
Specifica e formula di correttezza.
-
I costrutti di sequenza, selezione e iterazione.
-
Correttezza degli algoritmi ricorsivi.
-
Algoritmi di ordinamento e selezione.
-
Algoritmi "Divide et Impera": mergesort, quicksort, heapsort.
-
Counting sort.
-
Selezione con tempo medio lineare.
-
Algoritmi "Greedy".
-
Selezione di attività.
-
Codice di Huffman.
-
Minimo albero di copertura di un grafo pesato.
-
Camminini minimi su grafi pesati.
-
Algoritmi di visita sui grafi.
-
Visita in ampiezza e in profondità.
-
Applicazione degli algoritmi di visita: componenti fortemente connesse,
ordinamento topologico.
|