Vertex coverIn graph theory, a vertex cover (sometimes node cover) of a graph is a set of vertices that includes at least one endpoint of every edge of the graph. In computer science, the problem of finding a minimum vertex cover is a classical optimization problem. It is NP-hard, so it cannot be solved by a polynomial-time algorithm if P ≠ NP. Moreover, it is hard to approximate – it cannot be approximated up to a factor smaller than 2 if the unique games conjecture is true. On the other hand, it has several simple 2-factor approximations.
Méthodes de points intérieursvignette|Visualisation de la méthode des points intérieur : le chemin reste à l’intérieur du polyèdre. vignette|Visualisation de la méthode du simplexe : le chemin suit les arêtes du polyèdre vignette|Visualisation de la méthode par ellipsoïde : l’ellipse se rétrécit Les méthodes de points intérieurs forment une classe d’algorithmes qui permettent de résoudre des problèmes d’optimisation mathématique.
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é.
Méthode de JacobiLa méthode de Jacobi, due au mathématicien allemand Karl Jacobi, est une méthode itérative de résolution d'un système matriciel de la forme Ax = b. Pour cela, on utilise une suite x qui converge vers un point fixe x, solution du système d'équations linéaires. On cherche à construire, pour x donné, la suite x = F(x) avec . où est une matrice inversible. où F est une fonction affine. La matrice B = MN est alors appelée matrice de Jacobi.
Morphism of schemesIn algebraic geometry, a morphism of schemes generalizes a morphism of algebraic varieties just as a scheme generalizes an algebraic variety. It is, by definition, a morphism in the category of schemes. A morphism of algebraic stacks generalizes a morphism of schemes. By definition, a morphism of schemes is just a morphism of locally ringed spaces. A scheme, by definition, has open affine charts and thus a morphism of schemes can also be described in terms of such charts (compare the definition of morphism of varieties).
Ellipsoïde de BesselL'ellipsoïde de Bessel (encore appelé Bessel 1841) est un ellipsoïde de référence utilisé pour l'Europe. Friedrich Wilhelm Bessel l'a calculé en 1841 à partir d'un important recueil de données topographiques à travers l'Europe (incluant la Russie) et l'Inde. Sa conception repose au total sur la longueur de dix arcs de méridien et 38 mesures précises de latitudes et longitudes. Les dimensions de cet ellipsoïde furent exprimées (conformément aux procédés de calcul numérique de l'époque) par leur logarithme.
Hayford ellipsoidThe Hayford ellipsoid is a geodetic reference ellipsoid, named after the US geodesist John Fillmore Hayford (1868–1925), which was introduced in 1910. The Hayford ellipsoid was also referred to as the International ellipsoid 1924 after it had been adopted by the International Union of Geodesy and Geophysics IUGG in 1924, and was recommended for use all over the world. Many countries retained their previous ellipsoids. The Hayford ellipsoid is defined by its semi-major axis a = 6378388.000m and its flattening f = 1:297.
Séparation et évaluationUn algorithme par séparation et évaluation, ou branch and bound en anglais, est une méthode générique de résolution de problèmes d'optimisation combinatoire. Cet algorithme a été introduit par Ailsa Land et Alison Harcourt (Doig) en 1960. L'optimisation combinatoire consiste à trouver un point minimisant une fonction, appelée coût, dans un ensemble dénombrable. Une méthode naïve pour résoudre ce problème est d'énumérer toutes les solutions du problème, de calculer le coût pour chacune, puis de donner le minimum.
Écriture bicaméraleUne écriture bicamérale est une écriture comprenant des lettres minuscules et des lettres capitales. Plus précisément, elle oppose deux œils de format (ou « casse ») — et parfois de tracé — différents pour chaque caractère. Par opposition, une écriture dans laquelle il n’existe pas une telle opposition est dite monocamérale ou unicamérale. On appelle les lettres des minuscules, tandis que les lettres d’un format plus grand, utilisées dans certains cas régis par la grammaire et l’orthotypographie, sont les majuscules (à ne pas confondre avec capitales).
DimensionLe terme dimension, du latin dimensio « action de mesurer », désigne d’abord chacune des grandeurs d’un objet : longueur, largeur et profondeur, épaisseur ou hauteur, ou encore son diamètre si c'est une pièce de révolution. L’acception a dérivé de deux façons différentes en physique et en mathématiques. En physique, la dimension qualifie une grandeur indépendamment de son unité de mesure, tandis qu’en mathématiques, la notion de dimension correspond au nombre de grandeurs nécessaires pour identifier un objet, avec des définitions spécifiques selon le type d’objet (algébrique, topologique ou combinatoire notamment).
