2° anno · annuale
Automi e linguaggi formali, macchina di Turing, computabilità e complessità, analisi degli algoritmi e strategie di progetto: divide et impera, greedy, backtracking.
Questo corso è in revisione. Scrivimi e ti avviso quando è pronto.
Licenza d'uso personale: puoi stamparlo per te, non condividerlo. Leggi la licenza.
moduli
Ogni modulo copre circa 12 ore di lezione e si vende anche da solo, a 6,99 €. Ti servono 4 moduli o più? Costerebbero 27,96 €: il carrello passa al corso completo, che costa 24,99 €.
L'indice dettagliato dei moduli viene pubblicato con l'uscita del corso.
programma ufficiale 2026/27
Modelli di computazione per i linguaggi formali (automi a stati finiti, automi push-down, traduzione guidata dalla sintassi), macchina di Turing, limiti di computabilità e complessità; strategie di progettazione degli algoritmi e metodi per valutarne correttezza e prestazioni. Risultati attesi: basi teoriche dell'informatica, legame tra modelli di calcolo e classi di linguaggi, correttezza e prestazioni degli algoritmi, principali algoritmi e strutture dati.
Gli argomenti del programma ufficiale. La corrispondenza con i moduli si vede qui quando il corso esce.
| Argomento |
|---|
| Prerequisiti: logica deduttiva e dimostrazioni |
| Linguaggi regolari e automi a stati finiti |
| Linguaggi liberi dal contesto e automi push-down |
| Macchina di Turing; introduzione a computabilità e complessità |
| Dalla macchina di Turing alla macchina RAM |
| Analisi degli algoritmi: caso pessimo, caso medio, complessità ammortizzata |
| Strutture dati fondamentali |
| Strategie algoritmiche: forza bruta e backtracking, divide et impera, decrease-and-conquer, transform-and-conquer |
| Compromesso spazio-tempo |
| Algoritmi greedy |
| Traduzione guidata dalla sintassi |
Fonte: pagina ufficiale dell'insegnamento (codice 114590). Sintesi a cura di Mobius: fa fede la pagina ufficiale.
anteprima
Le pagine vere del corso arrivano qui con la sua uscita. Intanto, la struttura: un argomento per sezione, definizioni e teoremi evidenziati, formule leggibili.
pacchetti
Tutti i corsi del 2° anno, compresi gli esami a scelta di robotica.
lezioni
Se un argomento non torna, i primi 15 minuti sono gratis. Poi 18 €/h online o 22 €/h in presenza a Genova.
stesso semestre
Sistemi dinamici lineari: segnali, trasformata di Laplace, equazioni di stato, stabilità, raggiungibilità e osservabilità, funzioni di trasferimento e sistemi non lineari.
Programmazione a oggetti in C++20: classi e UML, ereditarietà e polimorfismo, libreria standard, eccezioni, smart pointer e progetto finale.