Fondements de l'Informatique: Logique, modèles, calculs
INF 412
Intégralité du polycopié:
LA VERSION 2023 EST EN LIGNE SUR CETTE PAGE!!
MAIS CECI N'EST PAS LA PAGE OFFICIELLE. LA PAGE OFFICIELLE EST SUR MOODLE (MAIS NECESSITE UN LOGIN) !!
MAIS ICI, IL Y A AUSSI CELA POUR QUE CELA RESTE ACCESSIBLE AU RESTE DE L'UNIVERS.
Le document en un seul fichier en français
The document in one file in English
Chapitre par chapitre EN FRANCAIS:
- 01: Introduction
- 02: Récursivité et induction
- 03: Calcul propositionnel
- 04: Démonstrations
- 05: Calcul des prédicats
- 06: Modèles. Complétude
- 07: Machines de Turing
- 08: Autre modèles de calculs
- 09: Calculabilité
- 10: Incomplétude de l'arithmétique
- 11: Bases de l'analyse de complexité d'algorithmes
- 12: Complexité en temps
- 13: Quelques problèmes NP-complets
- 14: Complexité en espace mémoire
- 15: Solutions de certains exercices
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
Remerciements
Merci à tous ceux qui me signalent, ou m'ont déjà signalé des coquilles.
bournez@lix.polytechnique.fr
Thanks
Many thanks to all who point out, or pointed out, some mistakes. Even comments about my english are welcome.
bournez@lix.polytechnique.fr