Geometric invariant theoryIn mathematics, geometric invariant theory (or GIT) is a method for constructing quotients by group actions in algebraic geometry, used to construct moduli spaces. It was developed by David Mumford in 1965, using ideas from the paper in classical invariant theory. Geometric invariant theory studies an action of a group G on an algebraic variety (or scheme) X and provides techniques for forming the 'quotient' of X by G as a scheme with reasonable properties.
Treillis (ensemble ordonné)En mathématiques, un treillis () est une des structures algébriques utilisées en algèbre générale. C'est un ensemble partiellement ordonné dans lequel chaque paire d'éléments admet une borne supérieure et une borne inférieure. Un treillis peut être vu comme le treillis de Galois d'une relation binaire. Il existe en réalité deux définitions équivalentes du treillis, une concernant la relation d'ordre citée précédemment, l'autre algébrique. Tout ensemble muni d'une relation d'ordre total est un treillis.
Hilbert's fourteenth problemIn mathematics, Hilbert's fourteenth problem, that is, number 14 of Hilbert's problems proposed in 1900, asks whether certain algebras are finitely generated. The setting is as follows: Assume that k is a field and let K be a subfield of the field of rational functions in n variables, k(x1, ..., xn ) over k. Consider now the k-algebra R defined as the intersection Hilbert conjectured that all such algebras are finitely generated over k.
PermutationEn mathématiques, la notion de permutation exprime l'idée de réarrangement d'objets discernables. Une permutation d'objets distincts rangés dans un certain ordre correspond à un changement de l'ordre de succession de ces objets. La permutation est une des notions fondamentales en combinatoire, c'est-à-dire pour des problèmes de dénombrement et de probabilités discrètes. Elle sert ainsi à définir et à étudier le carré magique, le carré latin, le sudoku, ou le Rubik's Cube.
Theory of computationIn theoretical computer science and mathematics, the theory of computation is the branch that deals with what problems can be solved on a model of computation, using an algorithm, how efficiently they can be solved or to what degree (e.g., approximate solutions versus precise ones). The field is divided into three major branches: automata theory and formal languages, computability theory, and computational complexity theory, which are linked by the question: "What are the fundamental capabilities and limitations of computers?".
Problème SATvignette|Une instance du Sudoku peut être transformée en une formule de logique propositionnelle à satisfaire. Une assignation des variables propositionnelles donne une grille complétée. En informatique théorique, le problème SAT ou problème de satisfaisabilité booléenne est le problème de décision, qui, étant donné une formule de logique propositionnelle, détermine s'il existe une assignation des variables propositionnelles qui rend la formule vraie. Ce problème est important en théorie de la complexité.
NP (complexité)La classe NP est une classe très importante de la théorie de la complexité. L'abréviation NP signifie « non déterministe polynomial » (« en »). Un problème de décision est dans NP s'il est décidé par une machine de Turing non déterministe en temps polynomial par rapport à la taille de l'entrée. Intuitivement, cela revient à dire qu'on peut vérifier « rapidement » (complexité polynomiale) si une solution candidate est bien solution.
