Objectifs
Présenter, d’un point de vue théorique, les limites des capacités des ordinateurs, les limites entre problèmes accessibles et inaccessibles, et les limites inhérentes à l’informatique. Cette étude porte, non sur la programmation, mais sur les programmes eux-mêmes.
Programme
- Les différents modèles de calcul : machines à registres, fonctions récursives, machines de Turing; présentation du concept de calculabilité algorithmique.
- Notion d’algorithme universel : ensembles énumérables et décidables.
- Problèmes algorithmiquement indécidables; le théorème de Rice; problèmes indécidables en mathématiques.
- Le théorème de Gödel.
- Introduction à la théorie des problèmes NP–complets, i.e. « pratiquement indécidables ».
Bibliographie
- Introduction à la calculabilité, P. Wolper, [InterÉditions]
- Le langage des machines, R. Floyd et R. Biegel, [InternationalThomsonPublishing]
- Calculabilité et décidabilité, une introduction, J. M. Autebert, [Masson]
- Godel Escher Bach, Les brins d’une guirlande éternelle, D. Hofstadter, [InterÉditions]
Annales d’examens
Travaux dirigés
- Ensembles dénombrables et non dénombrables, numérotations
- Fonction universelle; machine à registres
- Transformation de programmes
- Fonctions récursives
- Machines de Turing
- Décidabilité et Machines de Turing
- Ensembles décidables, ensembles énumérables
- Réels calculables
- Réductions polynomiales, problèmes NP-complets
Devoirs
Wikipedia
