Informatica Teorica
Professore:
Giuseppe Di Battista
Email: gdb@dia.uniroma3.it
- Proprietà elementari dei linguaggi: operazioni su linguaggi, operatore
di Kleene, espressioni regolari, cardinalità dei linguaggi - Grammatiche formali: grammatiche di Chomsky, produzioni, riconoscimento di linguaggi.
- Linguaggi regolari: automi a stati finiti, relazioni tra automi e linguaggi regolari, pumping
lemma, chiusura dei linguaggi regolari, espressioni regolari e linguaggi regolari, decidibilità
e linguaggi regolari, teorema di Myhill-Nerode. - Linguaggi non contestuali.
- Cardinalità di insiemi infiniti.
- Macchine di Turing (MT) e Turing calcolabilità: funzionamento delle MT, MT multinastro,
MT non deterministiche, descrizione linearizzata delle MT, MT universale, il problema della fermata,
calcolabilità secondo Turing, teorema di Rice, linguaggi di tipo 0 e MT. - Macchine a registri (RAM): modelli di costo per RAM, modello a costi uniformi, modello a costi
logaritimici, RAM e MT. - Teoria della complessità: tipologie di problemi, problemi di decisione, complessità
e problemi di decisione su linguaggi, classi di complessità, relazioni
elementari tra classi di complessità, riducibilità, completezza, la classe NP, NP-completezza,
esempi di problemi NP-completi, la classe Pspazio, Pspazio-completezza, teorema di Savitch, le classi L e NL, NL-completezza.