- Docente: Luciano Bononi
- 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)
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
Essendo un corso di studio internazionale, il corso di Algorithms
and Data Structures for Computational Biology viene tenuto
completamente in lingua inglese.
Introduction to algorithms and basic data structures:
definitions, algorithms, simple data structures. Lists, arrays,
simple operations, examples, implementation. Complex data
structures, computation efficiency and relation between computation
efficiency and data structures. Stacks and queues (definition,
examples, implementation). Trees, visit algorithms of a tree and
tree operations. Sets, dictionaries and hash tables, their
operations and implementation concepts. Graphs, visit algorithms
for graphs, operations and implementation concepts. Exercices and
tests ( graphs and trees, priority queues and heaps). Binary trees,
search trees, balanced binary trees, B-trees, AVL trees.
Algorithms. Decision tree. Analysis of computational complexity of
algorithms. O(), Omega() and Theta() functions. Iterative and
recursive programming methodologies. Divide and conquer. Recursion.
Greedy techniques (knapsack problem, radix sorting problem, Huffman
codes). Binary search. Sorting algorithms. Sequence pattern
analysis and matching. Algorithm optimization. Complexity analysis
of algorithms. Exercises and tests.
Testi/Bibliografia
It is fundamental to use the electronic slides and material
provided during the classes, including live exercises. Electronic
slides will be provided (also made available on the teachers'
website).
Suggested readings (not to be necessarily purchased).
Books more specific on computational biology
topics:
- 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
Books more general on computer algorithms and data structures
topics:
- 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 corso si svolge al secondo semestre e rappresenta un modulo unico di 10 cfu. Il modulo è strutturato in lezioni frontali in aula, tutte in inglese, in cui vengono presentati innanzitutto gli aspetti teorici degli argomenti trattati. In particolare, dopo aver introdotto le nozioni di base, relative alla progettazione di strutture dati e della loro relazione con il costo in termini di spazio e con l'efficienza di esecuzione di algoritmi al calcolatore, vengono enunciati, e in alcuni casi dimostrati, i principali risultati nell'ambito della progettazione di algoritmi e della complessità computazionale nell'esecuzione degli algoritmi su architetture di calcolo non parallele. Vengono infine introdotte le tecniche di programmazione iterative, ricorsive, divide et impera, greedy e di programmazione dinamica e vengono illustrati i loro utilizzi in funzione diella riduzione della complessità computazionale e spaziale sul calcolatore. Successivamente ampio spazio viene dedicato alle applicazioni delle nozioni e delle tecniche presentate, e alla risoluzione di esercizi nel contesto delle metodologie di analisi della bioinformatica e biologia molecolare. Oltre alle lezioni frontali in aula, vengono svolte esercitazioni in aula (semplici), e vengono fornite esercitazioni (homework) sui temi analizzati.
Modalità di verifica e valutazione dell'apprendimento
La verifica dell'apprendimento avviene attraverso una prova scritta
finale di 3 ore e una contestuale prova orale di circa 30 minuti.
Per la prova scritta viene ammesso l'uso di: libri, appunti, ma non
l'uso di calcolatrici e supporti informatici, e nemmeno l'uso di
strumenti che consentano accesso a Internet. La prova scritta è
strutturata in più parti: la prima riguarda la progettazione di un
algoritmo e della relative strutture dati orientate alla massima
efficienza computazionale, secondo requisiti di prestazioni e di
spazio di memoria predefiniti, facendo ricorso alle conoscenze
sviluppate nel corso. Viene richiesto di sviluppare le strutture
dati e lo pseudo codice dell'algoritmo e commentare le scelte
effettuate definendo la complessità spaziale e computazionale
ottenuta. Il primo esercizio richiede circa 90 minuti e vale circa
metà della valutazione della prova scritta. I dettagli su durata e
peso della valutazione di ogni esercizio sono indicati nel testo di
volta in volta. La seconda parte della prova scritta riguarda una
serie di esercizi mirati a verificare la conoscenza e la capacità
di interpretare e applicare i concetti studiati. Tali esercizi sono
spesso simili e derivati dalle esercitazioni svolte durante il
corso. Il tempo a disposizione per la seconda parte è di 90 minuti
e il peso della seconda parte è circa la metà della valutazione
totale.
La calendarizzazione delle prove scritte avviene entro la fine del
corso in aula. Sono previsti appelli della prova scritta nei mesi
di Giugno, Luglio, Settembre, ottobre, Dicembre e Febbraio. E'
necessario effettuare l'iscrizione alle prove sulla piattaforma
almaesami entro le scadenze fissate di volta in volta.
Previo superamento della prova scritta, ottenendo una valutazione
di almeno 18/30, si procede alla convocazione per la successiva
prova orale, da effettuarsi entro la fine della sessione di esame,
nei giorni immediatamente successivi alla prova scritta. Il non
superamento della prova orale comporta la necessità di ripetere la
prova scritta contestuale in un appello successivo. In caso di
superamento della prova scritta e della prova orale, viene
effettuata la proposta di voto finale del corso, calcolata come
media pesata delle prove scritte e orale. Il peso delle prove
scritte e orale è di 80% e 30% rispettivamente (totale 110%). La
somma dei valori (voto scritto * 0,80) + (voto orale * 0,30)
fornisce il valore della proposta di voto. In caso di superamento
del valore di 30/30 è prevista l'attribuzione della lode. Per
superare l'esame dovranno risultare sufficienti entrambe le prove
scritta e orale.
E' possibile per i candidati presentare un progetto
facoltativo, inerente la progettazione, analisi e realizzazione
prototipale di soluzioni algoritmiche per problemi di
bioinformatica, basandosi sulle tecniche allo stato dell'arte. La
valutazione del progetto facoltativo, da 0 a 3 punti, si somma alla
valutazione finale della prova scritta e orale.
Strumenti a supporto della didattica
Proiettore e slide elettroniche.
Personal computer.
Lavagna.
Link ad altre eventuali informazioni
http://www.cs.unibo.it/~bononi/
Orario di ricevimento
Consulta il sito web di Luciano Bononi