v2.11.0 (5518)

Cours scientifiques - CSC_41012_EP : Fondement de l'Informatique : logique, modèles, calculs

Domaine > Informatique.

Descriptif

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 sont 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.


Pas de pré requis. En revanche, ce cours est un pré-requis pour les thématiques "Algorithmique et optimisation" et "Langages, preuves, calcul" du PA Info en 3ème année.

Modalités d'évaluation : Examen sur table.


Format des notes

Numérique sur 20

Littérale/grade réduit

Pour les étudiants du diplôme Programmes d'échange internationaux

Le rattrapage est autorisé (Note de rattrapage conservée)
    L'UE est acquise si note finale transposée >= C
    • Crédits ECTS acquis : 5 ECTS

    Le coefficient de l'UE est : 10

    La note obtenue rentre dans le calcul de votre GPA.

    La note obtenue est classante.

    Pour les étudiants du diplôme Titre d’Ingénieur diplômé de l’École polytechnique

    Le rattrapage est autorisé (Note de rattrapage conservée)
      L'UE est acquise si note finale transposée >= C
      • Crédits ECTS acquis : 5 ECTS

      Le coefficient de l'UE est : 10

      La note obtenue rentre dans le calcul de votre GPA.

      La note obtenue est classante.

      Programme détaillé


      Programme

      • Logique des propositions et des prédicats : Formules, modèles, satisfiabilité, validité, prouvabilité
      • 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
      Veuillez patienter