Automata, Languages and Computing

Il programma dell'insegnamento di Automata, Languages, and Computing è il seguente:
•    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: automi a pila non deterministici, relazioni tra automi e linguaggi CF, pumping lemma, chiusura e decidibilità, ambiguità.
•    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.
•   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 PSPACE. Complessità dei problemi di Machine Learning.

Non ci sono pre-requisiti specifici.

Slide fornite dal docente.

Libri consigliato:

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

Lezioni ed esercitazioni in aula.

Lezione in aula.

L'esame è costituito da una prova scritta con 8 domande e della durata di due ore.

Gli studenti che vorranno, potranno avvalersi del seguente ulteriore meccanismo di valutazione:
- Durante le lezioni verranno proposti esercizi da fare su moodle (domande in itinere) in tempo reale.
- Ciò potrà avvenire durante tutte le lezioni.
- La valutazione delle domande sarà sì/no.
- Coloro che avranno superato almeno l'ottanta per cento delle domande in itinere potranno fare, solo al primo appello, un compito di 6 domande, con tre quarti del tempo e conseguendo il massimo punteggio (7,5/30) sulle due domande da non fare.
- Coloro che avranno superato almeno il quaranta per cento delle domande in itinere potranno fare, solo al primo appello, un compito di 7 domande, con sette ottavi del tempo e conseguendo il massimo punteggio (3,75/30) sulla domanda da non fare.
- Potranno svolgere le domande in itinere solo coloro che saranno presenti a lezione.
- Per rilevare i presenti, in ogni lezione ci sarà un elenco informatizzato nel quale ciascuno potrà segnalare la propria presenza.
- L’elenco dei presenti non sarà usato in nessun altro modo.
- Per svolgere le domande in itinere sarà necessario portare a lezione almeno uno smartphone o un laptop o un tablet.

Il programma dell'insegnamento di Automata, Languages, and Computing è il seguente:
•    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: automi a pila non deterministici, relazioni tra automi e linguaggi CF, pumping lemma, chiusura e decidibilità, ambiguità.
•    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.
•   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 PSPACE. Complessità dei problemi di Machine Learning.

Non ci sono pre-requisiti specifici.

Slide fornite dal docente.

Libri consigliato:

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

Lezioni ed esercitazioni in aula.

Lezione in aula.

L'esame è costituito da una prova scritta con 8 domande e della durata di due ore.

Gli studenti che vorranno, potranno avvalersi del seguente ulteriore meccanismo di valutazione:
- Durante le lezioni verranno proposti esercizi da fare su moodle (domande in itinere) in tempo reale.
- Ciò potrà avvenire durante tutte le lezioni.
- La valutazione delle domande sarà sì/no.
- Coloro che avranno superato almeno l'ottanta per cento delle domande in itinere potranno fare, solo al primo appello, un compito di 6 domande, con tre quarti del tempo e conseguendo il massimo punteggio (7,5/30) sulle due domande da non fare.
- Coloro che avranno superato almeno il quaranta per cento delle domande in itinere potranno fare, solo al primo appello, un compito di 7 domande, con sette ottavi del tempo e conseguendo il massimo punteggio (3,75/30) sulla domanda da non fare.
- Potranno svolgere le domande in itinere solo coloro che saranno presenti a lezione.
- Per rilevare i presenti, in ogni lezione ci sarà un elenco informatizzato nel quale ciascuno potrà segnalare la propria presenza.
- L’elenco dei presenti non sarà usato in nessun altro modo.
- Per svolgere le domande in itinere sarà necessario portare a lezione almeno uno smartphone o un laptop o un tablet.

Il programma dell'insegnamento di Automata, Languages, and Computing è il seguente:
•    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: automi a pila non deterministici, relazioni tra automi e linguaggi CF, pumping lemma, chiusura e decidibilità, ambiguità.
•    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.
•   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 PSPACE. Complessità dei problemi di Machine Learning.

Non ci sono pre-requisiti specifici.

Slide fornite dal docente.

Libri consigliato:

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

Lezioni ed esercitazioni in aula.

Lezione in aula.

L'esame è costituito da una prova scritta con 8 domande e della durata di due ore.

Gli studenti che vorranno, potranno avvalersi del seguente ulteriore meccanismo di valutazione:
- Durante le lezioni verranno proposti esercizi da fare su moodle (domande in itinere) in tempo reale.
- Ciò potrà avvenire durante tutte le lezioni.
- La valutazione delle domande sarà sì/no.
- Coloro che avranno superato almeno l'ottanta per cento delle domande in itinere potranno fare, solo al primo appello, un compito di 6 domande, con tre quarti del tempo e conseguendo il massimo punteggio (7,5/30) sulle due domande da non fare.
- Coloro che avranno superato almeno il quaranta per cento delle domande in itinere potranno fare, solo al primo appello, un compito di 7 domande, con sette ottavi del tempo e conseguendo il massimo punteggio (3,75/30) sulla domanda da non fare.
- Potranno svolgere le domande in itinere solo coloro che saranno presenti a lezione.
- Per rilevare i presenti, in ogni lezione ci sarà un elenco informatizzato nel quale ciascuno potrà segnalare la propria presenza.
- L’elenco dei presenti non sarà usato in nessun altro modo.
- Per svolgere le domande in itinere sarà necessario portare a lezione almeno uno smartphone o un laptop o un tablet.

Il programma dell'insegnamento di Automata, Languages, and Computing è il seguente:
•    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: automi a pila non deterministici, relazioni tra automi e linguaggi CF, pumping lemma, chiusura e decidibilità, ambiguità.
•    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.
•   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 PSPACE. Complessità dei problemi di Machine Learning.

Non ci sono pre-requisiti specifici.

Slide fornite dal docente.

Libri consigliato:

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

Lezioni ed esercitazioni in aula.

Lezione in aula.

L'esame è costituito da una prova scritta con 8 domande e della durata di due ore.

Gli studenti che vorranno, potranno avvalersi del seguente ulteriore meccanismo di valutazione:
- Durante le lezioni verranno proposti esercizi da fare su moodle (domande in itinere) in tempo reale.
- Ciò potrà avvenire durante tutte le lezioni.
- La valutazione delle domande sarà sì/no.
- Coloro che avranno superato almeno l'ottanta per cento delle domande in itinere potranno fare, solo al primo appello, un compito di 6 domande, con tre quarti del tempo e conseguendo il massimo punteggio (7,5/30) sulle due domande da non fare.
- Coloro che avranno superato almeno il quaranta per cento delle domande in itinere potranno fare, solo al primo appello, un compito di 7 domande, con sette ottavi del tempo e conseguendo il massimo punteggio (3,75/30) sulla domanda da non fare.
- Potranno svolgere le domande in itinere solo coloro che saranno presenti a lezione.
- Per rilevare i presenti, in ogni lezione ci sarà un elenco informatizzato nel quale ciascuno potrà segnalare la propria presenza.
- L’elenco dei presenti non sarà usato in nessun altro modo.
- Per svolgere le domande in itinere sarà necessario portare a lezione almeno uno smartphone o un laptop o un tablet.

Il programma dell'insegnamento di Automata, Languages, and Computing è il seguente:
•    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: automi a pila non deterministici, relazioni tra automi e linguaggi CF, pumping lemma, chiusura e decidibilità, ambiguità.
•    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.
•   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 PSPACE. Complessità dei problemi di Machine Learning.

Non ci sono pre-requisiti specifici.

Slide fornite dal docente.

Libri consigliato:

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

Lezioni ed esercitazioni in aula.

Lezione in aula.

L'esame è costituito da una prova scritta con 8 domande e della durata di due ore.

Gli studenti che vorranno, potranno avvalersi del seguente ulteriore meccanismo di valutazione:
- Durante le lezioni verranno proposti esercizi da fare su moodle (domande in itinere) in tempo reale.
- Ciò potrà avvenire durante tutte le lezioni.
- La valutazione delle domande sarà sì/no.
- Coloro che avranno superato almeno l'ottanta per cento delle domande in itinere potranno fare, solo al primo appello, un compito di 6 domande, con tre quarti del tempo e conseguendo il massimo punteggio (7,5/30) sulle due domande da non fare.
- Coloro che avranno superato almeno il quaranta per cento delle domande in itinere potranno fare, solo al primo appello, un compito di 7 domande, con sette ottavi del tempo e conseguendo il massimo punteggio (3,75/30) sulla domanda da non fare.
- Potranno svolgere le domande in itinere solo coloro che saranno presenti a lezione.
- Per rilevare i presenti, in ogni lezione ci sarà un elenco informatizzato nel quale ciascuno potrà segnalare la propria presenza.
- L’elenco dei presenti non sarà usato in nessun altro modo.
- Per svolgere le domande in itinere sarà necessario portare a lezione almeno uno smartphone o un laptop o un tablet.