Martedì, 15 marzo 2011
Introduzione al corso. Obiettivi, programma e materiale didattico del corso. Alfabeti e stringhe. Il monoide sintattico. Linguaggi. Approcci alla caratterizzazione di linguaggi: espressioni, grammatiche, automi. Operazioni insiemistiche su linguaggi: unione, intersezione, complemento. Operazioni sul monoide sintattico: Prodotto (o concatenazione) di linguaggi, iterazione (o operazione stella) di linguaggi. Espressioni regolari. Applicazione delle espressioni regolari alla descrizione dei cammini su un grafo.

Martedì, 22 marzo 2011
Determinazione di una espressione regolare che descrive un linguaggio dato. Manipolazione di e.r. Proprietà algebriche dell'operazione di concatenazione: non commutatività, distributiva destra e sinistra. Raccoglimento a fattor comune. Linguaggio delle stringhe con non più di tre a; con un numero di a divisibile per 3, con esattamente una occorrenza della sottostringa aaa. Semplificazione dell'e.r. Introduzione alle grammatiche: simboli terminali, non terminali, assioma e regole di produzione. Derivazione diretta e indiretta. Esempio di derivazione.

Venerdì, 25 marzo 2011
Introduzione ai sistemi di riscrittura come modello di calcolo. Grammatiche di Chomsky. Concetti di derivazione diretta e di derivazione. Linguaggio generato da un grammatica. Grammatiche di Chomsky di tipo 0, di tipo 1 (CS), di tipo 2 (CF) di tipo 3. Linguaggi di tipo 0, 1, 2, 3. Esempi di grammatiche di vario tipo.

Martedì, 29 marzo 2011
Esempi di grammatiche di tipo 0, 1. Derivazioni di stringhe. Grammatica di tipo 0 e di tipo 1 per anbnbn. Esercizi sulla determinazione di e.r.. Linguaggi delle stringhe: che contengono sia ab che ba, che non contengono né aabb, in cui ogni a è preceduta e seguita da una b. Grammatiche di tipo 3: determinazione di una grammatica per il linguaggio delle stringhe contenenti un numero dispari di a e un numero pari di b.

Venerdì, 1 aprile 2011
Definizione dei linguaggi regolari. Importanza e applicazioni dei linguaggi regolari. Automi a stati finiti (ASF): definizione ed esempi. Dimostrazione del fatto che i linguaggi riconosciuti da ASF possono essere generati con grammatiche di tipo 3 e sono quindi linguaggi regolari. Introduzione agli automi a stati finiti non deterministici e chiusura dei linguaggi regolari rispetto a unione, complementazione, intersezione, concatenazione, iterazione. Dimostrazione del fatto che i linguaggi rappresentati da espressioni regolari possono essere riconosciuti da ASF.

Martedì, 5 aprile 2011
Determinazione di una ASF che riconosca un linguaggio dato. Eliminazione delle regole che generano la stringa vuota. Identificazione ed eliminazione dei non terminali infecondi e corrispondenza con gli stati non raggiungibili o dai quali non si raggiunge uno stato finale. Stato di errore. Automa del linguaggio complementare. Esempi: automi per i linguaggi delle stringhe con numero di a divisibile per 3, stringhe senza aa e bb, stringhe con un numero pari di a dispari di b, stringhe che non contengono 3 b consecutive, stringhe che contengono sia ab che ba, stringhe in cui ogni a è preceduta e seguita da una b. Conversione di un ASFD in una grammatica regolare. Sostituzione ed eliminazione della ricorsione. Automi ND. Transizioni non deterministiche e parallelismo. Albero della computazione per un ASFND.

Venerdì, 8 aprile 2011
Automi a stati finiti non deterministici (ASFND): definizione ed esempi. Definizioni del concetto di computazione eseguita da ASFND come albero di computazioni nello spazio degli stati e computazione deterministica nell'insieme delle parti (power set) degli stati. Costruzione di un ASF equivalente ad un ASFND dato. Pumping lemma per i linguaggi regolari. Esempio di linguaggio non regolare con dimostrazione basata sul pumping lemma. Proprietà decidibili per i linguaggi regolari: dato un ASF il linguaggio da esso riconosciuto è vuoto, finito, infinito. Decidibilità del problema dell'equivalenza per gli ASF.

Martedì, 12 aprile 2011
Trasformazione di automi ASFND in ASFD. Aumento del numero degli stati. Riconoscitori di sequenza. Determinazione dell'automa e sua trasformazione in grammatica regolare e in espressione regolare. Eliminazione delle regole che generano la stringa vuota. Identificazione ed eliminazione dei non terminali infecondi e corrispondenza con gli stati non raggiungibili o dai quali non si raggiunge uno stato finale. Stato di errore. Esercizi: stringhe con un numero di b uguale a 3k+1 con k intero; automa per riconoscere i numeri divisibili per 2 e per 3; automa per le costanti numeriche intere, in virgola fissa e in notazione esponenziale.

Venerdì, 15 aprile 2011
Definizione del linguaggi context free (CF). Importanza e applicazioni dei linguaggi CF. Introduzione informale ed esempi di linguaggi CF deterministici e non deterministici. Enunciazione del fatto che la classe dei linguaggi CF deterministici è contenuta strettamente nella classe dei linguaggi CF non deterministici. Il problema dell'ambiguità: definizione di grammatica ambigua e modi per eliminare l'ambiguità. Pumping lemma per i linguaggi CF. Esempio di linguaggi non CF con dimostrazione basata sul pumping lemma. Proprietà decidibili per i linguaggi CF: data una grammatica CF il linguaggio da essa generato è vuoto, finito o infinito. Chiusura dei linguaggi CF rispetto a unione, concatenazione, iterazione. Dimostrazione che i linguaggi CF non sono chiusi rispetto a intersezione e quindi non sono chiusi rispetto a complementazione. Enunciazione del fatto che l'equivalenza di linguaggi CF non deterministici non è decidibile mentre l'equivalenza per linguaggi CF deterministici è decidibile. Automi a pila non deterministici (APND) e automi a pila deterministici (AP): definizioni ed esempi. Esempi di AP che accettano per stato finale o per pila vuota.

Martedì, 19 aprile 2011
Esercizi sulle grammatiche context-free. Determinazione di una grammatica a partire dal linguaggio: linguaggio ambn con m>= n; linguaggio anbmcpdq con n+m = p+q; linguaggio delle stringhe con numero di b doppio del numero di a; linguaggio uawb con u e w stringhe su {a,b} di uguale lunghezza; linguaggio ambn con n ≤ m ≤ 2n. Grammatica per il linguaggio delle espressioni regolari. Grammatica per espressioni aritmetiche: precedenza degli operatori. Problema della ricorsione sinistra.
Venerdì, 29 aprile 2011
Forma ridotta, forma normale di Chomsky, forma normale di Greibach (GNF) per i linguaggi CF. Costruzione di automi a pila a partire da grammatiche CF in GNF. Introduzione alle Macchine di Turing. Definizioni ed esempi.
Venerdì, 06 maggio 2011
Introduzione alle Macchine di Turing. Definizioni ed esempi. Macchine di Turing a piu' nastri. Macchine di Turing non deterministiche. Macchina di Turing universale. Il problema della terminazione. Altri esempi di Macchine di Turing. Funzioni calcolabili (secondo Turing). Linguaggi decidibili e semidecidibili (secondo Turing). Relazione tra linguaggi semidecidibili e linguaggi di Chomsky di Tipo 0. Tesi di Church-Turing.
Martedì, 10 maggio 2011
Esercizi sulla trasformazione di grammatiche context-free in forma di Greibach. Scrittura dell'automa pushdown non deterministico corrisponente. Computazione su una stringa. Albero delle computazioni. Linguaggio ambn con m>= n. Linguaggio anbmcpdq con n+m = p+q. Linguaggio delle stringhe con numero di b doppio del numero di a. Linguaggio uawb con u e w stringhe su {a,b} di uguale lunghezza. Linguaggio ambn con n ≤ m ≤ 2n.
Venerdì, 13 maggio 2011
Macchine a registri (RAM) come modelli di semplici calcolatori. Modelli di costo (costi uniformi, costi logaritmici). Esempi. Simulazione di MT con RAM e di RAM con MT (con dimostrazioni).
Martedì, 17 maggio 2011
Esempi di macchine di Turing: macchina per il complemento a 2 di un numero binario, macchina incrementatrice di 1, macchina per il reverse di una stringa, macchina per lo shift di una stringa binaria. Composizione di MdT. Macchine elementari. Introduzione al LISP. Elementi del linguaggio: atomi e coppie puntate. Rappresentazione in memoria. Valore di un atomo. Atomi numerici e non. Atomi particolari: NIL e T. Ciclo read-eval-print. Rappresentazione delle liste con coppie puntate. Multiliste.
Venerdì, 20 maggio 2011
Introduzione al concetto di complessità computazionale di problemi. Richiami di concetti relativi alla complessità di problemi: modelli di macchina, upper bound e lower bound di complessità. Esempi: problema dell'ordinamento. problema della ricerca, prodotto di matrici. Classi di complessità. Relazioni tra classi in diversi modelli di calcolo. Relazioni tra classi spaziali e temporali. Relazioni tra classi deterministiche e non deterministiche. Il teorema di Savitch (con dimostrazione).
Martedì, 24 maggio 2011
Richiamo delle funzioni in LISP. Operatori e notazione prefissa. Valutazione di una lista come richiamo di una funzione. Funzione QUOTE. Struttura condizionale. Funzioni CAR, CDR, NULL e loro applicazioni alle liste. Definizioni di funzioni (DEFUN). Funzioni ricorsive sui numeri e sulle liste. Lunghezza di una lista, somma degli elementi di una lista. Funzione di costruzione CONS. Aggiunta di un elemento in fondo a una lista, concatenazione di due liste. Reverse di una lista. Inserimento ordinato in una lista ordinata (di numeri), insertion sort, eliminazione di un elemento da una lista, lista degli elementi di posto pari e di posto dispari, merge di due liste ordinate, mergesort, L2 prefisso di L1, L2 sottolista di L1, estrazione di una sottolista, numero di atomi in una multilista, lista degli atomi di una multilista, profondità massima di una multilista.
Venerdì, 27 maggio 2011
I teoremi di gerarchia spaziale e temporale (senza dimostrazioni). Le classi notevoli: LOGSPACE, P, NP, PSPACE, NPSPACE, EXPTIME. Relazioni tra le classi notevoli. La classe P come classe dei problemi computazionalmente trattabili. Esempi di problemi appartenenti a NP. Esempi di problemi appartenenti a PSPACE. Esempi di problemi fuori da EXPTIME e di problemi che richiedono un tempo di calcolo dell'ordine della funzione 'torre'.
Martedì, 31 maggio 2011
Funzioni LISP per le operazioni sugli insiemi (unione, intersezione, differenza simmetrica, prodotto cartesiano tra due e più insiemi). Soluzione di esercizi LISP di anni precedenti: diagonali di una matrice quadrata, verifica se una è matrice triangolare, rappresentazione di un ASF, cammino in un grafo, ciclo Hamiltoniano, colorazione di un grafo, colorazione di un grafo (altra versione).
Martedì, 07 giugno 2011
Esercizi LISP: dominating set, hitting set, set cover, pranzo di nozze, cavalieri della Tavola Rotonda, insieme dei delegati, vertex cover, clique. Torre di Hanoi: lista delle mosse. Esercizi su alberi binari: profondità, numero delle foglie, lista delle foglie, subtree.
Venerdì, 10 giugno 2011
Proprietà della classe NP. Riduzioni tra problemi. Problemi completi. NP-completezza. Esempi di problemi NP-completi. Il teorema di Cook (con accenno di dimostrazione).

Back