ASD III anno, 2002-03

Laurea e Diploma in Informatica

Corso di Algoritmi e Strutture Dati: Algoritmi, Calcolabilita' e Complessita' (III anno) - a.a. 2002/03
Questo e' l'ultimo anno in cui il corso sara' attivato

Ultima modifica: 29 Ottobre 2002
Docente: Prof. Eugenio Moggi (email moggi@disi.unige.it)
Orario (II semestre): Lun 11.00-13.00, Mer 9.00-10.00, Ven 16.00-18.00 (Aula 216) - inizio Mar 25/02/2003
Compitino 1a parte (10/03/2003 ore 11.00-13.00, aula 216): Risultati
Informazioni generali: Prerequisiti, Obiettivi, Programma, Testi di Riferimento
Informazioni on line: registro delle lezioni, note
ESAMI: Informazioni generali, Testi e soluzioni di esami precedenti Situazione voti
Lista degli studenti

Prerequisiti

ASD I anno e LM II anno, e' auspicabile aver seguito anche LP II anno.

Riprendere ed integrare il corso di ASD I anno. In particolare: illustrare idee generali per sviluppare ed analizzare algoritmi, algoritmi su grafi, strutture date avanzate, nozioni e risultati fondamentali di calcolabilita' e complessita' computazionale.

Modalita' degli esami

L'esame si suddivide in una prova scritta ed una orale. La prova scritta consiste di due parti valutate indipendentemente (relative rispettivamente alla prima e seconda parte del corso). Per ciascuna parte sara' dato un tempo prefissato (in genere 2 ore). Durante lo scritto e' possibile consultare dispense e libri. E' possibile conservare il voto dello scritto (o anche di una delle 2 parti) negli appelli successivi, basta non ritentarlo (o non cosegnare quella parte). Tuttavia, alla fine di ogni anno accademico viene fatto un reset dei voti (per maggiori dettagli vedi ESAMI).

Programma

concetti informali e loro formalizzazione [NOTE]:
- problema come relazione input-output
- algoritmo (deterministico) come automa, funzione calcolata e tempo astratto
- raffinamento di un algoritmo come simulazione tra automi
tecniche generali:
- tipi di dato astratti [RICHIAMI, NOTE]: segnatura, algebra (parziale), omomorfismi e simulazioni tra ADT (correttezza parziale)
- analisi di algoritmi ricorsivi [AHU87, CH 9]
- divide-et-impera, programmazione dinamica [AHU87, CH 10.1-2]
- euristiche: ricerca esaustiva, pruning, branch-and-bound [AHU87, CH 10.3-5]
alcuni ADT e loro implementazioni:
- dizionario [AHU87, CH 4.5-8]
- coda di priorita' [AHU87, CH 4.10-11]
- binary search trees [AHU87, CH 5.1-2], accenni a 2-3 e AVL trees [AHU87 5.4], B-trees [AHU87 11.4]
grafi e algoritmi su grafi [AHU87, CH 6, 7.1-3]
- rappresentazioni
- visite DFS e BFS
- test di aciclicita'
- topological sorting
- cammini minimi (vedi anche chiusura transitiva [NOTE])
algoritmi di ordinamento [AHU87, CH 8.3-4]: heapsort, quicksort
dal divide-et-impera alla programmazione dinamica [NOTE]
- numeri di fibonacci
- coefficenti binomiali
- problema dello zaino
PARTE CALCOLABILITA' e COMPLESSITA'
modelli di calcolo: TM, RAM, funzioni calcolabili, complessita' tempo e spazio, relazione tra i due modelli di calcolo, Tesi di Church e Tesi di Church estesa.
calcolabilita': funzioni calcolabili, problemi/sottoinsiemi decidibili e semidecidibili, riducibilita' tra problemi, codifica delle TM, TM universale, esempi di problemi non (semi)decidibili, proprieta' di chiusura dei sottoinsiemi (semi)decidibili.
complessita': classi di complessita', relazioni tra classi di complessita' ed O-notazione, classi naturali di complessita' (P, NP), teorema di Cook, esempi di problemi NP-completi.
panoramica su altri argomenti di complessita': accenni ad altri modelli di calcolo (per algoritmi probabilistici e paralleli), e relative classi di complessita'.

Testi di Riferimento

[AHU87] A.Aho, J.E.Hopcroft, J.D.Ullman. Data Structures and Algorithms. Addison-Wesley, 1987.
[Ber00] A.Bertossi. Algoritmi e Strutture di Dati. UTET-Libreria, 2000.
[CLRS01] T.H.Cormen, C.E.Leiserson, R.L.Rivest, C.Stein. Introduction to Algorithms. McGraw-Hill, 2001.
[P94] C.Papadimitriou. Computational Complexity. Addision-Wesley, 1994. (CH 1-3, 7-9)