Scheda programma d'esame
INTRODUCTION TO COMPUTABILITY AND ABSTRACT COMPLEXITY
PIERPAOLO DEGANO
Academic year2022/23
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 piú strettamente legate 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 (if Covid permits)
  • Periodic written tests (if Covid permits)

 

 

Capacità

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

 

Skills

Understanding, learning and reasoning in a deductive world

Modalità di verifica delle capacità

Scritto e orale, covid permettendo

Assessment criteria of skills

Written and oral (if Covid permits)

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 (i quantificatori!!); la nozione di funzione; capacità logiche-deduttive

Prerequisites

Naive set theory, algebra, logics (especially meaning and use of quantifiers); basic mathematics; reasoning capabilities

Indicazioni metodologiche

Lezioni ed esercitazioni tradizionali, covid permettendo

Teaching methods

Delivery: face to face (covid permitting)

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, covid permettendo

Assessment methods

Writen and oral (if Covid permits)

Altri riferimenti web

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

Updated: 03/08/2022 14:27