Algorithme de ShorEn arithmétique modulaire et en informatique quantique, l’algorithme de Shor est un algorithme quantique conçu par Peter Shor en 1994, qui factorise un entier naturel N en temps O et en espace . Beaucoup de cryptosystèmes à clé publique, tels que le RSA, deviendraient vulnérables si l'algorithme de Shor était un jour implanté dans un calculateur quantique pratique. Un message chiffré avec RSA peut être déchiffré par factorisation de sa clé publique N, qui est le produit de deux nombres premiers.
Matrice binaireUne matrice binaire est une matrice dont les coefficients sont soit 0, soit 1. En général ces coefficients sont les nombres de l'algèbre de Boole dans laquelle on appelle B l'ensemble constitué de deux éléments appelés valeurs de vérité {VRAI, FAUX}. Cet ensemble est aussi noté B = {1, 0} ou B = {⊤, ⊥}. On privilégie souvent la notation B = {1, 0}. Quand on programme des algorithmes utilisant ces matrices, la notation {VRAI, FAUX} peut coexister avec la notation {1, 0} car de nombreux langages acceptent ce polymorphisme.
Matrice d'incidenceEn mathématiques, et plus particulièrement en théorie des graphes, la matrice d'incidence d'un graphe est une matrice qui décrit le graphe en indiquant quels liens arrivent sur quels sommets. La matrice d'incidence est une matrice n x p, où n est le nombre de sommets du graphe et p est le nombre de liens (arêtes ou arcs). Cette matrice est définie de deux façons différentes selon que le graphe est orienté ou non orienté.
Algorithme de Primthumb|right|Arbre couvrant de poids minimum L'algorithme de Prim est un algorithme glouton qui calcule un arbre couvrant minimal dans un graphe connexe pondéré et non orienté. En d'autres termes, cet algorithme trouve un sous-ensemble d'arêtes formant un arbre sur l'ensemble des sommets du graphe initial et tel que la somme des poids de ces arêtes soit minimale. Si le graphe n'est pas connexe, alors l'algorithme détermine un arbre couvrant minimal d'une composante connexe du graphe.
Catégorie monoïdaleEn mathématiques, une catégorie monoïdale est une catégorie munie d'un bifoncteur qui généralise la notion de produit tensoriel de deux structures algébriques. Intuitivement, il s'agit de l'analogue, au niveau des catégories, de la notion de monoïde, c'est-à-dire que le bifoncteur joue le rôle d'une sorte de multiplication pour les objets de la catégorie. Une catégorie monoïdale est une catégorie munie : D'un bifoncteur appelé produit tensoriel. D'un objet I appartenant à appelé « objet unité ».
Cartesian monoidal categoryIn mathematics, specifically in the field known as , a where the monoidal ("tensor") product is the is called a cartesian monoidal category. Any with finite products (a "finite product category") can be thought of as a cartesian monoidal category. In any cartesian monoidal category, the terminal object is the monoidal unit. , a monoidal finite coproduct category with the monoidal structure given by the coproduct and unit the initial object is called a cocartesian monoidal category, and any finite coproduct category can be thought of as a cocartesian monoidal category.
Algorithme de DijkstraEn théorie des graphes, l'algorithme de Dijkstra (prononcé ) sert à résoudre le problème du plus court chemin. Il permet, par exemple, de déterminer un plus court chemin pour se rendre d'une ville à une autre connaissant le réseau routier d'une région. Plus précisément, il calcule des plus courts chemins à partir d'une source vers tous les autres sommets dans un graphe orienté pondéré par des réels positifs. On peut aussi l'utiliser pour calculer un plus court chemin entre un sommet de départ et un sommet d'arrivée.
Catégorie enrichieUne catégorie enrichie sur une catégorie monoïdale , ou -catégorie est une extension du concept mathématique de catégorie, où les morphismes, au lieu de former une classe ou un ensemble dépourvu de structure, sont des éléments de . Le concept de catégorie enrichie part de l'observation que dans de nombreuses situations, les morphismes ont une structure naturelle d'espace vectoriel ou topologique. La catégorie doit être monoïdale afin de pouvoir définir la composition des morphismes, appelés dans ce cas hom-objets au lieu de hom-sets.
Algorithme de rechercheEn informatique, un algorithme de recherche est un type d'algorithme qui, pour un domaine, un problème de ce domaine et des critères donnés, retourne en résultat un ensemble de solutions répondant au problème. Supposons que l'ensemble de ses entrées soit divisible en sous-ensemble, par rapport à un critère donné, qui peut être, par exemple, une relation d'ordre. De façon générale, un tel algorithme vérifie un certain nombre de ces entrées et retourne en sortie une ou plusieurs des entrées visées.
Algorithme probabilisteEn algorithmique, un algorithme probabiliste, ou algorithme randomisé, est un algorithme qui utilise une source de hasard. Plus précisément le déroulement de l’algorithme fait appel à des données tirées au hasard. Par exemple à un certain point de l’exécution, on tire un bit 0 ou 1, selon la loi uniforme et si le résultat est 0, on fait une certaine action A et si c'est 1, on fait une autre action. On peut aussi tirer un nombre réel dans l'intervalle [0,1] ou un entier dans un intervalle [i..j].
Objet initial et objet finalEn mathématiques, et plus particulièrement en théorie des catégories, un objet initial et un objet final sont des objets qui permettent de définir une propriété universelle. Donnons-nous une catégorie . Un objet de est dit initial si pour tout objet de , il existe une et une seule flèche de vers . De même, un objet est dit final (ou terminal) si pour tout objet , il existe une et une seule flèche de vers . En particulier, la seule flèche d'un objet initial (ou final) vers lui-même est l'identité.
ComplexificationIn mathematics, the complexification of a vector space V over the field of real numbers (a "real vector space") yields a vector space V^C over the complex number field, obtained by formally extending the scaling of vectors by real numbers to include their scaling ("multiplication") by complex numbers. Any basis for V (a space over the real numbers) may also serve as a basis for V^C over the complex numbers. Let be a real vector space.
