Calculabilité et Théorie de la Complexité

Définir une grammaire hors-contexte (CFG) et un automate à pile (AP).

Construire un automate à pile pour un langage hors-contexte simple (ex: {aⁿbⁿ | n ≥ 0}).

Définir formellement une machine de Turing (MT) et simuler son exécution.

Construire une machine de Turing pour un langage non hors-contexte (ex: {aⁿbⁿcⁿ | n ≥ 0}).

Énoncer la thèse de Church-Turing et définir les notions de langage récursif et récursivement énumérable.

Définir formellement le problème de l'arrêt (HALT) et démontrer son indécidabilité par diagonalisation.

Définir les classes de complexité P et NP et la notion de NP-complétude.

Expliquer le concept de réduction polynomiale et son usage pour prouver la NP-complétude d'un problème (ex: SAT vers 3-SAT).