Topic outline

  • General

    Collapse all Expand all

    • MCC : 2 notes de même poids

      • un oral dont les modalités seront précisées en début de cours
      • un contrôle terminal sur l'ensemble du cours (2h).

  • Cours

    Calculabilité (7h30)

    1. Introduction et Machines de Turing Définitions MT, configuration, acceptation, rejet, fonction calculable, langage récursivement énumérable, langage récursif
    2. Thèse de Church-Turing et codage Thèse de Church-Turing, codage raisonnable récursif et bijectif.
    3. Machines de Turing universelle et dénombrement machine de Turing universelle, ensembles dénombrables et indénombrables, diagonalisation.
    4. Indécidabilité Indécidabilité du problème de l'arrêt, notion de problème, langage associé, notion de réduction, théorème de Rice.
    5. Indécidabilité (suite) indécidabilité de MPCP et de PCP.

    Complexité (7h30)

    1. Complexité en temps déterministe définitions MT à k rubans, temps et espace de calcul, thèse de Church-Turing étendue, DTIME(f(n)), accélération linéaire.
    2. Classes de complexité en temps déterministe hiérarchie en temps déterministe, les classes P et EXP.
    3. Non déterminisme définition MT non déterministe, NTIME(f(n)), les classes NP, coNP et NEXP, certificat, hiérarchie en temps non-déterministe, padding, réduction many-one en temps polynomial, problème NP-difficile, NP-complet.
    4. NP-complétude SAT, 3SAT, théorème de Cook-Levin.
    5. NP-complétude problèmes NP-complets, CIRCUIT-SAT, Vertex-Cover, SubsetSum, CUBIC.

  • Partiels et examens

  • Ressources et bibliographie