Informatica Teorica

Synthetic program:

 

I modelli dell`informatica. Automi (a stati finiti, a pila, Macchine di Turing); Grammatiche; Modelli nondeterministici; reti di Petrii; Uso della logica matematica per modellare sistemi descriverne proprieta`. Teoria della computazione. Potenza dei modelli di calcolo; Tesi di Church; Problemi indecidibili. La complessita` del calcolo. I modelli di calcolo e le relazioni tra le loro complessita` computazionali; Accelerazione lineare. Analisi di algoritmi fondamentali (ricerca, ordinamento, gestione di tabelle). Strutture dati e algoritmi: code, pile, tabelle di hash; strutture statiche e dinamiche; liste; strutture ad albero, a grafo e ad albero specializzate; strutture dati per la gestione di memoria di massa. Progettazione di algoritmi: backtracking, divide et impera. NP-completezza.