Valutami
Scheda programma d'esame
ELEMENTI DI CALCOLABILITA' E COMPLESSITA'
PIERPAOLO DEGANO
Anno accademico2017/18
CdSINFORMATICA
Codice246AA
CFU6
PeriodoPrimo semestre
LinguaItaliano

ModuliSettore/iTipoOreDocente/i
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.
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

 
Skills

ndefrstanding, learning and reasoning in a deductive world
Modalità di verifica delle capacità

Scritto e orale
Assessment criteria of skills

Writte and oral
Comportamenti

Educati
Behaviors

Good
Modalità di verifica dei comportamenti

I soliti
Assessment criteria of behaviors

The usual ones
Prerequisiti (conoscenze iniziali)

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

Naive set theory, algebra, logics; basic mathematics
Indicazioni metodologiche

Lezioni ed esercitazioni tradizionali
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)

 

 

 
Syllabus

The course introduces the basic notions of computability and complexity. The first part presents and formalises the needed concepts and the nature of those problems admitting an effective solution. The second part characterises the problems solvable when the computational resources are bounded.

  • 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

 

 
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
  • 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.
  • Notes by the professor

 
Modalità d'esame

Scritto e orale
Assessment methods

Writen and oral
Altri riferimenti web

https://www.di.unipi.it/it/didattica/inf-l/insegnamenti/lista-dei-corsi?cds=inf31&anno=2017
Ultimo aggiornamento 15/01/2018 12:58