Algoritmi ricorsivi e relazioni di ricorrenza. Tipi di complessità computazionale e loro calcolo. Approccio "Divide et impera"; Algoritmi "greedy"; Programmazione dinamica; Algoritmi su stringhe; Problemi NP-completi. Algoritmi di approssimazione.
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.
M. Sisper, Introduzione alla teoria della computazione, Maggioli Editore, 2016. Collana Apogeo education.
Obiettivi Formativi
Conoscenze:
Conoscere le metodologie piu’ importanti per la progettazione di algoritmi e i metodi 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
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 (automi a stati finiti, algoritmo di Knuth-Morris-Pratt, algoritmo di Boyer-Moor, algoritmo di 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, colorazione di un grafo, bin packing.