Corso di: Algoritmi II (CFU 6)
Laurea Specialistica in Metodologie e Sistemi Informatici
Anno accademico: 2004-2005
INDICE
Obiettivi del corso
Il corso ha lo scopo di fornire nozioni avanzate per
il progetto, l'analisi ed il confronto di algoritmi. e di
introdurre le classi di complessità, con particolare riferimento
alle classi P e NP.
Prerequisiti
Si presuppone che lo studente conosca i concetti base dell'informatica
e abbia un po' di esperienza di programmazione. In particolare si
presuppone la conoscenza di alcune tecniche di programmazione, come la
tecnica "Divide et Impera" e la tecnica "Greedy", e la
familiarità con la nozione di complessità concreta per
algoritmi iterativi e ricorsivi.
Modalità d'esame
L'esame consiste in una prova orale. La partecipazione attiva a
esercitazioni e a seminari organizzati durante il corso, verrà
valutata come parte d'esame.
Libri di testo
"Algoritmi e strutture di dati".
UTET. Libreria, 2000.
- T. H.Cormen, C.E. Leiserson, R.L. Rivest
"Introduzione agli algoritmi"
Jackson libri, 1999
Per consultazione:
"Computational Complexity"
Addison-Wesley, Longman, 1995
"Algoritmi in C"
Addison-Wesley, Masson, 1993
Materiale didattico di supporto
Programma del corso
- Progetto e analisi di Algoritmi - Programmazione dinamica.
- Uso "top-down" e "bottom-up" di definizioni ricorsive di
funzioni
- Zaino
- Cammini minimi nei grafi
- Prodotto di matrici
- Progetto e analisi di Algoritmi - Backtracking
- Il problema delle n regine
- String-matching.
- Classi di complessità
- Certificati polinomiali
- Determinismo e non determinismo
- Le classi P e NP
- Riducibilità polinomiale
- NP-completezza
- Gerarchia di complessità
- Algoritmi di approssimazione
- Approssimazione assoluta ed errore relativo
- Schemi di approssimazione pienamente polinomiali
|