Inizio della pagina -
Logo DISCO
|
Visita la Versione ad elevata leggibilità
|
Vai al Contenuto della pagina
|
Vai alla Fine dei contenuti
|
Vai al Menu Principale
|
Vai alla Barra di navigazione (sei in)
|
Vai al Menu di navigazione (albero)
|
Vai alla Lista dei comandi
|
Vai alla Lista degli approfondimenti
|
Vai al Menu inferiore
|
Logo Ateneo
   
Didattica
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

Approfondimenti

Google Translate
Translate to English Translate to French Translate to German Translate to Spanish Translate to Chinese Translate to Portuguese Translate to Arabic
Translate to Albanian Translate to Bulgarian Translate to Croatian Translate to Czech Translate to Danish Translate to Dutch Translate to Finnish Translate to Greek Translate to Hindi
Translate to Hungarian Translate to Irish Translate to Japanese Translate to Korean Translate to Norwegian Translate to Polish Translate to Romanian Translate to Russian Translate to Serbian
Translate to Slovenian Translate to Swedish Translate to Thai Translate to Turkish

(C) Copyright 2016 - Dipartimento Informatica Sistemistica e Comunicazione - Viale Sarca, 336
20126 Milano - Edificio U14
redazioneweb@disco.unimib.it - ultimo aggiornamento di questa pagina 25/06/2015