En informatique théorique, qui étudie formellement la quantité de ressources (temps, espace mémoire, etc.) dont a besoin un algorithme pour résoudre un problème algorithmique.
Il s'agit donc d'étudier la difficulté intrinsèque des problèmes, de les organiser par classes de complexité et d'étudier les relations entre les classes de complexité.
2 types de problèmes:
problèmes de décision : ils posent une question dont la réponse est oui ou non
problèmes de recherche d'une solution :
Comportent une question ou plutôt une injonction de la forme « renvoyer un élément tel que… » dont la réponse consiste à fournir un tel élément;
Il s'agit donc d'un problème fonctionnel
La théorie de la complexité étudie principalement (mais pas uniquement) les problèmes de décision
Instance:
la donnée d'un problème s'appelle une instance.
Une instance du problème du voyageur de commerce est la donnée de villes et de distances séparant les villes.
Comme on mesure la complexité en fonction de la taille d'une instance, la représentation (le codage) d'une instance joue un rôle important.
Par exemple, un entier comme 13 peut être représenté en unaire (IIIIIIIIIIIII) ou en binaire (1101).
En unaire, la taille de l'instance 13 est 13
En binaire, la taille de l'instance est 4 (car il y a 4 chiffres dans 1101)
Traduction de la recherche à la décision:
Un problème de recherche peut parfois être transformé en un problème de décision équivalent
L'équivalence de ces deux problèmes doit être démontrée
Représentation: Si le problème n'a pas de précondition, un problème de décision peut être vu comme l'ensemble des instances positives, c'est-à-dire les instances pour lesquelles la réponse est "oui"
Réponse algorithmique:
Le nombre d'étapes dépend de la taille de l'entrée
La théorie de la complexité s'attache à connaître la difficulté (ou la complexité) intrinsèque d'un problème algorithmique, c'est-à-dire celle de l'algorithme le plus efficace pour ce problème.
On classifie les problèmes (et non pas les algorithmes) en termes de classes de complexité.
Pour les problèmes décidables, on cherche à évaluer les ressources – temps et espace mémoire – mobilisées pour obtenir algorithmiquement la réponse
Complexité d'un problème:
niveaux intermédiaires de difficulté entre les deux extrêmes
se fonde sur une estimation – théorique – des temps de calcul et des besoins en mémoire informatique
établit des hiérarchies de difficulté entre les problèmes algorithmiques, dont les niveaux sont appelés des « classes de complexité »
Mesure de la complexité:
on mesure la quantité de ressources (temps, espace, etc.) requis en fonction de la taille de l'entrée (instance)
On mesure la quantité de ressources en fonction de cette taille, qui sera notée n.
L'évaluation des ressources requises permet de répartir les problèmes dans des classes de complexité
Pour les machines déterministes, on définit la classe TIME(t(n)) des problèmes qui peuvent être résolus en temps t(n)
Le temps est le nombre de transitions sur machine de Turing ou le nombre d’opérations sur machine RAM
étant donné une liste de villes, et des distances entre toutes les paires de villes2, détermine un plus court chemin qui visite chaque ville une et une seule fois et qui termine dans la ville de départ
il s'agit d'un problème d'optimisation pour lequel on ne connait pas d'algorithme permettant de trouver une solution exacte rapidement dans tous les cas.
Plus précisément, on ne connait pas d'algorithme en temps polynomial, et sa version décisionnelle (pour une distance D, existe-t-il un chemin plus court que D passant par toutes les villes et qui termine dans la ville de départ ?) est un problème NP-complet
En 1972, Richard Karp montra que le problème de décision associé est NP-complet
Description:
étant donné n points (des « villes ») et les distances séparant chaque point, trouver un chemin de longueur totale minimale qui passe exactement une fois par chaque point et revienne au point de départ
on ne connaît pas de méthode de résolution permettant d'obtenir des solutions exactes en un temps raisonnable pour de grandes instances (grand nombre de villes) du problème
Pour 10 villes: 181 440 chemins possibles
Pour 20 villes: 6,082 × 10^16 chemins possibles
Résolution:
le calcul de tous les chemins pour 10 points est de 181 440 microsecondes soit 0,18 seconde
pour 15 points, cela représente déjà 43 589 145 600 microsecondes soit un peu plus de 12 heures
pour 20 points de 6 × 1016 microsecondes soit presque deux millénaires (1 901 années)
Pour 25 villes, le temps de calcul dépasse l'âge de l'Univers
Consiste en l'étude formelle de la quantité de ressources (par exemple de temps ou d'espace) nécessaire à l'exécution de cet algorithme.
Celle-ci ne doit pas être confondue avec la théorie de la complexité, qui elle étudie la difficulté intrinsèque des problèmes, et ne se focalise pas sur un algorithme en particulier.
Approches:
Une approche indépendante des facteurs matériels était donc nécessaire pour évaluer l'efficacité des algorithmes => d'où la naissance de l'analyse de la complexité
L'approche la plus classique est donc de calculer le temps de calcul dans le pire des cas.
La complexité en moyenne des algorithmes, à partir d'une répartition probabiliste des tailles de données, tente d'évaluer le temps moyen que l'on peut attendre de l'évaluation d'un algorithme sur une donnée d'une certaine taille.
La complexité amortie des structures de données consiste à déterminer le coût de suites d'opérations.
L'analyse lisse d'algorithme, plus récente, se veut plus proche des situations réelles en calculant la complexité dans le pire des cas sur des instances légèrement bruitées.
Exemple / Recherche dans une liste triée:
Supposons que le problème posé soit de trouver un nom dans un annuaire téléphonique qui consiste en une liste triée alphabétiquement
2 options:
Recherche linéaire : parcourir les pages dans l'ordre (alphabétique) jusqu'à trouver le nom cherché
Recherche dichotomique
Pire des cas pour l'option 1:
Le meilleur des cas est celui où le nom est le premier dans l'annuaire, le nom est alors trouvé instantanément.
Le pire des cas est celui où le nom est le dernier dans l'annuaire, le nom est alors trouvé après avoir parcouru tous les noms.
Si l'annuaire contient 30 000 noms, le pire cas demandera 30 000 étapes
La complexité dans le pire des cas de cette première méthode pour n entrées dans l'annuaire fourni est:
O(n)
ça veut dire que dans le pire des cas, le temps de calcul est de l'ordre de grandeur de n
=> il faut parcourir tous les n noms une fois
Pire des cas pour l'option 2:
Le second algorithme demandera dans le pire des cas de séparer en deux l'annuaire, puis de séparer à nouveau cette sous-partie en deux, ainsi de suite jusqu'à n'avoir qu'un seul nom.
Le nombre d'étapes nécessaire sera le nombre entier qui est immédiatement plus grand que log _{2} qui, quand n est 30 000, est 15 (car 2^{15} vaut 32 768).
La complexité (le nombre d'opérations) de ce second algorithme dans le pire des cas est alors O(log2 n) ce qui veut dire que l'ordre de grandeur du nombre d'opérations de ce pire cas est le logarithme en base 2 de la taille de l'annuaire
