Complementi di algoritmi e strutture dati

Struttura insegnamento e programma

Linea Milano
Edizione attiva
Responsabile
STUDENTI FREQUENTANTI
Programma
Algoritmi di string matching
Generalità sulle stringhe. Problema della massima sottosequenza comune e relativo algoritmo di programmazione dinamica. Problema di string-matching, algoritmo naive, automa dei prefissi. Algoritmi di Knuth-Morris-Pratt, di Rabin-Karp e di Boyer-Moore. La struttura dati di Suffix-tree: algoritmo naive di costruzione. L'uso del suffix-tree nei problemi di string-matching. L'algoritmo di Ukkonen per il calcolo del suffix-tree di una stringa in tempo lineare.

Complessità computazionale
Macchine di Turing deterministiche e non deterministiche. Proprietà di simulazione tra i due modelli. Le classi P e NP. Il problema della soddisfacibilità per formule booleane. La nozione di riduzione polinomiale. Esempi notevoli di riduzione polinomiale (SODD
Algoritmi probabilistici
Macchina di Turing probabilistica. La nozione generale di algoritmo probabilistico, la relativa funzione calcolata e procedure di riduzione della probabilità di errore. La disuguaglianza di Chernoff, il confronto con quella di Chebychev e le sue applicazioni. Esempio: protocollo di comunicazione probabilistico per l'uguaglianza di stringhe.
Il problema della primalità. Proprietà algebriche delle classi di resto, piccolo teorema di Fermat, gruppo dei resti coprimi. Numeri di Carmichael. Algoritmo di Miller-Rabin e relativa analisi dell'errore. La classe RP. Generazione casuale di numeri primi.
Classificazione degli algoritmi probabilistici: Las Vegas, 1-sided error, bounded error, unbounded error; la corrispondente riduzione della probabilità di errore. Classi di complessità probabilistiche: ZPP, RP, co-RP, BPP, PP.
Informazioni sul programma
Questo insegnamento rappresenta la naturale continuazione del corso di Algoritmi e Strutture Dati (fondamentale del 2° anno della laurea triennale di informatica). Esso mira a presentare alcuni algoritmi classici di particolare attualità non trattati nel corso precedente e nello stesso tempo a sviluppare temi di studio avanzati principalmente dedicati alla complessità computazionale e agli algoritmi probabilistici.
Il programma prevede tre parti: la prima è dedicata agli algoritmi di String Matching, il cui interesse è legato all'uso che se ne fa in biologia computazionale e allo studio di strutture dati efficienti e avanzate come i Suffix-tree. La seconda prevede lo studio dei modelli di calcolo non deterministico e delle principali classi di complessità in tempo e spazio: P, NP, L, NL, Pspace e le relative famiglie di problemi completi. La terza parte è dedicata alle procedure probabilistiche e comprende l'algoritmo di Rabin e le problematiche relative ai test di primalità.
Propedeuticità
Algoritmi e strutture dati, Automi e linguaggi formali, Matematica del discreto.
Prerequisiti e modalità di esame
Prerequisiti sono la conoscenza degli algoritmi e delle struture dati di base, la notazione asintotica, le nozioni di matematica presentate nei corsi del primo anno, le principali proprietà degli automi e dei linguaggi regolari.
Modalità d'esame: prova orale.
Metodi didattici
Insegnamento tradizionale
Materiale didattico e bibliografia
T.H. Cormen, C.E. Leiserson, R.L. Rivest, C. Stein, Introduzione agli algoritmi e strutture dati, 3/ed, McGraw-Hill Italia, 2010 (oppure edizione in inglese, 2009).
D. Gusfield, Algorithms on strings, trees and sequences (Computer Science and Computational Biology), Cambridge University Press, 1997 (Capitoli 5, 6.1, 7).
A. Bertoni, M. Goldwurm, Progetto e analisi di algoritmi (Dispense del corso di Algoritmi e Strutture Dati), Rapporto interno n. 230-98, Dip. Scienze dell'Informazione, Università degli studi di Milano, Ottobre 2008. Scaricabili da homes.di.unimi.it/~goldwurm/algo/
C. H. Papadimitriou, Computational Complexity, Addison-Wesley Publishing Company, 1994 (Sezione 7.3).
J. Hopcroft, J. Ullman, Introduction to automata theory, languages and computation, Addison-Wesley Publishing company, 1979.
J. Hromkovic, Design and Analysis of Randomized Algorithms, Springer, 2005 (Capitoli 1,2,6).
R. Motwani, P. Raghavan, Randomized Algorithms, Cambridge University Press, 1995 (Capitolo 14).
STUDENTI NON FREQUENTANTI
Programma
Identico a quello per i frequentanti
Prerequisiti e modalità di esame
Identiche a quelle per i frequentanti
Materiale didattico e bibliografia
Identico a quello per i frequentanti
Periodo
Secondo semestre
Periodo
Secondo semestre
Modalità di valutazione
Esame
Giudizio di valutazione
voto verbalizzato in trentesimi
Docente/i
Ricevimento:
Mercoledì 9:30-12:30
via Celoria 18, stanza 7007
Ricevimento:
martedì dalle 14:30 alle 17:30, oppure su appuntamento (accordi per e-mail).
dip. Matematica, via Saldini 50 (ufficio al secondo piano).