- Docente: Pietro Di Lena
- Crediti formativi: 10
- SSD: INF/01
- Lingua di insegnamento: Inglese
- Modalità didattica: Convenzionale - Lezioni in presenza
- Campus: Bologna
- Corso: Laurea Magistrale in Bioinformatics (cod. 8020)
-
dal 08/03/2023 al 12/06/2023
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
Sviluppo di algoritmi: algoritmi incrementali, algoritmi divide-et-impera, algoritmi greedy e algoritmi basati sulla programmazione dinamica
Analisi di algoritmi: analisi asintotica e comportamento asintotico degli algoritmi, risoluzione di equazioni di ricorrenza per l’analisi di algoritmi ricorsivi analysis
Algoritmi di ordinamento: insertion sort, merge sort, quick sort, limite asintotico inferiore per l’ordinamento basato sul confronto, ordinamento in tempo lineare, counting sort and radix sort
Strutture dati: array, alberi, al eri binari, pile, code, liste concatenate, tabelle hash, grafi, disjoint set, suffix tries, suffix trees and suffix arrays, Burrows-Wheeler transform
Algoritmi su grafi e alberi: algoritmi di visita, algoritmo di Kruskal's algorithm per il problema di calcolare l’albero di copertura minimo in un grafo
Algoritmi su stringhe: exact e approximate string matching, global sequence alignment, local sequence alignment, semiglobal sequence alignment
Algoritmi per problemi NP-completi: algoritmi brute force, algoritmi di approssimazione, algoritmi branch-&-bound, euristiche (basate su approccio greedy), esempi per il problema del commesso viaggiatore
Testi/Bibliografia
È fondamentale fare riferimento al materiale elettronico (slide con nozioni teoriche ed esercizi svolti) fornito durante il corso. Tale materiale sarà disponibile sulla pagina web del corso.
I libri di testo indicati sotto sono consigliati ma non necessari.
Testi specifici per la 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
Testi 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
Il metodo didattico consiste di lezioni frontali (supportate da slide e lavagna) e risoluzione di tipologie di esercizi che potrebbero essere richiesti in sede d’esame
Modalità di verifica e valutazione dell'apprendimento
La prova finale è composta da una parte scritta (3 ore) ed eventualmente da un orale (30 minuti). Durante la prova scritta non è possibile usare appunti o libri. La prova orale viene richiesta dal docente solo nel caso in cui la prova scritta abbia ottenuto una valutazione vicina al 18/30
Strumenti a supporto della didattica
Slide in formato elettronico e proiettore.
Personal computer.
Lavagna
Orario di ricevimento
Consulta il sito web di Pietro Di Lena