Remerciez-le!

Remerciez @Admin pour avoir partagé cet document gratuitement, de la manière la plus simple, en partageant sur les réseaux sociaux.

Theorie de la complexite Théorie de la complexité informatique théorique La théorie de la complexité est un domaine des mathématiques et plus précisément de l'informatique théorique qui étudie formellement la quantité de ressources en temps et en espace n

Théorie de la complexité informatique théorique La théorie de la complexité est un domaine des mathématiques et plus précisément de l'informatique théorique qui étudie formellement la quantité de ressources en temps et en espace nécessaire pour la résolution de problèmes au moyen de l'exécution d'un algorithme Il s'agit donc d'étudier la di ?culté intrinsèque de problèmes posés mathématiquement Sommaire Introduction Problème algorithmique Dé ?nition o Exemple de problème o Réponse algorithmique o Complexité d'un problème algorithmique o De l'existence à la décision Modèle de calcul Complexité en temps et en espace o Les quatre familles de classes de complexité en temps et en espace Classes de complexité o Classes L et NL o Classe P o Classe NP et classe Co-NP complémentaire de NP o Classe PSPACE o Classe EXPTIME o Classe NC Nick's Class o Classes probabilistes o Autres classes o Inclusions des classes o Problèmes C-complets ou C-di ?ciles ? Dé ?nition ? Exemples o Réduction de problèmes Problèmes ouverts en théorie de la complexité o Le problème ouvert P NP o Autres problèmes Notes Bibliographie Voir aussi o Articles connexes o Liens externes Introduction CUn algorithme répond à un problème Il est composé d'un ensemble d'étapes simples nécessaires à la résolution dont le nombre varie en fonction du nombre d'éléments à traiter D'autre part plusieurs algorithmes peuvent répondre à un même problème Pour savoir quelle méthode est plus e ?cace il faut les comparer Pour cela on utilise une mesure que l'on appelle la complexité qui représente le nombre d'étapes qui seront nécessaires pour résoudre le problème pour une entrée de taille donnée La théorie de la complexité s'attache à conna? tre la di ?culté ou la complexité d'une réponse par algorithme à un problème dit algorithmique posé de façon mathématique Pour la dé ?nir il faut présenter les concepts de problèmes algorithmiques de réponses algorithmiques aux problèmes et la complexité des problèmes algorithmiques Problème algorithmique Dé ?nition Un problème algorithmique est un problème posé de façon mathématique c'est- à-dire qu'il est énoncé rigoureusement dans le langage des mathématiques ?? le mieux étant d'utiliser le calcul des prédicats Il comprend des hypothèses des données et une question On distingue deux types de problèmes les problèmes de décision ils posent une question dont la réponse est oui ou non les problèmes d'existence ou de recherche d'une solution ils comportent une question ou plutôt une injonction de la forme trouver un élément tel que ? ? dont la réponse consiste à fournir un tel élément La théorie de la complexité étudie principalement mais pas uniquement les problèmes de décisions Exemple de problème Un exemple de problème de décision est Etant donné un entier n celui-ci est-il premier Réponse algorithmique Dans chaque catégorie de problèmes ci-dessus on dit qu'un problème a une réponse algorithmique si sa réponse peut être fournie par un algorithme Un problème est décidable s'il s'agit d'un problème de décision ?? donc d'un problème dont la réponse est soit oui soit non ?? et si sa réponse