Algorithme d'approximationEn informatique théorique, un algorithme d'approximation est une méthode permettant de calculer une solution approchée à un problème algorithmique d'optimisation. Plus précisément, c'est une heuristique garantissant à la qualité de la solution qui fournit un rapport inférieur (si l'on minimise) à une constante, par rapport à la qualité optimale d'une solution, pour toutes les instances possibles du problème.
Médiane (statistiques)En théorie des probabilités et en statistiques, la médiane est une valeur qui sépare la moitié inférieure et la moitié supérieure des termes d’une série statistique quantitative ou d’une variable aléatoire réelle. On peut la définir aussi pour une variable ordinale. La médiane est un indicateur de tendance centrale. Par comparaison avec la moyenne, elle est insensible aux valeurs extrêmes mais son calcul est un petit peu plus complexe. En particulier, elle ne peut s’obtenir à partir des médianes de sous-groupes.
Geometric medianIn geometry, the geometric median of a discrete set of sample points in a Euclidean space is the point minimizing the sum of distances to the sample points. This generalizes the median, which has the property of minimizing the sum of distances for one-dimensional data, and provides a central tendency in higher dimensions. It is also known as the 1-median, spatial median, Euclidean minisum point, or Torricelli point. The geometric median is an important estimator of location in statistics, where it is also known as the L1 estimator (after the L1 norm).
Approximation diophantiennevignette|Meilleurs approximations rationnelles pour les nombres irrationnels Π (vert), e (bleu), φ (rose), √3/2 (gris), 1/√2 (rouge) et 1/√3 (orange) tracées sous forme de pentes y/x avec des erreurs par rapport à leurs vraies valeurs (noirs) par CMG Lee. En théorie des nombres, l'approximation diophantienne, qui porte le nom de Diophante d'Alexandrie, traite de l'approximation des nombres réels par des nombres rationnels.
Problème du sac à dosEn algorithmique, le problème du sac à dos, parfois noté (KP) (de l'anglais Knapsack Problem) est un problème d'optimisation combinatoire. Ce problème classique en informatique et en mathématiques modélise une situation analogue au remplissage d'un sac à dos. Il consiste à trouver la combinaison d'éléments la plus précieuse à inclure dans un sac à dos, étant donné un ensemble d'éléments décrits par leurs poids et valeurs.
Schéma d'approximation en temps polynomialEn informatique, un schéma d'approximation en temps polynomial (en anglais polynomial-time approximation scheme, abrégé en PTAS) est une famille d'algorithmes d'approximation pour des problèmes d'optimisation combinatoire. On dit aussi plus simplement schéma d'approximation polynomial. Le plus souvent, les problèmes d'optimisation combinatoire considérés sont NP-difficiles. Plusieurs variantes des PTAS existent : des définitions plus restrictives comme les EPTAS et FPTAS, ou d'autres qui reposent sur les algorithmes probabilistes comme les PRAS et FPRAS.
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.
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.
Inégalité de Bienaymé-TchebychevEn théorie des probabilités, l'inégalité de Bienaymé-Tchebychev, est une inégalité de concentration permettant de montrer qu'une variable aléatoire prendra avec une faible probabilité une valeur relativement lointaine de son espérance. Ce résultat s'applique dans des cas très divers, nécessitant la connaissance de peu de propriétés (seules l'espérance et la variance doivent être connues), et permet de démontrer la loi faible des grands nombres.
Quantilevignette|Densité de probabilité d'une loi normale de moyenne μ et d'écart-type σ. On montre ici les trois quartiles Q1, Q2, Q3. L'aire sous la courbe rouge est la même dans les intervalles (−∞,Q1), (Q1,Q2), (Q2,Q3), et (Q3,+∞). La probabilité d'être dans chacun de ces intervalles est de 25%. En statistiques et en théorie des probabilités, les quantiles sont les valeurs qui divisent un jeu de données en intervalles de même probabilité égale. Il y a donc un quantile de moins que le nombre de groupes créés.
