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 a’ 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 a’, Addison-Wesly, 2003
Obiettivi Formativi
Conoscenze:
Conoscere le metodologie piu’ importanti per la progettazione di algoritmi e i metodi base per la valutazione della loro complessit a’.
Competenze acquisite:
Saper utilizzare le tecniche di progettazione nel modo piu’ efficace e saper valutare la complessit a’ degli algoritmi.
Capacit a’ 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 a’ formative di tipo individuale: 102
Numero di ore relative alle attivit a’ in aula: 72
Numero di ore relative ad attivit a’ di laboratorio (lezioni in laboratorio): 0
Numero di ore relative ad attivit a’ di esercitazioni (in laboratorio e in campo): 0
Numero di ore relative ad attivit a’ seminariali: 0
Numero di ore relative ad attivit a’ di stage: 0
Numero di ore per prove in itinere: 0
Altre Informazioni
Frequenza delle lezioni ed esercitazioni:
Non obbligatoria
Orario di ricevimento:
Martedi’ 9:30-10:30
Giovedi’ 11:00-13:00
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 piu’ vicini.
Algoritmi "greedy": pianificazione delle attivit a’; 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 a’ 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 a’; intersezione di due segmenti; inviluppo convesso; triangolazioni.