Complexité des problèmes et des algorithmes
Supports pédagogiques, travaux dirigés, applications et sujets d'évaluation consacrés à l'analyse de la complexité algorithmique et à la complexité des problèmes.
Cours
Complexité des algorithmes et des problèmes — P, NP et NP-complétude
Support de cours · 41 pages · 2026. Notions fondamentales, calcul de complexité, récurrences, classes de problèmes et satisfiabilité.
Travaux dirigés (TD)
TD 1 — Complexité
Algorithmes de graphes, Kruskal, Prim, Dijkstra, Bellman-Ford, 2-SAT, chemins et cycles hamiltoniens.
Travaux pratiques (TP)
Application SAT — Sécurité d'un réseau informatique
Modélisation booléenne de mécanismes pare-feu, VPN et IDS · exercice et correction.
Application SAT — Contrôle d'accès à une salle serveur
Contraintes sur badge, biométrie et autorisation administrateur · exercice et correction.
Ressources et évaluations
Devoir de niveau — 2022–2023
Notations grand O, complexité des problèmes et analyse d'algorithmes de graphes.
Devoir de niveau — 2023–2024
Classes de complexité, SAT, tri par insertion et problème des huit reines.