Table of Contents
Cours 2.33.32.33.3 Computing over the reals: models, computability, complexity (24h, 3ECTS)Responsable: Olivier Bournez, Professeur Ecole polytechnique. Thursday, from 12h45 to 15h45. Room 1004. 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 lecture is on Thursday 16th September 2021 * No lecture on November 4th 2021 * Exam on November 25th 2021, 12h45. VERSION 2021The course will be done on blackboard. Some course notes will be available and put online at the end of each course. * Lecture 1:
* Lecture 2:
* Lecture 3:
* Lecture 4:
Bibliography for 4 first courses: * Klaus Weihrauch. Computable Analysis: an introduction. Springer. 2000. * http://cca-net.de/vasco/, an the excellent “Tutorial: Computability & Complexity in Analysis” on this web 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. * Lecture 5:
* Lecture 6:
* Lecture 7:
Notes: part II (updated)
* Lecture 8:
+ Bibliography: - Blum, L., BLUM, L. A., Cucker, F., Shub, M., & Smale, S. (1998). Complexity and real computation. Springer Science & Business Media. - Poizat, B. (1995). Les petits cailloux (Vol. 995). Lyon: Aléas. - Koiran, P. (1994). Computing over the reals with addition and order. Theoretical Computer Science, 133(1), 35-47. - Koiran, P. (1997). A weak version of the Blum, Shub, and Smale model. Journal of Computer and System Sciences, 54(1), 177-189. BELOW IS THE PAGE OF 2018Course content in 2018 (2021 will be different) :The course will be done on blackboard. Some course notes will be available and put online at the end of each course. * Lecture 1:
* Lecture 2:
* Lecture 3:
* Lecture 4:
* Lecture 5:
* Lecture 6:
* Lecture 7:
* Lecture 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 (version 2018)The 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 |