- 28/10/02 (1h).
Formalizzazione delle nozioni di problema (di input-output) e di
algoritmo (sequenziale e deterministico) mediante automi e nozioni
derivate. Correttezza parziale e totale.
Automi con transizioni pesate (a valori in un monoide ordinato) e
rivitazione delle nozioni correlate. Esempi di monoidi per
complessita' tempo e spazio.
- 29/10/02 (2h).
Dimostrazioni di correttezza parziale mediante invarianti.
Tecnica per dimostrare la terminazione di un automa.
Esempi: problema del sorting di una sequenza (di reali),
formalizzazione del selection-sort e bubble-sort,
dimostrazione di correttezza parziale e terminazione.
- 31/10/02 (2h).
Automi con transizioni pesate, complessita' e maggiorazione in
funzione della dimensione dell'input.
Simulazione tra automi e sue proprieta'.
Esempi di raffinamenti e simulazioni: selection-sort e bubble sort.
Applicazione delle tecniche per correttezza parziale e terminazione
per dimostrare che una relazione tra automi e' una simulazione.
- 05/11/02 (3h).
Schema divide-et-impera per la definizione ricorsiva di funzioni
parziali. Tecniche per dimostrare la terminazione e la correttezza
parziale (albero delle chiamate ricorsive). Esempi: selection-sort,
insertion-sort, merge-sort e quick-sort. Non-esempi: bubble-sort.
Definizione ricorsiva della complessita' esatta per un algoritmo
divide-et-impera.
- 08/11/02 (2h).
Maggiorazioni della complessita' esatta (in funzione della dimensione
del problema), il master method. Applicazioni delle tecniche di
maggiorazione agli esempi visti, inadeguatezza della maggiorazione nel
caso del quick-sort.
Altri esempi di algoritmi divide-et-impera: Moltiplicazione di grandi
numeri, calcolo ottimale della moltiplicazione di una sequenza di
matrici rettangolari.
- 12/11/02 (3h).
Tipi di dato come algebre parziali eterogenee: segnature, termini,
algebre, interpretazione dei termini. Esempi: stack e insiemi (finiti).
Definizione di simulazione e simulazione parziale.
Metodologia di implementazione di un tipo di dato (a partire da un
modello canonico). Esempi: naturali e sequenze binarie, insiemi
finiti e liste (o bit-vector).
Proprieta' di simulazioni e simulazioni parziale. Composizione di
simulazioni. Relazione tra omomorfismi e simulazioni.
- 15/11/02 (2h).
Implementazioni del tipo di dato set: a bit-vector, a liste o porzione
di array (senza ripetizioni, ordinate). Possibili implementazioni
delle operazioni per la rappresentazione a liste, discussione della
loro correttezza e complessita'.
Specifica della complessita' in termini del modello canonico, invece
che dell'algebra che descrive l'implementazione.
- 19/11/02 (3h).
Estensione del tipo di dato set con complementazione (U infinito):
modo generico di definirsi una implementazione con complementazione
avendo una senza complementazione (ma e' necessaria la differenza).
Estensione del tipo di dato set con ordine lineare (denso) su U e
operazione intervallo: unione di intervalli limitati e non adiacenti
(in ordine crescente), funzione caratteristica con un numero finito di
punti di discontinuita'.
- 22/11/02 (2h). DOCENTE ASSENTE
- 26/11/02 (3h).
Restrizioni del tipo di dato set: dizionari e code di priorita'.
Implementazione naive (a liste ordinate); alberi di ricerca binari
(problema a stimare la complessita'); B-trees = albero di ricerca
perfettamente bilanciato che rappresenta l'insieme delle foglie (caso
con 2-3 figli).
B-trees: relazione tra altezza e cardinalita' dell'insieme
rappresentato, dimostrazione di correttezza di member per induzione
sulla struttura dell'albero. Insert (overflow e suddivisione),
proprieta' di correttezza per la funzione ausiliaria.
- 29/11/02 (2h).
B-trees: delete (underflow e concatenazione o bilanciamento).
Funzioni di conversione da B-tree a lista ordinata e viceversa
calcolabili in tempo lineare, ed implementazione delle operazioni
union, intersect, difference mediante conversione.
Il tipo di dato code di priorita' (min e deletemin). Implementazione
usando liste ordinate o B-tree. Modifica del modello canonico per
liste di priorita' usando multi-insiemi.
- 03/12/02 (3h).
Code di priorita: implementazione ad heap con albero quasi
perfettamente bilanciato rappresentato mediante un array
(costo logaritmico di insert e delmin).
Grafi orientati (etichettati): definizioni generali, varianti.
Rappresentazione di grafi: matrice di adiacenza e liste di adiacenza,
altre rappresentazioni.
Algoritmi su grafi (rappresentati con liste di adiacenza) per calcolo
in-degree e topological sorting: correttezza ed implementazione con
complessita tempo O(V+E).
- 06/12/02 (2h). DOCENTE ASSENTE
- 10/12/02 (3h).
Correttezza del topological sorting mediante invariante. Test di
aciclicita'. Tempistiche ottimali. Definizione di visita di un
grafo, e sue proprieta' (nodi visitati=nodi raggiungibili, albero di
visita). Schema generale per visite di grafi, usando un insieme di
nodi esaminati e di nodi frontiera.
- 13/12/02 (2h).
La visita BFS e DFS come istanze dello schema generale implementando la
frontiera come coda e stack. Algoritmo per BFS in O(V+E), Algoritmo
ricorsivo per DFS in O(V+E).
Rappresentazione di grafi etichettati con reali positivi con matrici a
valori reali positivi estesi. Lunghezza di un cammino e distanza tra
nodi. L'algoritmo di Dijkstra per calcolare le distanze da un nodo in
tempo O(V^2). Correttezza dell'algoritmo di Dijkstra mediante
invariante.
- 17/12/02 (3h).
Risultato di decomposizione di un cammino da u a v con nodi intermedi
in U+w. Algoritmo di Floyd per il calcolo delle distanze. Semianelli
(chiusi): definizione, esempi e costruzioni di semianelli (chiusi).
Relazione tra matrici quadrate a valori in semianelli chiusi e grafi
etichettati. Operazioni su matrici e loro interpretazione in termini
di grafi: prodotto, chiusura transitiva (e riflessiva).
Adattamento dell'algoritmo di Floyd per calcolare la chiusura
transitiva in un semianello chiuso A: decomposizione univoca di un
cammino proprio da u a v con nodi intermedi in U+w; ruolo della
operazione a^*. Esempi di problemi su grafi che si possono ridurre ad
un problema di chiusura transitiva mediante una opportuna scelta del
semianello: esistenza di un cammino, cammino di lunghezza minima (con
etichette a valori in R).
20/12/02 LEZIONE CANCELLATA
VACANZE DI NATALE
- 07/01/03 (3h).
Esempi di problemi su grafi che si possono ridurre ad un problema di
chiusura transitiva mediante una opportuna scelta del semianello:
cammino di capacita' massima, cammino di lunghezza massima, insieme di
stringhe (insiemi di caratteri) associato ai cammini da x ad y (archi
etichettati con caratteri di un alfabeto).
Esempio con semi-anello composito: numero di cammini di lunghezza minima.
Contro-esempio (non soddisfa le proprieta' di un semi-anello):
cammino di lunghezza minima tra quelli di capacita' massima.
Variante dell'algoritmo di Floyd per costruirsi un cammino di
lunghezza minima (se esiste): matrice con nodi intermedi.
10/01/03 LEZIONE CANCELLATA
- 14/01/03 (3h).
La programmazione dinamica come ottimizzazione del divide-et-impera.
Analisi della complessita' tempo e spazio tra divide-et-impera e
programmazione dinamica sulla base del grafo delle chiamate ricorsive:
cammini e chiamate ricorsive (divide-et-impera),
nodi raggiungibili e soluzioni da memorizzare (programmazione dinamica).
Tecniche associate alla programmazione dinamica: approccio
demand-driven, approccio bottom-up (e riduzione della complessita'
spazio).
Esempi di applicazione della programmazione dinamica: numeri di
fibonacci, coefficenti binomiali, moltiplicazione ottimale di matrici,
problema dello zaino (tecnica demand-driven preferibile).
- 17/01/03 (2h - inizio ore 15.30).
Esercizi
- 21/01/03 (3h).RECUPERO
Esercizi
SOSPENSIONE DELLE LEZIONI
- 25/02/03 (1h).
introduzione: differenza tra problemi e algoritmi; algoritmi e modelli
di calcolo; classi di problemi "indipendenti" dal modello di calcolo;
problemi decidibili e semi-decidibili (relazione con logica
matematica); classi naturali di complessita' ("problemi trattabili").
- 26/02/03 (1h).
Richiami su automi deterministici:
relazione di transizione, computazione, funzione calcolata,
complessita' tempo, correttezza parziale e totale,
simulazione tra automi e sue proprieta'.
Esempio: sorting di una sequenza (di reali), formalizzazione del
selection-sort.
- 28/02/03 (2h).
Il modello di calcolo delle TM (ad un nastro) e automa associato.
Linguaggio T-decidibile e T-semidecidibile.
Le classi di linguaggi R e RE, inclusione di R in RE. La tesi di
Church (invarianza di R ed RE al variare del modello di calcolo).
Altri modelli di calcolo: RAM e automa associato, TM a m-nastri.
03/03/03 DOCENTE IMPEGNATO CON ESAME DOTTORATO
- 05/03/03 (1h).
Richiami su automi deterministici (solo per studenti del nuovo
ordinamento): tecniche per dimostrare correttezza parziale e
terminazione, esempi di invariante e simulazione.
- 07/03/03 (2h).
Varianti delle TM: input read-only, output write-only, traduttori.
Le classi di complessita' tempo TIME_m(f) e TIME(f). La classe P dei
problemi trattabili.
Inclusione di TIME_m(f) in TIME_1(O(f^2)) e simulazione di una TM a
m-nastri con una TM ad 1 nastro.
Il teorema di linear speed-up: simulazione di molti passi con pochi passi.
- 10/03/03 (2h). COMPITINO 1a PARTE
- 12/03/03 (1h).
Le classi di complessita' spazio SPACE_m(f) e SPACE(f) e TM offline.
Simulazione di una TM a m-nastri di lavoro con una TM ad 1 nastro
lavoro, inclusione di SPACE_m(f) in SPACE_1(f).
Il teorema di tape-compression: rappresentazione di m caratteri con un
carattere.
- 14/03/03 (2h).
Il modello di calcolo delle RAM, automa associato, e relative classi
di complessita' tempo. Confronto con il modello delle TM.
Simulazione di una TM mediante RAM in O(f).
Simulazione di una RAM mediante una TM con la tecnica del log file.
- 17/03/03 (2h).
Crescita lineare della dimensione degli interi, e simulazione di una
RAM che lavora in tempo f con una TM che lavora in tempo O(f^3(n)).
Impossibilita' di simulare una RAM con moltiplicazione che lavora in
tempo f con una TM che lavora in tempo O(f^k(n)).
Le TM non-deterministiche (NDTM), definizione di linguaggio deciso e
tempo/spazio di lavoro. Le classi di complessita' non-deterministiche
NTIME(f) e NSPACE(f).
- 19/03/03 (1h).
Simulazione di una TM non-deterministica mediante una TM
deterministica mediante visita BFS dell'albero delle possibili
computazioni, e relazione tra NTIME e TIME.
Esempi di algoritmi non-deterministici per SAT e Reachability.
- 21/03/03 (2h).
Risultati di riduzione ad un nastro, speed-up e tape compression per
le classi non-deterministiche.
Relazione tra complessita' spazio e numero di configurazioni
raggiungibili (tecnica di loop detection tramite contatore).
Classi di complessita' tempo-spazio e deterministiche e non: risultati
di inclusione ovvi. Inclusione NTIME in SPACE (visita per livelli
dell'albero delle computazioni) e NSPACE in TIME (ricerca di un
cammino nel grafo dell ID). Inclusione di NSPACE in SPACE (teorema di
Savitch).
- 24/03/03 (2h).
Classi naturali: relazioni di inclusione.
La nozione di riduzione tra problemi. Proprieta' della riduzione,
proprieta' di chiusura per riduzione dei problemi (semi)decidibili.
Uso della riduzione per dimostrare la non (semi)decidibilita'.
Riduzione poly-time e/o log-space. Proprieta' di chiusura delle
classi naturali rispetto riduzione.
Classi di linguaggi e linguaggi C-completi (rispetto ad una riduzione).
TM canoniche ed equivalenza tra TM e TM canoniche.
26/03/03 LEZIONE CANCELLATA
28/03/03 LEZIONE CANCELLATA
- 31/03/03 (2h).
Codifica TM canoniche come stringhe.
La funzione universale (per riconoscitori e traduttori). La TM
universale. I linguaggi H (halting problem, codifica delle coppie) e
K, semidecidibilita' di H (usando la TM universale) e K (riducibile ad
H). Non decidibilita' di K (e H).
RE-completezza di H.
- 02/04/03 (1h).
La TM universale per traduttori (con input read-only e output
write-only).
Teorema S-m-n e definizione implicita di codifiche di TM.
Non decidibilita' delle proprieta' estensionali dei programmi (Teorema
di Rice).
- 04/04/03 (2h).
Esempi di proprieta' estensionali.
Proprieta' di chiusura di R ed RE rispetto ai connettivi logici.
Caratterizzazione di R in termini di RE (RE non e' chiuso per
complementazione).
Proprieta' di chiusura di R per` quantificazione limitata
Predicato di Kleene. Chiusura di RE per quantificazione esistenziale
illimitata, e per quantificazione limitata.
07/04/03 LEZIONE CANCELLATA
09/04/03 LEZIONE CANCELLATA
11/04/03 LEZIONE CANCELLATA
- 14/04/03 (2h).
Caratterizzazione di RE in termini di R (predicato di Kleene).
Dimostrazioni alternative delle proprieta' di chiusura di RE usando il
predicato di Kleene.
Caratterizzazione di R ed RE in termini di enumerazioni.
- 16/04/03 (1h).
Riassunto proprieta' di chiusura di R ed RE rispetto a:
riduzione, connettivi logici, quantificazione (limitata ed illimitata).
ESERCIZI: TOT, etc.
vacanze pasquali
- 28/04/03 (2h).
ESERCIZI su calcolabilita' del tipo "dire se un linguaggio appartiene
ad R o RE". Dimostrazioni (per assurdo) che TOT non e' riducibile al
complementare di K, e che funzioni con certe proprieta' non possono
essere calcolabili.
- 30/04/03 (1h).
proprieta' di chiusura delle classi naturali rispetto ad operazioni
insiemistiche, quantificazione limitata (N, NL)
- 02/05/03 (3h recupero).
proprieta' di chiusura delle classi naturali rispetto a
quantificazione limitata (P, NP, PSPACE).
Caratterizzazione di NP in termini di P. Analisi di complessita' per
la TM universale e per il predicato di Kleene.
Problemi completi: varianti della TM universale, e problemi completi
per NL, P, NP e PSPACE ottenuti da varianti dell'halting problem.
- 05/05/03 (2h).
Teoremi di gerarchia spazio e tempo.
Inclusioni strette tra classi naturali di complessita'.
- 07/05/03 (1h).
Problemi logici che risultano essere completi per qualche classe
naturale: CVP (P), monotone CVP (P), SAT (NP), k-SAT (NP se k>2),
2-SAT (NL), HORNSAT (P), QBF (PSPACE). Verifica che SAT appartiene ad NP.
- 09/05/03 (2h).
P-completezza di CVP.
Metodo della tabella:
corrispondenza riga descrizione istantanea,
corrispondenza tabella computazione.
Codifica booleana di una tabella, Circuito buoleano per calcolare la
tabella corrispondente ad una computazione.
NP-completezza di SAT: codifica di una tabella mediante variabili
booleane; formula in CNF per esprimere che esiste una tabella
che rappresenta una computazione accettante.
- 12/05/03 (2h).
NP-completezza di (riduzione di SAT a) 3-SAT e CIRCUIT SAT.
P-completezza di (riduzione di CVP a) MONOTONE CVP.
HORNSAT P-completo: costruzione del modello minimo e verifica dei
goal; riduzione di CVP a HORSAT (simile a riduzione a monotone CVP).
QBF PSPACE-completo (formula compatta, ma non in CNF, per esprimere
P(u,v,n) esiste un cammino di lunghezza <= 2^n da u a v nel grafo
delle ID di M con input x).
- 14/05/03 (1h).
QBF PSPACE-completo: completamento della dimostrazione. Reachability
e' ML-completo: mappare x in un problema di reachability per il grafo
delle ID di M con input x, con M NDTM con input read-only che lavora
in spazio logaritmico.
- 16/05/03 (2h).
Problemi NP-completi su grafi non-orientati:
3_SAT < independent set < node cover, clique;
3-colorability (senza dimostrazione).
Problemi NP-completi su grafi orientati:
hamilton path, travelling salesman problem.
Problemi NP-completi numerici:
integer programming, problema dello zaino.
- 19/05/03 (2h).
Chiusura per concatenazione di P e NP. Chiusura per Kleene star di NP
e P. Chiusura per coding di NP. P non e' chiuso per coding, se P non
coincide con NP. NL-completezza di una variante di Reachability.
- 21/05/03 (1h). ESERCIZI su complessita'..
- 23/05/03 (2h). ESERCIZI su I parte.
- 26/05/03 (2h). ESERCIZI su complessita'.
- 28/05/03 (1h). ESERCIZI su calcolabilita'.
- 30/05/03 (2h). ESERCIZI su I parte.
fine lezioni