| Bloc 1 (22-23 août) - Introduction, Récursivité/Induction, Calcul propositionnel. |
 Cours 1 |
Globalement: Introduction, Récursivité/Induction, Calcul propositionnel.
|
|
 Sujet de la PC1 |
|
|
| Bloc 2 (29-30 août) - Calcul propositionnel. Introduction au calcul des prédicats. |
Cours 2 |
Globalement: Calcul propositionnel: rappels, complétude fonctionnelle, théorème de compacité. Calcul des prédicats.
|
|
PC2 : preuves par résolution |
|
|
| Bloc 3 (5-6 Septembre) - Calculs des prédicats. Complétude. |
Cours 3 |
Globalement: Grands théorèmes du calcul des prédicats. Complétude.
|
|
 Enregistrement vidéo du cours du 5 septembre |
|
|
PC3 : logique du premier ordre |
|
|
| Bloc 4 (12-13 Septembre ) - Incomplétude. Introduction aux machines de Turing. |
Cours 4 |
|
|
PC4 : Machines de Turing |
|
|
| Bloc 5 (19-20 Septembre) - Machines de Turing. Modèles de Calculs. Thèse de Church-Turing. Calculabilité. |
Cours 5 |
Globalement: Machines de Turing. Modèle de Calculs. Thèse de Church-Turing. Calculabilité.
|
|
Enregistrement vidéo amphi du 19 septembre |
|
|
PC5 : Calculabilité |
|
|
| Archives PC Notée |
Archives de PC notées |
- PC 6 Notée 2018:
- PC 5 Notée 2017:
- PC 5 Notée 2016:
- PC 5 Notée 2015:
- Pour l'édition 2013, la PC notée était la PC 6, donc avec un cours de plus et une PC de plus....
- Pour l'édition 2012, les PC précédentes étaient différentes: plusieurs exercices correspondents maintenant à des exercices des PCs actuelles
-
- Pour l'édition 2011, la PC notée était la PC 6, donc avec un cours de plus et une PC de plus et les PC précédentes étaient différentes: plusieurs exercices correspondents maintenant à des exercices des PCs actuelles
- Ce cours n'existait pas auparavant.
|
|
Sujet 2019 |
|
|
Solution 2019 |
|
|
Correction du partiel 2020 |
|
|
Sujet 2021 |
|
|
Correction 2021 |
|
|
Sujet 2022 |
|
|
Correction 2022 |
|
|
| Bloc 6 (26-27 Septembre) - Calculabilité. Révisions |
Cours 6 |
Globalement:
Calculabilité.
|
|
Enregistrement vidéo de l'amphi du 26 septembre |
|
|
| Bloc 7 (10-11 Octobre) - Preuve du théorème d'incomplétude. Introduction à la complexité |
Cours 7 |
Globalement:
Calculabilité.
|
|
Enregistrement vidéo de l'amphi du 10 Octobre |
|
|
PC7 : pavages de Wang |
|
|
| Bloc 8 (18-19 Octobre) - NP-complétude. |
Cours 8 |
Globalement:
NP-compétude.
|
|
Enregistrement vidéo cours du 18 octobre 2023 |
|
|
PC8 : Complexité |
|
|
| Bloc 9 (25-26 Octobre) - NP-complétude: suite. |
Cours 9 |
Globalement: NP-compétude (suite).
|
|
Enregistrement vidéo du 24 Octobre 2023 |
|
|
PC9 : problèmes NP-complets |
|
|
| Bloc 10 (7-8 Novembre) - Autres complexités |
Cours 10 |
Globalement: Autres complexités.
|
|
Enregistrement vidéo de l'amphi du 7 novembre 2023 |
|
|
PC10 : Complexité et récursion |
|
|
| Compléments (Facultatifs) |
Vidéos |
Les vidéos suivantes m'ont été signalées et me semblent de très bonne qualité.
- Sur le théorème d'incomplétude:
|
|
Machines de Turing |
- Prototypes physiques de Machines de Turing
- EN VENTE
- PROTOTYPES:
- Machine de Turing mécanique réalisée par Marc RAYNAUD vidéo .
- Machine de Turing en bois réalisée par Richard Ridel
- Machines de Turing réalisée à l'ENS Lyon vidéo
- Preuves ou vidéo "amusantes" à propos de la Turing complétude de différents systèmes ou des machines de Turing
- The LEGO Turing Machine
- La machine de Turing en cartes Magic (Passe-Science)
|
