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 insegnamento E3101Q033

Docente responsabile: 
Gianluca Della Vedova

PROGRAMMA

Obiettivi e contenuti:
Il corso introduce i principali algoritmi di ricerca e analisi di testi che trovano applicazione nella realizzazione di strumenti software oggi utilizzati in vari contesti applicativi, fra cui la Bioinformatica.

Programma:
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.

Risultati di apprendimento previsti:
Si prevede che lo studente acquisisca l'abilità di progettare e implementare algoritmi di ricerca di pattern in testi e compressione dati.

Prerequisiti:
Algoritmi e strutture dati.

Aims and contents:
In this course, we present the main algorithms to analyse and search for patterns in a text. Such algorithms are widely used for building software tools that are employed in several contexts, such as Bioinformatics.

Program details:
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.

Learning outcomes:
The students are expected to learn how to design and implement pattern matching and text compression algorithms.

Prerequisites:
Algorithms and Data structures.

Tipo esame:
Scritto e orale

Tipo valutazione:
Voto finale

 

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 11/11/2013