La théorie de la calculabilité et de la complexité est née au début du XXe siècle, dans le contexte de la crise des fondements des mathématiques, lorsque logiciens et mathématiciens ont cherché à formaliser la notion de calcul effectif et à comprendre les limites intrinsèques du raisonnement algorithmique. Ces travaux ont conduit à l’émergence de modèles formels du calcul, tels que les machines de Turing, et à l’identification de problèmes fondamentalement indécidables.
Ce cours propose une introduction aux fondements théoriques de l’informatique à travers l’étude des modèles de calcul, de la notion de calculabilité et de la complexité algorithmique. Il aborde les machines de Turing et l’équivalence entre les principaux modèles de calcul, les techniques de réduction et les problèmes indécidables, ainsi que les classes de complexité P et NP et la notion de NP-complétude.