Description

Logique : syntaxe des formules logiques, sémantique de vérité du calcul propositionnel, déduction naturelle (règles d’inférence, notions d’arbres et de preuves).

Calculabilité, complexité :

• 
  

  Modèle de calcul. Machines de Turing : définition, principales variantes (ruban biinfini vs infini, machine à plusieurs rubans). La machine de Turing est le modèle de calcul retenu pour l’étude des notions qui suivent.

  
  


• 
  

  Calculabilité : universalité, décidabilité, indécidabilité. Problème de l’arrêt.

  
  


• 
  

  Complexité : complexité en temps et en espace, classe P. Acceptation par certificat, classe NP. Réduction polynomiale. NP-complétude. Théorème de Cook.

  
  

Finalité

Préparer les agrégatifs à passer dans les conditions les plus favorables les épreuves écrites et orales du concours de l'agrégation d'informatique.

Public

Etre admis.e à la préparation à l'agrégation d'Informatique.