Computational complexityIn computer science, the computational complexity or simply complexity of an algorithm is the amount of resources required to run it. Particular focus is given to computation time (generally measured by the number of needed elementary operations) and memory storage requirements. The complexity of a problem is the complexity of the best algorithms that allow solving the problem. The study of the complexity of explicitly given algorithms is called analysis of algorithms, while the study of the complexity of problems is called computational complexity theory.
Théorie de la complexité (informatique théorique)vignette|Quelques classes de complexité étudiées dans le domaine de la théorie de la complexité. Par exemple, P est la classe des problèmes décidés en temps polynomial par une machine de Turing déterministe. La théorie de la complexité est le domaine des mathématiques, et plus précisément de l'informatique théorique, qui étudie formellement le temps de calcul, l'espace mémoire (et plus marginalement la taille d'un circuit, le nombre de processeurs, l'énergie consommée ...) requis par un algorithme pour résoudre un problème algorithmique.
Classe de complexitéEn informatique théorique, et plus précisément en théorie de la complexité, une classe de complexité est un ensemble de problèmes algorithmiques dont la résolution nécessite la même quantité d'une certaine ressource. Une classe est souvent définie comme l'ensemble de tous les problèmes qui peuvent être résolus sur un modèle de calcul M, utilisant une quantité de ressources du type R, où n, est la taille de l'entrée. Les classes les plus usuelles sont celles définies sur des machines de Turing, avec des contraintes de temps de calcul ou d'espace.
Centrale à inertiethumb|Gyrolaser de forme triangulaire, technologie de gyromètre couramment utilisée dans les centrales à inertie. Une centrale à inertie ou centrale inertielle est un instrument utilisé en navigation, capable d'intégrer les mouvements d'un mobile (accélération et vitesse angulaire) pour estimer son orientation (angles de roulis, de tangage et de cap), sa vitesse linéaire et sa position. L'estimation de position est relative au point de départ ou au dernier point de recalage.
Complexité en tempsEn algorithmique, la complexité en temps est une mesure du temps utilisé par un algorithme, exprimé comme fonction de la taille de l'entrée. Le temps compte le nombre d'étapes de calcul avant d'arriver à un résultat. Habituellement, le temps correspondant à des entrées de taille n est le temps le plus long parmi les temps d’exécution des entrées de cette taille ; on parle de complexité dans le pire cas. Les études de complexité portent dans la majorité des cas sur le comportement asymptotique, lorsque la taille des entrées tend vers l'infini, et l'on utilise couramment les notations grand O de Landau.
Computational resourceIn computational complexity theory, a computational resource is a resource used by some computational models in the solution of computational problems. The simplest computational resources are computation time, the number of steps necessary to solve a problem, and memory space, the amount of storage needed while solving the problem, but many more complicated resources have been defined. A computational problem is generally defined in terms of its action on any valid input.
Cartographie et localisation simultanéesvignette|Une carte générée par le robot Darmstadt. La localisation et cartographie simultanées, connue en anglais sous le nom de SLAM (simultaneous localization and mapping) ou CML (concurrent mapping and localization), consiste, pour un robot ou véhicule autonome, à simultanément construire ou améliorer une carte de son environnement et de s’y localiser. La plupart des robots industriels sont fixes et effectuent des tâches dans un environnement connu.
Algorithmethumb|Algorithme de découpe d'un polygone quelconque en triangles (triangulation). Un algorithme est une suite finie et non ambiguë d'instructions et d’opérations permettant de résoudre une classe de problèmes. Le domaine qui étudie les algorithmes est appelé l'algorithmique. On retrouve aujourd'hui des algorithmes dans de nombreuses applications telles que le fonctionnement des ordinateurs, la cryptographie, le routage d'informations, la planification et l'utilisation optimale des ressources, le , le traitement de textes, la bio-informatique L' algorithme peut être mis en forme de façon graphique dans un algorigramme ou organigramme de programmation.
Navigation inertiellevignette|295x295px|Centrale à inertie du missile S3, Musée de l'Air et de l'Espace, Paris Le Bourget (France) La navigation inertielle (en anglais, inertial navigation system ou INS) est une technique utilisant des capteurs d’accélération et de rotation afin de déterminer le mouvement absolu d’un véhicule (avion, missile, sous-marin...). Elle a l’avantage d’être totalement autonome. La navigation inertielle a été utilisée sur les V1 et V2 allemands. Charles Stark Draper est connu comme le « père de la navigation inertielle ».
Référentiel galiléenEn physique, un référentiel galiléen (nommé ainsi en hommage à Galilée), ou inertiel, se définit comme un référentiel dans lequel le principe d'inertie (première loi de Newton) est vérifié, c'est-à-dire que tout corps ponctuel libre (i. e. sur lequel ne s’exerce aucune force ou sur lequel la résultante des forces est nulle) est en mouvement de translation rectiligne uniforme, ou au repos (qui est un cas particulier de mouvement rectiligne uniforme). Par suite, la vitesse du corps est constante (au cours du temps) en direction et en norme.
