APM_5OD23_TA - Théorie de la complexité (TC)

Ce cours s'appuie sur les problèmes de graphes pour présenter la Théorie de la Complexité. La complexité algorithmique étudie la difficulté intrinsèque des problèmes; en particulier vis-à-vis du temps nécessaire à leur résolution.Nous faisons une introduction à l'étude des classes de complexité; en s'appuyant sur divers problèmes d'optimisation combinatoire; principalement de graphes. A la fin du cours les élèves sauront évaluer la difficulté d'un problème de recherche opérationnelle et déterminer le type de résolution approprié: une méthode exacte pour un problème 'facile' et; en général; une méthode approchée pour un problème 'difficile'.Nous ferons une étude détaillée des classes P et NP. Les problèmes calculables en temps polynomial déterministe forment la classe P. La classe NP contient la classe P et est constituée de problèmes dont la solution est vérifiable en temps polynomial; mais la trouver peut demander un temps exponentiel. Ces deux classes contiennent des milliers de problèmes de la théorie des graphes; de logique; des automates et d'autres domaines.