Linguaggio "a salti" TACC
Linguaggio TACC: introduzione informale, esempi (somma, sottrazione, moltiplicazione, funzione identica, zero), macroistruzioni e problema del ricalco. Def. formale: sintassi (variabili, etichette, enunciati, istruzioni, programmi, lunghezza dei programmi). Semantica: stato, istantanea, istantanea iniziale, istantanea terminale.

Computazione
Computazione o calcolo (in senso stretto e in senso ampio); algoritmo; funzione parziale; funzione calcolata da un programma; funzione (parzialmente) calcolabile.

Composizione e ricorsione
Definizione formale di macroistruzione (di tipo "funzionale": W <- f(x1, ..., xn)), programma in forma normalizzata, progr. traslato; macroistruzioni di branching basate sul valore di verita' di un predicato calcolabile. Calcolabilita' della funzione composta; calcolabilita' della funzione ottenuta per ricorsione; la ricorsione puo' essere ottenuta tramite l'iterazione.

Classi di funzioni
Funzioni calcolabili e non calcolabili; funzioni primitivamente ricorsivamente chiuse (PRC); funzioni primitive ricorsive (PR); PR e' la piu' piccola classe PRC; le funzioni calcolabili sono PRC.

Goedelizzazione
Funzione (calcolabile) coppia di Cantor <,>, codifica di k-ple di lunghezza nota, codifica (goedelizzazione) di k-ple di lunghezza non nota a priori; funzioni l(), r() e ()i e loro calcolabilita'. Goedelizzazione di TACC: codifica di variabili, di etichette, di istruzioni, di programmi.

Teoremi fondamentali della calcolabilita'
Problema dell'arresto. Teorema dell'arresto. Teorema di universalita'. Interprete IACC. Programmi equivalenti. Algoritmi equivalenti. (Pseudo)Teorema di Rice.

Nozioni alternative di calcolabilita'
Linguaggio While (Backus-Naur Form) e calcolabilita'. Equivalenza tra TACC e While. Equivalenza tra istruzioni GOTO e strutture while. Teorema di Boehm-Jacopini. Funzioni ricorsive parziali. Equivalenza tra funzioni calcolabili e funzioni ricorsive parziali. Calcolabilita' secondo Turing e sua equivalenza con la precedente nozione di calcolabilita'.

Calcolabilita' su informazione non numerica
Calcolabilita' su caratteri, stringhe e simboli di un alfabeto discreto. Es: codifica ASCII. Esempi di funzioni (calcolabili) su stringhe, caratteri e numeri. Tesi di Church. Il test di Turing e la questione sulla calcolabilita' dell'Intelligenza. Calcolabilita' su informazione "multimediale" e ruolo della discretizzazione (digitalizzazione).

Complessita' di calcolo delle funzioni
Equivalenza teorica tra i paradigmi astratti di calcolo e i calcolatori digitali reali; problema dell'"effettiva" calcolabilita'. Ricerca di classi di funzioni facili o difficili da calcolare con risorse (tempo e spazio) finite. Definizioni di: spazio occupato da uno stato; spazio occupato da un programma su un certo input; complessita' in spazio di un programma; tempo impiegato su un certo input; complessita' in tempo. Complessita' polinomiale ed esponenzile. Teoremi che mostrano come la complessita' in tempo ponga un upper-bound alla complessita' in spazio. Tesi di Church estesa.

P, NP e NP-completezza
Linguaggio TACC non-deterministico, istruzione fork. Alberi di computazione e funzione calcolata. Equivalenza tra classi di funzioni calcolabili in TACC non-deterministico e TACC deterministico. Classi P e NP. Teo: P e' un sottoinsieme di NP. Riduzioni polinomiali. Funzioni polinomialmente equivalenti. Teoremi che mettono in relazione P ed NP sulla base delle riduzioni polinomiali tra coppie di funzioni. NP-completezza. Teo: se g() e' NP-completa e g() e' in P, allora P=NP. (Pseudo)Teorema di Cook.

Calcolabilita' e complessita' in pratica
Processo di astrazione. Abstract Data Type (ADT). Esempi (interi, reali, stringhe, insiemi, array, stack, liste linkate, liste circolari). Realizzazione di ADT: strutture dati e algoritmi. Esempio: il problema della ricerca (Search). Calcolo in pratica della complessita' in tempo di un algoritmo. Algoritmo di ricerca dicotomica. I 4 livelli del processo di astrazione: (i) ADT, (ii) strutture dati e algoritmi, (iii) implementazione, (iv) rappresentazione interna. Metodologie di sviluppo top-down e bottom-up.

Strutture di dati e algoritmi
Ricerca dicotomica: formulazione ricorsiva e sua complessita' in tempo. Strategia "divide et impera". Algoritmo Merge-Sort e sua complessita' in tempo. Prontuario pratico di calcolo della complessita' (operazioni atomiche, funzioni, sequenze, iterazioni, ricorsioni). Alberi di ricerca binaria (BST). Visite in-order, pre-order e post-order. Algoritmo InOrderTreeWalk() e sua complessita'. Algoritmo TreeMin() e sua complessita'. Algoritmo TreeSearch() e sua complessita'. Inserimenti di nuovi elementi: TreeInsert(). Hash tables. Alberi binari (binary search trees). Red-Black trees. B-trees. Algortimi sui grafi: rappresentazione dei grafi, visita sui grafi ed alberi, problema del minimum spanning tree (algortimo di Kruskal e Prim), problema del cammino minimo da una sorgente (algortimo di Dijkstra), problema del cammino minimo per ogni coppia di nodi (algoritmo di Floyd-Warshall). Programmazione Dinamica. Algoritmi greedy

Linguaggi formali e traduttori
Alfabeti e libguaggi; operazioni su linguaggi; espressioni regolari, linguaggi regolari; grammatiche; riconoscitori, automi a stati finiti; linguaggi context-free; automi a pila; analisi ascendente e discendente. Principi di traduzione sintattica.

Edmondo Trentin (Tel. 0577-234636)