Algoritmi ricorsivi e relazioni di ricorrenza; Approccio "Divide et impera"; Algoritmi "greedy"; Programmazione dinamica; Algoritmi su stringhe; Problemi NP-completi. Algoritmi di approssimazione; Problemi indecidibili. Elementi di geometria computazionale.
S. Baase, Computer Algorithms Introduction to Design and Analysis, 2nd Edition, Addison Wesley, 1988.
A. Bertossi, Algoritmi e strutture di dati, Utet Libreria, 2000.
A. Bertossi, A. Montresor, Algoritmi e strutture di dati, Città Studi Edizioni, 2010.
T. H. Cormen, C.E. Leiserson, R. L. Rivest, Introduzione agli algoritmi, Jackson Libri, 2003.
P. Crescenzi, G. Gambosi, R. Grossi, Strutture di dati e algoritmi – Progettazione, analisi e visualizzazione, Pearson Addison Wesley, 2006.
C. Demetrescu, I. Finocchi, G. F. Italiano, Algoritmi e strutture dati, Seconda edizione, McGraw-Hill, 2008.
J.E. Hopcroft, R. Motwani, J.D. Ullman, Automi, linguaggi e calcolabilità, Addison-Wesly, 2003
Obiettivi Formativi
Conoscenze:
Conoscere le metodologie più importanti per la progettazione di algoritmi e i metodi base per la valutazione della loro complessità.
Competenze acquisite:
Saper utilizzare le tecniche di progettazione nel modo più efficace e saper valutare la complessità degli algoritmi.
Capacità acquisite al termine del corso:
Utilizzare consapevolmente le proprie conoscenze per individuare strategie risolutive di problemi reali.
Prerequisiti
Corsi raccomandati: Informatica
Metodi Didattici
Numero di ore totali del corso: 150
Numero di ore per studio personale e altre attività formative di tipo individuale: 102
Numero di ore relative alle attività in aula: 72
Numero di ore relative ad attività di laboratorio (lezioni in laboratorio): 0
Numero di ore relative ad attività di esercitazioni (in laboratorio e in campo): 0
Numero di ore relative ad attività seminariali: 0
Numero di ore relative ad attività di stage: 0
Numero di ore per prove in itinere: 0
Altre Informazioni
Frequenza delle lezioni ed esercitazioni:
Non obbligatoria
Strumenti a supporto della didattica:
Algoritmi ricorsivi e relazioni di ricorrenza.
Approccio “Divide et impera”: schema generale; prodotto di interi; prodotto di matrici e algoritmo di Strassen; trasformata discreta di Fourier e prodotto di polinomi; ricerca della coppia di punti più vicini.
Algoritmi “greedy”: pianificazione delle attività; codici di Huffman; ricoprimento di punti con intervalli; problemi di sequenziamento.
Programmazione dinamica: schema generale; prodotto di una sequenza di matrici; triangolazioni minime; problema del resto; partizione di un insieme di interi; problema dello zaino 0-1; cammini minimi; algoritmo di Dijkstra.
Stringhe: la distanza fra due stringhe; il problema della massima sottosequenza comune; il problema dello string matching; automi a stati finiti e stringhe; algoritmo di Knuth, Morris e Pratt. Algoritmo Rabin-Karp.
Problemi NP-completi: certificati polinomiali; non determinismo; riducibilità polinomiale; prove di NP-completezza.
Algoritmi di approssimazione: scheduling di lavori; set covering; copertura di vertici; il problema del commesso viaggiatore; il problema della colorazione di un grafo; il problema della somma di sottoinsieme; bin packing.
Problemi indecidibili.
Elementi di geometria computazionale: prodotti incrociati e loro proprietà; intersezione di due segmenti; inviluppo convesso; triangolazioni.