- Oggetto:
- Oggetto:
Calcolabilità e complessità
- Oggetto:
Anno accademico 2013/2014
- Codice dell'attività didattica
- INT0369
- Docenti
- (Titolare del corso)
Lavinia Egidi (Titolare del corso) - Corso di studi
- Laurea Magistrale Interateneo in Fisica dei sistemi complessi
- Tipologia
- C=Affine o integrativo
- Crediti/Valenza
- 6
- SSD dell'attività didattica
- INF/01 - informatica
- Lingua di insegnamento
- Italiano
- Modalità di frequenza
- Facoltativa
- Tipologia d'esame
- Orale
- Prerequisiti
-
Conoscenza di fondamenti di programmazione, logica, analisi e, preferibilmente, architetture di elaboratori e linguaggi formali. Per la frequenza del corso: capacità di programmazione in Java (non richiesta per sostenere l'esame)
Knowledge of basic aspect of programming, logic, calculus and, preferably, of computer architectures and formal languages - Oggetto:
Sommario insegnamento
- Oggetto:
Obiettivi formativi
Il corso mira ad insegnare le basi teoriche dell' Informatica, sottolineando l'esistenza di problemi indecidibili e di problemi che richiedono troppe risorse per essere trattati in pratica.
The course aims at teaching the theoretical bases of Computer Science, with stress on the existence of undecidable problems and of problems that require too many computational resources to be practically treated.
- Oggetto:
Modalità di verifica dell'apprendimento
L'attività in laboratorio è parte essenziale del corso (non si tratta di esercitazioni ma di vere e proprie lezioni). Agli studenti è richiesto di realizzare simulatori di diversi modelli di macchina di Turing in Java (a partire da codice già disponibile), di implementare macchine di Turing, e di implementare in Java le costruzioni che sono alla base delle dimostrazioni di molti teoremi. Lo scopo dell'attività in laboratorio è permettere agli studenti di raggiungere una comprensione piú profonda dei modelli studiati, e delle simulazioni presenti in quasi tutte le dimostrazioni di teoremi. L'attività di programmazione serve solo per aiutare alla comprensione e non è richiesta la consegna degli esercizi svolti (il docente è disponibile a fornire un sotto-insieme degli esercizi svolti in laboratorio realizzabili utilizzando un qualunque linguaggio di programmazione di alto livello).
Activity in lab will be an essential part of the course. The students will be requested to realize in Java simulators of various Turing machine models (most of the code is provided), to implement Turing machines' code, and to implement in Java the constructions that are at the heart of the proofs of many theorems. The aim of the lab activity is allowing the students to reach a deeper understanding of the models studied, and of the simulations present in almost all the proofs of the theorems presented. The programming activity is intended as a means to enhance comprehension of the material, students are not required to submit the completed exercises (upon student's request, a subset of the lab exercises are available that can be implemented using any high level programming language)
- Oggetto:
Programma
Calcolabilità
- Macchine di Turing
- Funzion calcolabili secondo Turing
- Insiemi ricorsivi e ricorsivamente enumerabili
- Tesi di Church
- Diagonalizzazione
- Indecidibilità
Complessità
- Misure di complessità, crescita asintotica di funzioni, modelli e rappresentazione di problemi
- Teorema di accelerazione lineare
- Macchine di Turing non deterministiche e modello Guess&Verify
- Le classi P ed NP, problemi in NP, riduzioni polinomiali, problemi NP-completi, SAT, Teorema di Cook reductions, NP-complete problems, SAT, Cook's Theorem
- Complessità in termini di spazio, relazioni tra classi di complessità in termini di spazio e di tempo; Teorema di Savitch
- Teoremi della gerarchia temporale e spaziale (e funzioni time- e space-constructible)
- Macchine di Turing e la gerarchia di Chomsky
- Esistenza di linguaggi non in P
Computability
- Turing Machines
- Turing computable functions
- Recursive and recursively enumerable sets
- Church's Thesis
- Diagonalization
- Undecidability
Complexity
- Complexity measures, rates of growth, models and representation of problems.
- Linear Speedup Theorem
- Non deterministic Turing machines and the Guess&Verify model
- The classes P and NP, problems in NP, polynomial reductions, NP-complete problems, SAT, Cook's Theorem
- Space complexity, relations between space and time complexities; Savitch's Theorem
- Time and space Hyerarchy Theorems (and time- and space-constructible functions)
- Turing machines and the Chomsky hyerarchy
- Existence of languages not in P
Testi consigliati e bibliografia
- Oggetto:
- Thomas A. Sudkamp, Languages and Machines, Pearson International Edition, 2006
- materiale aggiuntivo disponibile sul sito DIR del corso
- Per l'NP-completezza può essere utile: Garey-Johnson, Computers and Intractability, Freeman, 1979
- Thomas A. Sudkamp, Languages and Machines, Pearson International Edition, 2006
- additional material available on the DIR site
- For NP-completeness, the following is useful: Garey-Johnson, Computers and Intractability, Freeman, 1979
- Oggetto:
