Presentare la teoria dei linguaggi e, parallelamente, la teoria degli automi. Introdurre i paradigmi della computabilità e della complessità. Al termine del corso gli studenti dovrebbero conoscere nuove metodologie formali, dovrebbero riuscire a rivisitare in modo critico, dal punto di vista del potere espressivo, metodologie già introdotte in modo pragmatico e dovrebbero essere in grado di classificare i problemi dal punto di vista delle risorse richieste per la loro risoluzione.
Curriculum
scheda docente materiale didattico
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.
Libri consigliati:
G. Ausiello, F. d'Amore, G. Gambosi, Linguaggi Modelli Complessità, Franco Angeli (i primi dieci capitoli sono distribuiti dagli autori gratuitamente)
M. Sipser, Introduction to the Theory of Computation, Thompson
Programma
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.
Testi Adottati
Slide fornite dal docente.Libri consigliati:
G. Ausiello, F. d'Amore, G. Gambosi, Linguaggi Modelli Complessità, Franco Angeli (i primi dieci capitoli sono distribuiti dagli autori gratuitamente)
M. Sipser, Introduction to the Theory of Computation, Thompson
Modalità Erogazione
Lezioni ed esercitazioni in aula.Modalità Valutazione
L'esame è costituito da una prova scritta di 3-4 ore. Per sola comodità di erogazione, tale prova è suddivisa in due parti. Valutazione in itinere: alternativamente all'esame ci si può avvalere della valutazione in itinere (prove intermedie). La valutazione in itinere non è mutualmente esclusiva rispetto a quella tradizionale, tuttavia, lo studente che si presenta all'esame in un regolare appello rifiuta implicitamente il voto della valutazione in itinere. Il risultato della valutazione in itinere, qualora accettato dallo studente, sarà verbalizzato esclusivamente nella prima sessione d'esame. Si prevedono 4/5 prove intermedie in tutto, distribuite nel primo semestre. Il programma di ciascuna prova comprende tutto il programma svolto dal primo giorno di lezione fino alla lezione immediatamente precedente la prova. Il voto finale si otterrà facendo la media dei voti delle singole prove dopo aver scartato il voto più basso (oppure, non considerando una prova a cui lo studente è stato assente). Nel periodo di emergenza COVID-19 l’esame di profitto sarà svolto secondo quanto previsto all’art.1 del Decreto Rettorale n°. 703 del 5 maggio 2020. scheda docente materiale didattico
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.
Libri consigliati:
G. Ausiello, F. d'Amore, G. Gambosi, Linguaggi Modelli Complessità, Franco Angeli (i primi dieci capitoli sono distribuiti dagli autori gratuitamente)
M. Sipser, Introduction to the Theory of Computation, Thompson
Mutuazione: 20810256 Automata, Languages and Computing in Ingegneria informatica LM-32 DI BATTISTA GIUSEPPE
Programma
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.
Testi Adottati
Slide fornite dal docente.Libri consigliati:
G. Ausiello, F. d'Amore, G. Gambosi, Linguaggi Modelli Complessità, Franco Angeli (i primi dieci capitoli sono distribuiti dagli autori gratuitamente)
M. Sipser, Introduction to the Theory of Computation, Thompson
Modalità Erogazione
Lezioni ed esercitazioni in aula.Modalità Valutazione
L'esame è costituito da una prova scritta di 3-4 ore. Per sola comodità di erogazione, tale prova è suddivisa in due parti. Valutazione in itinere: alternativamente all'esame ci si può avvalere della valutazione in itinere (prove intermedie). La valutazione in itinere non è mutualmente esclusiva rispetto a quella tradizionale, tuttavia, lo studente che si presenta all'esame in un regolare appello rifiuta implicitamente il voto della valutazione in itinere. Il risultato della valutazione in itinere, qualora accettato dallo studente, sarà verbalizzato esclusivamente nella prima sessione d'esame. Si prevedono 4/5 prove intermedie in tutto, distribuite nel primo semestre. Il programma di ciascuna prova comprende tutto il programma svolto dal primo giorno di lezione fino alla lezione immediatamente precedente la prova. Il voto finale si otterrà facendo la media dei voti delle singole prove dopo aver scartato il voto più basso (oppure, non considerando una prova a cui lo studente è stato assente). Nel periodo di emergenza COVID-19 l’esame di profitto sarà svolto secondo quanto previsto all’art.1 del Decreto Rettorale n°. 703 del 5 maggio 2020. scheda docente materiale didattico
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.
Libri consigliati:
G. Ausiello, F. d'Amore, G. Gambosi, Linguaggi Modelli Complessità, Franco Angeli (i primi dieci capitoli sono distribuiti dagli autori gratuitamente)
M. Sipser, Introduction to the Theory of Computation, Thompson
Mutuazione: 20810256 Automata, Languages and Computing in Ingegneria informatica LM-32 DI BATTISTA GIUSEPPE
Programma
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.
Testi Adottati
Slide fornite dal docente.Libri consigliati:
G. Ausiello, F. d'Amore, G. Gambosi, Linguaggi Modelli Complessità, Franco Angeli (i primi dieci capitoli sono distribuiti dagli autori gratuitamente)
M. Sipser, Introduction to the Theory of Computation, Thompson
Modalità Erogazione
Lezioni ed esercitazioni in aula.Modalità Valutazione
L'esame è costituito da una prova scritta di 3-4 ore. Per sola comodità di erogazione, tale prova è suddivisa in due parti. Valutazione in itinere: alternativamente all'esame ci si può avvalere della valutazione in itinere (prove intermedie). La valutazione in itinere non è mutualmente esclusiva rispetto a quella tradizionale, tuttavia, lo studente che si presenta all'esame in un regolare appello rifiuta implicitamente il voto della valutazione in itinere. Il risultato della valutazione in itinere, qualora accettato dallo studente, sarà verbalizzato esclusivamente nella prima sessione d'esame. Si prevedono 4/5 prove intermedie in tutto, distribuite nel primo semestre. Il programma di ciascuna prova comprende tutto il programma svolto dal primo giorno di lezione fino alla lezione immediatamente precedente la prova. Il voto finale si otterrà facendo la media dei voti delle singole prove dopo aver scartato il voto più basso (oppure, non considerando una prova a cui lo studente è stato assente). Nel periodo di emergenza COVID-19 l’esame di profitto sarà svolto secondo quanto previsto all’art.1 del Decreto Rettorale n°. 703 del 5 maggio 2020. scheda docente materiale didattico
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.
Libri consigliati:
G. Ausiello, F. d'Amore, G. Gambosi, Linguaggi Modelli Complessità, Franco Angeli (i primi dieci capitoli sono distribuiti dagli autori gratuitamente)
M. Sipser, Introduction to the Theory of Computation, Thompson
Mutuazione: 20810256 Automata, Languages and Computing in Ingegneria informatica LM-32 DI BATTISTA GIUSEPPE
Programma
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.
Testi Adottati
Slide fornite dal docente.Libri consigliati:
G. Ausiello, F. d'Amore, G. Gambosi, Linguaggi Modelli Complessità, Franco Angeli (i primi dieci capitoli sono distribuiti dagli autori gratuitamente)
M. Sipser, Introduction to the Theory of Computation, Thompson
Modalità Erogazione
Lezioni ed esercitazioni in aula.Modalità Valutazione
L'esame è costituito da una prova scritta di 3-4 ore. Per sola comodità di erogazione, tale prova è suddivisa in due parti. Valutazione in itinere: alternativamente all'esame ci si può avvalere della valutazione in itinere (prove intermedie). La valutazione in itinere non è mutualmente esclusiva rispetto a quella tradizionale, tuttavia, lo studente che si presenta all'esame in un regolare appello rifiuta implicitamente il voto della valutazione in itinere. Il risultato della valutazione in itinere, qualora accettato dallo studente, sarà verbalizzato esclusivamente nella prima sessione d'esame. Si prevedono 4/5 prove intermedie in tutto, distribuite nel primo semestre. Il programma di ciascuna prova comprende tutto il programma svolto dal primo giorno di lezione fino alla lezione immediatamente precedente la prova. Il voto finale si otterrà facendo la media dei voti delle singole prove dopo aver scartato il voto più basso (oppure, non considerando una prova a cui lo studente è stato assente). Nel periodo di emergenza COVID-19 l’esame di profitto sarà svolto secondo quanto previsto all’art.1 del Decreto Rettorale n°. 703 del 5 maggio 2020.