Università degli Studi di Perugia

Prova scritta con esercizi da svolgere (della durata di 120 minuti).

Da definire

- Linguaggi e grammatiche
Alfabeti e linguaggi. Espressioni regolari. Grammatiche di Chomsky.

- Modelli di calcolo. Linguaggi regolari: automi a stati finiti, proprietà dei linguaggi regolari. Linguaggi context-free; automi a pila, proprietà dei linguaggi context-free. Macchine di
Turing deterministiche, non deterministiche e multinastro. Composizione di macchine di Turing. La macchina di Turing Universale. Problemi indecidibili. Macchine a registri a costi logaritmici e a costi uniformi. Correlazione tra macchine di Turing e macchine a registri.

- Teoria della complessità. Classi di problemi. Complessità temporale e spaziale dei problemi. Classi notevoli di complessità. Karp-riducibilità. Problemi NP-hard e NP-completi.

- Tecniche algoritmiche per problemi NP-Hard. Ulteriori problemi NP-Hard e NP-completi. Algoritmi euristici. Algoritmi di approssimazione. Algoritmi di branch and bound.

- Applicazioni. Applicazioni delle espressioni regolari. Automi a stati finiti per ricerche testuali. Applicazioni delle grammatiche context-free (parser).

Linguaggi e grammatiche. Modelli di calcolo. Teoria della complessità. Tecniche algoritmiche per problemi NP-Hard. Applicazioni.

Lezioni ed esercitazioni frontali.

- Dispense a cura del docente.
- Giorgio Ausiello, Fabrizio D'Amore, Giorgio Gambosi, "Linguaggi, Modelli, Complessità" Ed. Franco Angeli.

Conoscenze di base sui linguaggi formali, sui modelli di calcolo, sulla complessità di algoritmi e problemi. Tecniche algoritmiche per la risoluzione di problemi computazionalmente difficili.

To be defined

martedì e giovedì: 14:30 - 17:30

Ricevimento studenti per possibili approfondimenti o chiarimenti

Facoltativa.

Facoltà di Ingegneria (sede di Perugia) - Via G. Duranti, 93