Diviser pour régner (informatique)thumb|652x652px|Trois étapes (diviser, régner, combiner) illustrées avec l'algorithme du tri fusion En informatique, diviser pour régner (du latin , divide and conquer en anglais) est une technique algorithmique consistant à : Diviser : découper un problème initial en sous-problèmes ; Régner : résoudre les sous-problèmes (récursivement ou directement s'ils sont assez petits) ; Combiner : calculer une solution au problème initial à partir des solutions des sous-problèmes.
Polynôme symétriqueEn mathématiques, un polynôme symétrique est un polynôme en plusieurs indéterminées, invariant par permutation de ses indéterminées. Ils jouent notamment un rôle dans les relations entre coefficients et racines. Soit A un anneau commutatif unitaire. Un polynôme Q(T, ..., T) en n indéterminées à coefficients dans A est dit symétrique si pour toute permutation s de l'ensemble d'indices {1, ..., n}, l'égalité suivante est vérifiée : Exemples Pour n = 1, tout polynôme est symétrique.
Matrice antisymétriqueEn mathématiques, et plus précisément en algèbre linéaire, une matrice antisymétrique est une matrice carrée opposée à sa transposée. Une matrice carrée A à coefficients dans un anneau quelconque est dite antisymétrique si sa transposée est égale à son opposée, c'est-à-dire si elle satisfait à l'équation : A = –A ou encore, en l'écrivant avec des coefficients sous la forme A = (ai,j), si : pour tout i et j, aj,i = –ai,j Les matrices suivantes sont antisymétriques : Le cas où la matrice est à coefficients dans un anneau de caractéristique 2 est très particulier.
Definite quadratic formIn mathematics, a definite quadratic form is a quadratic form over some real vector space V that has the same sign (always positive or always negative) for every non-zero vector of V. According to that sign, the quadratic form is called positive-definite or negative-definite. A semidefinite (or semi-definite) quadratic form is defined in much the same way, except that "always positive" and "always negative" are replaced by "never negative" and "never positive", respectively.
Complexité de la multiplication de matricesEn informatique théorique, la complexité de la multiplication de matrices est le nombre d'opérations requises pour l'opération de produit matriciel. Les algorithmes de multiplication de matrices constituent un sujet central dans les algorithmes théoriques et numériques en algèbre linéaire numérique et en optimisation, donc déterminer la complexité en temps du produit est d'une importance pratique. L'application directe de la définition mathématique de la multiplication de matrices donne un algorithme qui nécessite opérations sur le corps de base pour multiplier deux matrices d'ordre .
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.
SymétrieLa symétrie est une propriété d'un système : c'est lorsque deux parties sont semblables. L'exemple le plus connu est la symétrie en géométrie. De manière générale, un système est symétrique quand on peut permuter ses éléments en laissant sa forme inchangée. Le concept d'automorphisme permet de préciser cette définition. Un papillon, par exemple, est symétrique parce qu'on peut permuter tous les points de la moitié gauche de son corps avec tous les points de la moitié droite sans que son apparence soit modifiée.
Matrice hessienneEn mathématiques, la matrice hessienne (ou simplement le hessien ou la hessienne) d'une fonction numérique est la matrice carrée, notée , de ses dérivées partielles secondes. Etant donnée une fonction à valeurs réelles dont toutes les dérivées partielles secondes existent, le coefficient d'indice de la matrice hessienne vaut . Autrement dit, On appelle discriminant hessien (ou simplement hessien) le déterminant de cette matrice. Le terme « hessien » a été introduit par James Joseph Sylvester, en hommage au mathématicien allemand Ludwig Otto Hesse.
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.
Algorithme de sélectionEn algorithmique, un algorithme de sélection est une méthode ayant pour but de trouver le k-ième plus petit élément d'un ensemble d'objets (étant donné un ordre et un entier k). La question de la sélection est un problème essentiel en algorithmique, notamment dans la recherche du maximum, du minimum et de la médiane. Plusieurs algorithmes ont été proposés et plusieurs contextes ont été étudiés : algorithmes en ligne, complexité amortie, complexité en moyenne, ensemble d'objet particuliers etc.
