Informatica Teorica

 :: Informatica Teorica ::

Quanto ti è piaciuta la materia? * ** *** **** ***** N° voti: 63

Come ti è sembrato il corso? * ** *** **** ***** N° voti: 44

Docente: Gabriella Trucco

Esame

L'esame consiste in una prova scritta divisa in 3 parti:

• automi e linguaggi
• calcolabilità
• complessità

Per ogni parte ci sono 2 domande: una di teoria (dimostrazioni ecc.) e un esercizio. Per superare la prova è necessario raggiungere il 18 e aver risposto ad almeno una domanda per ogni parte.

Libro di testo

Introduction To The Theory Of Computation - Michael Sipser
(non cercatelo su torrent, perché anche se c'è è illegale scaricarlo, eh!)

Appunti e Dimostrazioni

• Automi a stati finiti (3 Marzo 2010)
• Nondeterminismo (17 Marzo 2010)
• Linguaggi non regolari (17 Marzo 2010)
• Linguaggi liberi dal contesto (17 Marzo 2010)
• Automi a pila (14 Aprile 2010)
• Macchina di Turing (21 Aprile 2010)
• Decidibilità (21 Aprile 2010)
• Riducibilità (28 Aprile 2010)
• Complessità nel tempo (5 Maggio 2010)
• Classe di complessità NP (12 Maggio 2010)
• NP-Completezza (12 Maggio 2010)
• Spazio-complessità (19 Maggio 2010)
• Teoremi della gerarchia (26 Maggio 2010)
• Complessità circuitale (26 Maggio 2010)

---

UniCrema | Secondo Semestre | Complementari o magistrale