La th\u00e9orie de la complexit\u00e9 informatique est une branche de l'informatique qui \u00e9tudie les ressources n\u00e9cessaires pour r\u00e9soudre des probl\u00e8mes informatiques. Il fournit une abstraction math\u00e9matique du mat\u00e9riel informatique et une analyse des algorithmes, ce qui en fait un \u00e9l\u00e9ment essentiel dans la compr\u00e9hension et l'\u00e9valuation de l'efficacit\u00e9 informatique des algorithmes et des limites de ce que les ordinateurs peuvent faire.<\/p>\n
L\u2019\u00e9mergence de la th\u00e9orie de la complexit\u00e9 computationnelle en tant que domaine distinct remonte aux ann\u00e9es 1950 et 1960. Cependant, ses principes sous-jacents ont \u00e9t\u00e9 d\u00e9velopp\u00e9s depuis le d\u00e9but de l\u2019informatique th\u00e9orique et de la th\u00e9orie des algorithmes. L'\u00e9tape la plus importante a eu lieu en 1965 lorsque Juris Hartmanis et Richard Stearns ont propos\u00e9 les classes de complexit\u00e9 temporelle P (temps polynomial) et EXP (temps exponentiel), lan\u00e7ant ainsi l'\u00e9tude formelle de la complexit\u00e9 informatique. Leur travail leur a valu le prix Turing en 1993.<\/p>\n
La question P vs NP, l'un des probl\u00e8mes non r\u00e9solus les plus c\u00e9l\u00e8bres en informatique, a \u00e9t\u00e9 \u00e9voqu\u00e9e pour la premi\u00e8re fois par John Nash en 1955, puis formalis\u00e9e ind\u00e9pendamment par Stephen Cook et Leonid Levin en 1971. Ce probl\u00e8me, qui concerne essentiellement la relation entre les probl\u00e8mes qui peuvent \u00eatre r\u00e9solus rapidement et ceux dont les solutions peuvent \u00eatre v\u00e9rifi\u00e9es rapidement, a motiv\u00e9 une grande partie de la recherche en th\u00e9orie de la complexit\u00e9 computationnelle.<\/p>\n
La th\u00e9orie de la complexit\u00e9 informatique consiste \u00e0 mesurer la quantit\u00e9 de ressources informatiques \u2013 telles que le temps, la m\u00e9moire et la communication \u2013 n\u00e9cessaires pour r\u00e9soudre un probl\u00e8me. La complexit\u00e9 d'un probl\u00e8me est d\u00e9finie en termes de ressources requises par le meilleur algorithme possible qui r\u00e9sout le probl\u00e8me.<\/p>\n
Pour mesurer la complexit\u00e9 d'un algorithme, on d\u00e9finit g\u00e9n\u00e9ralement une taille d'entr\u00e9e (g\u00e9n\u00e9ralement le nombre de bits requis pour repr\u00e9senter l'entr\u00e9e) et d\u00e9crit la ressource en fonction de la taille d'entr\u00e9e. Les classes de complexit\u00e9 cat\u00e9gorisent les probl\u00e8mes en fonction de la quantit\u00e9 d'une ressource informatique sp\u00e9cifique requise pour les r\u00e9soudre. Des exemples de classes de complexit\u00e9 incluent P (probl\u00e8mes qui peuvent \u00eatre r\u00e9solus en temps polynomial), NP (probl\u00e8mes dont les solutions peuvent \u00eatre v\u00e9rifi\u00e9es en temps polynomial) et NP-complet (probl\u00e8mes auxquels tout probl\u00e8me NP peut \u00eatre r\u00e9duit en temps polynomial).<\/p>\n
La principale pr\u00e9occupation de la th\u00e9orie de la complexit\u00e9 informatique est de d\u00e9terminer la difficult\u00e9 inh\u00e9rente aux probl\u00e8mes informatiques, qui est souvent, mais pas toujours, exprim\u00e9e en termes de complexit\u00e9 temporelle. Un probl\u00e8me est consid\u00e9r\u00e9 comme \u00ab difficile \u00bb si le temps n\u00e9cessaire pour le r\u00e9soudre augmente rapidement \u00e0 mesure que la taille de l'entr\u00e9e augmente.<\/p>\n
La complexit\u00e9 d'un probl\u00e8me est d\u00e9termin\u00e9e par la construction de mod\u00e8les math\u00e9matiques de calcul, puis par l'analyse de ces mod\u00e8les. Le mod\u00e8le le plus courant est la machine de Turing, une machine abstraite qui manipule des symboles sur une bande de ruban adh\u00e9sif selon un ensemble fini de r\u00e8gles.<\/p>\n
Un aspect fondamental de la complexit\u00e9 informatique est le concept de \u00ab\u00a0classe\u00a0\u00bb d'un probl\u00e8me, qui est un ensemble de probl\u00e8mes de complexit\u00e9 li\u00e9e aux ressources. Comme mentionn\u00e9 pr\u00e9c\u00e9demment, P, NP et NP-complete sont des exemples de classes probl\u00e9matiques. Classer les probl\u00e8mes de cette mani\u00e8re permet de d\u00e9limiter le paysage de ce qui est r\u00e9alisable sur le plan informatique et de ce qui ne l'est pas.<\/p>\n
Classification des probl\u00e8mes<\/strong>: La th\u00e9orie de la complexit\u00e9 informatique classe les probl\u00e8mes en diff\u00e9rentes classes en fonction de leur complexit\u00e9.<\/p>\n<\/li>\n Mesure de l'utilisation des ressources<\/strong>: Il fournit une approche math\u00e9matique pour mesurer les ressources requises par un algorithme.<\/p>\n<\/li>\n Difficult\u00e9 inh\u00e9rente au probl\u00e8me<\/strong>: Il \u00e9tudie la difficult\u00e9 inh\u00e9rente aux probl\u00e8mes de calcul, quel que soit l'algorithme utilis\u00e9 pour les r\u00e9soudre.<\/p>\n<\/li>\n Limites du calcul<\/strong>: Il cherche \u00e0 d\u00e9terminer les limites de ce qui est informatiquement possible et impossible.<\/p>\n<\/li>\n \u00c9quivalence informatique<\/strong>: Il r\u00e9v\u00e8le des \u00e9quivalences informatiques en montrant comment divers probl\u00e8mes peuvent \u00eatre transform\u00e9s ou r\u00e9duits les uns dans les autres.<\/p>\n<\/li>\n<\/ol>\n Il existe diff\u00e9rentes mani\u00e8res de mesurer la complexit\u00e9 d\u2019un probl\u00e8me, et chaque type de mesure peut correspondre \u00e0 une classe de complexit\u00e9 diff\u00e9rente.<\/p>\nDiff\u00e9rents types de mesures de complexit\u00e9<\/h2>\n