Corso di Algoritmi e Strutture Dati: Algoritmi, Calcolabilita' e
Complessita' (III anno) - a.a. 1998/99
Il corso e' utilizzato anche dagli studenti del IV anno al posto di
MFI. Nel primo semestre il corso e' sdoppiato in due parti, una per
il III anno e l'altra per il IV anno. Nel secondo semestre il corso
e' unificato.
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.
Esame scritto ed orale. A meta' corso (Febbraio) vi sara' la
possibilita' di essere esaminati sulla parte di Algoritmi.
- PARTE PER STUDENTI DEL III ANNO: 40 ore
- 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]
- eurestiche [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, 2-3 trees, AVL trees, B-trees
[AHU87, CH 5.1-2, 5.4, 11.4]
- MF set [AHU87, CH 5.5]
- 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])
- componenti fortemente connesse
- minimum cost spanning tree
- algortimi 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
- chiusura transitiva
- moltiplicazione di matrici rettangolari
- PARTE PER STUDENTI DEL IV ANNO: 40 ore
- tipi di dato astratti (e richiami di LM):
- strutture eterogenee totali (algebre totali):
sintassi (segnatura,termini,formule),
semantica (modelli ed interpretazione di termini e formule)
- strutture eterogenee parziali (algebre parziali):
sintassi, semantica
- specifiche dei requisiti (loose)
- sistemi deduttivi:
soundness e completeness (relativamente ad un frammento)
- specifiche design: modello iniziale,
condizioni per l'esistenza del modello iniziale
- regole di riscrittura: confluenza, normalizzazione forte,
forme normali e decidibilita' dell'uguaglianza
- fondamenti di programmazione funzionale e tipi:
- strutture applicative e algebre combinatorie (parziali):
teoria equazionale, modelli, riscrittura, potere espressivo,
proprieta' aggiuntive (estensionalita', test di uguaglianza)
- lambda calcolo non tipato: alpha-conversione, beta-riduzione,
confluenza, relazioni con la logica combinatoria
- estensioni del lambda calcolo (con costanti):
semantica operazione, errori dinamici, equivalenza osservazionale
- type sistems: termini con e senza informazione di tipo
- type systems e semantica operazionale: subject reduction
- tipi come sottoinsiemi: soundness di un type system
- tipi: funzionali, record, variant, reference; subtyping;
ricorsivi, polimorfi (universali), astratti (esistenziali)
- algoritmi di type checking e type inference, risultati negativi
- ????concetti di base per processi reattivi e concorrenti:
- sistemi di transizione etichettati (LTS)
- CCS: semantica operazionale
- specifica di sistemi reattivi e concorrenti:
LTS, cenni ad altri formalismi
- equivalenza osservazionale tra processi:
bisimulazione, cenni ad altre nozioni
- PARTE A COMUNE: 40 ore
- 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'.
- [AHU87] A.Aho, J.E.Hopcroft, J.D.Ullman. Data Structures and
Algorithms. Addison-Wesley, 1987.
- [HS86] J.R.Hindley, J.P.Seldin. Introduction to Combinators and
Lambda-Calculus. Cambridge University Press, 1986.
(CH 1-3, 6-10)
- [C97] L.Cardelli. Type Systems. Handbook of Comp. Sci. and
Engineering, CRC Press, 1997.
- [P94] C.Papadimitriou. Computational Complexity.
Addision-Wesley, 1994.
(CH 1-3, 7-9)
Laurea e Diploma in
Informatica