Descrizione
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)
Recensioni
Ancora non ci sono recensioni.