Randomized roundingWithin computer science and operations research, many combinatorial optimization problems are computationally intractable to solve exactly (to optimality). Many such problems do admit fast (polynomial time) approximation algorithms—that is, algorithms that are guaranteed to return an approximately optimal solution given any input. Randomized rounding is a widely used approach for designing and analyzing such approximation algorithms.
Générateur de nombres aléatoires matérielEn informatique, un générateur de nombres aléatoires matériel (aussi appelé générateur de nombres aléatoires physique ; en anglais, hardware random number generator ou true random number generator) est un appareil qui génère des nombres aléatoires à partir d'un phénomène physique, plutôt qu'au moyen d'un programme informatique. De tels appareils sont souvent basés sur des phénomènes microscopiques qui génèrent de faibles signaux de bruit statistiquement aléatoires, tels que le bruit thermique ou l'effet photoélectrique.
Temps de calcul pseudo-polynomialEn informatique théorique, et notamment en théorie de la complexité, un algorithme est appelé pseudo-polynomial si sa complexité en temps est un polynôme en la valeur numérique de l'entrée (mais pas nécessairement en la taille en mémoire de l'entrée). Considérons le problème du test de primalité. On peut vérifier qu'un entier naturel donné n est premier en testant qu'il n'est divisible par aucun des entiers . Cela exige divisions, de sorte que le temps pris par cet algorithme naïf est linéaire en la valeur n .
Fetch-and-addFetch And Add en informatique, désigne l'instruction d'extraction et d'ajout de processeur (FAA pour Fetch-And-Add) incrémentant atomiquement le contenu d'un emplacement de mémoire par une valeur spécifiée. Autrement dit, l'instruction d'extraction et d'ajout effectue l'opération incrémentant la valeur à l'adresse x par a (où x est une adresse de mémoire et a est une valeur quelconque), puis retourne la valeur d'origine de l'adresse x, de telle sorte que si cette opération est exécutée par un processus dans un système simultané, aucun autre processus ne verra jamais un résultat intermédiaire.
Logarithmevignette|Tracés des fonctions logarithmes en base 2, e et 10. En mathématiques, le logarithme (de logos : rapport et arithmos : nombre) de base d'un nombre réel strictement positif est la puissance à laquelle il faut élever la base pour obtenir ce nombre. Dans le cas le plus simple, le logarithme compte le nombre d'occurrences du même facteur dans une multiplication répétée : comme 1000 = 10×10×10 = 10, le logarithme en base 10 de 1000 est 3. Le logarithme de en base est noté : . John Napier a développé les logarithmes au début du .
Identités logarithmiquesCet article dresse une liste d'identités utiles lorsqu'on travaille avec les logarithmes. Ces identités sont toutes valables à condition que les réels utilisés (, , et ) soient strictement positifs. En outre, les bases des logarithmes doivent être différentes de 1. Pour toute base , on a : Par définition des logarithmes, on a : Ces trois identités permettent d'utiliser des tables de logarithme et des règles à calcul ; connaissant le logarithme de deux nombres, il est possible de les multiplier et diviser rapidement, ou aussi bien calculer des puissances ou des racines de ceux-ci.
Langage algébrique déterministeEn informatique théorique et en théorie des langages, un langage algébrique déterministe est un langage algébrique reconnu (par états finals) par un automate à pile déterministe. L'intérêt des langages déterministes est que leur analyse syntaxique se fait en temps linéaire en la longueur du mot, alors que dans un langage algébrique quelconque, la complexité est cubique, ou en tout cas se ramène à la complexité du produit matriciel, donc est en O(n2,37) où n est la longueur du mot par l'algorithme de Valiant.
DéterminismeLe déterminisme est une théorie philosophique selon laquelle chaque événement, en vertu du principe de causalité, est déterminé par les événements passés conformément aux lois de la nature. En physique, cette idée se traduit par la notion de système déterministe, c'est-à-dire un système soumis à une dynamique qui associe à chaque condition initiale un et un seul état final. On parle également de système déterministe en automatique pour désigner un système pour lequel les mêmes entrées produisent toujours exactement les mêmes sorties, par opposition à un système stochastique pour lequel les mêmes entrées peuvent produire différentes sorties.
Algorithme de Monte-CarloEn algorithmique, un algorithme de Monte-Carlo est un algorithme randomisé dont le temps d'exécution est déterministe, mais dont le résultat peut être incorrect avec une certaine probabilité (généralement minime). Autrement dit un algorithme de Monte-Carlo est un algorithme qui utilise une source de hasard, dont le temps de calcul est connu dès le départ (pas de surprise sur la durée du calcul), cependant dont la sortie peut ne pas être la réponse au problème posé, mais c'est un cas très rare.
Automate fini déterministeUn automate fini déterministe, parfois abrégé en AFD (en anglais deterministic finite automaton, abrégé en DFA) est un automate fini dont les transitions à partir de chaque état sont déterminées de façon unique par le symbole d'entrée. Un tel automate se distingue ainsi d'un automate fini non déterministe, où au contraire plusieurs possibilités de transitions peuvent exister simultanément pour un état et un symbole d'entrée donné.
