69443 - ALGORITHMS AND DATA STRUCTURES FOR COMPUTATIONAL BIOLOGY

Conoscenze e abilità da conseguire

At the end of the course, the student has the basic Knoledge in design and analysis of correct and efficient algorithms and data structures. In particular, the student has basic knowledge on algorithms and data structures. The student will be able to: design correct and efficient algorithm for common computational tasks; analyze existing algorithms and data structures; design and analyze new algorithms and data structures.

Contenuti

Progettazione di algoritmi: progettazione incrementale, divide-and-conquer, greedy, programmazione dinamica

Analisi di algoritmi: analisi del tempo di esecuzione, comportamento asintotico di algoritmi, funzioni nell'analisi asintotica, risoluzione di equazioni di ricorrenza per l'analisi del tempo di esecuzione di algoritmi ricorsivi

Algoritmi di ordinamento: insertion sort, merge sort, heap sort, quick sort, limiti inferiori di algoritmi basati su confronti, ordinamento in tempo lineare, counting sort, radix sort, shellsort

Strutture dati: array, alberi di decisione, alberi binari, heap, code con priorita', insiemi binari, dizionari, pile, code, liste, alberi radicati come liste, tabelle hash, alberi binari bilanciati, grafi, merge-find sets, suffix tries, trees e arrays, Burrows-Wheeler transform

Algoritmi su alberi e grafi: visite, ordinamento topologico, cammini minimi, algoritmo di Kruskal per il problema dell'albero minimo di copertura

Algoritmi su stringhe: algoritmo di Huffman, string matching approssimato, massima sottosequenza comune, edit distance, allineamento di sequenze globale, locale e semiglobale

Algoritmi per problemi NP-completi: backtracking, algoritmi di enumerazione, algoritmi approssimati, branch-&-bound, euristiche (basate su greedy / ricerca locale), esempi per il problema del commesso viaggiatore

Testi/Bibliografia

E' fondamentale l'uso delle slide e del materiale usato a lezione, inclusi gli esercizi svolti a lezione. Le slide sono rese disponibili sulla pagina web del corso.

I testi seguenti sono letture suggerite, ma non da acquistare obbligatoriamente.

Libri specifici su argomenti di biologia computazionale:

- Carlos Setubal, Joao Meidanis, Introduction to computational molecular biology, Cengage Learning eds., 1997;
- C. Gibas, P. Jambeck, Developing Bioinformatics Computer Skills, O'Reilly media, 2001

Libri più generali su algoritmi e strutture dati:

- Alfred V. Aho, Jeffrey D. Ullman, John E. Hopcroft. Data Structures and Algorithms. Addison Wesley, 1983.
- Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, Clifford Stein. Introduction to Algorithms. McGraw-Hill, 2001.
- Donald E. Knuth. The Art of Computer Programming, Volumes 1-3. Addison-Wesley Professional, 1998.
- S.B. Kishor Data Structures, Edition 3. Das Ganu Prakashan, Nagpur, 2008.

Metodi didattici

I metodi didattici includono lezioni frontali (supportate da slide e lavagna) e la discussione di esercizi, da risolversi su carta, sui portatili degli studenti o alla lavagna.

Modalità di verifica e valutazione dell'apprendimento

L'esame finale (che copre tutti e 3 i moduli) è composto da una parte scritta (3 ore) e una parte orale facoltativa (30 minuti). Durante la parte scritta NON è consentito l'uso di libri, note, calcolatrici o sistemi di comunicazione, incluso l'accesso a internet. Se il candidato supera l'esame scritto (con un voto superiore o uguale a 18/30) può essere schedulato per la parte orale, nel caso la valutazione dello scritto sia bassa. In questo caso, per superare l'esame, è necessario ottenere una valutazione sufficiente in entrambe le parti.

Strumenti a supporto della didattica

Slide e proiettore.
Personal computer.
Lavagna.

Orario di ricevimento

Consulta il sito web di Pietro Di Lena

Consulta il sito web di Zeynep Kiziltan

Consulta il sito web di Zeynep Kiziltan