Calculabilité

- Savoir ce qu'est un problème, un calcul, un modèle de calcul
- Comprendre les limites de ce que peut faire un ordinateur (résultats d'incalculabilité et d'indécidabilité)
- Comprendre ce que signifie qu'un problème est difficile
- Comparer des problèmes en terme de calculabilité et de complexité

La première partie du cours explore les fondements théoriques de l’informatique, en s’appuyant sur le modèle des machines de Turing pour définir la notion de calcul et d’algorithme. Il aborde les concepts clés d’indécidabilité (comme le problème de l’arrêt) et de réduction, illustrant comment certains problèmes ne peuvent pas être résolus par un algorithme. Le cours présente également des variantes des machines de Turing (multi-rubans, non-déterminisme) et leur équivalence. Il discute des limites du calcul, notamment à travers la thèse de Church-Turing.

La seconde partie introduit les concepts fondamentaux de la complexité algorithmique, en se concentrant sur l'analyse des ressources (temps, espace) nécessaires pour résoudre des problèmes. Il définit les classes de complexité comme P (problèmes solubles en temps polynomial) et NP (problèmes vérifiables en temps polynomial), et explore la question ouverte majeure P = NP ?. Le cours aborde également les notions de réduction polynomiale, de NP-complétude, illustrée par des problèmes emblématiques comme SAT (satisfiabilité booléenne), et de complexité spatiale. Enfin, il présente les limites des modèles de calcul classiques et introduit brièvement la complexité probabiliste (BPP) et quantique (BQP).

Compétences de base en programmation, architecture des ordinateur et logique.