Accès plus rapide que le navigateur!
30 relations: Albert R. Meyer, Algorithme probabiliste, Andreï Kolmogorov, Axiomes de Peano, États-Unis, Boris Trakhtenbrot, Complexité en moyenne des algorithmes, Dnipro, Hasard, Informatique, Institut de mathématiques Clay, Jean-Paul Delahaye, Machine de Turing, Massachusetts Institute of Technology, Pour la science, Probabilité algorithmique, Problème de l'arrêt, Problème de la décision, Problème NP-complet, Problème P ≟ NP, Problèmes du prix du millénaire, République socialiste soviétique d'Ukraine, Stephen Cook, Théorème de Cook, Théorèmes d'incomplétude de Gödel, Théorie de l'information, Théorie de la calculabilité, Théorie de la complexité (informatique théorique), Université d'État de Moscou, Université de Boston.
Albert R. Meyer
Albert Ronald da Silva Meyer (né en 1941) est professeur d'informatique au Massachusetts Institute of Technology (MIT).
Nouveau!!: Leonid Levin et Albert R. Meyer · Voir plus »
Algorithme probabiliste
En algorithmique, un algorithme probabiliste, ou algorithme randomisé, est un algorithme qui utilise une source de hasard.
Nouveau!!: Leonid Levin et Algorithme probabiliste · Voir plus »
Andreï Kolmogorov
Andreï Nikolaïevitch Kolmogorov (à Tambov – à Moscou) est un mathématicien russe et soviétique qui a apporté des contributions significatives en mathématiques, notamment en théorie des probabilités, topologie, turbulence, mécanique classique, logique intuitionniste, théorie algorithmique de l'information et en analyse de la complexité des algorithmes.
Nouveau!!: Leonid Levin et Andreï Kolmogorov · Voir plus »
Axiomes de Peano
Giuseppe Peano En mathématiques, les axiomes de Peano sont des axiomes pour l'arithmétique proposés initialement à la fin du par Giuseppe Peano, et qui connaissent aujourd'hui plusieurs présentations qui ne sont pas équivalentes, suivant la théorie sous-jacente, théorie des ensembles, logique du second ordre ou d'ordre supérieur, ou logique du premier ordre.
Nouveau!!: Leonid Levin et Axiomes de Peano · Voir plus »
États-Unis
Les États-Unis (prononcé), en forme longue les États-Unis d'AmériqueComme la plupart des pays, les États-Unis ont un nom « court » pour l'usage courant, pédagogique et cartographique, et un nom « long » pour l'usage officiel.
Nouveau!!: Leonid Levin et États-Unis · Voir plus »
Boris Trakhtenbrot
Boris Avraamovitch Trakhtenbrot (en Борис Авраамович Трахтенброт, en בועז טרכטנברוט), dont le prénom est aussi Boaz, né le dans le village de Briceva (raion de Dondușeni, en Moldavie, alors intégré au royaume de Roumanie), et mort le à Rehovot (Israël), est un informaticien théoricien, logicien et mathématicien roumain, soviétique, devenu israélien.
Nouveau!!: Leonid Levin et Boris Trakhtenbrot · Voir plus »
Complexité en moyenne des algorithmes
La complexité en moyenne d'un algorithme est la quantité d'une ressource donnée, typiquement le temps, utilisée par l'algorithme lors de son exécution pour traiter une entrée tirée selon une distribution donnée.
Nouveau!!: Leonid Levin et Complexité en moyenne des algorithmes · Voir plus »
Dnipro
Dnipro (en Дніпро) ou Dniepr (en Днепр) — jusqu'en 1926 Ekaterinoslav ou Iekaterinoslav, de 1926 à 2016 Dnipropetrovsk (retranscrit de l’ukrainien) ou Dniepropetrovsk (retranscrit du russe) — est une ville d'Ukraine et la capitale administrative de l'oblast de Dnipropetrovsk.
Nouveau!!: Leonid Levin et Dnipro · Voir plus »
Hasard
jeux de hasard). alt.
Nouveau!!: Leonid Levin et Hasard · Voir plus »
Informatique
bibliothèque d'Art et d'Archéologie de Genève (2017). L'informatique est un domaine d'activité scientifique, technique, et industriel concernant le traitement automatique de l'information numérique par l'exécution de programmes informatiques hébergés par des dispositifs électriques-électroniques: des systèmes embarqués, des ordinateurs, des robots, des automates Ces champs d'application peuvent être séparés en deux branches.
Nouveau!!: Leonid Levin et Informatique · Voir plus »
Institut de mathématiques Clay
L’institut de mathématiques Clay (en anglais, Clay Mathematics Institute, ou CMI) a été fondé en par Landon Clay, un homme d'affaires de Boston, président-directeur général de « East Hill Management », et son épouse Lavinia Clay dans le but de promouvoir et disséminer la connaissance mathématique dans le monde, en instaurant un système de prix pour les chercheurs mathématiciens.
Nouveau!!: Leonid Levin et Institut de mathématiques Clay · Voir plus »
Jean-Paul Delahaye
Jean-Paul Delahaye est un informaticien et mathématicien français né à Saint-Mandé (Seine) le.
Nouveau!!: Leonid Levin et Jean-Paul Delahaye · Voir plus »
Machine de Turing
En informatique théorique, une machine de Turing est un modèle abstrait du fonctionnement des appareils mécaniques de calcul, tel un ordinateur.
Nouveau!!: Leonid Levin et Machine de Turing · Voir plus »
Massachusetts Institute of Technology
Le grand dôme du MIT. Le Massachusetts Institute of Technology (MIT), en français Institut de technologie du Massachusetts, est un institut de recherche américain et une université, spécialisé dans les domaines de la science et de la technologie.
Nouveau!!: Leonid Levin et Massachusetts Institute of Technology · Voir plus »
Pour la science
Pour la science est une revue mensuelle de vulgarisation scientifique française fondée en 1977.
Nouveau!!: Leonid Levin et Pour la science · Voir plus »
Probabilité algorithmique
En théorie algorithmique de l'information, la probabilité algorithmique, aussi connue comme probabilité de Solomonoff, est une méthode permettant d’assigner une probabilité à une observation donnée.
Nouveau!!: Leonid Levin et Probabilité algorithmique · Voir plus »
Problème de l'arrêt
L'animation illustre une machine impossible: il n'y a pas de machine qui lit n'importe quel code source d'un programme et dit si son exécution termine ou non. En théorie de la calculabilité, le problème de l'arrêt est le problème de décision qui détermine, à partir d'une description d'un programme informatique, et d'une entrée, si le programme s'arrête avec cette entrée ou non.
Nouveau!!: Leonid Levin et Problème de l'arrêt · Voir plus »
Problème de la décision
En logique mathématique, on appelle problème de la décision ou, sous son nom d'origine en allemand, Entscheidungsproblem, le fait de déterminer de façon mécanique (par un algorithme) si un énoncé est un théorème de la logique égalitaire du premier ordre, c’est-à-dire s'il se dérive dans un système de déduction sans autres axiomes que ceux de l'égalité (exemples: système à la Hilbert, calcul des séquents, déduction naturelle).
Nouveau!!: Leonid Levin et Problème de la décision · Voir plus »
Problème NP-complet
En théorie de la complexité, un problème NP-complet ou problème NPC (c'est-à-dire un problème complet pour la classe NP) est un problème de décision vérifiant les propriétés suivantes.
Nouveau!!: Leonid Levin et Problème NP-complet · Voir plus »
Problème P ≟ NP
Représentation visuelle des deux configurations possibles. Le problème est une conjecture en mathématiques, et plus précisément en informatique théorique, considérée par de nombreux chercheurs comme une des plus importantes conjectures du domaine, et même des mathématiques en général.
Nouveau!!: Leonid Levin et Problème P ≟ NP · Voir plus »
Problèmes du prix du millénaire
Les problèmes du prix du millénaire sont un ensemble de sept défis mathématiques réputés insurmontables, posés par l'Institut de mathématiques Clay en.
Nouveau!!: Leonid Levin et Problèmes du prix du millénaire · Voir plus »
République socialiste soviétique d'Ukraine
La république socialiste soviétique d'Ukraine (en, Oukrayins'ka Radians'ka Sotsialistytchna Respoublika; en, Oukraïnskaïa Sovietskaïa Sotsialistitcheskaïa Respoublika; « République socialiste des conseils ukrainienne ») est, entre le et la dislocation de l'URSS en 1991, l'une des républiques de l'Union soviétique.
Nouveau!!: Leonid Levin et République socialiste soviétique d'Ukraine · Voir plus »
Stephen Cook
Stephen Arthur Cook (né en 1939 à Buffalo dans l'État de New York) est un informaticien et mathématicien américano-canadien, qui a apporté plusieurs contributions majeures à la théorie de la complexité.
Nouveau!!: Leonid Levin et Stephen Cook · Voir plus »
Théorème de Cook
En informatique théorique, plus précisément en théorie de la complexité, le théorème de Cook aussi appelé théorème de Cook-Levin est le théorème qui affirme que le problème SAT, c'est-à-dire le problème de satisfaisabilité d'une formule de la logique propositionnelle, est NP-complet.
Nouveau!!: Leonid Levin et Théorème de Cook · Voir plus »
Théorèmes d'incomplétude de Gödel
Les théorèmes d'incomplétude de Gödel sont deux théorèmes célèbres de logique mathématique, publiés par Kurt Gödel en 1931 dans son article (« Sur les propositions formellement indécidables des Principia Mathematica et des systèmes apparentés »).
Nouveau!!: Leonid Levin et Théorèmes d'incomplétude de Gödel · Voir plus »
Théorie de l'information
La théorie de l'information, sans précision, est le nom usuel désignant la théorie de l'information de Shannon, qui est une théorie utilisant les probabilités pour quantifier le contenu moyen en information d'un ensemble de messages, dont le codage informatique satisfait une distribution statistique que l'on pense connaître.
Nouveau!!: Leonid Levin et Théorie de l'information · Voir plus »
Théorie de la calculabilité
La théorie de la calculabilité (appelée aussi parfois théorie de la récursion) est un domaine de la logique mathématique et de l'informatique théorique.
Nouveau!!: Leonid Levin et Théorie de la calculabilité · Voir plus »
Théorie de la complexité (informatique théorique)
P est la classe des problèmes décidés en temps polynomial par une machine de Turing déterministe. La théorie de la complexité est le domaine des mathématiques, et plus précisément de l'informatique théorique, qui étudie formellement le temps de calcul, l'espace mémoire (et plus marginalement la taille d'un circuit, le nombre de processeurs, l'énergie consommée…) requis par un algorithme pour résoudre un problème algorithmique.
Nouveau!!: Leonid Levin et Théorie de la complexité (informatique théorique) · Voir plus »
Université d'État de Moscou
L'université d'État Lomonossov de Moscou (en russe Московский государственный университет имени М., Moskovski gossoudarstvenny ouniversitet imeni M. V. Lomonossova, abréviation MGU) est une université russe située à Moscou.
Nouveau!!: Leonid Levin et Université d'État de Moscou · Voir plus »
Université de Boston
L’université de Boston (en anglais, Boston University, BU) est une université américaine, située à Boston.
Nouveau!!: Leonid Levin et Université de Boston · Voir plus »
