Table of Contents
## 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 coursThis course is discussing computability and complexity theory for computations over the real numbers. ## Pre-requisitesBasic notions from theoretical computer science (Turing machines, NP-completeness, P, NP, etc...) ## Course DescriptionWe 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 LanguageEnglish 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: - Complexity (end)
- Consolidated pdf: courses 1-6 |Computable analysis
* Course 7: - Computing with dynamical systems with non-necessarily rationals coefficients
- Space/time contractions for PCD Systems
* Course 8: - (cf Dynamic undecidability also for computability properties)
## 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 CoursesThe following is a coherent list of courses on the thematic 'Algorithms and Complexity'. * 2-11-1 Advanced Algorithms * 2-11-2 Randomness in Complexity * 2-12-1 Techniques in Cryptography and Cryptanalysis * 2-13-2 Error correcting codes and applications to cryptography * 2-18-1 Distributed algorithms for the networks * 2-18-2 Algorithmique distribuée avec mémoire partagée * 2-24-1 Optimisation * 2-29-1 Graph algorithms * 2-33-1 Theory of Computations * 2-34-1 Quantum information and applications * 2-38-1 Algorithms for embedded graphs |