Fondements de l'Informatique: Logique, modèles, calculs
CSC_41012_EP
INF 412
CONTACT
- bournez@lix.polytechnique.fr
- http://www.lix.polytechnique.fr/~bournez/i.php/Main/HomePage
- Mastodon @bournez@lipn.info
- Twitter: bournez
- YouTube: olivier bournez
MENU: clicker sur l'item à gauche.
Cette page:
Version 2024: quelques mises à jours.
NOUVEAU: ACCES MOODLE ANONYME: https://moodle.polytechnique.fr/course/view.php?id=17298
Version 2020:
Les cours de l'école polytechnique, comme ce cours sont maintenant sur moodle.
Je laisse disponible certains documents sur ces pages.
En particulier le polycopié, mis à jour (amélioré) chaque année avec les retours que l'on me fait.
AINSI QUE DES TRANSPARENTS
ET MERCI COVID'19, il y a eu par le passé des VIDEOS: VIDEOS (EDITION 2020)
Accès direct:
- Liens directs:
Enseignants:
- Responsable du cours:
(avec des TD-mens (oui, en l'état pas TD-womens..))
Description du cours
La page du catalogue relative à ce cours.
Ce cours présente les fondements de l'informatique en tant que science. Si l'idée d'utiliser des machines pour effectuer des calculs est ancienne, c'est dans les années 30 que les travaux d'Alan Turing, Alonzo Church, Kurt Goedel et d'autres ont posé les bases de ce qui allait devenir l'informatique que nous connaissons aujourd'hui.
Leurs travaux ont révélé que le raisonnement et le calcul sont intimement liés et ces bases doivent donc se comprendre dans la tradition, plus ancienne, de la logique et des fondements des mathématiques, de Peano à Zermelo en passant par Hilbert et bien d'autres. Il est remarquable que ces bases soient toujours d'actualité, malgré les progrès technologiques spectaculaires.
Alors que d'autres cours montrent comment programmer, on explicite ici le cadre de ce qui est faisable, en termes - de calculabilité : certains problèmes ne peuvent pas être résolus par une machine ; - de complexité : certains problèmes ne peuvent être résolus en un temps raisonnable.
C'est par exemple sur ces points que reposent les technologies cryptographiques et le fameux problème "P=NP" à $1.000.000.
Programme
Logique des propositions et des prédicats : Formules, modèles, satisfiabilité, validité, prouvabilité.
Théorème de complétude de Gödel. Théorèmes d'incomplétude de Gödel.
Exemples de théories: arithmétique et théorie des ensembles Modèle de calcul : machines de Turing, calculabilité, décidabilité, théorème de l'arrêt, machine universelle
Classes de complexité : P, NP, réduction de problème, NP-complétude, problèmes SAT, complexité en espace.
Plus à propos des sujets de ce cours.
Voir la page dédiée
Mais sélection de la page dédiée plus haut, en faisant un peu de publicité (non intéressée, juste pour rendre honneur à l'énergie positive et les efforts pédagogiques de leurs auteurs):
- Machines de Turing.
- EN VENTE: Machine de Turing électronique (auteur: Thierry Delattre, produit en vente). 12 états max par algorithme. Pour plus d'infos écrire à contact@thamtham.fr www.machine-de-turing.fr Twitter: thamographe
- Machine de Turing mécanique réalisée par Marc Raynaud.
- Incomplétude et théorèmes de Gödel
- Les vidéos suivantes m'ont été signalées et me semblent de très bonne qualité.
- Vidéo YouTube "ScienceEtonnante" sur "Les théorèmes d'Incomplétude de Gödel.
- Vidéo YouTube "Passe-Science" sur "Incomplétude - Passe-science #7"