Le cours de complexité algorithmique en 2024.
Objectifs du cours
Ce cours de première année de master a pour objectif de familiariser les étudiants d'informatique avec trois théories extrêmement riches et dont les développements récents ont été spectaculaires : la théorie de la calculabilité et de la décidabilité, la théorie de la complexité et la théorie de l'approximation.
La théorie de la programmation, qui englobe ces trois théories, cherche à répondre formellement à trois questions fondamentales posées de manière informelle :
La dématérialisation croissante et la virtualisation progressive de notre univers quotidien ont alimenté des questions fondamentales qui semblaient réservées aux logiciens et/ou aux philosophes au début du siècle dernier. La cryptographie, l'analyse numérique, l'intelligence artificielle, pour ne citer que ces domaines, ont stimulé les recherches sur la notion de calcul qui n'ont jamais été aussi vivaces qu'aujourd'hui en informatique.
La première partie du cours est consacrée à la théorie de la calculabilité et de la décidabilité. Avant même d'aborder les notions de performances et d'efficacité, il est utile de connaître la portée des ordinateurs et savoir ce que l'on peut espérer en obtenir. Cette question nous amènera à décortiquer le concept de calcul et nous verrons que tout ne peut pas être calculé, indépendamment du temps et de l'espace disponible.
La deuxième partie est dévolue à l'étude de la théorie de la complexité. C'est cette théorie qui s'inscrit naturellement dans la suite des enseignements d'algorithmique de licence. Les notions de complexité en temps et en espace ont été abordées dès la première année, formalisées en deuxième année avec l'introduction de la machine ram et sont devenues centrales en 3ème année. On sait à présent comparer l'efficacité des algorithmes grâce à leurs fonctions de complexité. Cette fois, il ne s'agit pas d'étudier de nouveaux algorithmes et leur complexité, si ce n'est pour illustrer le propos, mais d'établir une classification et une hiérarchie dans les problèmes de décision. Nous verrons que nous ne savons pas résoudre efficacement de nombreux problèmes fondamentaux.
La dernière partie est une introduction à la théorie de l'approximation. Il s'agit d'une piste naturelle pour franchir cette apparente barrière établie par la théorie de la complexité. L'idée est simple, si on ne peut pas trouver de procédé efficace pour calculer la solution d'un problème, peut-on faire mieux en relâchant nos exigences sur le résultat attendu ?
Contrôle des connaissances
Le contrôle des connaissances est constitué :
Annales des contrôles terminaux
L'absence de lien sur une session 2 s'explique par la réussite de tous les étudiants à l'ecue I231 dès la 1ère session.Documents de travail
Vous trouverez le polycopié du cours ici dans sa version pdf. La version en ligne n'est pas encore achevée (la plupart des liens ci-dessous sont encore inactivés).
Quelques fiches sont disponibles dans l'attente de rédaction des chapitres correspondants.
- ✍ Introduction
- ✍ Contradictions et théorie des ensembles
- ✍ Ensembles finis et infinis
- ✍ Modèles de calcul, algorithmes
- ✍ La machine ram
- ✍ La machine de Turing
- ✍ Calculabilité et décidabilité
- ✍ Le voyageur de commerce
- ✍ Fonctions de complexité
- ✍ Les classes P et NP
- ✍ Réduction polynomiale, classe NP-complet
- ✍ Théorème de Cook et exemples
- ✍ Approximation
Travaux pratiques
Les travaux pratiques consistent d'une part à étudier les deux problèmes suivant puis à implanter une solution (et non implémenter) en langage C puis d'écrire un simulateur pour la machine de Turing.
Bibliographie
Les deux premiers ouvrages demandent assez peu de connaissances mathématiques mais une bonne maturité pour comprendre les tenants et les aboutissants de cette théorie. La deuxième référence est également très abordable mais les démonstrations omniprésentes demandent une pratique certaine dans le domaine des mathématiques discrètes. Le dernier ouvrage est le plus difficile, les outils mathématiques sous-jacents dépassent rarement le niveau de la licence, mais ils sont très variés. La nature du sujet et les démonstrations parfois extrêmement élaborées, en font un ouvrage qui s'adresse principalement aux étudiants de master avec une bonne culture mathématique.