Page begin -
Logo DISCO
|
Go to the Highly accessible area
|
Go to the Content page
|
Go to the End of content
|
Go to the Main menu
|
Go to the Navigation Bar (location)
|
Go to the Navigation menu (tree)
|
Go to the Commands list
|
Go to the Further readings
|
Go to the Bottom Menu
|
Logo Ateneo
   
Education
Algoritmica su Stringhe

Codice ins.

Insegnamento

CFU ins.

Tipo ins.

Anno

Sem.

SSD ins.

Responsabile insegnamento

E3101Q033

Algoritmica su stringhe

4

OBS

3

1

INF/01

DELLA VEDOVA Gianluca

 

Text algorithms

 

 

 

 

 

 

Contenuti:
Algoritmi di pattern matching esatto:Knuth-Morris-Pratt, Boyer-Moore, Karp-Rabin. Bit-parallel. Pattern matching approssimato. Alberi di suffisso. Array di suffisso. Compressione di testi. Espressioni regolari. Distanza fra sequenze. Allineamento di sequenze.

Obiettivi formativi:

Si prevede che lo studente acquisisca l’abilità di comprendere, progettare e implementare algoritmi di gestione testi, ricerca di pattern in testi e compressione dati.

Prerequisiti:

Alberi di ricerca, hash, visita di alberi, programmazione dinamica.

Metodi didattici:
Lezioni ed esercitazioni.

Altre informazioni:

Nessuna

Programma esteso:

  • Pattern matching. Algoritmo di Knuth-Morris-Pratt.
  • Algoritmo di Boyer-Moore.
  • Algoritmi basati su NFA. Algoritmi seminumerici. Pattern matching approssimato: agrep. Programmazione dinamica.
  • Algoritmo di Karp-Rabin. Algoritmi basati su FFT.
  • Alberi di suffisso: Definizioni. Array di suffisso: Definizioni. Relazioni fra alberi di suffisso e array.
  • Implementare albero di suffisso. Alberi di suffisso generalizzati. Applicazioni degli alberi di suffisso: sottostringa più lunga.
  • Array di suffisso: algoritmo per la costruzione.
  • Array di suffisso: algoritmi per il pattern matching. Pattern matching su testi circolari. Compressione tipo Lempel-Ziv con alberi di suffisso.
  • Algoritmo per calcolare lca di due foglie in tempo costante. Grafo delle parole (DAWG). Calcolo della massima estensione.
  • Tandem repeats, sottostringa comune più lunga. Tandem repeats in stringhe circolari. Applicazioni degli alberi di suffisso: ricerca di stringhe contenute in altre stringhe. Altre applicazioni degli alberi di suffisso: ricerca dei palindromi, matching con wildcard.
  • Algoritmi per pattern matching approssimato: Baeza-Yates Perleberg, Chang Lawler, Myers
  • Distanza di edit pesata: algoritmi basati su alberi di suffisso.
  • Tecnica di Hirschberg. Distanza di edit con banda.
  • Tecnica dei quattro russi.
  • Allineamento locale e globale di 2 sequenze. Gap (definizioni)
  • Algoritmi per gap generici, affini e convessi. Allineamento di k sequenze: Programmazione dinamica, algoritmo di Carrillo-Lipman.
  • Espressioni regolari.
  • Cenni di compressione LZ, Burrows-Wheeler (Bzip)

Testi di riferimento:
"Algorithms on Strings, Trees and Sequences”, di Daniel Gusfield, Cambridge Univ. Press

Modalità di verifica dell'apprendimento:
Tipo esame:

Scritto e orale separati

Tipo valutazione:
Voto finale

Contents:

Exact pattern matching:Knuth-Morris-Pratt, Boyer-Moore, Karp-Rabin. Bit-parallel. Approximate Pattern matching. Suffix trees. Suffix arrays. Text compression. Regular expressions. Sequence alignment.

Goals:

The students are expected to learn how to understand, design and implement pattern matching and text compression algorithms.

Requisites:
Search trees, hashes, tree traversal, dynamic programming.

Teaching methods:
Lectures

Other informations:

None

Detailed program:

  • Pattern matching. Knuth-Morris-Pratt.
  • Boyer-Moore.
  • NFA-based algorithms. Seminumerical Algorithms. Approximated pattern matching: agrep. Dynamic Programming.
  • Karp-Rabin. FFT-based Algorithm.
  • Suffix Trees, Suffix Arrays: Definitions. Relation between suffix trees and suffix arrays.
  • Implementing suffix trees. Generalized suffix trees. Applications of suffix trees: computing the longest substring.
  • Constructing Suffix arrays
  • Pattern Matching with Suffix Arrays. Pattern matching on circular text. Lempel-Ziv-like compression with suffix trees.
  • Constant-time algorithm to compute the lca of two leaves in a tree. Word Graph (DAWG). Computing the longest extension.
  • Applications: Tandem repeats, optimal algorithm to compute the longest common substring. Tandem repeats in circular strings. Finding which strings are substrings of other strings. Finding palindromes. Pattern matching with wildcards.
  • Approximate pattern matching: Baeza-Yates Perleberg, Chang Lawler, Myers
  • Weighted edit distance: algorithms with suffix-trees.
  • The Hirschberg technique. Edit distance within a band.
  • Four Russians technique.
  • Global and local alignment of 2 strings. Definition of gap.
  • Algorithms for general, affine and convex gaps. Multiple sequence alignment: dynamic programming, Carrillo-Lipman.
  • Regular expressions.
  • Sketches of compression. LZ, Burrows-Wheeler (Bzip).

Textbooks:

 “Algorithms on Strings, Trees and Sequences”, di Daniel Gusfield, Cambridge Univ. Press

Learning assessment method:                                                                                                                      
Examination:

Separate written and oral

Evaluation type:
Final degree

Further readings
(C) Copyright 2016 - Dipartimento Informatica Sistemistica e Comunicazione - Viale Sarca, 336
20126 Milano - Edificio U14
redazioneweb@disco.unimib.it - last update of this page 25/06/2015