Algoritmi e Principi dell’Informatica

1. I modelli dell’informatica 

• Automi (a stati finiti, a pila, Macchine di Turing)
• Modelli nondeterministici (automi)
• Grammatiche
• Introduzione alla logica matematica 
• Uso della logica matematica per modellare sistemi e descriverne proprietà.

2. Teoria della computazione

• Potenza dei modelli di calcolo
• Tesi di Church
• Problemi indecidibili
• Tecniche di dimostrazione di indecidibilità 

3. Teoria della complessità

• Nozioni e notazioni fondamentali per l’analisi di complessità
• I modelli di calcolo e le relazioni tra le loro complessità computazionali
• Definizione di complessità spaziale e temporale per macchina di Turing deterministica
• Astrazioni e notazione asintotica
• Complessità di automi a stati finiti, a pila e macchina di Turing a nastro singolo
• Accelerazione lineare
• La macchina RAM
• Valutazione di complessità con criterio del costo costante
• Il criterio logaritmico
• Il teorema di correlazione polinomiale
• Gerarchie di complessità
• Cenni all’NP-completezza

4. Strutture dati e algoritmi fondamentali

• Algoritmi di ricerca e ordinamento
• Strutture dati elementari (pile, code, liste): rappresentazione, algoritmi di ricerca e gestione
• Tabelle hash: funzioni di hash, indirizzamento aperto.
• Alberi e loro gestione
• Alberi binari
• Algoritmi di visita e gestione
• Alberi rosso-neri
• Grafi, loro rappresentazione e gestione (cenni)