Réduction polynomialeUne réduction polynomiale est un outil d'informatique théorique, plus particulièrement de théorie de la complexité. C'est une classe particulière de réductions particulièrement importante, notamment pour le problème P = NP. Dans le cadre des langages formels pour les problèmes de décision, on dit qu'un langage est réductible en temps polynomial à un langage (noté ) s'il existe une fonction calculable en temps polynomial telle que pour tout , si et seulement si .
Théorie des représentations d'un groupe finivignette|Ferdinand Georg Frobenius, fondateur de la théorie de la représentation des groupes. En mathématiques et plus précisément en théorie des groupes, la théorie des représentations d'un groupe fini traite des représentations d'un groupe G dans le cas particulier où G est un groupe fini. Cet article traite de l'aspect mathématique et, de même que l'article de synthèse « Représentations d'un groupe fini », n'aborde que les représentations linéaires de G (par opposition aux représentations projectives ou ).
Représentation irréductibleEn mathématiques et plus précisément en théorie des représentations, une représentation irréductible est une représentation non nulle qui n'admet qu'elle-même et la représentation nulle comme sous-représentations. Le présent article traite des représentations d'un groupe. Le théorème de Maschke démontre que dans de nombreux cas, une représentation est somme directe de représentations irréductibles. Dans le cas des groupes finis, les informations liés aux représentations irréductibles sont encodées dans la table de caractères du groupe.
Hiérarchie polynomialeEn théorie de la complexité, la hiérarchie polynomiale est une hiérarchie de classes de complexité qui étend la notion de classes P, NP, co-NP. La classe PH est l'union de toutes les classes de la hiérarchie polynomiale. Il existe plusieurs définitions équivalentes des classes de la hiérarchie polynomiale. On peut définir la hiérarchie à l'aide des quantificateurs universel () et existentiel ().
Nombre d'orvignette|upright=1.2|La proportion définie par a et b est dite d'« extrême et moyenne raison » lorsque a est à b ce que est à a, soit : lorsque Le rapport a/b est alors égal au nombre d'or (phi). Le nombre d'or (ou section dorée, proportion dorée, ou encore divine proportion) est une proportion, définie initialement en géométrie comme l'unique rapport a/b entre deux longueurs a et b telles que le rapport de la somme a + b des deux longueurs sur la plus grande (a) soit égal à celui de la plus grande (a) sur la plus petite (b), ce qui s'écrit : avec Le découpage d'un segment en deux longueurs vérifiant cette propriété est appelé par Euclide découpage en « extrême et moyenne raison ».
Représentation régulièreEn mathématiques et plus précisément en théorie des groupes, les représentations régulières (gauche et droite) d'un groupe G sont les représentations de G associées aux deux actions (à gauche et à droite) de G sur lui-même par translation. Si G est un groupe fini ce sont, pour un corps fixé K, deux actions linéaires de G sur le K-espace vectoriel KG des applications de G dans K. Si G est un groupe localement compact, ce sont deux représentations continues unitaires de G sur un certain espace de Hilbert inclus dans CG.
Poids (théorie des représentations)Dans le domaine mathématique de la théorie des représentations, un poids d'une algèbre A sur un corps F est un morphisme d'algèbres de A vers F ou, de manière équivalente, une représentation de dimension un de A sur F. C'est l'analogue algébrique d'un caractère multiplicatif d'un groupe. L'importance du concept découle cependant de son application aux représentations des algèbres de Lie et donc aussi aux représentations des groupes algébriques et des groupes de Lie.
Golden rectangleIn geometry, a golden rectangle is a rectangle whose side lengths are in the golden ratio, , which is (the Greek letter phi), where is approximately 1.618. Golden rectangles exhibit a special form of self-similarity: All rectangles created by adding or removing a square from an end are golden rectangles as well. A golden rectangle can be constructed with only a straightedge and compass in four simple steps: Draw a square. Draw a line from the midpoint of one side of the square to an opposite corner.
Hardness of approximationIn computer science, hardness of approximation is a field that studies the algorithmic complexity of finding near-optimal solutions to optimization problems. Hardness of approximation complements the study of approximation algorithms by proving, for certain problems, a limit on the factors with which their solution can be efficiently approximated. Typically such limits show a factor of approximation beyond which a problem becomes NP-hard, implying that finding a polynomial time approximation for the problem is impossible unless NP=P.
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é.
