Parisian Master of Research in Computer Science
Master Parisien de Recherche en Informatique (MPRI)

Cours 2.33.3

2.33.1 Computing over the reals: models, computability, complexity (24h, 3ECTS)

Responsable: Olivier Bournez, Professeur Ecole polytechnique.

Fridays, from 16h15 to 19h15.

Note: - No course on Friday September 21, 2018 - No course on Friday September 28, 2018

Course 2 on Friday October 5 2018

Motivations et objectifs du cours

This course is discussing computability and complexity theory for computations over the real numbers.

Pre-requisites

Basic notions from theoretical computer science (Turing machines, NP-completeness, P, NP, etc...)

Course Description

We will introduce various way to model and discuss computations over the real numbers:

For example:

* Computable analysis: a real is seen as a sequence of converging rational numbers, and one considers Turing machines transforming rational sequences into rational sequences

* Continuous time models of computation: what can be computed using analog electronics, circuits?

Course Language

English upon request. French by default.

Messages :

Messages: * The first course is on Friday 14th September 2018

* No course on Friday 21 September, and Friday 28 September analyserecursive.pdf

Course content :

The course will be done on blackboard.

Some course notes will be available and put online at the end of each course.

* Course 1:

  • Computable analysis: computable reals. (see consolidated pdf below)

* Course 2:

  • Computable analysis: computable functions (see consolidated pdf below)

* Course 3:

  • Computable functions: oracle view. Modulus of continuity.
  • Computable subsets.

* Course 4:

  • Intermediate Value Theorem
  • Complexity

* Course 5:

  • Selected results
  • Complexity

* Course 6:

* Course 7:

  • Computing with dynamical systems with non-necessarily rationals coefficients
  • Space/time contractions for PCD Systems

* Course 8:

Course notes :

Course notes:

See course above.

Bibliography (Edition 2018-2019) :

Bibliography for first courses:

* Klaus Weihrauch. Computable Analysis: an introduction. Springer. 2000.

* http://cca-net.de/vasco/, et l'excellent “Tutorial: Computability & Complexity in Analysis” sur cette page.

* Vasco Brattka, Peter Hertling, and Klaus Weihrauch. A tutorial on computable analysis. In S. Barry Cooper, Benedikt Löwe, and Andrea Sorbi, editors, New Computational Paradigms: Changing Conceptions of What is Computable, pages 425-491. Springer, New York, 2008.

Relevant Courses

 
Universités partenaires Université Paris-Diderot
Université Paris-Saclay
ENS Cachan École polytechnique Télécom ParisTech
ENS
Établissements associés Université Pierre-et-Marie-Curie CNRS INRIA CEA