Problème du voyageur de commercevignette|Le problème de voyageur de commerce : calculer un plus court circuit qui passe une et une seule fois par toutes les villes (ici 15 villes). En informatique, le problème du voyageur de commerce, ou problème du commis voyageur, est un problème d'optimisation qui consiste à déterminer, étant donné un ensemble de villes, le plus court circuit passant par chaque ville une seule fois. C'est un problème algorithmique célèbre, qui a donné lieu à de nombreuses recherches et qui est souvent utilisé comme introduction à l'algorithmique ou à la théorie de la complexité.
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.
Approximation-preserving reductionIn computability theory and computational complexity theory, especially the study of approximation algorithms, an approximation-preserving reduction is an algorithm for transforming one optimization problem into another problem, such that the distance of solutions from optimal is preserved to some degree. Approximation-preserving reductions are a subset of more general reductions in complexity theory; the difference is that approximation-preserving reductions usually make statements on approximation problems or optimization problems, as opposed to decision problems.
Problème de couverture par ensemblesEn informatique théorique, le problème de couverture par ensembles (Set Cover problem en anglais) est un problème d'algorithmique particulièrement important car c'est l'un des 21 problèmes NP-complets de Karp . Étant donné un ensemble A, on dit qu'un élément e est couvert par A si e appartient à A. Étant donné un ensemble U et une famille S de sous-ensembles de U, le problème consiste à couvrir tous les éléments U avec une sous-famille de S la plus petite possible.
Dureté (matériau)La dureté d'un matériau est définie comme la résistance mécanique qu'un matériau oppose à la pénétration. Pour mesurer la dureté d'un matériau, un pénétrateur de faible déformabilité (cône ou sphère en diamant, carbure de tungstène lié au cobalt ou acier extra-dur) est enfoncé à la surface du matériau à tester avec une force connue pendant un temps donné. Plus l'empreinte laissée est petite, plus le matériau est dur. La dureté se mesure sur différentes échelles selon le type de matériau considéré.
Machine simpleOn appelle machine simple un dispositif mécanique élémentaire permettant de transformer une force de module et de direction déterminés en une force dont le module ou la direction sont différents. Selon les Anciens, il y a cinq machines simples : le levier, la poulie, le coin, le treuil et la vis sans fin. Au Livre II de ses Mécaniques, Héron d'Alexandrie a étudié chacune d'elles. La Renaissance identifie une sixième : le plan incliné. Généralement, les machines simples sont classées en six à huit types : levier ; roue ; poulie ; coin ; plan incliné vis ; engrenage ; treuil.
Oracle (machine de Turing)vignette|upright=2|Une machine de Turing avec oracle peut faire appel à une boîte noire (oracle). En théorie de la complexité ou de la calculabilité, les machines de Turing avec oracle sont une variante des machines de Turing disposant d'une boîte noire, un oracle, capable de résoudre un problème de décision en une seule opération élémentaire. En particulier, l'oracle peut résoudre en temps constant un problème indécidable comme le problème de l'arrêt.
Machine de TuringEn informatique théorique, une machine de Turing est un modèle abstrait du fonctionnement des appareils mécaniques de calcul, tel un ordinateur. Ce modèle a été imaginé par Alan Turing en 1936, en vue de donner une définition précise au concept d’algorithme ou de « procédure mécanique ». Il est toujours largement utilisé en informatique théorique, en particulier dans les domaines de la complexité algorithmique et de la calculabilité.
Indentation (matériau)L'indentation est une technique de mesure de propriétés mécanique des matériaux. Si la force et la pénétration ne sont pas enregistrées au cours de l'essai, elle ne permet que de mesurer la dureté d'un matériau. Si elles sont enregistrées et contrôlées, on parle d'indentation instrumentée. L'indentation non-instrumentée consiste à appliquer une charge, dans des conditions déterminées, à la surface du matériau, à l'aide d'un indenteur ou pénétrateur. Après l'essai, le matériau s'étant déformé, on observe une empreinte que l'on peut mesurer.
Structural integrity and failureStructural integrity and failure is an aspect of engineering that deals with the ability of a structure to support a designed structural load (weight, force, etc.) without breaking and includes the study of past structural failures in order to prevent failures in future designs. Structural integrity is the ability of an item—either a structural component or a structure consisting of many components—to hold together under a load, including its own weight, without breaking or deforming excessively.
