Fondamentaux de la théorie de la complexité informatique EITC/IS/CCTF

Étant donné que la quantité de ressources nécessaires pour exécuter un algorithme varie avec la taille de l'entrée, la complexité est généralement exprimée sous la forme d'une fonction f(n), où n est la taille de l'entrée et f(n) est soit la complexité la plus défavorable ( la quantité maximale de ressources requises sur toutes les entrées de taille n) ou la complexité moyenne des cas (la moyenne de la quantité de ressources sur toutes les entrées de taille n). Le nombre d'opérations élémentaires requises sur une entrée de taille n est communément appelé complexité temporelle, où les opérations élémentaires sont censées prendre un temps constant sur un ordinateur particulier et ne changent que d'un facteur constant lorsqu'elles sont exécutées sur une machine différente. La quantité de mémoire requise par un algorithme sur une entrée de taille n est appelée complexité spatiale.

Le temps est la ressource la plus souvent considérée. Lorsque le terme « complexité » est utilisé sans qualificatif, il fait généralement référence à la complexité du temps.

Les unités de temps traditionnelles (secondes, minutes, etc.) ne sont pas employées dans la théorie de la complexité car elles dépendent trop de l'ordinateur choisi et de l'avancement de la technologie. Par exemple, un ordinateur d'aujourd'hui peut exécuter un algorithme beaucoup plus rapidement qu'un ordinateur des années 1960, mais cela est dû aux percées technologiques du matériel informatique plutôt qu'à une qualité inhérente de l'algorithme. L'objectif de la théorie de la complexité est de quantifier les besoins en temps inhérents aux algorithmes, ou les limitations de temps fondamentales qu'un algorithme imposerait à n'importe quel ordinateur. Ceci est accompli en comptant le nombre d'opérations de base effectuées pendant le calcul. Ces procédures sont communément appelées étapes parce qu'elles sont considérées comme prenant un temps constant sur une machine particulière (c'est-à-dire qu'elles ne sont pas affectées par la quantité d'entrée).

Une autre ressource importante est la quantité de mémoire informatique requise pour exécuter les algorithmes.

Une autre ressource souvent utilisée est la quantité d'opérations arithmétiques. Dans ce scénario, le terme «complexité arithmétique» est utilisé. La complexité temporelle est généralement le produit de la complexité arithmétique par un facteur constant si une contrainte supérieure sur la taille de la représentation binaire des nombres qui surviennent lors d'un calcul est connue.

La taille des nombres entiers utilisés lors d'un calcul n'est pas contrainte pour de nombreuses méthodes, et il est irréaliste de supposer que les opérations arithmétiques nécessitent un temps fixe. Par conséquent, la complexité temporelle, également appelée complexité binaire, peut être nettement supérieure à la complexité arithmétique. La difficulté arithmétique de calculer le déterminant d'une matrice de nn entiers, par exemple, est O(n^3) pour les techniques standards (élimination gaussienne). Étant donné que la taille des coefficients peut augmenter de manière exponentielle pendant le calcul, la complexité en bits des mêmes méthodes est exponentielle en n. Si ces techniques sont utilisées en conjonction avec l'arithmétique multi-modulaire, la complexité des bits peut être réduite à O(n^4).

La complexité binaire, en termes formels, fait référence au nombre d'opérations sur les bits nécessaires pour exécuter un algorithme. Il équivaut à la complexité temporelle à un facteur constant près dans la plupart des paradigmes de calcul. Le nombre d'opérations sur les mots machine requis par les ordinateurs est proportionnel à la complexité des bits. Pour des modèles de calcul réalistes, la complexité temporelle et la complexité binaire sont donc identiques.

La ressource qui est souvent considérée dans le tri et la recherche est le nombre de comparaisons d'entrées. Si les données sont bien organisées, c'est un bon indicateur de la complexité temporelle.

Sur toutes les entrées potentielles, compter le nombre de pas dans un algorithme est impossible. Étant donné que la complexité d'une entrée augmente avec sa taille, elle est généralement représentée en fonction de la taille de l'entrée n (en bits), et donc la complexité est une fonction de n. Pour les entrées de même taille, cependant, la complexité d'un algorithme peut varier considérablement. En conséquence, une variété de fonctions de complexité sont couramment utilisées.

La complexité dans le pire des cas est la somme de toute la complexité pour toutes les entrées de taille n, tandis que la complexité moyenne est la somme de toute la complexité pour toutes les entrées de taille n (cela a du sens, car le nombre d'entrées possibles d'une taille donnée est fini). Lorsque le terme "complexité" est utilisé sans être davantage défini, la complexité temporelle la plus défavorable est prise en compte.

La complexité dans le pire des cas et dans le cas moyen est notoirement difficile à calculer correctement. De plus, ces valeurs exactes ont peu d’application pratique car tout changement de paradigme de machine ou de calcul ferait légèrement varier la complexité. De plus, l’utilisation des ressources n’est pas importante pour les petites valeurs de n, donc la facilité de mise en œuvre est souvent plus attrayante qu’une faible complexité pour les petits n.

Pour ces raisons, la plus grande attention est accordée au comportement de la complexité pour n élevé, c'est-à-dire à son comportement asymptotique lorsque n tend vers l'infini. Par conséquent, la grande notation O est couramment utilisée pour indiquer la complexité.

Modèles informatiques

Le choix d'un modèle de calcul, qui consiste à préciser les opérations essentielles qui sont effectuées dans une unité de temps, est important pour déterminer la complexité. On parle parfois de machine de Turing multibande lorsque le paradigme de calcul n'est pas spécifiquement décrit.

Un modèle de calcul déterministe est un modèle dans lequel les états ultérieurs de la machine et les opérations à effectuer sont entièrement définis par l'état précédent. Les fonctions récursives, le calcul lambda et les machines de Turing ont été les premiers modèles déterministes. Les machines à accès aléatoire (également appelées machines RAM) sont un paradigme populaire pour simuler des ordinateurs du monde réel.

Lorsque le modèle de calcul n'est pas défini, une machine de Turing multibande est généralement supposée. Sur les machines de Turing multibandes, la complexité temporelle est la même que sur les machines RAM pour la plupart des algorithmes, bien qu'une attention considérable à la manière dont les données sont stockées en mémoire puisse être nécessaire pour atteindre cette équivalence.

Divers choix peuvent être faits à certaines étapes du calcul dans un modèle de calcul non déterministe, comme les machines de Turing non déterministes. Dans la théorie de la complexité, toutes les options réalisables sont considérées en même temps, et la complexité temporelle non déterministe est la quantité de temps nécessaire lorsque les meilleurs choix sont toujours faits. En d'autres termes, le calcul est effectué simultanément sur autant de processeurs (identiques) que nécessaire, et le temps de calcul non déterministe est le temps mis par le premier processeur pour terminer le calcul. Ce parallélisme peut être utilisé en informatique quantique en utilisant des états intriqués superposés lors de l'exécution d'algorithmes quantiques spécialisés, tels que la factorisation de Shor d'entiers minuscules par exemple.

Même si un tel modèle de calcul n'est pas actuellement praticable, il a une signification théorique, en particulier par rapport au problème P = NP, qui demande si les classes de complexité produites en utilisant le « temps polynomial » et le « temps polynomial non déterministe » comme plus petite valeur supérieure les bornes sont les mêmes. Sur un ordinateur déterministe, la simulation d'un algorithme NP nécessite un "temps exponentiel". Si une tâche peut être résolue en temps polynomial sur un système non déterministe, elle appartient à la classe de difficulté NP. Si un problème est dans NP et n'est pas plus facile que n'importe quel autre problème NP, on dit qu'il est NP-complet. Le problème du sac à dos, le problème du voyageur de commerce et le problème de satisfiabilité booléenne sont tous des problèmes combinatoires NP-complets. L'algorithme le plus connu a une complexité exponentielle pour tous ces problèmes. Si l'un de ces problèmes pouvait être résolu en temps polynomial sur une machine déterministe, alors tous les problèmes NP pourraient également être résolus en temps polynomial, et P = NP serait établi. À partir de 2017, il est largement admis que P NP , ce qui implique que les pires situations de problèmes NP sont fondamentalement difficiles à résoudre, c'est-à-dire qu'elles prennent beaucoup plus de temps que n'importe quelle période possible (décennies) étant donné des longueurs d'entrée intéressantes.

Calcul parallèle et distribué

L'informatique parallèle et distribuée consiste à répartir le traitement sur plusieurs processeurs qui fonctionnent tous en même temps. La distinction fondamentale entre les différents modèles est la méthode d'envoi des données entre les processeurs. La transmission de données entre processeurs est généralement très rapide dans le calcul parallèle, tandis que le transfert de données entre processeurs dans le calcul distribué se fait sur un réseau et est donc beaucoup plus lent.

Un calcul sur N processeurs prend au moins le quotient par N du temps qu'il prend sur un seul processeur. En réalité, étant donné que certaines sous-tâches ne peuvent pas être parallélisées et que certains processeurs peuvent avoir besoin d'attendre un résultat d'un autre processeur, cette borne théoriquement idéale ne sera jamais atteinte.

Le problème clé de la complexité est donc de développer des algorithmes pour que le produit du temps de calcul par le nombre de processeurs soit le plus proche possible du temps nécessaire pour effectuer le même calcul sur un seul processeur.

Calcul quantique

Un ordinateur quantique est un ordinateur doté d'un modèle de calcul basé sur la mécanique quantique. La thèse de Church-Turing est vraie pour les ordinateurs quantiques, ce qui implique que tout problème qu'un ordinateur quantique peut résoudre peut également être résolu par une machine de Turing. Cependant, certaines tâches pourraient théoriquement être résolues en utilisant un ordinateur quantique plutôt qu'un ordinateur classique avec une complexité temporelle nettement inférieure. Pour l'instant, c'est strictement théorique, car personne ne sait comment développer un ordinateur quantique pratique.

La théorie de la complexité quantique a été créée pour étudier les différents types de problèmes pouvant être résolus par les ordinateurs quantiques. Il est utilisé dans la cryptographie post-quantique, qui est le processus de création de protocoles cryptographiques résistants aux attaques des ordinateurs quantiques.

Complexité du problème (bornes inférieures)

L'infimum des complexités des algorithmes qui peuvent résoudre le problème, y compris les techniques non découvertes, est la complexité du problème. En conséquence, la complexité d'un problème est égale à la complexité de tout algorithme qui le résout.

En conséquence, toute complexité donnée en notation grand O représente une complexité à la fois de l'algorithme et du problème qui l'accompagne.

D'un autre côté, il est souvent difficile d'obtenir des bornes inférieures non triviales sur la complexité d'un problème, et il existe peu de stratégies pour y parvenir.

Afin de résoudre la plupart des problèmes, toutes les données d'entrée doivent être lues, ce qui prend un temps proportionnel à l'ampleur des données. En conséquence, de tels problèmes ont au moins une complexité linéaire, ou, en notation big oméga, une complexité de Ω(n).

Certains problèmes, tels que ceux du calcul formel et de la géométrie algébrique computationnelle, ont de très grandes solutions. Étant donné que la sortie doit être écrite, la complexité est limitée par la taille maximale de la sortie.

Le nombre de comparaisons requises pour un algorithme de tri a une borne inférieure non linéaire de Ω(nlogn). Par conséquent, les meilleurs algorithmes de tri sont les plus efficaces puisque leur complexité est O(nlogn). Le fait qu'il y ait n! façons d'organiser n choses conduit à cette borne inférieure. Parce que chaque comparaison divise cette collection de n ! ordres en deux morceaux, le nombre de N comparaisons nécessaires pour distinguer tous les ordres doit être 2N > n!, impliquant O(nlogn) par la formule de Stirling.

Réduire un problème à un autre problème est une stratégie courante pour obtenir des contraintes de complexité réduites.

Développement d'algorithmes

L'évaluation de la complexité d'un algorithme est un élément important du processus de conception car elle fournit des informations utiles sur les performances qui peuvent être attendues.

C'est un malentendu fréquent que, du fait de la loi de Moore, qui prédit la croissance exponentielle de la puissance informatique moderne, l'évaluation de la complexité des algorithmes deviendra moins pertinente. Ceci est incorrect car la puissance accrue permet le traitement de quantités massives de données (big data). Par exemple, tout algorithme devrait bien fonctionner en moins d'une seconde lors du tri alphabétique d'une liste de quelques centaines d'entrées, comme la bibliographie d'un livre. D'autre part, pour un million d'entrées (par exemple, les numéros de téléphone d'une grande ville), les algorithmes de base qui nécessitent des comparaisons O(n2) devraient effectuer un trillion de comparaisons, ce qui prendrait trois heures à une vitesse de 10 millions de comparaisons par seconde. Le tri rapide et le tri par fusion, en revanche, ne nécessitent que des comparaisons nlogn (comme complexité moyenne pour le premier, comme complexité dans le pire des cas pour le second). Cela produit environ 30,000,000 1,000,000 3 comparaisons pour n = 10 XNUMX XNUMX, ce qui ne prendrait que XNUMX secondes à XNUMX millions de comparaisons par seconde.

Par conséquent, l'évaluation de la complexité peut permettre l'élimination de nombreux algorithmes inefficaces avant la mise en œuvre. Cela peut également être utilisé pour affiner des algorithmes complexes sans avoir à tester toutes les variantes possibles. L'étude de la complexité permet de focaliser l'effort pour augmenter l'efficacité d'une implémentation en déterminant les étapes les plus coûteuses d'un algorithme complexe.