Programme – contenu de l’UE
Tout n’est pas calculable ou décidable par ordinateur ! Nous reviendrons sur la nécessité de concevoir une notion rendant compte formellement de la notion intuitive d’algorithme, qui conduit à la production de divers modèles de calcul, dont nous rappellerons quelques exemples significatifs (machines de Turing, machines RAM, algorithmes de Markov, ...). Le concept de système de programmation acceptable, que nous expliciterons, rend compte de la classe des fonctions que ces modèles calculent et le théorème de l’isomorphisme de Rogers, que nous prouverons, fonde leur équivalence (du point de vue du calcul).
Nous donnerons des exemples d’indécidabilité. Puis, nous limitant au “monde du décidable”, nous aborderons quelques résultats de complexité structurelle, comme les théorèmes de hiérarchies, après en avoir revu les classes “usuelles” P, NP, PSPACE, ainsi que des exemples de langages complets pour chacune d’elles. Enfin, nous terminerons par une introduction à une autre notion de complexité, la complexité de Kolmogorov, et discuterons la notion d’aléatoire.
- Différents modèles de calcul. Preuve de l’isomorphisme de Rogers.
- Complexité structurelle (classes fondamentales, hiérarchies).
- Complexité de Kolmogorov.
- Indécidabilité (théorèmes de Gödel, commentaires).
Compétences acquises
Méthodologiques :
- Les différentes approches du calcul (algorithmique, logique).
- Les différents points de vue conduisant à différents types de complexité dont la comparaison éclaire la problématique et les difficultés.
Techniques :
Toutes les techniques essentielles de l’informatique fondamentale (techniques algorithmiques, énumérations, réductions ...).
Algorithmiques / codages / réductions / techniques de décidabilité et d’indécidabilité.
Secteur d’activité concerné et compétences métier acquises :
Informatique fondamentale et métiers de la recherche.
| 
