Fondements de l'Informatique: Logique, modèles, calculs
CSC_41012_EP
INF 412
Foundations of computer science: Logic, models, computations
THE VERSION 2022 IS ONLINE!!
The document in one file in English
Chapter by chapter in English:
- 01: Introduction
- 02: Recurrence and induction
- 03: Propositional Calculus
- 04: Proofs
- 05: Predicate calculus
- 06: Models. Completeness
- 07: Turing machines
- 08: A few other models of computation
- 09: Computability
- 10: Incompleteness of arithmetic
- 11: Basic of complexity analysis of algorithms
- 12: Time complexity
- 13: Some NP-complete problems
- 14: Space complexity
- 15: Solutions of some exercises
Thanks
Many thanks to all who point out, or pointed out, some mistakes. Even comments about my english are welcome.
bournez@lix.polytechnique.fr