Transducteur finiEn informatique théorique, en linguistique, et en particulier en théorie des automates, un transducteur fini (appelé aussi transducteur à états finis par une traduction littérale de l'anglais finite state transducer) est un automate fini avec sorties. C'est une extension des automates finis. Ils opèrent en effet sur les mots sur un alphabet d'entrée et, au lieu de simplement accepter ou refuser le mot, ils le transforment, de manière parfois non déterministe, en un ou plusieurs mots sur un alphabet de sortie.
Forme quadratique binaireEn mathématiques, une forme quadratique binaire est une forme quadratique — c'est-à-dire un polynôme homogène de degré 2 — en deux variables : Les propriétés d'une telle forme dépendent de façon essentielle de la nature des coefficients a, b, c, qui peuvent être par exemple des nombres réels ou rationnels ou, ce qui rend l'étude plus délicate, entiers. Fermat considérait déjà des formes quadratiques binaires entières, en particulier pour son théorème des deux carrés.
Vecteur isotropeEn mathématiques, un vecteur isotrope pour une forme bilinéaire f est un vecteur x tel que f(x, x) = 0. Soient E un espace vectoriel et f une forme bilinéaire symétrique sur E. On dit qu'un vecteur x de E est isotrope (pour f, ou pour la forme quadratique associée) si f(x, x) = 0. L'ensemble des vecteurs isotropes est appelé le cône isotrope. Il contient le noyau de f. Au cône isotrope, on associe une quadrique projective. La forme bilinéaire est dite définie — et la forme quadratique est dite anisotrope — si 0 est son seul vecteur isotrope.
Alphabet (formal languages)In formal language theory, an alphabet, sometimes called a vocabulary, is a non-empty set of indivisible symbols/glyphs, typically thought of as representing letters, characters, digits, phonemes, or even words. Alphabets in this technical sense of a set are used in a diverse range of fields including logic, mathematics, computer science, and linguistics. An alphabet may have any cardinality ("size") and depending on its purpose maybe be finite (e.g., the alphabet of letters "a" through "z"), countable (e.
Definite matrixIn mathematics, a symmetric matrix with real entries is positive-definite if the real number is positive for every nonzero real column vector where is the transpose of . More generally, a Hermitian matrix (that is, a complex matrix equal to its conjugate transpose) is positive-definite if the real number is positive for every nonzero complex column vector where denotes the conjugate transpose of Positive semi-definite matrices are defined similarly, except that the scalars and are required to be positive or zero (that is, nonnegative).
Forme bilinéaireEn mathématiques, plus précisément en algèbre linéaire, une forme bilinéaire est une application qui à un couple de vecteurs associe un scalaire, et qui a la particularité d'être linéaire en ses deux arguments. Autrement dit, étant donné un espace vectoriel V sur un corps commutatif K, il s'agit d'une application f : V × V → K telle que, pour tous et tous , Les formes bilinéaires sont naturellement introduites pour les produits scalaires.
Automate quantiqueEn informatique quantique et en informatique théorique, un automate fini quantique est une généralisation des automates finis où un mot est accepté selon le résultat d'une certaine mesure. Il existe plusieurs modèles des automates finis quantiques ; le plus restrictif est celui des automates dits « measure-once » de ; un autre est celui des automates « measure-many » de . Ces deux modèles sont très différents l'un de l’autre ; le modèle « measure-once » se rapproche plus de la théorie classique des automates finis.
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.
P/polyEn informatique théorique, plus précisément en théorie de la complexité, P/poly est la classe de problèmes de décision décidés par une famille de circuits booléens de tailles polynomiales. Cette classe a été introduite par Karp et Lipton en 1980. Cette classe est importante, car comme P est incluse dans P/poly, si on démontre que NP ⊈ P/poly, alors on résout le problème ouvert P est différent de NP. Il y a deux définitions équivalentes, la première donnée avec le modèle de calcul des circuits booléens, l'autre avec des machines de Turing.
Nombre complexe déployéEn mathématiques, les nombres complexes déployés ou fendus forment un anneau commutatif non-intègre, extension des nombres réels définis de manière analogue aux nombres complexes (usuels). La différence-clef entre les deux est que la multiplication des nombres complexes (usuels) respecte la norme euclidienne standard (carrée) : sur alors que la multiplication des nombres complexes déployés, quant à elle, respecte la norme de Minkowski ou norme lorentzienne (carrée) Les nombres complexes déployés ont beaucoup d'autres noms, voir la section des synonymes ci-dessous.
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.
Circuit complexityIn theoretical computer science, circuit complexity is a branch of computational complexity theory in which Boolean functions are classified according to the size or depth of the Boolean circuits that compute them. A related notion is the circuit complexity of a recursive language that is decided by a uniform family of circuits (see below). Proving lower bounds on size of Boolean circuits computing explicit Boolean functions is a popular approach to separating complexity classes.
