Arbre splayUn arbre splay (ou arbre évasé) est un arbre binaire de recherche auto-équilibré possédant en outre la propriété que les éléments auxquels on a récemment accédé (pour les ajouter, les regarder ou les supprimer) sont rapidement accessibles. Ils disposent ainsi d'une complexité amortie en O(log n) pour les opérations courantes comme insertion, recherche ou suppression. Ainsi dans le cas où les opérations possèdent une certaine structure, ces arbres constituent des bases de données ayant de bonnes performances, et ceci reste vrai même si cette structure est a priori inconnue.
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.
Many-one reductionIn computability theory and computational complexity theory, a many-one reduction (also called mapping reduction) is a reduction which converts instances of one decision problem (whether an instance is in ) to another decision problem (whether an instance is in ) using an effective function. The reduced instance is in the language if and only if the initial instance is in its language . Thus if we can decide whether instances are in the language , we can decide whether instances are in its language by applying the reduction and solving .
Dual normIn functional analysis, the dual norm is a measure of size for a continuous linear function defined on a normed vector space. Let be a normed vector space with norm and let denote its continuous dual space. The dual norm of a continuous linear functional belonging to is the non-negative real number defined by any of the following equivalent formulas: where and denote the supremum and infimum, respectively.
Espace séparableEn mathématiques, et plus précisément en topologie, un espace séparable est un espace topologique contenant un sous-ensemble dense et au plus dénombrable, c'est-à-dire contenant un ensemble fini ou dénombrable de points dont l'adhérence est égale à l'espace topologique tout entier. espace à base dénombrable Tout espace à base dénombrable est séparable. La réciproque est fausse, mais : Tout espace pseudométrisable séparable est à base dénombrable.Beaucoup d'espaces usuels sont de ce type.
Espace polonaisEn mathématiques, un espace métrisable à base dénombrable (ou séparable, cela revient au même pour un espace métrisable) est un espace polonais si sa topologie peut être définie par une distance qui en fait un espace complet. Tout espace compact métrisable, tout sous-espace fermé ou ouvert d'un espace polonais, tout produit dénombrable d'espaces polonais, tout espace de Banach séparable est un espace polonais. Cette terminologie a été introduite par le groupe Bourbaki, dans le volume sur la topologie générale de ses Éléments de mathématique.
Partition binaire de l'espacethumb|Partition binaire de l'espace (haut) et arbre BSP correspondant (bas). L'espace contient des segments {A, B1, B2, C1, C2, D1, D2, D3}. Le nœud racine contient le segment A ; les deux sous-arbres correspondent aux zones de part et d'autre de A. thumb|Partition binaire d'un espace à trois dimensions pour la construction d'un arbre k-d. La partition binaire de l'espace (binary space partitioning ou BSP) est un système utilisé pour diviser l'espace en zones convexes.
Métrique (physique)En relativité restreinte et en relativité générale, une métrique est un invariant relativiste infinitésimal ayant la dimension d'une longueur. Mathématiquement, il s'agit d'un tenseur métrique relatif à la variété différentielle représentant l'espace-temps physique. En relativité générale, une métrique dans un référentiel contient toutes les informations sur la gravitation telle qu'elle y est perçue. Une métrique d'espace-temps s'exprime sous la forme d'une somme algébrique de carrés de formes différentielles linéaires.
Distance de TchebychevLa distance de Tchebychev, distance de Chebyshev ou ∞-distance, est la distance entre deux points donnée par la différence maximale entre leurs coordonnées sur une dimension. La distance de Tchebychev tient son nom du mathématicien russe Pafnouti Tchebychev. Entre deux points A et B, de coordonnées respectives et , la distance de Tchebychev est définie par : Autrement dit : c'est la distance associée à la norme « infini ». La distance de Tchebychev est équivalente à la d'ordre infini.
