From BIMIB
0708 - Analisi di Algoritmi (LS)
Questa è la home page del modulo "Analisi di Algoritmi" del corso della laurea specialistica in informatica "Tecniche di analisi e di verifica" - anno accademico 2007/08.
Il docente di riferimento di questo modulo è Prof. Paola Bonizzoni.
Avvisi
- Esame completato. Il corso è ufficialmente terminato.
- Aggiunte le modalità di esame. La consegna è stata fissata per il 15 luglio 2008.
- Aggiunti link a materiale riguardante le tecniche di manipolazione di bit in parole di memoria nel materiale del corso.
- Cambiamento orario esercitazione. Come concordato durante la prima esercitazione è stata effettuata una modifica all'orario del corso. Dal 29 aprile, le esercitazioni si terranno il martedì dalle 9.30 alle 11.30 in aula U14-03 (T014).
- Pubblicato un commento riguardante la discussione della prima esercitazione tra il materiale del corso.
Orario
Periodo: dal 07 apr 08 al 06 giu 08.
Lezione: Lunedì, ore 10.30-13.30, aula U6-37, Prof. Paola Bonizzoni.
Esercitazione: Dott. Yuri Pirola
fino al 22 aprile compreso: Martedì, ore 8.30-10.30, aula U6-23,
dal 29 aprile compreso: Martedì, ore 9.30-11.30, aula U14-03 (T014).
Nota: Controllare sempre l'orario ufficiale.
Programma
Il programma di riferimento del modulo comprende le seguenti voci:
- Tecniche di analisi degli algoritmi. Algoritmi su grafi.
- Algoritmi di approssimazione per problemi NP-difficili e accenni agli algoritmi probabilistici e randomizzati.
- Applicazioni di algoritmi. I contenuti varieranno di anno in anno e riguarderanno:
- algoritmi per la clusterizzazione di dati, la compressione dei dati, strutture dati di indicizzazione: trie, suffix tree e suffix array,
- algoritmi per motori di ricerca.
Lezioni svolte
- Introduzione agli algoritmi di ricerca di testo nel Web:
- string matching mediante automi a stati finiti (14-15 aprile);
- algoritmo Knuth-Morris-Pratt (21 aprile);
- algoritmo Boyer-Moore (29 aprile);
- matching di espressioni regolari (5 maggio);
- costruzione dell'automa non deterministico per il riconoscimento di espressioni regolari (12 maggio);
- utilizzo nella ricerca di pattern definiti mediante espressioni regolari (12 maggio);
- introduzione ai suffix-tree e ai suffix-tree generalizzati (6-13 maggio):
- costruzione di suffix tree e suffix tree generalizzati;
- matching di pattern su una o più stringhe;
- estrazione della più lunga sottostringa comune a più stringhe in tempo lineare;
- string matching tramite metodi aritmetici:
- manipolazione di singoli bit all'interno di parole di memoria (13 maggio);
- metodo dello "shift-and" (20 maggio);
- metodi di bit counting (26 maggio);
- uso delle espressioni regolari nel linguaggio Perl (19-26 maggio, Dott. Raffaella Rizzi).
- Analisi ammortizzata:
- analisi aggregata della complessità computazionale di tabelle dinamiche (22 aprile);
- analisi della complessità computazionale di tabelle dinamiche con il metodo del banchiere e con il metodo del potenziale (28 aprile);
- analisi della complessità computazionale della procedura KMP-compute-prefix-function con il metodo del potenziale (28 aprile).
Modalità di esame
L'esame consiste in una prova scritta individuale riguardante i contenuti del corso. Il testo di tale prova è stato inviato agli indirizzi mail raccolti durante il corso. Il termine improrogabile di consegna è fissato per il 15 luglio 2008. Se uno studente interessato non avesse ancora ricevuto il testo è pregato di comunicarlo quanto prima a Yuri Pirola.
Materiale del corso
- Commento sulla condizione necessaria per Graph Isomorphism link;
- Bitwise tricks and techniques:
- bit counting link;
- una parte del volume 4 di "The Art of Computer Programming" di Knuth, pre fascicolo 1a;
- Introduzione al linguaggio Perl:
- Dispense su algoritmi di ricerca di testi link.
Riferimenti
