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
   
Enrolled
Algoritmica su Stringhe

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 1 e 2.

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 1, 2.

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 25/03/2011