Complexité

Code APOGÉE : MA6AY010 | 6 ECTS | Enseignants : Hervé Fournier et Bertrand Gentou
Volume horaire : 3h CM + 3h TD sur 8 semaines | Validation : CC + examen
Mutualisé avec : M1 mathématiques (MFA), M1 Mathématiques et Informatique, M1 MIC

Programme

Introduction

• Modèle de calcul, pseudo-langage
• Situer la difficulté algorithmique de certains problèmes classiques
• Exemples :
  • Temps polynomial : méthodes de tris, plus courts chemins
  • Problèmes nécessitant peu de mémoire : accessibilité de deux sommets dans un graphe
  • Problèmes nécessitant beaucoup de temps et/ou de mémoire

Formalisation des mesures de complexité

• Complexité en temps et espace
• Réductions entre problèmes : transitivité, notion de complétude, problème « représentatif » d’une difficulté algorithmique

Problèmes réputés difficiles en temps

• Problèmes difficiles en théorie et en pratique, exemples
• NP : définition (algorithmes non-déterministe, witness-checking), NP-complétude
• Théorème de Cook-Levin : SAT est NP-complet
• Exemples de problèmes NP-complets et réductions : cliques, ensembles indépendants maximaux, recouvrement des sommets d’un graphe (Vertex Cover), ordonnancement de tâches, contraintes
• Résolution pratiques de problèmes difficiles : SAT-solver pour le problème de satisfaisabilité, approches pratiques type kernelization pour les problèmes paramétrés (exemple de Vertex Cover)

Problèmes réputés difficiles en espace (et au delà)

• Espace mémoire polynomial (PSPACE) : définition et exemple (recherche de stratégie gagnante dans des jeux)
• Problèmes PSPACE-complets

Algorithmique parallèle

• Problèmes parallélisables efficacement. Exemples : implémentation des opérations arithmétiques usuelles, multiplication matricielle, matching maximal dans un graphe
• Classes de complexité parallèle et circuits (NC et AC)
• Problèmes non-parallélisables efficacement: P-complétude, exemples

Perspectives

• Comparaison des classes de complexité (efficacité comparée des approches algorithmiques), hiérarchie en temps et en espace
• Ouvertures possibles : rudiments sur les algorithmes d’approximation, algorithmes probabilistes

Bibliographie

• Arora, S. & Barak, B. (2009). Computational complexity: a modern approach. Cambridge : Cambridge University Press.
• Dasgupta, S., Papadimitriou, C. H. & Vazirani, U. V. (2008). Algorithms. New York : McGraw-Hill.
• Manber, U. (1989). Introduction to algorithms: a creative approach. Reading, MA : Addison-Wesley.