Fondements de l'Informatique:

 Logique, modèles, calculs

INF 412







Recent Changes- Printable Version - Search:



 

LES EDITIONS 2016 ET SUIVANTES SERONT SUR MOODLE

Accès direct:

Enseignants:

  • Amphis: Amphi Gay-Lussac. Les mercredi (sauf séance 5) de 10h30 à 12h00. A partir du 26 Août 2015.
  • Petites Classes (TDs): Les mecredi de 13h30 à 15h30, ou de 15h45 à 17h45. SAUF PC 5 qui aura lieu de 10h30 à 12h30.

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.

Edit - History - Print - Recent Changes - Search - Edit menu - Private
Page last modified on March 30, 2016, at 10:55 AM