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é.
Algorithmic efficiencyIn computer science, algorithmic efficiency is a property of an algorithm which relates to the amount of computational resources used by the algorithm. An algorithm must be analyzed to determine its resource usage, and the efficiency of an algorithm can be measured based on the usage of different resources. Algorithmic efficiency can be thought of as analogous to engineering productivity for a repeating or continuous process. For maximum efficiency it is desirable to minimize resource usage.
Inégalité de ChernoffEn théorie des probabilités, l'inégalité de Chernoff permet de majorer la queue d'une loi de probabilité, c'est-à-dire qu'elle donne une valeur maximale de la probabilité qu'une variable aléatoire dépasse une valeur fixée. On parle également de borne de Chernoff. Elle est nommée ainsi en l'honneur du mathématicien Herman Chernoff. Elle est comparable à l'inégalité de Markov mais donne une borne exponentielle. Il existe de nombreux énoncés, et de nombreux cas particuliers.
Graphe dualEn théorie des graphes, le graphe dual d'un graphe plongé dans une surface est défini à l'aide des composantes de son complémentaire, lesquelles sont reliées entre elles par les arêtes du graphe de départ. Cette notion généralise celle de dualité dans les polyèdres. Il faut noter qu'un même graphe abstrait peut avoir des graphes duaux non isomorphes en fonction du plongement choisi, même dans le cas de plongements dans le plan. Un graphe (plongé) isomorphe à son dual est dit autodual.
Majorant ou minorantEn mathématiques, soient (E , ≤) un ensemble ordonné et F une partie de E ; un élément x de E est : un majorant de F s'il est supérieur ou égal, par la relation binaire définie au préalable, à tous les éléments de F : ; un minorant de F s'il est inférieur ou égal, par la relation binaire définie au préalable, à tous les éléments de F :. Si F possède un majorant x alors on dit que F est une partie majorée. Si F possède un minorant x alors on dit que F est une partie minorée.
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.
Efficacité (statistiques)En statistique, lefficacité est une mesure de la qualité d'un estimateur, d'une expérimentation ou d'un test statistique. Elle permet d'évaluer le nombre d'observations nécessaires pour atteindre un seuil : plus un estimateur est efficace, plus l'échantillon d'observations nécessaire pour atteindre un objectif de précision sera petit. Lefficacité relative de deux procédures est le rapport de leurs efficacités, bien que le concept soit plus utilisé pour le rapport de l'efficacité d'une procédure donnée et d'une procédure théorique optimale.
Loi de probabilité à plusieurs variablesvignette|Représentation d'une loi normale multivariée. Les courbes rouge et bleue représentent les lois marginales. Les points noirs sont des réalisations de cette distribution à plusieurs variables. Dans certains problèmes interviennent simultanément plusieurs variables aléatoires. Mis à part les cas particuliers de variables indépendantes (notion définie ci-dessous) et de variables liées fonctionnellement, cela introduit la notion de loi de probabilité à plusieurs variables autrement appelée loi jointe.
UncertaintyUncertainty refers to epistemic situations involving imperfect or unknown information. It applies to predictions of future events, to physical measurements that are already made, or to the unknown. Uncertainty arises in partially observable or stochastic environments, as well as due to ignorance, indolence, or both. It arises in any number of fields, including insurance, philosophy, physics, statistics, economics, finance, medicine, psychology, sociology, engineering, metrology, meteorology, ecology and information science.
Test suiteIn software development, a test suite, less commonly known as a validation suite, is a collection of test cases that are intended to be used to test a software program to show that it has some specified set of behaviors. A test suite often contains detailed instructions or goals for each collection of test cases and information on the system configuration to be used during testing. A group of test cases may also contain prerequisite states or steps, and descriptions of the following tests.
