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].
Algorithme de Las VegasEn informatique, un algorithme de Las Vegas est un type d'algorithme probabiliste qui donne toujours un résultat correct ; son caractère aléatoire lui donne de meilleures performances temporelles en moyenne. Comme le suggère David Harel dans son livre d'algorithmique, ainsi que Motvani et Raghavan, le tri rapide randomisé est un exemple paradigmatique d'algorithme de Las Vegas.
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.
Classe de complexitéEn informatique théorique, et plus précisément en théorie de la complexité, une classe de complexité est un ensemble de problèmes algorithmiques dont la résolution nécessite la même quantité d'une certaine ressource. Une classe est souvent définie comme l'ensemble de tous les problèmes qui peuvent être résolus sur un modèle de calcul M, utilisant une quantité de ressources du type R, où n, est la taille de l'entrée. Les classes les plus usuelles sont celles définies sur des machines de Turing, avec des contraintes de temps de calcul ou d'espace.
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.
Algorithmically random sequenceIntuitively, an algorithmically random sequence (or random sequence) is a sequence of binary digits that appears random to any algorithm running on a (prefix-free or not) universal Turing machine. The notion can be applied analogously to sequences on any finite alphabet (e.g. decimal digits). Random sequences are key objects of study in algorithmic information theory. As different types of algorithms are sometimes considered, ranging from algorithms with specific bounds on their running time to algorithms which may ask questions of an oracle machine, there are different notions of randomness.
Hasardvignette|Les jeux de dés sont des symboles du hasard (jeux de hasard). vignette|Tyché ou Fortuna et sa corne d'abondance (fortune, hasard, en grec ancien, sort en latin) déesse allégorique gréco-romaine de la chance, des coïncidences, de la fortune, de la prospérité, de la destinée...|alt= Le hasard est le principe déclencheur d'événements non liés à une cause connue. Il peut être synonyme de l'« imprévisibilité », de l'« imprédictibilité », de fortune ou de destin.
Complexité de KolmogorovEn informatique théorique et en mathématiques, plus précisément en théorie de l'information, la complexité de Kolmogorov, ou complexité aléatoire, ou complexité algorithmique d'un objet — nombre, , chaîne de caractères — est la taille du plus petit algorithme (dans un certain langage de programmation fixé) qui engendre cet objet. Elle est nommée d'après le mathématicien Andreï Kolmogorov, qui publia sur le sujet dès 1963. Elle est aussi parfois nommée complexité de Kolmogorov-Solomonoff.
Chosen-ciphertext attackA chosen-ciphertext attack (CCA) is an attack model for cryptanalysis where the cryptanalyst can gather information by obtaining the decryptions of chosen ciphertexts. From these pieces of information the adversary can attempt to recover the hidden secret key used for decryption. For formal definitions of security against chosen-ciphertext attacks, see for example: Michael Luby and Mihir Bellare et al. A number of otherwise secure schemes can be defeated under chosen-ciphertext attack.
Sécurité sémantiqueLa sécurité sémantique est une notion de sécurité importante dans le cadre des preuves de sécurité des protocoles cryptographiques. Cette notion a été introduite en 1984 par Shafi Goldwasser et Silvio Micali. Elle est définie indépendamment du type de cryptographie du système (c’est-à-dire symétrique ou asymétrique), mais est principalement utilisée dans les preuves des schémas à clef publique. La sécurité sémantique traduit formellement le fait qu’il doit être difficile de retrouver de l’information sur le message originel en ayant accès au chiffrement de ce message et aux informations publiques du protocole.
