Docente: Gianluca Della Vedova
Crediti: 4
Obiettivi formativi:il corso introduce i principali algoritmi di ricerca nei testi che trovano applicazione nella realizzazione di strumenti software oggi utilizzati in Internet e in ambiente Web per l’elaborazione di diverse tipologie di dati. In particolare, lo studente acquisisce l’abilità di progettare semplici algoritmi di ricerca di pattern che hanno applicazione in Bioinformatica o nella realizzazione di algoritmi per motori di ricerca.
Programma:
1. Algoritmi di pattern matching esatto:Knuth-Morris-Pratt, Boyer-Moore, Karp-Rabin. Bit-parallel.
2. Strutture dati: Suffix tree, Affix tree, Suffix array, Affix array
3. Pattern matching approssimato: Agrep.
4. Compressione Liv-Zempel, pattern matching su sequenze compresse,
5. Indicizzazione di testi