ECTS - University of Pisa
Scheda programma d'esame
INTRODUCTION TO COMPUTABILITY AND ABSTRACT COMPLEXITY
PIERPAOLO DEGANO
Academic year2016/17
CourseCOMPUTER SCIENCE
Code246AA
Credits6
PeriodSemester 1
LanguageItalian

ModulesAreaTypeHoursTeacher(s)
ELEMENTI DI CALCOLABILITA' E COMPLESSITA'INF/01LEZIONI48
PIERPAOLO DEGANO unimap
Obiettivi di apprendimento
Learning outcomes
Conoscenze

Comprendere quali sono i problemi risolvibili meccanicamente, in assenza e in presenza di vincoli sulle risorse di calcolo. Si avrà cura di legare i risultati della teoria introdotta ad applicazioni pú strettamente legarte alla nostra disciplina.

 
Knowledge

The student who successfully completes the course will be able to demonstrate a solid knowledge of foundations of computability theory and abstract complexity theory.

The student who successfully completes the course will be able to demonstrate a solid knowledge of foundations of computability theory and abstract complexity theory.
Modalità di verifica delle conoscenze

Verifiche intermedie e finali

 
Assessment criteria of knowledge

In the written exam the student will be required to solve excercises about computability and formal languages (see the course website for examples). In the oral exam the student will be required to manage the definitions and the theoretical results

Methods:

  • Final oral exam
  • Final written exam
  • Periodic written tests

In the written exam the student will be required to solve excercises about computability and formal languages (see the course website for examples). In the oral exam the student will be required to manage the definitions and the theoretical results

Methods:

  • Final oral exam
  • Final written exam
  • Periodic written tests

 
Capacità

 È richiesta la capacità di comprensione, apprendimento e ragionamento logico-deduttivo

 
Modalità di verifica delle capacità

Scritto e orale
Comportamenti

Educati
Modalità di verifica dei comportamenti

I soliti
Prerequisiti (conoscenze iniziali)

 Un po' di teoria degli insiemi e delle strutture algebriche; un po' di logica; la nozione di funzione.
Corequisiti

V. sopra
Prerequisiti per studi successivi

I concetti e le nozioni impartite iin questo corso
Teaching methods

Delivery: face to face

Learning activities:

  • attending lectures
  • participation in discussions

Attendance: Advised

Teaching methods:

  • Lectures

Delivery: face to face

Attendance: Advised

Learning activities:

  • attending lectures
  • participation in discussions

 

Teaching methods:

  • Lectures

 
Programma (contenuti dell'insegnamento)

 

Il corso introduce le nozioni fondamentali della teoria della calcolabilità e della complessità. La prima parte delinea i concetti e la natura dei problemi che hanno soluzione effettiva. La seconda parte caratterizza i problemi che sono risolvibili con risorse di calcolo limitate.

  • Macchine di Turing (deterministiche e non, a più nastri, I/O)
  • Linguaggi calcolabili, MdT universale
  • Funzioni ricorsive e linguaggi di programmazione,
  • Totalità e diagonalizzazione
  • Teoremi fondamentali
  • Riducibilità, problemi insolubili
  • Funzioni di misura di tempo e spazio
  • Classi di complessità (tempo/spazio) deterministiche e non, P- e NP-completezza
  • Cenni si altre classi (co-NP, caso, approssimazione, parallelismo)

 

Programma

 

  • Turing machines (deterministic, non-deterministic, k-tapes, I/O)
  • Computable languages, Universal Turing machine
  • Recursive functions and programming languages
  • Total functions and diagonalization
  • Main theorems
  • Reducibility, unsolvable problems
  • Time and space measures
  • Deterministic and non-deterministic complexity classes (time/space), P- e NP-completeness
  • Other classes (co-NP, random, approximation, parallelism) -- outline

 

 

 
Syllabus

Models of computability: general recursive functions, Turing Machines; Fundamental results of computability; Recursive and recursively enumerable sets; Regular languages, grammars and finite states automata; Free context languages: grammars and pushdown automata; P and NP problems; NP-complete problems; Cook's theorem.

Models of computability: general recursive functions, Turing Machines; Fundamental results of computability; Recursive and recursively enumerable sets; Regular languages, grammars and finite states automata; Free context languages: grammars and pushdown automata; P and NP problems; NP-complete problems; Cook's theorem.
Bibliografia e materiale didattico
  • Ch.H. Papadimitriou, Computational Complexity, Addison-Wesley, 1994.
  • R.J. Soare, Recursively Enumerable Sets and Degrees, Springer-Verlag, 1988. P. Degano, Notes.
  • E. Börger, Computability, Complexity, Logic, North-Holland, 1989.
  • A. Bernasconi, B. Codenotti, Introduzione alla Complessità Computazionale, Springer, 1998.
  • T.H. Cormen, C.E. Leiserson, L.R. Rivest, Introduction to Algorithms, MIT Press, 1990.
  • M.R. Garey, D.S. Johnson, Computers and Intractability, Freeman & Co., 1979.
  • H.R. Lewis, Ch.H. Papadimitriou, Elements of the Theory of Computation, Prentice-Hall, 1981.
  • N.D. Jones, Computability and Complexity, MIT Press, 1997.
  • R. Sommerhalden, S.C. van Westrhenen, The Theory of Computability, Addison-Wesley, 1988.
  • Note del docente

 
Bibliography

Reading material (in English) available in the web site of the course (http://www.di.unipi.it/~turini/Didattica.htm - ask Franco Turini for a password)

Reading material (in English) available in the web site of the course (http://www.di.unipi.it/~turini/Didattica.htm - ask Franco Turini for a password)
Modalità d'esame

Scritto e orale
Stage e tirocini

Nessuno
Altri riferimenti web

https://www.di.unipi.it/it/didattica/inf-l/insegnamenti/lista-dei-corsi?cds=inf31&anno=2017
Updated: 16/05/2017 11:03