Tags:
create new tag
view all tags

Automi, CalcolabilitÓ e ComplessitÓ
a.a. 2018/2019

Prof. EMANUELA FACHINI
STUDIO: D.to Scienze dell'Informazione Via Salaria,113 - 00198 ROMA
TEL: 0649918314.
E-MAIL: fachini[AT]di.uniroma1.it
ORARIO DI RICEVIMENTO: LUNED╠ ore 14,00-16,00 o su appuntamento.


Diario delle lezioni dell'a.a. 2018/2019

Diario delle lezioni dell'a.a. 2017/2018 Diario delle lezioni di CalcolabilitÓ e ComplessitÓ dell'a.a. 2016-2017 Diario delle lezioni dell'a.a. 2015-2016


Avvisi per gli studenti

Presentazione del corso

Informazioni generali: lezioni, libro di testo, esercizi proposti nelle sedute di esami, valutazioni degli esami appelli a.a. 2016/2017.

Obiettivi e risultati attesi

Programma del corso

Diario delle lezioni


Avvisi

Appello settembre 2018

Qui trovate il risultato della valutazione della prova scritta MATACCsett18.pdf. Tutti gli studenti sono invitati a venire a visionare il loro elaborato lunedý, dalle 10 alle 12 o dalle 14 alle 16. Solo gli studenti che sono risultati sufficienti e che desiderano migliorare il voto potranno affrontare una prova orale, gli studenti insufficienti presentano gravi lacune e sono quindi i primi a doversi presentare lunedý per consigli su come migliorare la loro preparazione. Chi fosse soddisfatto del voto e non ritenesse necessario visionare il compito pu˛ anche semplicemente comunicarmi per email che accetta il voto.


Presentazione del corso L'insegnamento prevede lo studio dei risultati fondamentali di tre teorie: la teoria dei linguaggi formali o degli automi, la teoria della calcolabilitÓ e quella della complessitÓ. Si vedranno i risultati essenziali sugli automi a stati finiti e sugli automi a pila, modelli limitati rispetto alle macchine di Turing. La teoria della calcolabilitÓ riguarda i risultati raggiunti a proposito di una fondamentale domanda: quali sono le capacitÓ fondamentali e quali i limiti di un calcolatore?
Negli anni '30 gli ormai famosi risultati negativi di Church e Turing dimostrarono l'esistenza di questi limiti: alcuni problemi non possono essere risolti con un calcolatore. Questo ha dato origine alla teoria della calcolabitÓche essenzialmente studia cosa rende un problema tanto difficile da non poter essere risolto con un calcolatore. Lo studio ha prodotto una casistica di problemi e di tecniche per dimostrare la possibilitÓ o non possibilitÓ di soluzione algoritmica, ma anche vari modelli teorici di calcolo, che spesso si sono rivelati utili anche nella progettazione di nuovi calcolatori.
Alcuni problemi , comunque, pur essendo teoricamente affrontabili con un calcolatore, non lo sono in pratica (nessuno ha abbastanza tempo per aspettare la risposta). La teoria della complessitÓ affronta la questione: che cosa rende cosý difficili da risolvere alcuni problemi e facili altri? Uno dei principali risultati di questa teoria consiste in uno schema di classificazione dei problemi basato sulla loro difficoltÓ computazionale. Il principale problema aperto di questa teoria Ŕ anche il principale problema aperto dell'informatica (un problema da un milione di dollari).



Obiettivi corso

Al termine del corso gli studenti conosceranno i principali metodi e risultati della teoria degli Automi, della Teoria della CalcolabilitÓ e della ComplessitÓ e sapranno applicarli per individuare la complessitÓ di problemi in diversi campi. In particolare sapranno
1.giustificare l'esistenza di problemi privi di soluzioni algoritmiche o intrattabili.
2.descrivere esempi concreti di problemi indecidibili, non dimostratamente intrattabili o intrattabili.
3. la definizione formale dei diversi modelli, deterministici e non, di macchina introdotti
4. le definizioni di complessitÓ di tempo e spazio per macchine di Turing e quella di riducibilitÓ polinomiale
5. il senso e l'importanza della questione "P=NP?"

Gli studenti saranno in grado di
1. costruire DFA, automi a pila e Macchine di Turing deterministiche e non, da una specifica (formale o informale)
2. ridurre un problema ad un altro per dimostrarne la decidibilitÓ o l'indecidibilitÓ.
3. usare la riducibilitÓ polinomiale per dimostrare la NP-completezza di problemi.
4. collocare problemi nell'opportuna classe di complessitÓ di spazio o tempo.



Programma del corso

Automi e Linguaggi

Linguaggi regolari e automi a stati finiti. Linguaggi acontestuali e automi a pila

Teoria della CalcolabitÓ

Macchine di Turing.Tesi di Church-Turing. Problemi indecidibili: il problema della fermata La riduzione tra problemi: uno strumento per dimostrarne l'indecibilitÓ o la decidibilitÓ. Esempi di problemi decidibili e indecidibili.

Teoria della ComplessitÓ

ComplessitÓ di tempo e spazio per le macchine di Turing.Classi di complessitÓ.Problemi trattabili e problemi non provatamente intrattabili: le classi P e NP. Riduzioni polinomiali e NP-completezza. Teorema di Cook- Levin e altri problemi NP-completi. il teorema di Savitch

Qui trovate il programma dettagliato dell' a.a. 17/18 ProgrammaACC17-18.pdf. Qui quelli degli anni accademici precedenti 2014/2015, 2015/2016 e 2016/2017: ProgrammaCC1516.pdf, ProgrammaACC1617.pdf.


Informazioni generali.

Lezioni

Le lezioni si svolgeranno nell'aula 2 il mercoledý e il venerdý dalle 10,30 alle 13, in via Castro Laurenziano.

Prerequisiti
E' indispensabile la conoscenza della notazione asintotica e il suo uso nell'analisi degli algoritmi. Bisogna aver una buona conoscenza di algoritmi fondamentali (in particolare su grafi) e di tecniche di analisi della complessitÓ degli algoritmi. E' utile conoscere le principali tecniche di progettazione di algoritmi (ricerca esaustiva, programmazione dinamica).



Materiale per il corso
I link elencati nella pagina "Link utili" portano alle biografie o alle pagine web di alcuni dei protagonisti delle teorie oggetto del corso, forniscono quindi una prospettiva storica dei risultati ma anche materia di riflessione su problemi esistenziali di varia natura.

I libri

Il corso si baserÓ sul testo di
M. Sipser, Introduction to the Theory of Computation, PWS Publishing Company, II edizione (ma anche la prima va bene). E' disponibile la traduzione in italiano: Introduzione alla teoria della computazione. Apogeo Edizioni.

Il testo seguente Ŕ di utile consultazione:

[2] , Motwani R., Ullman J.D., Automi, linguaggi e calcolabilitÓ, I edizione italiana,Addison-Wesley,2003

Chi volesse leggere l'articolo originale di Turing pu˛ scaricarlo qui: Turing.pdf.

Testi esercizi proposti negli appelli di esame. ACC20Sett18.pdf, ACC10Gen18.pdf, ACC6Giu18.pdf. ACC16apr18.pdf. TestoACC4Sett17.pdf. ACCGiu17.pdf. E le soluzioni: SolACCGiu17.pdf AppStrACCApr17.pdf. _ACC13Gen17.pdf. SolPIACCNov16.pdf. ACC7Nov16.pdf, SolACC7Nov16.pdf. ACC8Giu16.pdf ACC1lu16.pdf Es4CC2015.pdf



Valutazione degli studenti

L'esame consiste di una prova scritta. Per il superamento dell'esame per tutti gli studenti che seguono il corso sono previste prove durante lo svolgimento delle lezioni e durante la settimana degli esoneri. Le prove consistono in domande di collegamento o approfondimento degli argomenti studiati o in esercizi. Chi supera queste prove pu˛ essere esonerato in tutto o in parte dall'esame. Comunque ogni studente Ŕ tenuto a presentarsi all'esame dopo aver verificato che la propria preparazione Ŕ adeguata. Lo studente che ha raggiunto la sufficienza pu˛ migliorare il voto presentandosi all'appello successivo e svolgendo l'esercizio o gli esercizi su cui Ŕ andato peggio.
Il voto finale sarÓ calcolato tenendo conto dei punteggi conseguiti nelle prove e, per coloro che seguono il corso, anche del grado di partecipazione attiva allo stesso.

Gli studenti che si presentano all'esame, partire dall'appello di gennaio, e ottengono una valutazione inferiore a 12/30 dimostrano non solo di non essersi preparati ma anche di non essere in grado di valutare la propria preparazione e quindi non saranno ammessi all'esame nell'appello successivo.


DIARIO DELLE LEZIONI 2018/2019


mercoledý 26/9/2018

2 ore;Introduzione al corso.

DIARIO DELLE LEZIONI 2017/2018

venerdý 22/12/2017 2 ore; Le classi di spazio: PSPACE, L e NL. InPoltreNP.pdf
12,15 - 13 V prova in aula II gruppo Es22Dic17.pdf, Riduzione22Dic17.pdf.

mercoledý 20/12/2017 2 ore; La classe coNP, FACTOR, l'isomorfismo tra grafi e i problemi intermedi. coNP.pdf.
12,15 - 13 V prova in aula I gruppo. Es20Dic17.pdf, RidEs20Dic17.pdf.

venerdý 15/12/2017 3 ore; Ancora esempi di problemi NP completi e Teorema di Savitch. Savitch.pdf, NPcompleti2.pdf.

mercoledý 13/12/2017 3 ore; Teorema di Cook-Levin. NPcomplCook.pdf NPcompleti_.pdf

venerdý 8/12/2017 3 ore; vacanza accademica

mercoledý 6/12/2017 3 ore; Il verificatore: nuova definizione di NP, Verificatore.pdf.

venerdý 1/12/2017 2 ore; classi di complessitÓ, ClassiCompl.pdf.
12,15 - 13 IV prova in aula II gruppo, EsACC4Dic.pdf.

mercoledý 29/11/2017 2 ore; Riduzioni: definizione ed esempi. Riduzioni.pdf, RideIndecidibilit.pdf.
12,15 - 13 IV prova in aula I gruppo, EsACC29Nov.pdf.

venerdý 24/11/2017 3 ore; Il problema dell'accettazione e della fermata per macchine di Turing: loro indecidibilitÓ e loro Turing riconoscibilitÓ. Macchina di Turing universale, IndFermataTM.pdf, TMUniversale.pdf. Qualche esercizio: NumerabilitTuringCalc.pdf. Due problemi decidibili per CFG: DecChiusCFL.pdf.

mercoledý 22/11/2017 3 ore; Macchine di Turing non deterministiche, TMNonDet.pdf. Esistenza di problemi non Turing riconoscibili, NonDecEsiste.pdf.

venerdý 17/11/2017 2 ore; Macchine di Turing a k nastri e loro equivalenza con le macchine di Turing a un solo nastro, TMKnastri.pdf.
12,15 - 13,00: III prova in aula per il secondo gruppo, EsACC17Nov.pdf.

mercoledý 15/11/2017 2 ore; Macchine di Turing: definizione ed esempi, TMDef.pdf.
12,15 - 13,00: III prova in aula per il primo gruppo, EsACC15Nov.pdf.

venerdý 10/11/2017 3 ore; La lezione non si terrÓ per un concomitante e irrinunciabile impegno del docente.

mercoledý 8/11/2017 2 ore; AmbiguitÓ e CFG, AmbiguitCFG.pdf. PDA e CFG, CFGePDA.pdf.
12,15 - 13,00: II prova in aula per il primo gruppo, Es811.pdf.

venerdý 3/11/2017 2 ore; CFG: introduzione ed esempi, CFG.pdf.
12,15 - 13,00: II prova in aula per il secondo gruppo, Es311.pdf.

mercoledý 1/11/2017 3 ore; lezione non tenuta perchÚ giorno festivo

venerdý 27/10/2017 3 ore; Esercizi di costruzione di NFA, PDA e problemi di decisione per i DFA. EserciziNFAePDA_.pdf.

mercoledý 25/10/2017 3 ore; Automi a pila: definizioni ed esempi, PDA.pdf. Esercizi sul pumping lemma.

venerdý 20/10/2017 3 ore; Espressioni regolari e loro equivalenza con i DFA (teorema di Kleene), EspressioniRegolari.pdf. Esercizi sul pumping lemma, EsPumping.pdf.
13,15 - 13,45: I prova in aula per il secondo gruppo, i testi: Es2010.pdf.

mercoledý 18/10/2017 3 ore; Chiusura rispetto a concatenazione e stella di Kleene Linguaggi_e_operazioni.pdf, Pumping lemma per i regolari PumpingLemma.pdf. Soluzioni esercizi su DFA,NFA e proprietÓ di chiusura proposti nella lezione precedente.
13,15 - 13,45: I prova in aula per il primo gruppo, i testi: EsEsame18Ott17.pdf.

venerdý 13/10/2017 3 ore; NFA: gli automi finiti non deterministici. NFAdefDimEq.pdf, EserciziAutomi.pdf.

mercoledý 11/10/2017 3 ore;Il problema del vuoto per DFA, l'algoritmo per riduzione a PATH e quello basato sulla ricerca esaustiva dell'insieme delle parole sull'alfabeto di input di lunghezza minore al numero degli stati. Chiusura della classe dei linguaggi accettati da un DFA rispetto a unione, intersezione e complemento. PrimeChiusure.pdf

venerdý 6/10/2017 3 ore; Automi a stati finiti, Deterministic Finite Automata, prime definizioni ed esempi. DFA1Intr.pdf.

mercoledý 4/10/2017 3 ore; Introduzione al corso: breve descrizione contenuto del programma, problemi di decisione e linguaggi, problemi di decisione e problemi di ricerca. IntrACC17.pdf.


DIARIO DELLE LEZIONI 2016/2017

mercoledý 21/12/2016 4 ore; Esercitazione riassuntiva sulla seconda parte del programma. EsAula21dic2016.pdf.

giovedý 15/12/2016 2 ore; dalle 9 alle 11, nell'orario di Linguaggi e Compilatori: Teorema di Savicth. Savitch.pdf, qualche incursione dentro P e oltre NP, InPoltreNP.pdf.

mercoledý 14/12/2016 3 ore; Problemi NP completi. NPcompleti_.pdf

venerdý 9/12/2016 2 ore; lezione annullata e anticipata al 6 dicembre.

mercoledý 7/12/2016 3 ore; Teorema di Cook. NP-complCook.pdf, Esercizi di uso delle riduzioni in prove di indecidibilitÓ e sulla Turing riconoscibilitÓ. EserciziDecTuringRic.pdf

martedý 6/12/2016 3 ore; dalle ore 9 alle ore 10,45. ll verificatore. Nuova definizione di NP, Verificatore.pdf

venerdý 2/12/2016 2 ore; Classi di complessitÓ, definizioni ed esempi, ClassiCompl.pdf.

mercoledý 30/11/2016 3 ore; Riduzioni: uno strumento per dimostrare decidibilitÓ o indecidibilitÓ dei problemi. Riduzioni.pdf, TMUniversale.pdf, RideIndecidibilit.pdf.

venerdý 25/11/2016 2 ore; poichÚ lo sciopero indetto rende difficile per gli studenti pendolari e romani il raggiungimento della sede universitaria la lezione Ŕ annullata e sarÓ recuperata il 6 dicembre, durante l'orario dell'insegnamento della prof.ssa Finocchi.

mercoledý 23/11/2016 3 ore; Esistenza di problemi indecidibili. NonDecesiste.pdf. Il problema della fermata. IndFermataTM.pdf.

venerdý 18/11/2016 2 ore;Macchine di Turing non deterministiche e loro equivalenza con le deterministiche. TMNonDet.pdf

mercoledý 16/11/2016 3 ore; Macchine di Turing a k nastri e loro equivalenza con le macchine di Turing a un solo nastro. TMKnastri.pdf

venerdý 11/11/2016 2 ore;Macchine di Turing: prime definizioni ed esempi. TMDef.pdf.

mercoledý 9/11/2016 3 ore; Prova intermedia. PIACCNov16.pdf:.

venerdý 4/11/2016 2 ore;Esercizi riassuntivi programma svolto EsAula.pdf.

mercoledý 2/11/2016 2 ore; ProprietÓ di chiusura e problemi di decisione per i CFL. ChiusureCFL.pdf

venerdý 28/10/2016 2 ore; lezione annullata

lunedý 24/10/2016 3 ore; Equivalenza CFG e PDA, AmbiguitÓ e forme normali per CFG. Problemi di decisione per CFG. CFGePDA.pdf, AmbiguitCFG.pdf, algCYK.pdf.

venerdý 21/10/2016 2 ore; Grammatiche context-free, prime proprietÓ. CFGIntr.pdf

mercoledý 19/10/2016 3 ore; Automi a pila, definizioni ed esempi. Prime proprietÓ. PDA.pdf.

venerdý 14/10/2016 2 ore; espressioni regolari ed equivalenza con i DFA. EspressioniRegolari.pdf.

mercoledý 12/10/2016 3 ore; Conclusione NFA e pumping lemma per i regolari ed esercizi in aula. EserciziNFAPumping.pdf Il file Ŕ stato corretto, c'era un errore nel DFA prodotto.

venerdý 7/10/2016 2 ore;Equivalenza tra DFA e NFA, NFA.pdf, Pumping Lemma per i regolari PumpingLemma.pdf.

mercoledý 5/10/2016 3 ore;Linguaggi e operazioni su di essi. Automi a stata finiti non deterministici Linguaggi_e_operazioni.pdf, NFA.pdf.

venerdý 30/09/2016 2 ore;Introduzione alla teoria degli automi. DFA1Intr.pdf: il file Ŕ stato aggiornato.

mercoledý 26/09/2016 3 ore; Introduzione al corso. IntrACC16.pdf


DIARIO DELLE LEZIONI 2015/2016

venerdý 18/12/2015 2 ore; Esercitazione sui contenuti della seconda parte del corso, EsACCDic2015.pdf.

mercoledý16/12/2015 2 ore;teorema di Savitch. PSPACE e PSPACE-completezza, Savitch.pdf, PSPACE-completeness.pdf.

venerdý 11/12/2015 2 ore; Esempi di problemi NPcompleti. NPcompleti.pdf.

mercoledý 9/12/2015 2 ore; 12,30 - 13,45. Teorema di Cook Levin. Cook.pdf

mercoledý 9/12/2015 2 ore; 10,45 - 12,15. Verificatore polinomiale ed esempi di problemi in NP. DefCompl2.pdf

venerdý 4/12/2015 2 ore; lezione annullata per evento in dipartimento "incontro con le aziende"

mercoledý 2/12/2015 2 ore; ComplessitÓ: prime definizioni DefComp.pdf

venerdý 27/11/2015 2 ore; lezione annullata.

mercoledý 25/11/2015 2 ore; Riduzioni e loro utilizzo per costruire algoritmi o dimostrare l'indecidibilitÓ. Riduzioni.pdf, Rid_Indecidibilita.pdf.

venerdý 20/11/2015 2 ore; Macchina universale, Esistenza problemi non Turing riconoscibili e proprietÓ di chiusura dei linguaggi Turing riconoscibili, FermataTM.pdf.

mercoledý 18/11/2015 2 ore; Esistenza di problemi indecidibli. EsistenzaNonDec.pdf, IndFermataTM.pdf

venerdý 13/11/2015 2 ore; TM a pi¨ nastri e non deterministiche TMPiuNastri.pdf, TM3NonDet.pdf

mercoledý 11/11/2015 2 ore; Macchine di Turing: definizione ed esempi, TMDef.pdf.

venerdý 6/11/2015 2 ore; Prova intermedia. Qui i testi: ProvaIntermediaACC2015.pdf

mercoledý 4/11/2015 2 ore; Esercizi sul programma svolto, EseAula.pdf.

venerdý 30/10/2015 2 ore; CFG e PDA. AmbiguitÓ e proprietÓ di chiusura CFGePDA.pdf, AmbiguitaCFG.pdf, IlComplemento.pdf.

mercoledý 28/10/2015 2 ore; lezione non tenuta per malattia

venerdý 21/10/2015 2 ore; Grammatiche acontestuali, CFGIntr.pdf.

mercoledý 20/10/2015 2 ore; Automi a pila PDA.pdf

venerdý 16/10/2015 2 ore; lezione non tenuta per evento in CittÓ universitaria.

mercoledý 14/10/2015 2 ore; Espressioni regolari ed equivalenza DFA, EspressioniRegolari.pdf.

venerdý 9/10/2015 2 ore; Il pumping lemma. Esercizi di costruzione NFA e problemi di decisione per DFA PumpingLemma.pdf

mercoledý 7/10/2015 2 ore; Automi nondeterministici, equivalenza con DFA e chiusura classe dei regolari rispetto a concatenazione e stella di Kleene, NFA.pdf.

venerdý 2/10/2015 2 ore; Le principali operazioni sui linguaggi e la chiusura della classe dei linguaggi accettati da unDFA rispetto a queste operazioni. Linguaggi_e_operazioni.pdf

mercoledý 30/9/2015 2 ore; Definizioni formali e prime proprietÓ DFA DFA1Intr.pdf. Ho aggiunto l'automa dell'esercizio e il teorema dimostrato a lezione

venerdý 25/9/2015 2 ore; conclusione descrizione degli argomenti che verranno trattati durante il corso. Prime definizioni: linguaggi e automi a stati finiti.

mercoledý 23/9/2015 2 ore; Introduzione al corso con breve descrizione degli argomenti che verranno trattati, IntCCII.pdf.


CalcolabilitÓ e ComplessitÓ a.a. 2014-2015

Programma del corso

Diario delle lezioni


Programmi definitivi dell'insegnamento di CalcolabilitÓ e ComplessitÓ

Qui trovate il programma definitivo di CC per l'a.a. 13/14: ProgrammaCC13:14.pdf.

Qui quello probabilmente definitivo per l'a.a. 14/15: ProgrammaCC14:15.pdf, e quello dell'a.a. 16/17 ProgrammaACC.pdf.


DIARIO DELLE LEZIONI 2014/2015

martedý 16/12/2014

2 ore; La classe dei giochi: PSPACE-completi. PSPACE.pdf

giovedý 11/12/2014

2 ore; Relazione tra problemi di ricerca e di ottimizzazione e i relativi problemi di decisione. Teorema di Savithc. DECvsRicOtt.pdf, Savitch.pdf

martedý 9/12/2014

2 ore; conclusione rassegna problemi NP-completi.

giovedý 4/12/2014

2 ore; NP-completezza, SAT e altri problemi NP-completi. Cook.pdf, NP-completi.pdf

martedý 2/12/2014

2 ore;Definizione alternativa di NP: il verificatore, definizioni ed esempi. coNP e sua relazione con NP, Verificatore.pdf.

giovedý 27/11/2014

2 ore; Definizioni di complessitÓ di tempo e di spazio e loro relazioni. Classi di complessitÓ. DefComp.pdf.

martedý 25/11/2014

2 ore; riduzioni definizioni ed esempi, Riduzioni.pdf, RideIndecidibilita.pdf.

giovedý 20/11/2014

2 ore; Esempi di problemi indecidibili: appartenenza e fermata per TM, esistenza problemi non Turing riconoscibili, FermataTM.pdf.

martedý 18/11/2014

2 ore; Esistenza di problemi indecidibili, EsistenzaNonDec.pdf.

giovedý 13/11/2014

2 ore; TM non deterministiche e loro equivalenza alle deterministiche, TMNonDet.pdf.

martedý 11/11/2014

2 ore; Lezione dedicata a domande sul programma svolto fino ad ora, Domande.pdf.

giovedý 6/11/2014

2 ore; lezione sospesa per decreto rettorale - allerta meteo.

martedý 4/11/2014

2 ore; Prime varianti di TM: le TM a pi¨ nastri, TMKnastri.pdf.

giovedý 30/10/2014

2 ore; Macchine di Turing: prime definizioni e proprietÓ. TM1Def.pdf.

martedý 28/10/2014

2 ore;Lezione in aula seminari. Il problema dell'appartenenza per CFG e altri problemi di decisione per i linguaggi contex-free. CFGalgCYK.pdf

giovedý 23/10/2014

2 ore; Grammatiche contex-free ed equivalenza PDA, CFGIntr.pdf, CFGePDA.pdf

martedý 21/10/2014

2 ore; PDA.pdf

giovedý 16/10/2014

2 ore;Automi a stati finiti non deterministici e loro equivalenza con le espressioni regolari EspressioniRegolari.pdf

martedý 14/10/2014

2 ore; Il pumping lemma per i regolari. PumpingLemma.pdf

giovedý 9/10/2014

2 ore;Automi a stati finiti non deterministici e loro equivalenza con i DFA: NFA.pdf.

martedý 7/10/2014

2 ore;DFA: prime definizioni ed esempi. DFAIntr.pdf, ChiusureDFA.pdf

giovedý 2/10/2014

2 ore; problemi come linguaggi, prime definizioni sui linguaggi, CCLinguaggi.pdf.

martedý 30/9/2014

2 ore;Introduzione al corso. CCintr.pdf

Date e Scadenze

September 2018
            01
02 03 04 05 06 07 08
09 10 11 12 13 14 15
16 17 18 19 20 21 22
23 24 25 26 27 28 29
30            


Avvisi Importanti

Avviso JFLAP

Seguendo questo link: http://www.cs.duke.edu/csed/jflap/log/form.php Ŕ possibile scaricare l'applicazione che vi consente di costruire e verificare vari tipi di macchine a stati finiti: DFA, automi a pila, macchine di Turing.


LinksUtili

Qui un tutorial sul modello quantistico

Un ricordo e un omaggio a Cobham: nel blog di Jeffrey Shallit "Recurrent thoughts about mathematics, science, politics, music, religion, and ... "

Questa Ŕ la homepage di David S. Johnson che insieme a Mike Garey ha pubblicato il testo in cui c'Ŕ la prima collezione ragionata di problemi NP-completi. Computers and Intractability: A Guide to the Theory of NP-Completeness. Nella pagina di Johnson trovate un link a un file pdf con un catalogo aggiornato di problemi NP-completi.

Questa è la pagina del corso diPhilosophy and Theoretical Computer Science, tenuto al MIT da S. Aaronson, dove trovate il link a vari articoli interessanti.

In questa pagina trovate un'applicazione Java, JFLAP, che vi consente di costruire automi a stati finiti di vario tipo, grammatiche e macchine di Turing, eseguirli su particolari input e verificare alcune costruzioni.

Cliccando qui andrete alla pagina dove il The Clay Mathematics Institute di Cambridge, Massachusetts (CMI) presenta sette problemi da un milione di dollari, tra cui P vs NP.
Qui trovate l'elenco dei vincitori del Turing Award, il Nobel per l'Informatica.

Qui potete documentarvi sulla storia del calcolatore e trovare i vincitori del premio annuale conferito dal Computer History Museum.

I link seguenti vi porteranno alle pagine bibliografiche di matematici, logici o infomatici citati durante le lezioni
CHURCH
GODEL
KLEENE
POST
THUE
TURING
ROBINSON
GREIBACH
CHOMSKY
CHOMSKI
RABIN
KARP
MATIYASEVICH
HILBERT
RUSSEL
CANTOR
HOPPER
PEANO
FREGE

ACKERMANN
HERBRAND
CURRY


Topic attachments
I Attachment History Action Size Date Who Comment
PDFpdf 2SATinP_.pdf r2 r1 manage 118.0 K 2011-12-12 - 08:49 EmanuelaFachini  
PDFpdf ACC10Gen18.pdf r1 manage 54.7 K 2018-01-17 - 08:12 EmanuelaFachini  
PDFpdf ACC11Gen16T1.pdf r1 manage 57.3 K 2016-01-15 - 16:41 EmanuelaFachini  
PDFpdf ACC11Gen16T2.pdf r1 manage 59.9 K 2016-01-15 - 16:49 EmanuelaFachini  
PDFpdf ACC16apr18.pdf r1 manage 51.3 K 2018-04-16 - 14:37 EmanuelaFachini  
PDFpdf ACC1lu16.pdf r1 manage 54.7 K 2016-09-14 - 15:21 EmanuelaFachini  
PDFpdf ACC20Sett18.pdf r1 manage 49.6 K 2018-09-21 - 08:51 EmanuelaFachini  
PDFpdf ACC6Giu18.pdf r1 manage 30.0 K 2018-06-12 - 12:57 EmanuelaFachini  
PDFpdf ACC7Nov16.pdf r1 manage 52.3 K 2016-11-17 - 14:36 EmanuelaFachini  
PDFpdf ACC8Giu16.pdf r2 r1 manage 63.3 K 2016-07-01 - 07:35 EmanuelaFachini  
PDFpdf ACCFeb17.pdf r1 manage 49.3 K 2017-02-05 - 11:34 EmanuelaFachini  
PDFpdf ACCGiu17.pdf r1 manage 49.9 K 2017-06-05 - 14:53 EmanuelaFachini  
PDFpdf AmbiguitCFG.pdf r2 r1 manage 110.3 K 2017-11-11 - 15:16 EmanuelaFachini  
PDFpdf AppStrACCApr17.pdf r1 manage 50.6 K 2017-03-29 - 15:31 EmanuelaFachini  
PDFpdf CFG.pdf r3 r2 r1 manage 127.3 K 2017-11-11 - 13:35 EmanuelaFachini  
PDFpdf CFGePDA.pdf r2 r1 manage 108.0 K 2017-11-11 - 15:16 EmanuelaFachini  
PDFpdf ChiusureCFL.pdf r2 r1 manage 145.2 K 2016-11-03 - 17:08 EmanuelaFachini  
PDFpdf Chiusure_e_Rice.pdf r6 r5 r4 r3 r2 manage 140.6 K 2013-10-31 - 09:05 EmanuelaFachini  
PDFpdf ClassiCompl.pdf r4 r3 r2 r1 manage 284.3 K 2017-12-05 - 10:01 EmanuelaFachini  
PDFpdf CommentoValACCDic15.pdf r1 manage 17.5 K 2015-12-22 - 13:21 EmanuelaFachini  
PDFpdf ComplessitaDef.pdf r1 manage 276.3 K 2012-11-20 - 10:49 EmanuelaFachini  
PDFpdf Cook.pdf r3 r2 r1 manage 179.1 K 2015-12-09 - 15:49 EmanuelaFachini  
PDFpdf DECvsRic.pdf r1 manage 107.9 K 2013-12-05 - 11:28 EmanuelaFachini  
PDFpdf DECvsRicOtt.pdf r1 manage 88.2 K 2014-12-10 - 14:10 EmanuelaFachini  
PDFpdf DFA1Intr.pdf r5 r4 r3 r2 r1 manage 237.2 K 2017-10-06 - 13:10 EmanuelaFachini  
PDFpdf DFAIntr.pdf r2 r1 manage 165.7 K 2016-09-30 - 12:20 EmanuelaFachini  
PDFpdf DecChiusCFL.pdf r1 manage 92.8 K 2017-11-24 - 14:31 EmanuelaFachini  
PDFpdf DefComp.pdf r2 r1 manage 212.6 K 2015-12-02 - 14:49 EmanuelaFachini  
PDFpdf DefCompl1.pdf r1 manage 171.5 K 2011-11-02 - 11:22 EmanuelaFachini  
PDFpdf DefCompl2.pdf r1 manage 226.7 K 2015-12-09 - 15:48 EmanuelaFachini  
PDFpdf Diagonalizzazione.pdf r1 manage 77.2 K 2012-10-16 - 10:26 EmanuelaFachini  
PDFpdf Es2010.pdf r1 manage 17.9 K 2017-10-23 - 14:24 EmanuelaFachini  
PDFpdf Es20Dic17.pdf r1 manage 29.3 K 2017-12-20 - 14:08 EmanuelaFachini  
PDFpdf Es22Dic17.pdf r1 manage 52.8 K 2017-12-22 - 14:07 EmanuelaFachini  
PDFpdf Es311.pdf r1 manage 27.2 K 2017-11-20 - 15:52 EmanuelaFachini  
PDFpdf Es4CC2015.pdf r1 manage 29.1 K 2016-01-25 - 15:32 EmanuelaFachini  
PDFpdf Es811.pdf r1 manage 20.0 K 2017-11-20 - 15:52 EmanuelaFachini  
PDFpdf EsACC15Nov.pdf r2 r1 manage 26.2 K 2017-11-20 - 15:52 EmanuelaFachini  
PDFpdf EsACC17Nov.pdf r1 manage 26.0 K 2017-11-19 - 08:57 EmanuelaFachini  
PDFpdf EsACC29Nov.pdf r1 manage 17.7 K 2017-12-01 - 15:09 EmanuelaFachini  
PDFpdf EsACC4Dic.pdf r1 manage 15.8 K 2017-12-01 - 15:07 EmanuelaFachini  
PDFpdf EsACCDic2015.pdf r1 manage 46.8 K 2015-12-21 - 14:00 EmanuelaFachini  
PDFpdf EsAula21dic2016.pdf r1 manage 280.1 K 2016-12-21 - 20:01 EmanuelaFachini  
PDFpdf EsAula29Nov.pdf r1 manage 31.8 K 2017-12-04 - 17:01 EmanuelaFachini  
PDFpdf EsAula4Dic.pdf r1 manage 28.5 K 2017-12-04 - 17:01 EmanuelaFachini  
PDFpdf EsEsame18Ott17.pdf r1 manage 12.5 K 2017-10-19 - 12:49 EmanuelaFachini  
PDFpdf EsPumping.pdf r1 manage 49.9 K 2017-10-21 - 14:25 EmanuelaFachini  
PDFpdf EserciziAutomi.pdf r1 manage 22.6 K 2017-10-13 - 14:28 EmanuelaFachini  
PDFpdf EserciziDecTuringRic.pdf r1 manage 90.8 K 2016-12-07 - 15:28 EmanuelaFachini  
PDFpdf EserciziNFAePDA.pdf r3 r2 r1 manage 475.6 K 2017-11-03 - 14:14 EmanuelaFachini  
PDFpdf EserciziNFAePDA_.pdf r1 manage 497.3 K 2017-10-30 - 10:03 EmanuelaFachini  
PDFpdf EsistenzaNonDec.pdf r4 r3 r2 r1 manage 104.8 K 2015-11-18 - 14:45 EmanuelaFachini  
PDFpdf EspressioniRegolari.pdf r2 r1 manage 308.5 K 2017-10-21 - 14:25 EmanuelaFachini  
PDFpdf FermataTM.pdf r3 r2 r1 manage 156.7 K 2015-11-21 - 09:11 EmanuelaFachini  
JPEGJPG IMG_0822.JPG r1 manage 1792.4 K 2016-02-11 - 09:18 EmanuelaFachini  
JPEGJPG IMG_0823.JPG r1 manage 1934.5 K 2016-02-11 - 09:13 EmanuelaFachini  
JPEGJPG IMG_0824.JPG r1 manage 1896.5 K 2016-02-11 - 09:38 EmanuelaFachini  
PDFpdf IlComplemento.pdf r1 manage 29.7 K 2015-10-30 - 14:52 EmanuelaFachini  
PDFpdf InPoltreNP.pdf r2 r1 manage 262.8 K 2017-12-22 - 14:07 EmanuelaFachini  
PDFpdf IndFermataTM.pdf r3 r2 r1 manage 57.6 K 2017-11-24 - 14:18 EmanuelaFachini  
PDFpdf IntCCII.pdf r1 manage 851.4 K 2015-09-23 - 15:15 EmanuelaFachini  
PDFpdf IntrACC17.pdf r1 manage 650.9 K 2017-10-04 - 14:06 EmanuelaFachini  
PDFpdf L__NL.pdf r5 r4 r3 r2 r1 manage 102.1 K 2014-01-07 - 11:15 EmanuelaFachini  
PDFpdf Linguaggi_e_operazioni.pdf r3 r2 r1 manage 113.6 K 2017-10-19 - 07:09 EmanuelaFachini  
PDFpdf MATACC10Gen18.pdf r1 manage 28.7 K 2018-01-17 - 08:41 EmanuelaFachini  
PDFpdf MATACCsett18.pdf r1 manage 31.2 K 2018-09-21 - 07:43 EmanuelaFachini  
PDFpdf MATValACCFeb16.pdf r1 manage 39.0 K 2016-02-05 - 10:00 EmanuelaFachini  
PDFpdf MatACC13Genn17.pdf r1 manage 53.7 K 2017-01-20 - 16:35 EmanuelaFachini  
PDFpdf MatACC27giu18.pdf r1 manage 25.8 K 2018-06-28 - 10:03 EmanuelaFachini  
PDFpdf MatACC28giu17.pdf r1 manage 25.4 K 2017-06-28 - 16:25 EmanuelaFachini  
PDFpdf MatACC31Gen2018.pdf r1 manage 39.5 K 2018-02-07 - 11:50 EmanuelaFachini  
PDFpdf MatACC4sett17.pdf r1 manage 58.8 K 2017-09-06 - 10:19 EmanuelaFachini  
PDFpdf MatACC5Giu17.pdf r1 manage 40.0 K 2017-06-08 - 12:09 EmanuelaFachini  
Unknown file formatnumbers MatACCFeb17.numbers r1 manage 711.8 K 2017-02-27 - 10:43 EmanuelaFachini  
PDFpdf MatACCFeb17.pdf r1 manage 50.6 K 2017-02-27 - 11:05 EmanuelaFachini  
PDFpdf MatACCMarzo2017.pdf r1 manage 36.7 K 2017-03-27 - 14:14 EmanuelaFachini  
PDFpdf MatACCNov16.pdf r1 manage 61.3 K 2016-11-22 - 17:04 EmanuelaFachini  
PDFpdf MatEsAulaMercoledi1718.pdf r1 manage 32.6 K 2017-11-20 - 15:40 EmanuelaFachini  
PDFpdf MatEsAulaVenerd1718.pdf r1 manage 28.7 K 2017-11-20 - 15:40 EmanuelaFachini  
PDFpdf MatEsVenerd3Nov.pdf r1 manage 34.4 K 2017-11-13 - 16:06 EmanuelaFachini  
PDFpdf MatEsameACCParziale.pdf r1 manage 24.5 K 2017-12-29 - 14:26 EmanuelaFachini  
PDFpdf MatValACC16Apr2018.pdf r1 manage 18.6 K 2018-04-17 - 09:03 EmanuelaFachini  
PDFpdf MatValACCSett16.pdf r1 manage 30.0 K 2016-09-21 - 09:04 EmanuelaFachini  
PDFpdf MergeSort_con_analisi.pdf r1 manage 166.5 K 2017-05-03 - 15:29 EmanuelaFachini  
PDFpdf NFA.pdf r8 r7 r6 r5 r4 manage 337.3 K 2016-10-07 - 14:24 EmanuelaFachini  
PDFpdf NFAdefDimEq.pdf r1 manage 350.5 K 2017-10-13 - 14:28 EmanuelaFachini  
PDFpdf NL=coNL.pdf r1 manage 114.5 K 2014-01-09 - 13:30 EmanuelaFachini  
PDFpdf NP-complCook.pdf r1 manage 332.4 K 2016-12-05 - 16:43 EmanuelaFachini  
PDFpdf NPcomplCook.pdf r1 manage 171.3 K 2017-12-13 - 14:54 EmanuelaFachini  
PDFpdf NPcompleti2.pdf r1 manage 106.1 K 2017-12-15 - 14:16 EmanuelaFachini  
PDFpdf NPcompleti_.pdf r3 r2 r1 manage 156.5 K 2017-12-13 - 14:52 EmanuelaFachini  
Compressed Zip archivezip NTM.zip r2 r1 manage 104.2 K 2011-10-18 - 08:58 EmanuelaFachini file aggiornato con esempi
PDFpdf NonDec.pdf r3 r2 r1 manage 191.7 K 2012-10-23 - 09:26 EmanuelaFachini  
PDFpdf NonDecEsiste.pdf r1 manage 104.6 K 2017-11-22 - 14:46 EmanuelaFachini  
Unknown file formatjff NonDetScriveBin.jff r1 manage 1.9 K 2013-10-15 - 10:23 EmanuelaFachini  
PDFpdf NumerabilitTuringCalc.pdf r2 r1 manage 51.1 K 2017-11-26 - 17:27 EmanuelaFachini  
PDFpdf PDA.pdf r2 r1 manage 260.5 K 2017-11-02 - 08:32 EmanuelaFachini  
PDFpdf PIACCNov16.pdf r1 manage 49.9 K 2016-11-12 - 12:59 EmanuelaFachini  
PDFpdf PSPACE-completeness.pdf r9 r8 r7 r6 r5 manage 175.4 K 2015-12-21 - 11:09 EmanuelaFachini  
PDFpdf Parity_games.pdf r1 manage 88.3 K 2013-12-17 - 11:13 EmanuelaFachini  
PDFpdf PrePIACC15.pdf r2 r1 manage 41.8 K 2015-11-11 - 15:31 EmanuelaFachini  
PDFpdf PrenACC6Giu18.pdf r1 manage 37.1 K 2018-06-06 - 16:31 EmanuelaFachini  
PDFpdf PrimeChiusure.pdf r1 manage 283.1 K 2017-10-11 - 14:48 EmanuelaFachini  
PDFpdf ProgCC2010:2011.pdf r1 manage 27.4 K 2012-01-26 - 11:20 EmanuelaFachini  
PDFpdf ProgCC2011:2012.pdf r2 r1 manage 28.6 K 2012-01-26 - 11:21 EmanuelaFachini  
PDFpdf ProgrammaACC.pdf r1 manage 36.7 K 2017-05-29 - 09:48 EmanuelaFachini  
PDFpdf ProgrammaACC1617.pdf r3 r2 r1 manage 45.9 K 2016-12-15 - 11:49 EmanuelaFachini  
PDFpdf ProgrammaACC17-18.pdf r1 manage 40.2 K 2018-02-20 - 08:27 EmanuelaFachini  
PDFpdf ProgrammaCC13:14.pdf r1 manage 28.0 K 2014-01-07 - 11:16 EmanuelaFachini  
PDFpdf ProgrammaCC14:15.pdf r1 manage 34.3 K 2014-11-17 - 11:34 EmanuelaFachini  
PDFpdf ProgrammaCC1516.pdf r1 manage 34.5 K 2016-10-10 - 13:13 EmanuelaFachini  
PDFpdf ProvaIntermediaACC2015.pdf r1 manage 39.5 K 2015-11-06 - 20:19 EmanuelaFachini  
PDFpdf PumpingLemma.pdf r6 r5 r4 r3 r2 manage 117.1 K 2017-10-19 - 07:09 EmanuelaFachini  
PDFpdf QuickSort.pdf r1 manage 127.4 K 2017-05-03 - 13:04 EmanuelaFachini  
PDFpdf RelRic.pdf r1 manage 210.1 K 2017-05-03 - 15:29 EmanuelaFachini  
PDFpdf RidEs20Dic17.pdf r1 manage 54.2 K 2017-12-22 - 15:25 EmanuelaFachini  
PDFpdf Rid_Indecidibilita.pdf r1 manage 75.6 K 2015-11-25 - 14:08 EmanuelaFachini  
PDFpdf RideIndecidibilit.pdf r3 r2 r1 manage 85.4 K 2017-11-30 - 07:40 EmanuelaFachini  
PDFpdf Riduzione22Dic17.pdf r1 manage 61.4 K 2017-12-22 - 15:25 EmanuelaFachini  
PDFpdf Riduzioni.pdf r4 r3 r2 r1 manage 133.0 K 2017-11-30 - 07:40 EmanuelaFachini  
PDFpdf Savitch.pdf r3 r2 r1 manage 147.3 K 2017-12-15 - 14:16 EmanuelaFachini  
PDFpdf SolACC7Nov16.pdf r3 r2 r1 manage 84.2 K 2016-12-07 - 15:28 EmanuelaFachini  
PDFpdf SolACCGiu17.pdf r1 manage 60.4 K 2017-06-12 - 10:38 EmanuelaFachini  
PDFpdf SolEsPI14Nov12.pdf r1 manage 80.9 K 2012-11-20 - 11:09 EmanuelaFachini  
PDFpdf SolPIACCNov16.pdf r1 manage 60.0 K 2016-11-17 - 13:34 EmanuelaFachini  
Compressed Zip archivezip TM.zip r1 manage 155.7 K 2013-10-03 - 10:20 EmanuelaFachini  
PDFpdf TM1Def.pdf r2 r1 manage 442.8 K 2014-11-03 - 14:58 EmanuelaFachini  
Unknown file formatjff TM2Nastri0n1n.jff r2 r1 manage 1.6 K 2013-10-10 - 12:32 EmanuelaFachini  
PDFpdf TM3NonDet.pdf r1 manage 130.7 K 2015-11-17 - 15:49 EmanuelaFachini  
PDFpdf TM5Rid.pdf r5 r4 r3 r2 r1 manage 165.6 K 2011-11-17 - 11:51 EmanuelaFachini  
PDFpdf TMDef.pdf r3 r2 r1 manage 633.4 K 2017-11-15 - 14:09 EmanuelaFachini  
PDFpdf TMKnastri.pdf r6 r5 r4 r3 r2 manage 228.0 K 2017-11-19 - 08:57 EmanuelaFachini  
PDFpdf TMNonDet.pdf r5 r4 r3 r2 r1 manage 309.5 K 2017-11-22 - 14:46 EmanuelaFachini  
PDFpdf TMUniv-Fermata.pdf r1 manage 183.8 K 2011-10-18 - 09:01 EmanuelaFachini  
PDFpdf TMUniversale.pdf r3 r2 r1 manage 129.8 K 2017-11-24 - 14:18 EmanuelaFachini  
Compressed Zip archivezip TMesempi.zip r2 r1 manage 3.0 K 2012-10-09 - 09:26 EmanuelaFachini  
Compressed Zip archivezip TMknastri.zip r1 manage 98.7 K 2011-10-12 - 10:16 EmanuelaFachini  
PDFpdf TestoACC4Sett17.pdf r1 manage 52.0 K 2017-09-06 - 10:19 EmanuelaFachini  
PDFpdf Turing.pdf r1 manage 42.1 K 2018-09-24 - 13:17 EmanuelaFachini  
PDFpdf Turing36.pdf r1 manage 331.5 K 2013-10-15 - 10:37 EmanuelaFachini  
PDFpdf ValACC11Gen16.pdf r1 manage 43.5 K 2016-01-14 - 16:09 EmanuelaFachini  
PDFpdf ValACCDic15.pdf r2 r1 manage 36.5 K 2015-12-22 - 13:29 EmanuelaFachini  
PDFpdf ValACCEs20ott17.pdf r1 manage 35.9 K 2017-10-23 - 14:16 EmanuelaFachini  
PDFpdf ValACCEsAulaMercoled18Ott.pdf r1 manage 36.7 K 2017-10-23 - 14:16 EmanuelaFachini  
PDFpdf ValACCMercoled1718.pdf r2 r1 manage 30.0 K 2017-12-29 - 13:51 EmanuelaFachini  
PDFpdf ValACCVenerd1718.pdf r1 manage 29.5 K 2017-12-29 - 12:10 EmanuelaFachini  
PDFpdf Verificatore.pdf r5 r4 r3 r2 r1 manage 241.4 K 2017-12-06 - 14:26 EmanuelaFachini  
PDFpdf _ACC13Gen17.pdf r1 manage 67.8 K 2017-01-17 - 16:29 EmanuelaFachini  
PDFpdf algCYK.pdf r1 manage 187.6 K 2016-10-24 - 13:03 EmanuelaFachini  
PDFpdf coNP.pdf r5 r4 r3 r2 r1 manage 295.1 K 2017-12-20 - 14:08 EmanuelaFachini  
PDFpdf matEsVenerd3Nov.pdf r1 manage 35.3 K 2017-11-13 - 15:55 EmanuelaFachini  
PDFpdf matMercoled8Nov.pdf r1 manage 37.6 K 2017-11-13 - 15:55 EmanuelaFachini  
PDFpdf tempoSpazioTM.pdf r1 manage 200.3 K 2013-11-19 - 11:23 EmanuelaFachini  
Edit | Attach | Watch | Print version | History: r637 < r636 < r635 < r634 < r633 | Backlinks | Raw View | Raw edit | More topic actions
Topic revision: r637 - 2018-09-24 - EmanuelaFachini






 
Questo sito usa cookies, usandolo ne accettate la presenza. (CookiePolicy)
This site is powered by the TWiki collaboration platform Powered by PerlCopyright © 2008-2018 by the contributing authors. All material on this collaboration platform is the property of the contributing authors.
Ideas, requests, problems regarding TWiki? Send feedback