Algoritmi ricorsivi e relazioni di ricorrenza. Tipi di complessità computazionale e loro calcolo. Dimostrazioni di correttezza degli algoritmi. Approccio "Divide et impera"; Algoritmi "greedy"; Programmazione dinamica; Algoritmi su stringhe; Problemi NP-completi. Algoritmi di approssimazione.
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.
J.E. Hopcroft, R. Motwani, J.D. Ullman, Automi, linguaggi e calcolabilit a’, Addison-Wesly, 2003.
M. Sisper, Introduzione alla teoria della computazione, Maggioli Editore, 2016. Collana Apogeo education.
Obiettivi Formativi
Conoscenze:
Conoscere le principali metodologie per la progettazione di algoritmi, per la dimostrazione della loro correttezza e per la valutazione della loro complessita’.
Competenze acquisite:
Saper utilizzare le tecniche di progettazione nel modo piu’ efficace e saper valutare la complessita’ degli algoritmi e argomentare sulla loro correttezza.
Capacita’ acquisite al termine del corso:
Utilizzare consapevolmente le proprie conoscenze per individuare strategie risolutive di problemi reali.
Prerequisiti
Corsi raccomandati: Informatica
Metodi Didattici
Conoscenza e capacità di comprensione: lezioni frontali
Conoscenza e capacità di comprensione applicate: esercitazioni in classe e esercizi da svolgere in autonomia
Autonomia di giudizio:
discussione degli argomenti in programma
Capacità di apprendere: lezioni frontali
Altre Informazioni
Frequenza delle lezioni in aula: raccomandata.
Modalità di verifica apprendimento
L’esame finale ha lo scopo di accertare l’acquisizione delle conoscenze e delle abilità tramite lo svolgimento di una prova orale. La prova orale consiste in una conversazione con il docente volta a far emergere la capacità di problem solving e le conoscenze acquisite.
Programma del corso
Correttezza di un algoritmo. Analisi ammortizzata. Algoritmi ricorsivi e metodi risolutivi di relazioni di ricorrenza.
Tecnica divide et impera: caratteristiche, ambiti di applicabilità, pro e contro. Esempi: calcolo della potenza di un numero, calcolo del primo e secondo massimo, calcolo del prodotto di due polinomi e del prodotto di due matrici, HeapSort, problema della massimizzazione del profitto di un titolo azionario, calcolo della coppia di punti di distanza minima in un piano.
Tecnica greedy: caratteristiche, ambiti di applicabilità, pro e contro. Esempi: il problema del rappresentante, il problema del resto, pianificazione e sequenziamento delle attività, codici di Huffman, problema dello zaino 0-1 e dello zaino, algoritmi di routing.
Programmazione dinamica: caratteristiche, ambiti di applicabilità, pro e contro. Esempi: calcolo dell'n-esimo numero di Fibonacci, il problema del rappresentante, il problema del resto, il problema dello zaino 0-1, prodotto di una sequenza di matrici, triangolazioni minime, problema della massimizzazione del profitto di un titolo azionario, problema della minimizzazione del cammino da eseguire tra tutte le coppie di nodi in un grafo.
Stringhe: distanza di edit fra due stringhe, il problema della massima sottosequenza comune, il problema dello string matching (algoritmo di Rabin-Karp, automi a stati finiti, algoritmo di Knuth-Morris-Pratt). Formulazione dei problemi.
Problemi NP, NP-c, NP-co e NP-h: certificati polinomiali, non determinismo, riducibilita’ polinomiale, prove di NP-completezza.
Algoritmi di approssimazione: caratteristiche, applicabilita', e fattore di approssimazione. Esempi: kSAT, copertura di insiemi e vertici, colorazione di un grafo, cicli hamiltoniani, job scheduling, bin packing.