Communication

461 relations: A New Kind of Science, AC, AC (complexité), AC0, ACM-IEEE Symposium on Logic in Computer Science, Albert R. Meyer, Alexandre Razborov, Alexeï Krylov, Algorithme, Algorithme à estimation de distribution, Algorithme d'optimisation, Algorithme de tracé d'arc de cercle de Bresenham, Algorithme DPLL, Algorithmique, Alice et Bob, Allan Borodin, Allocation de mémoire, Amin Shokrollahi, Amir Ronen, Analyse de la complexité des algorithmes, Andrei A. Bulatov, Andrew Odlyzko, Andrzej Grzegorczyk, Anil Nerode, Appariement à 3 dimensions, Apprentissage PAC, APX, APX (complexité), Arithmétique modulaire, Arnold Schönhage, Ashok K. Chandra, Automate linéairement borné, Avi Wigderson, Échange de clés Diffie-Hellman, École normale supérieure de Lyon, Épistémologie de l'informatique, Équilibre de Nash, Õ, Boris Trakhtenbrot, BPP, BPP (complexité), BQP, Calcul des propositions, Caml Light, Carsten Lund, Certificat (complexité), Charles Rackoff, Christos Papadimitriou, Chronologie de l'informatique, Circuit booléen, ..., Classe de complexité, Classe P, Classe préparatoire mathématiques, physique et informatique, Co-NP, Coloration de graphe, Combinatoire des mots, Combinatoire topologique, Combinatorica, Comparaison asymptotique, Complémentaire, Complémentaire (complexité), Complétude, Complet (complexité), Complexité abélienne d'un mot, Complexité algorithmique, Complexité d'un mot, Complexité d'un nombre entier, Complexité de Kolmogorov, Complexité de la communication, Complexité de Rademacher, Complexité des preuves, Complexité descriptive, Complexité en espace, Complexité en moyenne des algorithmes, Complexité en temps, Complexité essentielle, Complexité générique des algorithmes, Complexité implicite, Complexité paramétrée, Computational Complexity Conference, Conference on Implementation and Application of Automata, Conjecture de Berman-Hartmanis, Conjecture des jeux uniques, CONP, Conseil, Conseil (informatique théorique), Corps à un élément, Courbe remplissant le flocon de Koch, Crible algébrique, Critère de divisibilité, Cryptographie asymétrique, Cryptologie, CTL*, Dana Angluin, David S. Johnson, Décidabilité, Décomposition en produit de facteurs premiers, Démonstration formelle, Dérivation automatique, Dendrite (fractale), Dexter Kozen, Dima Grigoriev, Division euclidienne, Divisions successives, Dominic Welsh, Dor Minzer, DSPACE, DTIME, E (complexité), Edward Nelson (mathématicien), Elementary, ELEMENTARY (complexité), Elias Koutsoupias, Expression régulière, EXPSPACE, EXPTIME, Factorisation des polynômes, Fan-in, Fan-out, Fonction à sens unique, Fonction booléenne, Fonction constructible, Fonction négligeable (informatique), Formule booléenne quantifiée, Fragment (logique), Fundamenta Informaticae, Gabriel Lamé, Gadget (informatique), Géométrie hyperbolique, Günter Hotz, Gerhard Woeginger, Giorgio Ausiello, Grammaire contextuelle, Graphe de Frankl-Rödl, Graphe série-parallèle, Greedy randomized adaptive search procedure, Grete Hermann, Haiku (système d'exploitation), Harry Buhrman, Helmut Veith, Heuristique (mathématiques), Hiérarchie analytique, Hiérarchie booléenne, Hiérarchie de croissance rapide, Hiérarchie polynomiale, Hypercube magique, Impacts des Contrats Intelligents sur la société, Inégalité de Chernoff, Indicateur de cycles, Indistinguabilité calculatoire, Informatique, Informatique appliquée, Informatique quantique, Informatique théorique, Instance, Institut Max-Planck de physique des systèmes complexes, Intelligence artificielle, International Computing and Combinatorics Conference, International Symposium on Fundamentals of Computation Theory, International Symposium on Mathematical Foundations of Computer Science, Inverse modulaire, IP, IP (complexité), Isomorphisme de graphes, Jaroslav Nešetřil, Jin-Yi Cai, Johan Håstad, John von Neumann, Journal of Computer and System Sciences, Julia Kempe, Juraj Hromkovič, Juris Hartmanis, Kazimierz Kuratowski, Kernelisation, Kobbi Nissim, Kurt Mehlhorn, L, L (complexité), Langage congruentiel, Langage creux, Langage formel, Langage rationnel, Langage unaire, Largeur de clique, Larry J. Stockmeyer, Lawrence H. Landweber, László Lovász, Lemme de Schwartz-Zippel, Lemmings (jeu vidéo, 1991), Lenore Blum, Leonid Levin, Leslie Valiant, LH (complexité), Line graph, Liste d'informaticiens et précurseurs de l'informatique, Liste de classes de complexité, Liste de problèmes NP-complets, Liste de publications importantes en informatique, Liste de publications importantes en informatique théorique, Liste des principales conférences d'informatique théorique, Liste des projets BOINC, LOGCFL, Logique contrainte, Logique des graphes, Logique linéaire, Logique mathématique, Machine abstraite, Machine à vecteurs de support, Machine de Turing, Machine de Turing alternante, Machine de Turing non déterministe, Machine de Turing probabiliste, Machine de Turing universelle, Manuel Blum, Marc Snir, Marek Karpinski, Mario Szegedy, Mathématiques, Mathématiques computationnelles, Mathématiques discrètes, Matrice bande, Médaille John von Neumann, Médaille Konrad-Zuse, Médiane (statistiques), Métaheuristique, Méthode de factorisation de Fermat, Michael Garey, Michael J. Fischer, Michael Rabin, Michael Saks, Michael Shub, Michael Sipser, Michael Stewart Paterson, Mihalis Yannakakis, Minimisation d'un automate fini déterministe, Modèle standard (cryptologie), Morpion solitaire, Moteur de base de données, Multi-arbre, Naum Z. Shor, NC, NC (complexité), NE (complexité), Neeraj Kayal, Neil Immerman, NEXPSPACE, NEXPTIME, Nicolas Gauvrit, Nitin Saxena, NL, NL (complexité), Noam Nisan, Nombre de Shannon, Nombre premier, Nombre remarquable, NP, NP (complexité), NP-complétude faible, NP-difficile, NP-facile, NP-intermédiaire, NSPACE, NTIME, O, Oded Goldreich, Oded Regev, Olga Holtz, Oméga (homonymie), Omer Reingold, Optimisation combinatoire, Optimisation de code, Optimisation linéaire, Optimisation linéaire en nombres entiers, Optimisation multidisciplinaire, Optimisation sous contraintes distribuée, Oracle (machine de Turing), Ordinateur à ADN, Ordinateur quantique, P, P (complexité), P-complet, P/poly, Parallélisme (informatique), Parallel random access machine, Partition binaire de l'espace, Partition d'un entier, Partition en cliques, Patrick C. Fischer, Paul E. Schupp, Paul Spirakis, Paul Vitanyi, PCP, Peter Winkler, PH (complexité), Philip Mirowski, Philippe Flajolet, Phylo, Physique numérique (théorique), Placement-routage, Plus longue sous-séquence commune, Point d'articulation (théorie des graphes), Polylogarithmique, Polynôme, PP, PP (complexité), PPA, PPA (complexité), Prasad Raghavendra, Preuve de sécurité, Preuve naturelle, Preuve vérifiable de manière probabiliste, Principe de Yao, Prix ACM en informatique, Prix Donald E. Knuth, Prix EATCS, Prix Gödel, Prix Grace-Murray-Hopper, Prix Michael-et-Sheila-Held, Prix Turing, Problème 3-SAT, Problème à promesse, Problème de comptage, Problème de couverture par sommets, Problème de décision, Problème de l'évaluation d'un circuit, Problème de l'isomorphisme de graphes, Problème de la clique, Problème de la résiduosité quadratique, Problème de la somme de sous-ensembles, Problème de recherche, Problème de satisfaction de contraintes, Problème des huit dames, Problème des multiplications matricielles enchaînées, Problème des pièces de monnaie, Problème du sac à dos, Problème du stable maximum, Problème du voyageur de commerce, Problème non élémentaire, Problème NP-complet, Problème SAT, Produit zig-zag de graphes, Programmation lettrée, Programming a Computer for Playing Chess, Project Euler, Propagation de contraintes, Protocole Arthur-Merlin, PSPACE, Puissance parfaite, R, RAIRO Informatique théorique et applications, Rajeev Motwani, Ran Raz, Règle de Cramer, Récursivement énumérable, Réduction (complexité), Réduction en espace logarithmique, Réduction polynomiale, Réplication (informatique), Résultats effectifs en théorie des nombres, RE, Recherche opérationnelle, Recuit simulé, Représentations d'un groupe fini, Richard Bellman, Richard E. Ladner, Richard J. Lipton, Richard Jozsa, Richard Karp, Richard Stearns, Rod Downey, Ronald Book, RP, RP (complexité), Russell Impagliazzo, Salil Vadhan, Samuel R. Buss, Sanjeev Arora, SAT, Séquençage de tâches, SC (complexité), Schéma d'approximation en temps polynomial, Scott Aaronson, Segmentation en plans, Seinosuke Toda, Shafi Goldwasser, Sharp-P-complet, Sheila A. Greibach, Shmuel Safra, Sigma (homonymie), Sim (jeu), Simulation d'un système à N corps, Sokoban, Somme de radicaux, Speedup (homonymie), Stable (théorie des graphes), Standard Template Library, Stephen Cook, Steven Rudich, Stratégie d'évaluation (informatique), Structure de données, Structured Query Language, Subhash Khot, Suite de Fibonacci, Symposium on Discrete Algorithms, Symposium on Theoretical Aspects of Computer Science, Système de preuve interactive, Taux d'expansion (théorie des graphes), TC (complexité), Temps de calcul pseudo-polynomial, Test de primalité de Lucas-Lehmer, Tetravex, Tetris, TFNP, Thèse de Church, Théorème d'accélération linéaire, Théorème d'Immerman-Szelepcsényi, Théorème de Cook, Théorème de Courcelle, Théorème de Fagin, Théorème de hiérarchie, Théorème de hiérarchie en temps déterministe, Théorème de Karp-Lipton, Théorème de Mahaney, Théorème de Meyer, Théorème de Robertson-Seymour, Théorème de Savitch, Théorème de Sipser-Gács-Lautemann, Théorème de Toda, Théorème des quatre couleurs, Théorème du codage de canal, Théorème optimisation/séparation, Théorème PCP, Théorie de l'élimination, Théorie de la complexité, Théorie des automates, Théorie des bases de données, Théorie des codes, Théorie des graphes, Thêta (homonymie), Thomas Vidick, Toniann Pitassi, Tournesol (mathématiques), Triangulation d'un polygone, UP, UP (complexité), Uriel Feige, Usage des lettres grecques en sciences, Vérification de modèles, Vijay Vazirani, Viktor Vassiliev, Virginia Vassilevska Williams, Vitesse de convergence des suites, Walter Savitch, Xi Chen, ZPP, ZPP (complexité), 1972 en informatique, 1973 en informatique, 1993 en informatique, 2-EXPTIME, 21 problèmes NP-complets de Karp. Développer l'indice (411 plus) » « Compacter l'indice

A New Kind of Science

A New Kind of Science (Un nouveau type de science), souvent référé par ses initiales NKS, est un livre best-seller, écrit par Stephen Wolfram, et publié par sa société Wolfram Research sous le nom de publication Wolfram Media, en 2002.

Nouveau!!: Théorie de la complexité (informatique théorique) et A New Kind of Science · Voir plus »

AC

Cette page recense les différentes significations (codes, sigles, abréviations, etc.) résultant du rapprochement des lettres A et C.

Nouveau!!: Théorie de la complexité (informatique théorique) et AC · Voir plus »

AC (complexité)

En théorie de la complexité, AC est la classe de complexité définie comme l'union des ACi, où ACi est la classe de complexité des problèmes décidés par des circuits booléens de profondeur O(\log^i n), de taille polynomiale, dont les portes sont des ET et des OU, de degrés entrants non bornés (en fait, d'autres portes peuvent être autorisés comme des portes "OU exclusif" ou NON car elles sont exprimables, sans changer la complexité, par des ET et des OU).

Nouveau!!: Théorie de la complexité (informatique théorique) et AC (complexité) · Voir plus »

AC0

Calculer le ième bit de la somme de deux nombres a et b est dans AC0. L'image montre un circuit de taille polynomiale en la taille de l'entrée, ie. 2n et de profondeur constante (ici de profondeur 5 pour tout n). En théorie de la complexité, AC0 est une classe de complexité définie par des circuits booléens de profondeur constante.

Nouveau!!: Théorie de la complexité (informatique théorique) et AC0 · Voir plus »

ACM-IEEE Symposium on Logic in Computer Science

La conférence ACM-IEEE Symposium on Logic in Computer Science (abrégé en LICS) est la principale conférence scientifique informatique en relation avec la logique mathématique.

Nouveau!!: Théorie de la complexité (informatique théorique) et ACM-IEEE Symposium on Logic in Computer Science · Voir plus »

Albert R. Meyer

Albert Ronald da Silva Meyer (né en 1941) est professeur d'informatique au Massachusetts Institute of Technology (MIT).

Nouveau!!: Théorie de la complexité (informatique théorique) et Albert R. Meyer · Voir plus »

Alexandre Razborov

Alexandre Alexandrovitch Razborov (Алекса́ндр Алекса́ндрович Разбо́ров, né le), connu aussi sous le nom de Sacha Razborov, est un mathématicien et un informaticien théoricien soviétique et russe.

Nouveau!!: Théorie de la complexité (informatique théorique) et Alexandre Razborov · Voir plus »

Alexeï Krylov

Alexeï Nikolaïevitch Krylov (en Алексей Николаевич Крылов) (né le dans le gouvernement de Simbirsk en Russie - mort le à Léningrad) est un ingénieur naval et mémorialiste russe.

Nouveau!!: Théorie de la complexité (informatique théorique) et Alexeï Krylov · Voir plus »

Algorithme

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.

Nouveau!!: Théorie de la complexité (informatique théorique) et Algorithme · Voir plus »

Algorithme à estimation de distribution

Les algorithmes à estimation de distribution (Estimation of Distribution Algorithms, EDA, en anglais) forment une famille de métaheuristiques inspirée des algorithmes génétiques.

Nouveau!!: Théorie de la complexité (informatique théorique) et Algorithme à estimation de distribution · Voir plus »

Algorithme d'optimisation

Les algorithmes d’optimisation cherchent à déterminer le jeu de paramètres d’entrée d’une fonction donnant à cette fonction la valeur maximale ou minimale.

Nouveau!!: Théorie de la complexité (informatique théorique) et Algorithme d'optimisation · Voir plus »

Algorithme de tracé d'arc de cercle de Bresenham

L’algorithme de tracé d'arc de cercle de Bresenham, ou algorithme de tracé d'arc de cercle par point milieu (midpoint en anglais) permet, pour une complexité algorithmique très réduite, de tracer des cercles en image matricielle.

Nouveau!!: Théorie de la complexité (informatique théorique) et Algorithme de tracé d'arc de cercle de Bresenham · Voir plus »

Algorithme DPLL

En informatique, l'algorithme de Davis–Putnam–Logemann–Loveland (DPLL) est un algorithme de backtracking, complet, de résolution du problème SAT.

Nouveau!!: Théorie de la complexité (informatique théorique) et Algorithme DPLL · Voir plus »

Algorithmique

Organigramme de programmation représentant l'algorithme d'Euclide. Lalgorithmique est l'étude et la production de règles et techniques qui sont impliquées dans la définition et la conception d'algorithmes, c'est-à-dire de processus systématiques de résolution d'un problème permettant de décrire précisément des étapes pour résoudre un problème algorithmique.

Nouveau!!: Théorie de la complexité (informatique théorique) et Algorithmique · Voir plus »

Alice et Bob

Schéma de communication entre Alice et Bob intercepté par Mallory Les personnages Alice et Bob sont des figures classiques en cryptologie.

Nouveau!!: Théorie de la complexité (informatique théorique) et Alice et Bob · Voir plus »

Allan Borodin

Allan Bertram Borodin est un chercheur en informatique américano-canadien né en 1941, à la retraite après avoir enseigné à l'Université de Toronto, U. Toronto Computer Science, retrieved 2012-03-17.

Nouveau!!: Théorie de la complexité (informatique théorique) et Allan Borodin · Voir plus »

Allocation de mémoire

L'allocation de mémoire vive désigne les techniques et les algorithmes sous-jacents permettant de réserver de la mémoire vive à un programme informatique pour son exécution.

Nouveau!!: Théorie de la complexité (informatique théorique) et Allocation de mémoire · Voir plus »

Amin Shokrollahi

Mohammad Amin Shokrollahi est un mathématicien et informaticien iranien enseignant à l'École polytechnique fédérale de Lausanne.

Nouveau!!: Théorie de la complexité (informatique théorique) et Amin Shokrollahi · Voir plus »

Amir Ronen

Amir Ronen, né en 1965, est un informaticien israélien.

Nouveau!!: Théorie de la complexité (informatique théorique) et Amir Ronen · Voir plus »

Analyse de la complexité des algorithmes

Représentation d'une recherche linéaire (en violet) face à une recherche binaire (en vert). La complexité algorithmique de la seconde est logarithmique alors que celle de la première est linéaire. L'analyse de la complexité d'un algorithme consiste en l'étude formelle de la quantité de ressources (par exemple de temps ou d'espace) nécessaire à l'exécution de cet algorithme.

Nouveau!!: Théorie de la complexité (informatique théorique) et Analyse de la complexité des algorithmes · Voir plus »

Andrei A. Bulatov

Andreï Arnoldovitch Boulatov (en, orthographié à l'anglaise: Andrei A. Bulatov) est un informaticien et mathématicien russo-canadien; né le 11 janvier 1975 à Alapaïevsk; il est professeur d'informatique à l'université Simon Fraser.

Nouveau!!: Théorie de la complexité (informatique théorique) et Andrei A. Bulatov · Voir plus »

Andrew Odlyzko

Andrew Michael Odlyzko, né le à Tarnów en Pologne, est un mathématicien et informaticien.

Nouveau!!: Théorie de la complexité (informatique théorique) et Andrew Odlyzko · Voir plus »

Andrzej Grzegorczyk

Andrzej Grzegorczyk (–) est un mathématicien polonais.

Nouveau!!: Théorie de la complexité (informatique théorique) et Andrzej Grzegorczyk · Voir plus »

Anil Nerode

Anil Nerode, né le à Los Angeles, est un mathématicien américain.

Nouveau!!: Théorie de la complexité (informatique théorique) et Anil Nerode · Voir plus »

Appariement à 3 dimensions

Appariement à 3 dimensions. (a) Donnée ''T''. (b)–(c) Deux solutions. (c) est de taille maximum. En mathématiques, et notamment en théorie des graphes, un appariement à 3 dimensions (en anglais: 3-dimensional matching) est une généralisation du couplage (aussi appelé appariement en dimension 2) à une situation ternaire qui, techniquement, est celle des hypergraphes dits 3-uniformes.

Nouveau!!: Théorie de la complexité (informatique théorique) et Appariement à 3 dimensions · Voir plus »

Apprentissage PAC

L'apprentissage PAC (pour probably approximately correct en anglais) est un cadre théorique pour l'apprentissage automatique.

Nouveau!!: Théorie de la complexité (informatique théorique) et Apprentissage PAC · Voir plus »

APX

APX peut faire référence à.

Nouveau!!: Théorie de la complexité (informatique théorique) et APX · Voir plus »

APX (complexité)

En théorie de la complexité, APX est la classe des problèmes algorithmiques pour lesquels il existe un algorithme d'approximation en temps polynomial avec un ratio d'approximation constant.

Nouveau!!: Théorie de la complexité (informatique théorique) et APX (complexité) · Voir plus »

Arithmétique modulaire

En mathématiques et plus précisément en théorie algébrique des nombres, l’arithmétique modulaire est un ensemble de méthodes permettant la résolution de problèmes sur les nombres entiers.

Nouveau!!: Théorie de la complexité (informatique théorique) et Arithmétique modulaire · Voir plus »

Arnold Schönhage

Arnold Schönhage (né le à Lockhausen, auj. Bad Salzuflen) est un mathématicien et informaticien allemand.

Nouveau!!: Théorie de la complexité (informatique théorique) et Arnold Schönhage · Voir plus »

Ashok K. Chandra

Ashok Kumar Chandra (né le en Inde, et mort le en Californie) est un informaticien qui a travaillé notamment chez Microsoft Research à Mountain View, en Californie, où il était directeur général du Internet Services Research Center.

Nouveau!!: Théorie de la complexité (informatique théorique) et Ashok K. Chandra · Voir plus »

Automate linéairement borné

En informatique théorique, et en particulier en théorie des automates, un automate linéairement borné (en anglais, abrégé en LBA) est une machine de Turing non déterministe qui n'utilise qu'une portion contiguë du ruban de taille linéaire en la taille de l'entrée.

Nouveau!!: Théorie de la complexité (informatique théorique) et Automate linéairement borné · Voir plus »

Avi Wigderson

Avi Wigderson (אבי ויגדרזון), né le, est un mathématicien et informaticien théorique israélien.

Nouveau!!: Théorie de la complexité (informatique théorique) et Avi Wigderson · Voir plus »

Échange de clés Diffie-Hellman

En cryptographie, l'échange de clés Diffie-Hellman, du nom de ses auteurs Whitfield Diffie et Martin Hellman, est une méthode, publiée en 1976, par laquelle deux agents, nommés par convention Alice et Bob, peuvent se mettre d'accord sur un nombre (qu'ils peuvent utiliser comme clé pour chiffrer la conversation suivante) sans qu'un troisième agent appelé Ève puisse découvrir le nombre, même en ayant écouté tous leurs échanges.

Nouveau!!: Théorie de la complexité (informatique théorique) et Échange de clés Diffie-Hellman · Voir plus »

École normale supérieure de Lyon

L'École normale supérieure de Lyon (ou ENS de Lyon) est une grande école scientifique et littéraire française, l'une des quatre écoles normales supérieures.

Nouveau!!: Théorie de la complexité (informatique théorique) et École normale supérieure de Lyon · Voir plus »

Épistémologie de l'informatique

L'épistémologie de l'informatique est la branche de l'épistémologie, parmi les épistémologies disciplinaires, qui prend pour objet d'étude l'informatique en tant que science pour en déterminer son épistémologie, c'est-à-dire, d'une part son ou ses objet(s), ses principes, ses concepts fondamentaux, ses théories et résultats, i.e. ce qui la constitue; d'autre part ses modes de construction de nouvelles connaissances, ses processus d'inférence et d'émergence de nouveaux concepts, les éléments à l'origine de ses évolutions, i.e. ce qui la fait progresser; et enfin, ses fondements, son origine, sa portée objective, i.e. ce qui la justifie dans le concert des sciences (introduction).

Nouveau!!: Théorie de la complexité (informatique théorique) et Épistémologie de l'informatique · Voir plus »

Équilibre de Nash

Le dilemme du prisonnier: chacun des deux joueurs dispose de deux stratégies: D pour dénoncer, C pour ne pas dénoncer. La matrice présente le gain des joueurs. Si les deux joueurs choisissent D (se dénoncent), aucun ne regrette son choix, car s'il avait choisi C, alors que l'autre a opté pour D, sa « tristesse » aurait augmenté. C'est un équilibre de Nash — il y a « non-regret » de son choix par chacun, au vu du choix de l'autre. En théorie des jeux, un équilibre de Nash est une situation où.

Nouveau!!: Théorie de la complexité (informatique théorique) et Équilibre de Nash · Voir plus »

Õ

Õ (minuscule : õ), appelé O tilde, est un graphème utilisé dans l’écriture de l’apalai, de l’estonien, du guarani, de l’umbundu, de l’odual, du portugais, du tchourama, du vietnamien, du zarma.

Nouveau!!: Théorie de la complexité (informatique théorique) et Õ · 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!!: Théorie de la complexité (informatique théorique) et Boris Trakhtenbrot · Voir plus »

BPP

BPP est un sigle qui peut signifier.

Nouveau!!: Théorie de la complexité (informatique théorique) et BPP · Voir plus »

BPP (complexité)

En informatique théorique, plus précisément en théorie de la complexité, la classe BPP (bounded-error probabilistic polynomial time) est la classe de problèmes de décision décidés par une machine de Turing probabiliste en temps polynomial, avec une probabilité d'erreur dans la réponse inférieure à 1/3.

Nouveau!!: Théorie de la complexité (informatique théorique) et BPP (complexité) · Voir plus »

BQP

En théorie de la complexité des algorithmes BQP (bounded error quantum polynomial time) est la classe des problèmes de décision qui peuvent être résolus par un calculateur quantique en un temps polynomial, avec une probabilité d'erreur d'au plus 1/3 dans tous les cas.

Nouveau!!: Théorie de la complexité (informatique théorique) et BQP · Voir plus »

Calcul des propositions

Le calcul des propositions ou calcul propositionnel, (ou encore logique des propositions) fait partie de la logique mathématique.

Nouveau!!: Théorie de la complexité (informatique théorique) et Calcul des propositions · Voir plus »

Caml Light

était une implémentation légère du langage de programmation Caml développé par l'INRIA.

Nouveau!!: Théorie de la complexité (informatique théorique) et Caml Light · Voir plus »

Carsten Lund

Carsten Lund, né le juillet 1963 à Aarhus, au Danemark, est un informaticien théoricien d'origine danoise qui travaille actuellement (en 2015) à Bedminster, dans le New Jersey, aux Laboratoires de AT&T.

Nouveau!!: Théorie de la complexité (informatique théorique) et Carsten Lund · Voir plus »

Certificat (complexité)

En informatique théorique, plus précisément en théorie de la complexité des algorithmes, un certificat est, de façon simplifiée, une information permettant de certifier que l'entrée est correcte.

Nouveau!!: Théorie de la complexité (informatique théorique) et Certificat (complexité) · Voir plus »

Charles Rackoff

Charles Weill Rackoff est un cryptologue américain.

Nouveau!!: Théorie de la complexité (informatique théorique) et Charles Rackoff · Voir plus »

Christos Papadimitriou

Christos Harilaos Papadimitriou (en Χρήστος Χαρίλαος Παπαδημητρίου), né le à Athènes, est un professeur et chercheur en informatique grec.

Nouveau!!: Théorie de la complexité (informatique théorique) et Christos Papadimitriou · Voir plus »

Chronologie de l'informatique

: 1645 - 1703 - 1725 - 1728 - 1745 - 1801 - 1822 - 1834 - 1836 - 1843 - 1847 - 1851 - 1869 - 1876 - 1890 -1914 - 1920 - 1928 - 1931 - 1936 - 1937 - 1939 - 1941 - 1942 - 1943 - 1944 - 1945 - 1946 - 1947 - 1948 - 1949 - 1950 - 1951 - 1952 - 1953 - 1954 - 1955 - 1956 - 1957 - 1958 - 1959 - 1960 - 1961 - 1962 - 1963 - 1964 - 1965 - 1966 - 1967 - 1968 - 1969 - 1970 - 1971 - 1972 - 1973 - 1974 - 1975 - 1976 - 1977 - 1978 - 1979 - 1980 - 1981 - 1982 - 1983 - 1984 - 1985 - 1986 - 1987 - 1988 - 1989 - 1990 - 1991 - 1992 - 1993 - 1994 - 1995 - 1996 - 1997 - 1998 - 1999 - 2000 - 2001 - 2002 - 2003 - 2004 - 2005 - 2006 - 2007 - 2008 - 2009 - 2010 - 2011 - 2012 - 2013 - 2014 - 2015 - 2016 - 2017 - 2018 - 2019 - 2020 - 2021 - 2022 - 2023 - 2024.

Nouveau!!: Théorie de la complexité (informatique théorique) et Chronologie de l'informatique · Voir plus »

Circuit booléen

Exemple circuit booléen à deux entrées et une sortie. Le circuit contient 3 portes logique. En théorie de la complexité, un circuit booléen est un modèle de calcul constitué de portes logiques (fonctions logiques) reliées entre elles.

Nouveau!!: Théorie de la complexité (informatique théorique) et Circuit booléen · Voir plus »

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.

Nouveau!!: Théorie de la complexité (informatique théorique) et Classe de complexité · Voir plus »

Classe P

Classe P peut faire référence à.

Nouveau!!: Théorie de la complexité (informatique théorique) et Classe P · Voir plus »

Classe préparatoire mathématiques, physique et informatique

Dans le système éducatif français, la classe préparatoire mathématiques, physique et Informatique ou MPI est une des voies d'orientation en seconde année, communément appelée Maths spé, de la filière des classes préparatoires scientifiques.

Nouveau!!: Théorie de la complexité (informatique théorique) et Classe préparatoire mathématiques, physique et informatique · Voir plus »

Co-NP

En informatique théorique, co-NP (ou coNP) est une classe de complexité, c'est-à-dire un ensemble de problèmes de décision au sens de la théorie de la complexité.

Nouveau!!: Théorie de la complexité (informatique théorique) et Co-NP · Voir plus »

Coloration de graphe

Une coloration du graphe de Petersen avec 3 couleurs. En théorie des graphes, la coloration de graphe consiste à attribuer une couleur à chacun de ses sommets de manière que deux sommets reliés par une arête soient de couleur différente.

Nouveau!!: Théorie de la complexité (informatique théorique) et Coloration de graphe · Voir plus »

Combinatoire des mots

La combinatoire des mots est une branche des mathématiques et de l'informatique théorique qui applique l'analyse combinatoire aux mots finis ou infinis.

Nouveau!!: Théorie de la complexité (informatique théorique) et Combinatoire des mots · Voir plus »

Combinatoire topologique

La combinatoire topologique est un domaine mathématique de la combinatoire qui applique des méthodes topologiques et algébrico-topologiques à la résolution de problèmes en combinatoire.

Nouveau!!: Théorie de la complexité (informatique théorique) et Combinatoire topologique · Voir plus »

Combinatorica

Combinatorica est une revue mathématique qui publie des articles en combinatoire et en informatique théorique.

Nouveau!!: Théorie de la complexité (informatique théorique) et Combinatorica · Voir plus »

Comparaison asymptotique

Comparaison asymptotique des fonctions utilisées en informatique plus précisément en algorithme. On voit par exemple que la fonction exponentielle (2^n) croit plus vite que la fonction linéaire (n). En mathématiques, plus précisément en analyse, la comparaison asymptotique est une méthode consistant à étudier la vitesse de croissance d'une fonction.

Nouveau!!: Théorie de la complexité (informatique théorique) et Comparaison asymptotique · Voir plus »

Complémentaire

Un complémentaire sert à compléter un tout.

Nouveau!!: Théorie de la complexité (informatique théorique) et Complémentaire · Voir plus »

Complémentaire (complexité)

En théorie de la complexité (un domaine de l'informatique théorique), on parle du complémentaire d'une classe C, noté co-C ou coC, pour désigner l'ensemble des langages complémentaires des langages de la classe.

Nouveau!!: Théorie de la complexité (informatique théorique) et Complémentaire (complexité) · Voir plus »

Complétude

La notion de complétude est utilisée dans plusieurs domaines scientifiques.

Nouveau!!: Théorie de la complexité (informatique théorique) et Complétude · Voir plus »

Complet (complexité)

En informatique théorique, et notamment en théorie de la complexité, un problème complet pour une classe de complexité est un problème de décision qui fait partie des problèmes les plus difficiles à résoudre de cette classe.

Nouveau!!: Théorie de la complexité (informatique théorique) et Complet (complexité) · Voir plus »

Complexité abélienne d'un mot

En informatique théorique, et notamment en combinatoire des mots, il existe plusieurs manières de cerner la complexité d'une suite infinie de symboles, parmi lesquelles il y a la complexité algorithmique ou la complexité de Kolmogorov.

Nouveau!!: Théorie de la complexité (informatique théorique) et Complexité abélienne d'un mot · Voir plus »

Complexité algorithmique

* Théorie de la complexité des algorithmes en informatique théorique.

Nouveau!!: Théorie de la complexité (informatique théorique) et Complexité algorithmique · Voir plus »

Complexité d'un mot

La complexité combinatoire d'un mot ou plus simplement la complexité d'un mot ou d'une suite est un moyen de mesurer, en combinatoire et en mathématique, et spécialement en combinatoire des mots, divers paramètres d'un mot qui expriment combien il est « compliqué ».

Nouveau!!: Théorie de la complexité (informatique théorique) et Complexité d'un mot · Voir plus »

Complexité d'un nombre entier

La complexité d'un nombre entier est le nombre minimal de 1 nécessaires pour écrire ce nombre en n'utilisant que.

Nouveau!!: Théorie de la complexité (informatique théorique) et Complexité d'un nombre entier · Voir plus »

Complexité de Kolmogorov

En 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, image numérique, chaîne de caractères — est la taille du plus petit algorithme (dans un certain langage de programmation fixé) qui engendre cet objet.

Nouveau!!: Théorie de la complexité (informatique théorique) et Complexité de Kolmogorov · Voir plus »

Complexité de la communication

La complexité de la communication ou complexité de communication est une notion étudiée en informatique théorique.

Nouveau!!: Théorie de la complexité (informatique théorique) et Complexité de la communication · Voir plus »

Complexité de Rademacher

La complexité de Rademacher est un concept d'informatique théorique; il se situe plus précisément à l'intersection de théorie de apprentissage automatique et de la théorie de la complexité.

Nouveau!!: Théorie de la complexité (informatique théorique) et Complexité de Rademacher · Voir plus »

Complexité des preuves

En informatique théorique, la complexité des preuves ou complexité des démonstrations est le domaine qui étudie les ressources nécessaires pour prouver ou réfuter un énoncé mathématique.

Nouveau!!: Théorie de la complexité (informatique théorique) et Complexité des preuves · Voir plus »

Complexité descriptive

En informatique théorique, la complexité descriptive est une branche de la théorie de la complexité et de la théorie des modèles, qui caractérise les classes de complexité en termes de logique qui permet de décrire les problèmes.

Nouveau!!: Théorie de la complexité (informatique théorique) et Complexité descriptive · Voir plus »

Complexité en espace

En algorithmique, la complexité en espace est une mesure de l'espace utilisé par un algorithme, en fonction de propriétés de ses entrées.

Nouveau!!: Théorie de la complexité (informatique théorique) et Complexité en espace · 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!!: Théorie de la complexité (informatique théorique) et Complexité en moyenne des algorithmes · Voir plus »

Complexité en temps

En algorithmique, la complexité en temps est une mesure du temps utilisé par un algorithme, exprimé comme fonction de la taille de l'entrée.

Nouveau!!: Théorie de la complexité (informatique théorique) et Complexité en temps · Voir plus »

Complexité essentielle

La complexité essentielle relative à un problème, généralement dans le cadre d'un projet informatique, désigne le degré de complexité minimal d'un programme pour résoudre un problème ou appliquer une solution.

Nouveau!!: Théorie de la complexité (informatique théorique) et Complexité essentielle · Voir plus »

Complexité générique des algorithmes

La complexité générique est un domaine particulier de la complexité algorithmique qui concerne l’étude de la complexité de problèmes algorithmiques pour « la plupart des données ».

Nouveau!!: Théorie de la complexité (informatique théorique) et Complexité générique des algorithmes · Voir plus »

Complexité implicite

En informatique théorique, la complexité implicite est une branche de la théorie de la complexité calculatoire qui caractérise les classes de complexité par des restrictions syntaxiques sur le langage de programmation de haut niveau.

Nouveau!!: Théorie de la complexité (informatique théorique) et Complexité implicite · Voir plus »

Complexité paramétrée

En algorithmique, la complexité paramétrée (ou complexité paramétrique) est une branche de la théorie de la complexité qui classifie les problèmes algorithmiques selon leur difficulté intrinsèque en fonction de plusieurs paramètres sur les données en entrée ou sur la sortie.

Nouveau!!: Théorie de la complexité (informatique théorique) et Complexité paramétrée · Voir plus »

Computational Complexity Conference

La conférence Computational Complexity Conference (abrégé en CCC) est une conférence scientifique annuelle dans le domaine de l'informatique théorique, dont les origines remontent à 1986.

Nouveau!!: Théorie de la complexité (informatique théorique) et Computational Complexity Conference · Voir plus »

Conference on Implementation and Application of Automata

International Conference on Implementation and Application of Automata (abrégé en CIAA) est une conférence scientifique annuelle dans le domaine de l'informatique théorique, réunissant chercheurs et enseignants du supérieur et de l'industrie concernés par la théorie, les implémentations et les applications des automates et de structures voisines.

Nouveau!!: Théorie de la complexité (informatique théorique) et Conference on Implementation and Application of Automata · Voir plus »

Conjecture de Berman-Hartmanis

En théorie de la complexité, la conjecture de Berman-Hartmanis est une conjecture non résolue qui prétend que tous les langages NP-complets se ressemblent.

Nouveau!!: Théorie de la complexité (informatique théorique) et Conjecture de Berman-Hartmanis · Voir plus »

Conjecture des jeux uniques

La conjecture des jeux uniques (en anglais Unique Games Conjecture et souvent abrégée UGC) est une conjecture en théorie de la complexité, proposée par Subhash Khot en 2002.

Nouveau!!: Théorie de la complexité (informatique théorique) et Conjecture des jeux uniques · Voir plus »

CONP

* En informatique théorique, co-NP est une classe de complexité.

Nouveau!!: Théorie de la complexité (informatique théorique) et CONP · Voir plus »

Conseil

Pas de description.

Nouveau!!: Théorie de la complexité (informatique théorique) et Conseil · Voir plus »

Conseil (informatique théorique)

En théorie de la complexité, un conseil est une entrée supplémentaire passée à une machine de Turing qui dépend de la taille de l'entrée, afin d'aider la machine à reconnaître un langage.

Nouveau!!: Théorie de la complexité (informatique théorique) et Conseil (informatique théorique) · Voir plus »

Corps à un élément

En mathématiques, et plus précisément en géométrie algébrique, le corps à un élément est le nom donné de manière quelque peu fantaisiste à un objet qui se comporterait comme un corps fini à un seul élément, si un tel corps pouvait existerTout corps contient au moins deux éléments distincts (l'identité pour l'addition, 0, et celle pour la multiplication, 1).

Nouveau!!: Théorie de la complexité (informatique théorique) et Corps à un élément · Voir plus »

Courbe remplissant le flocon de Koch

La courbe remplissant le flocon de Koch est une courbe remplissante définie pour recouvrir la surface incluse dans un flocon de Koch.

Nouveau!!: Théorie de la complexité (informatique théorique) et Courbe remplissant le flocon de Koch · Voir plus »

Crible algébrique

En théorie des nombres, l'algorithme du crible du corps de nombres généraliséAussi connu sous son nom anglais, generalised number field sieve, ou son acronyme: GNFS.

Nouveau!!: Théorie de la complexité (informatique théorique) et Crible algébrique · Voir plus »

Critère de divisibilité

En mathématiques et plus précisément en arithmétique modulaire, un critère de divisibilité est une particularité d'un entier permettant de déterminer si ce nombre est divisible par un autre.

Nouveau!!: Théorie de la complexité (informatique théorique) et Critère de divisibilité · Voir plus »

Cryptographie asymétrique

Schéma du chiffrement asymétrique: une clé sert à chiffrer et une seconde à déchiffrer La cryptographie asymétrique, ou cryptographie à clé publique est un domaine relativement récent de la cryptographie.

Nouveau!!: Théorie de la complexité (informatique théorique) et Cryptographie asymétrique · Voir plus »

Cryptologie

Au cours de la Seconde Guerre mondiale, la machine de Lorenz est exploitée pour chiffrer les communications militaires allemandes de haute importance stratégique ou tactique. La cryptologie, étymologiquement la « science du secret », n'est considérée comme une science que depuis le.

Nouveau!!: Théorie de la complexité (informatique théorique) et Cryptologie · Voir plus »

CTL*

En informatique théorique, notamment en vérification formelle, CTL* (prononcé en anglais) est une logique temporelle.

Nouveau!!: Théorie de la complexité (informatique théorique) et CTL* · Voir plus »

Dana Angluin

Dana Angluin est professeur d' informatique à l'université de Yale.

Nouveau!!: Théorie de la complexité (informatique théorique) et Dana Angluin · Voir plus »

David S. Johnson

David Stifler Johnson, né le à Washington, mort le, est chercheur en informatique américain.

Nouveau!!: Théorie de la complexité (informatique théorique) et David S. Johnson · Voir plus »

Décidabilité

En logique mathématique, le terme décidabilité recouvre deux concepts liés: la décidabilité logique et la décidabilité ''algorithmique''.

Nouveau!!: Théorie de la complexité (informatique théorique) et Décidabilité · Voir plus »

Décomposition en produit de facteurs premiers

Décomposition du nombre 864 en facteurs premiers En mathématiques et plus précisément en arithmétique, la décomposition en produit de facteurs premiers, aussi connue comme la factorisation entière en nombres premiers ou encore plus couramment la décomposition en facteurs premiers, consiste à chercher à écrire un entier naturel non nul sous forme d'un produit de nombres premiers.

Nouveau!!: Théorie de la complexité (informatique théorique) et Décomposition en produit de facteurs premiers · Voir plus »

Démonstration formelle

Une démonstration formelle est une séquence finie de propositions (appelées formules bien formées dans le cas d'un langage formel) dont chacun est un axiome, une hypothèse, ou résulte des propositions précédentes dans la séquence par une règle d'inférence.

Nouveau!!: Théorie de la complexité (informatique théorique) et Démonstration formelle · Voir plus »

Dérivation automatique

En mathématique et en calcul formel, la dérivation automatique (DA), également appelé dérivation algorithmique, dérivation formelle, ou auto-dérivation est un ensemble de techniques d'évaluation de la dérivée d'une fonction par un programme informatique.

Nouveau!!: Théorie de la complexité (informatique théorique) et Dérivation automatique · Voir plus »

Dendrite (fractale)

Le terme de dendrite s'applique à un certain type de croissance fractale, de par leur ressemblance aux dendrites biologiques.

Nouveau!!: Théorie de la complexité (informatique théorique) et Dendrite (fractale) · Voir plus »

Dexter Kozen

Dexter Campbell Kozen (né le) est un informaticien théoricien américain.

Nouveau!!: Théorie de la complexité (informatique théorique) et Dexter Kozen · Voir plus »

Dima Grigoriev

Dima Grigoriev (Dmitri Iourievitch Grigoriev), né le à Leningrad, est un mathématicien et informaticien théoricien d'origine russe.

Nouveau!!: Théorie de la complexité (informatique théorique) et Dima Grigoriev · Voir plus »

Division euclidienne

Écriture de la division euclidienne de 30 par 7, le quotient est 4 et le reste 2.En mathématiques, et plus précisément en arithmétique, la division euclidienne ou division entière est une procédure de calcul qui, à deux entiers naturels appelés dividende et diviseur, associe deux autres entiers appelés quotient (quotient euclidien s'il y a ambiguïté) et reste.

Nouveau!!: Théorie de la complexité (informatique théorique) et Division euclidienne · Voir plus »

Divisions successives

En arithmétique, la méthode par divisions successives est la méthode la plus simple et la plus ancienne pour déterminer si un nombre entier naturel est premier (test de primalité) ou s'il est composé, pour en trouver la décomposition en produit de facteurs premiers.

Nouveau!!: Théorie de la complexité (informatique théorique) et Divisions successives · Voir plus »

Dominic Welsh

James Anthony Dominic Welsh (connu professionnellement sous le nom de DJA Welsh) (né le) Debrett's, retrieved 2012-03-11.

Nouveau!!: Théorie de la complexité (informatique théorique) et Dominic Welsh · Voir plus »

Dor Minzer

Dor Minzer est un chercheur en informatique théorique, professeur assistant au MIT.

Nouveau!!: Théorie de la complexité (informatique théorique) et Dor Minzer · Voir plus »

DSPACE

En théorie de la complexité, DSPACE (ou SPACE) désigne une famille de classes de complexité caractérisées par leur complexité en espace sur une machine de Turing déterministe.

Nouveau!!: Théorie de la complexité (informatique théorique) et DSPACE · Voir plus »

DTIME

En théorie de la complexité, DTIME (ou TIME) désigne une famille de classes de complexité caractérisée par leur complexité en temps sur une machine de Turing déterministe.

Nouveau!!: Théorie de la complexité (informatique théorique) et DTIME · Voir plus »

E (complexité)

En informatique théorique et notamment en théorie de la complexité, la classe E est une classe de complexité; c'est l'ensemble des problèmes de décision qui peuvent être décidés par une machine de Turing déterministe en temps exponentiel avec un exposant linéaire.

Nouveau!!: Théorie de la complexité (informatique théorique) et E (complexité) · Voir plus »

Edward Nelson (mathématicien)

Edward Nelson (né le à Decatur, Géorgie, États-Unis et décédé le) est un mathématicien américain.

Nouveau!!: Théorie de la complexité (informatique théorique) et Edward Nelson (mathématicien) · Voir plus »

Elementary

Elementary est un mot qui signifie élémentaire en anglais.

Nouveau!!: Théorie de la complexité (informatique théorique) et Elementary · Voir plus »

ELEMENTARY (complexité)

En théorie de la complexité, la classe de complexité ELEMENTARY des fonctions récursives élémentaires est la réunion des classes de la hiérarchie exponentielle.

Nouveau!!: Théorie de la complexité (informatique théorique) et ELEMENTARY (complexité) · Voir plus »

Elias Koutsoupias

Elias Koutsoupias, (Ηλίας Κουτσουπιάς, né en 1963 d'Elias Koutsoupias) est un informaticien grec, professeur à l'université d'Oxford.

Nouveau!!: Théorie de la complexité (informatique théorique) et Elias Koutsoupias · Voir plus »

Expression régulière

Stephen Cole Kleene, dont les travaux ont fondé le concept d'expression régulière. En informatique, une expression régulière ou expression rationnelle ou expression normaleD'après la de la norme ISO/IEC 9075:1989 par le Conseil du Trésor du Canada et qui est par le Bureau de la traduction du gouvernement du Canada.

Nouveau!!: Théorie de la complexité (informatique théorique) et Expression régulière · Voir plus »

EXPSPACE

En théorie de la complexité, EXPSPACE est la classe des problèmes décidables en espace exponentiel par une machine de Turing déterministe.

Nouveau!!: Théorie de la complexité (informatique théorique) et EXPSPACE · Voir plus »

EXPTIME

En théorie de la complexité, EXPTIME (ou EXP) est la classe de complexité qui est l'ensemble des problèmes de décision décidés par une machine de Turing déterministe en temps exponentiel.

Nouveau!!: Théorie de la complexité (informatique théorique) et EXPTIME · Voir plus »

Factorisation des polynômes

En mathématiques, la factorisation d'un polynôme consiste à écrire celui-ci comme produit de polynômes.

Nouveau!!: Théorie de la complexité (informatique théorique) et Factorisation des polynômes · Voir plus »

Fan-in

En électronique et en complexité algorithmique, le fan-in d'un fil électrique, d'une porte logique, ou d'un port d'entrée d'un bloc, est le nombre d'entrées que ce bloc gère ou peut gérer.

Nouveau!!: Théorie de la complexité (informatique théorique) et Fan-in · Voir plus »

Fan-out

En électronique et en complexité, le fan-out d'un fil électrique, ou d'une porte logique, ou d'un port de sortie d'un bloc, est le nombre maximal de blocs qui peuvent être connectés à la sortie de cet élément.

Nouveau!!: Théorie de la complexité (informatique théorique) et Fan-out · Voir plus »

Fonction à sens unique

Panneau de signalisation routière de sens unique Une fonction à sens unique (ou one-way function en anglais) est une fonction qui peut être aisément calculée, mais qui est difficile à inverser — c'est-à-dire qu'étant donnée une image, il est difficile de lui trouver un antécédent.

Nouveau!!: Théorie de la complexité (informatique théorique) et Fonction à sens unique · Voir plus »

Fonction booléenne

Arbre de décision binaire Une fonction booléenne est une fonction prenant en entrée une liste de bits et donnant en sortie un unique bit.

Nouveau!!: Théorie de la complexité (informatique théorique) et Fonction booléenne · Voir plus »

Fonction constructible

En théorie de la complexité, une fonction constructible en temps est une fonction f des entiers naturels vers les entiers naturels, avec la propriété que f(n) peut être calculée à partir de n par une machine de Turing qui se termine en un temps du même ordre de grandeur que f(n).

Nouveau!!: Théorie de la complexité (informatique théorique) et Fonction constructible · Voir plus »

Fonction négligeable (informatique)

Une fonction négligeable en informatique fondamentale, surtout en cryptographie et en complexité algorithmique, est une notion qui permet de caractériser (souvent pour en ignorer les effets) une fonction mathématique dont la contribution est faible par rapport à une référence.

Nouveau!!: Théorie de la complexité (informatique théorique) et Fonction négligeable (informatique) · Voir plus »

Formule booléenne quantifiée

En théorie de la complexité, en informatique théorique, en logique mathématique, une formule booléenne quantifiée (ou formule QBF pour en anglais) est une formule de la logique propositionnelle où les variables propositionnelles sont quantifiées.

Nouveau!!: Théorie de la complexité (informatique théorique) et Formule booléenne quantifiée · Voir plus »

Fragment (logique)

En logique mathématique, un fragment d'un langage ou d'une théorie logique est un sous-ensemble de ce langage obtenu en lui imposant des restrictions syntaxiques.

Nouveau!!: Théorie de la complexité (informatique théorique) et Fragment (logique) · Voir plus »

Fundamenta Informaticae

Fundamenta Informaticae est une revue scientifique en informatique théorique.

Nouveau!!: Théorie de la complexité (informatique théorique) et Fundamenta Informaticae · Voir plus »

Gabriel Lamé

Gabriel Lamé, dit Lamé de La Droitière, né le à Tours, mort le à Paris, est un mathématicien français.

Nouveau!!: Théorie de la complexité (informatique théorique) et Gabriel Lamé · Voir plus »

Gadget (informatique)

En informatique théorique, et plus précisément en théorie de la complexité, un gadget est un morceau d'une instance qui simule le comportement d'un autre problème algorithmique.

Nouveau!!: Théorie de la complexité (informatique théorique) et Gadget (informatique) · Voir plus »

Géométrie hyperbolique

En mathématiques, la géométrie hyperbolique (nommée auparavant géométrie de Lobatchevski, lequel est le premier à en avoir publié une étude approfondie) est une géométrie non euclidienne vérifiant les quatre premiers postulats d’Euclide, mais pour laquelle le cinquième postulat, qui équivaut à affirmer que par un point extérieur à une droite passe une et une seule droite qui lui est parallèle, est remplacé par le postulat selon lequel « par un point extérieur à une droite passent plusieurs droites parallèles à celle-ci » (il en existe alors une infinité).

Nouveau!!: Théorie de la complexité (informatique théorique) et Géométrie hyperbolique · Voir plus »

Günter Hotz

Günter Hotz (né le à Rommelhausen, commune de Limeshain) est un pionnier de l'informatique allemande.

Nouveau!!: Théorie de la complexité (informatique théorique) et Günter Hotz · Voir plus »

Gerhard Woeginger

Gerhard J. Woeginger, né le à Graz, en Autriche et mort le, est un mathématicien et informaticien autrichien.

Nouveau!!: Théorie de la complexité (informatique théorique) et Gerhard Woeginger · Voir plus »

Giorgio Ausiello

Giorgio Ausiello (né en 1941) est un informaticien italien.

Nouveau!!: Théorie de la complexité (informatique théorique) et Giorgio Ausiello · Voir plus »

Grammaire contextuelle

Une grammaire contextuelle est une grammaire formelle dans laquelle les substitutions d'un symbole non terminal sont soumises à la présence d'un contexte gauche et d'un contexte droit.

Nouveau!!: Théorie de la complexité (informatique théorique) et Grammaire contextuelle · Voir plus »

Graphe de Frankl-Rödl

Le graphe de Frankl-Rödl \operatornameFR_1/3^3 est formé des sommets d'un cube tridimensionnel et des arêtes entre des sommets à distance deux. En théorie des graphes et en théorie de complexité des calculs, un graphe de Frankl-Rödl est un graphe dont les sommets sont les sommets d'un hypercube, et les arêtes joignent des sommets qui sont à une même distance paire fixe les uns des autres.

Nouveau!!: Théorie de la complexité (informatique théorique) et Graphe de Frankl-Rödl · Voir plus »

Graphe série-parallèle

Opérations de composition en série et en parallèle pour les graphes série-parallèle. En théorie des graphes, les graphes série-parallèle sont des graphes avec deux sommets distingués, la source et le puits, et formés récursivement par deux opérations qui sont la composition en série et la composition parallèle.

Nouveau!!: Théorie de la complexité (informatique théorique) et Graphe série-parallèle · Voir plus »

Greedy randomized adaptive search procedure

Greedy randomized adaptive search procedure (GRASP) est une métaheuristique, c'est-à-dire un algorithme d’optimisation visant à résoudre des problèmes d’optimisation difficile (au sens de la théorie de la complexité) pour lesquels on ne connaît pas de méthode classique plus efficace.

Nouveau!!: Théorie de la complexité (informatique théorique) et Greedy randomized adaptive search procedure · Voir plus »

Grete Hermann

Grete (Henry-) Hermann, née le à Brême, où elle meurt le, est une mathématicienne et philosophe allemande connue pour ses travaux en mathématiques, en physique, en philosophie et en éducation.

Nouveau!!: Théorie de la complexité (informatique théorique) et Grete Hermann · Voir plus »

Haiku (système d'exploitation)

Haiku (qui s'appelait anciennement OpenBeOS) est un système d'exploitation libre.

Nouveau!!: Théorie de la complexité (informatique théorique) et Haiku (système d'exploitation) · Voir plus »

Harry Buhrman

Harry Buhrman (né en 1966) est un informaticien néerlandais.

Nouveau!!: Théorie de la complexité (informatique théorique) et Harry Buhrman · Voir plus »

Helmut Veith

Helmut Veith (–) est un informaticien autrichien qui a travaillé dans les domaines du model checking, génie logiciel, sécurité des systèmes d'information, et logique pour l'informatique.

Nouveau!!: Théorie de la complexité (informatique théorique) et Helmut Veith · Voir plus »

Heuristique (mathématiques)

Au sens le plus large, l'heuristique est la psychologie de la découverte, abordée par différents mathématiciens.

Nouveau!!: Théorie de la complexité (informatique théorique) et Heuristique (mathématiques) · Voir plus »

Hiérarchie analytique

En logique mathématique et en théorie de la complexité, la hiérarchie analytique est une extension de la hiérarchie arithmétique définie à partir de formules de la logique du second ordre sur les entiers naturels.

Nouveau!!: Théorie de la complexité (informatique théorique) et Hiérarchie analytique · Voir plus »

Hiérarchie booléenne

En informatique théorique, plus précisément en théorie de la complexité, la hiérarchie booléenne (notée BH pour Boolean hierarchy en anglais) est une hiérarchie de classes de complexité obtenues comme combinaisons booléennes (intersections, unions, et passage au complémentaire) de problèmes de décision de NP.

Nouveau!!: Théorie de la complexité (informatique théorique) et Hiérarchie booléenne · Voir plus »

Hiérarchie de croissance rapide

En théorie de la calculabilité et en théorie de la démonstration, une hiérarchie de croissance rapide (parfois appelée une hiérarchie de Grzegorczyk étendue) est une famille, indexée par les ordinaux, de fonctions rapidement croissantes fα: N → N (où N est l'ensemble des entiers naturels, et α est un ordinal inférieur à un certain ordinal dénombrable généralement très grand).

Nouveau!!: Théorie de la complexité (informatique théorique) et Hiérarchie de croissance rapide · Voir plus »

Hiérarchie polynomiale

En théorie de la complexité, la hiérarchie polynomiale est une hiérarchie de classes de complexité qui étend la notion de classes P, NP, co-NP.

Nouveau!!: Théorie de la complexité (informatique théorique) et Hiérarchie polynomiale · Voir plus »

Hypercube magique

En mathématiques, un hypercube magique de dimension d est la généralisation d'un carré magique (d.

Nouveau!!: Théorie de la complexité (informatique théorique) et Hypercube magique · Voir plus »

Impacts des Contrats Intelligents sur la société

L'Impact des Contrats Intelligents sur la société commence à être discuté et mesuré, au fur et à mesure de l'apparition d'applications tangibles reposant sur ces contrats.

Nouveau!!: Théorie de la complexité (informatique théorique) et Impacts des Contrats Intelligents sur la société · Voir plus »

Inégalité de Chernoff

En théorie des probabilités, l'inégalité de Chernoff permet de majorer la queue d'une loi de probabilité, c'est-à-dire qu'elle donne une valeur maximale de la probabilité qu'une variable aléatoire dépasse une valeur fixée.

Nouveau!!: Théorie de la complexité (informatique théorique) et Inégalité de Chernoff · Voir plus »

Indicateur de cycles

En combinatoire, un indicateur de cycles est un polynôme en plusieurs variables qui porte certaines informations sur l'action d'un groupe de permutations.

Nouveau!!: Théorie de la complexité (informatique théorique) et Indicateur de cycles · Voir plus »

Indistinguabilité calculatoire

En informatique fondamentale, l’indistinguabilité calculatoire permet d’exprimer la similarité de deux distributions de probabilités en prenant en compte des notions de complexité algorithmique.

Nouveau!!: Théorie de la complexité (informatique théorique) et Indistinguabilité calculatoire · 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!!: Théorie de la complexité (informatique théorique) et Informatique · Voir plus »

Informatique appliquée

L'informatique appliquée est un champ de connaissances enseigné dans les universités et écoles supérieures, qui s'intéresse aux sujets de science informatique qui peuvent être exploités directement dans l'industrie.

Nouveau!!: Théorie de la complexité (informatique théorique) et Informatique appliquée · Voir plus »

Informatique quantique

L'informatique quantique est le sous-domaine de l'informatique qui traite des calculateurs quantiques et des associés.

Nouveau!!: Théorie de la complexité (informatique théorique) et Informatique quantique · Voir plus »

Informatique théorique

Une représentation artistique d'une machine de Turing. Les machines de Turing sont un modèle de calcul. L'informatique théorique est l'étude des fondements logiques et mathématiques de l'informatique.

Nouveau!!: Théorie de la complexité (informatique théorique) et Informatique théorique · Voir plus »

Instance

Le mot instance peut avoir plusieurs significations dans différents domaines.

Nouveau!!: Théorie de la complexité (informatique théorique) et Instance · Voir plus »

Institut Max-Planck de physique des systèmes complexes

Bâtiment de l'Institut Max-Planck de physique des systèmes complexes à Dresde LInstitut Max-Planck de physique des systèmes complexes (MPI PSC) (en allemand Max-Planck-Institut für Physik komplexer Systeme) est un institut de recherche extra-universitaire dépendant de la Société Max-Planck situé à Dresde.

Nouveau!!: Théorie de la complexité (informatique théorique) et Institut Max-Planck de physique des systèmes complexes · Voir plus »

Intelligence artificielle

assistants personnels intelligents sont l'une des applications concrètes de l'intelligence artificielle dans les années 2010. L'intelligence artificielle (IA) est un ensemble de théories et de techniques visant à réaliser des machines capables de simuler l'intelligence humaine.

Nouveau!!: Théorie de la complexité (informatique théorique) et Intelligence artificielle · Voir plus »

International Computing and Combinatorics Conference

La conférence International Computing and Combinatorics Conference (abrégé en COCOON) est une conférence scientifique dans le domaine de l’informatique théorique, et plus particulièrement de ses aspects algorithmiques.

Nouveau!!: Théorie de la complexité (informatique théorique) et International Computing and Combinatorics Conference · Voir plus »

International Symposium on Fundamentals of Computation Theory

La conférence International Symposium on Fundamentals of Computation Theory (abrégé en FCT) est une conférence scientifique biennale dans le domaine de l’informatique théorique.

Nouveau!!: Théorie de la complexité (informatique théorique) et International Symposium on Fundamentals of Computation Theory · Voir plus »

International Symposium on Mathematical Foundations of Computer Science

La conférence International Symposium on Mathematical Foundations of Computer Science (abrégé en MFCS) est une conférence scientifique dans le domaine de l’informatique théorique.

Nouveau!!: Théorie de la complexité (informatique théorique) et International Symposium on Mathematical Foundations of Computer Science · Voir plus »

Inverse modulaire

En mathématiques et plus précisément en arithmétique modulaire, l'inverse modulaire d'un entier relatif a pour la multiplication modulo n est un entier u satisfaisant l'équation: En d'autres termes, il s'agit de l'inverse dans l'anneau des entiers modulo ''n'', noté ℤ/nℤ ou ℤ.

Nouveau!!: Théorie de la complexité (informatique théorique) et Inverse modulaire · Voir plus »

IP

Pas de description.

Nouveau!!: Théorie de la complexité (informatique théorique) et IP · Voir plus »

IP (complexité)

En informatique théorique, et notamment en théorie de la complexité, la classe IP (une abréviation pour, c'est-à-dire « interactif en temps polynomial ») est la classe des problèmes de décision qui peuvent être résolus par un système de preuve interactive.

Nouveau!!: Théorie de la complexité (informatique théorique) et IP (complexité) · Voir plus »

Isomorphisme de graphes

En mathématiques, dans le cadre de la théorie des graphes, un isomorphisme de graphes est une bijection entre les sommets de deux graphes qui préserve les arêtes.

Nouveau!!: Théorie de la complexité (informatique théorique) et Isomorphisme de graphes · Voir plus »

Jaroslav Nešetřil

Jaroslav (Jarik) Nešetřil (en) né le à Brno, est un mathématicien et informaticien théoricien tchèque, en poste à l'université Charles de Prague.

Nouveau!!: Théorie de la complexité (informatique théorique) et Jaroslav Nešetřil · Voir plus »

Jin-Yi Cai

Jin-Yi Cai (en chinois: 蔡进), né le 23 janvier 1961 à Shanghai, est un mathématicien et informaticien sino-américain.

Nouveau!!: Théorie de la complexité (informatique théorique) et Jin-Yi Cai · Voir plus »

Johan Håstad

Johan Håstad, né en 1960, est un informaticien théorique suédois connu particulièrement pour son travail sur la complexité algorithmique.

Nouveau!!: Théorie de la complexité (informatique théorique) et Johan Håstad · Voir plus »

John von Neumann

John von Neumann (János Lajos Neumann) (János Lajos Neumann en hongrois), né le à Budapest et mort le à Washington, est un mathématicien et physicien américano-hongrois.

Nouveau!!: Théorie de la complexité (informatique théorique) et John von Neumann · Voir plus »

Journal of Computer and System Sciences

Le Journal of Computer and System Sciences (abrégé en « JCSS ») est une revue scientifique dans le domaine de l'informatique théorique dont les publications sont basées sur le principe de l'évaluation par les pairs.

Nouveau!!: Théorie de la complexité (informatique théorique) et Journal of Computer and System Sciences · Voir plus »

Julia Kempe

Julia Kempe, née en, est une informaticienne et mathématicienne d'origine allemande.

Nouveau!!: Théorie de la complexité (informatique théorique) et Julia Kempe · Voir plus »

Juraj Hromkovič

Juraj Hromkovič (né le 24 août 1958 à Bratislava) est un informaticien slovaque; il est professeur à l' École polytechnique fédérale de Zurich.

Nouveau!!: Théorie de la complexité (informatique théorique) et Juraj Hromkovič · Voir plus »

Juris Hartmanis

Juris Hartmanis (né le à Riga en Lettonie et mort le) est un informaticien américain d'origine lettonne.

Nouveau!!: Théorie de la complexité (informatique théorique) et Juris Hartmanis · Voir plus »

Kazimierz Kuratowski

Kazimierz Kuratowski né en 1896 à Varsovie et mort en 1980 dans cette même ville, est un mathématicien polonais.

Nouveau!!: Théorie de la complexité (informatique théorique) et Kazimierz Kuratowski · Voir plus »

Kernelisation

En informatique théorique, et notamment en théorie de la complexité, la kernelisation ou réduction au noyau est une formalisation d'un prétraitement efficace d'une instance d'un problème NP-difficile qui consiste à l'alléger et à le simplifier.

Nouveau!!: Théorie de la complexité (informatique théorique) et Kernelisation · Voir plus »

Kobbi Nissim

Kobbi Nissim (en קובי נסים) est un informaticien théoricien, professeur au département d'informatique de l'université de Georgetown et professeur affilié au.

Nouveau!!: Théorie de la complexité (informatique théorique) et Kobbi Nissim · Voir plus »

Kurt Mehlhorn

Kurt Mehlhorn (né le à Ingolstadt) est un chercheur en informatique allemand, connu pour ses travaux en algorithmique, géométrie algorithmique, théorie de la complexité, complexité de la communication et algorithmique des graphes.

Nouveau!!: Théorie de la complexité (informatique théorique) et Kurt Mehlhorn · Voir plus »

L

L est la lettre et la consonne de l'alphabet latin.

Nouveau!!: Théorie de la complexité (informatique théorique) et L · Voir plus »

L (complexité)

En informatique théorique, et notamment dans la théorie de la complexité, la classe L est la classe des problèmes de décision décidés par une machine de Turing déterministe qui utilise un espace de taille logarithmique en fonction de la taille de l'entrée,.

Nouveau!!: Théorie de la complexité (informatique théorique) et L (complexité) · Voir plus »

Langage congruentiel

Un langage congruentiel est un langage formel qui est la réunion d'un nombre fini de classes d'une congruence sur l'alphabet donné.

Nouveau!!: Théorie de la complexité (informatique théorique) et Langage congruentiel · Voir plus »

Langage creux

En théorie de la complexité, un langage creux est un langage où le nombre de mots de longueur n est borné par un polynôme en n. Ils sont utiles dans l'étude de la classe NP.

Nouveau!!: Théorie de la complexité (informatique théorique) et Langage creux · Voir plus »

Langage formel

Un langage formel, en mathématiques, en informatique et en linguistique, est un ensemble de mots.

Nouveau!!: Théorie de la complexité (informatique théorique) et Langage formel · Voir plus »

Langage rationnel

En théorie des langages, les langages rationnels ou langages réguliers ou encore langages reconnaissables peuvent être décrits de plusieurs façons équivalentes.

Nouveau!!: Théorie de la complexité (informatique théorique) et Langage rationnel · Voir plus »

Langage unaire

En théorie des langages, en théorie de la complexité, un langage unaire est un langage qui ne contient que des mots sur une seule et même lettre, généralement notée 1.

Nouveau!!: Théorie de la complexité (informatique théorique) et Langage unaire · Voir plus »

Largeur de clique

Construction d'un graphe (ici un graphe à distance héréditaire) de largeur de clique 3 par une succession d'unions disjointes, de renommages et de fusions d'étiquettes. Les étiquettes des sommets sont affichées sous forme de couleurs. En théorie des graphes, la largeur de clique d'un graphe G est l'un des paramètres qui décrit la complexité structurelle du graphe; il est étroitement lié à largeur arborescente, mais contrairement à celle-ci, elle peut être bornée même pour des graphes denses.

Nouveau!!: Théorie de la complexité (informatique théorique) et Largeur de clique · Voir plus »

Larry J. Stockmeyer

Larry Joseph Stockmeyer (né en 1948 à Evansville, en Indiana, et mort le) est un informaticien théoricien américain.

Nouveau!!: Théorie de la complexité (informatique théorique) et Larry J. Stockmeyer · Voir plus »

Lawrence H. Landweber

Lawrence Hugh Landweber (né en 1942 ou 1943) est professeur émérite en informatique sur la chaire John P. Morgridge à l'université du Wisconsin à Madison.

Nouveau!!: Théorie de la complexité (informatique théorique) et Lawrence H. Landweber · Voir plus »

László Lovász

László Lovász (né le à Budapest) est un mathématicien hongrois connu pour ses travaux en combinatoire, notamment en théorie des graphes, et informatique théorique et président de l'Académie hongroise des sciences depuis 2014.

Nouveau!!: Théorie de la complexité (informatique théorique) et László Lovász · Voir plus »

Lemme de Schwartz-Zippel

En mathématiques, le lemme de Schwartz-Zippel est un résultat important pour évaluer l'égalité entre deux polynômes multivariés.

Nouveau!!: Théorie de la complexité (informatique théorique) et Lemme de Schwartz-Zippel · Voir plus »

Lemmings (jeu vidéo, 1991)

Lemmings est un jeu vidéo de réflexion développé par le studio écossais DMA Design, aujourd'hui Rockstar North et édité par Psygnosis en 1991.

Nouveau!!: Théorie de la complexité (informatique théorique) et Lemmings (jeu vidéo, 1991) · Voir plus »

Lenore Blum

Lenore Blum, née le à New York, est une mathématicienne américaine, dont les recherches portent entre autres sur la théorie des modèles, les corps différentiels et la complexité de calcul avec des nombres réels (machine BSS), se spécialisant dans la concorde de domaines qui ne semblent pas préalablement liés.

Nouveau!!: Théorie de la complexité (informatique théorique) et Lenore Blum · Voir plus »

Leonid Levin

Leonid Anatolievich Levin (Леонид Анатольевич Левин, né le à Dnipropetrovsk, RSS d'Ukraine) est un informaticien et logicien russo-ukraino-américain.

Nouveau!!: Théorie de la complexité (informatique théorique) et Leonid Levin · Voir plus »

Leslie Valiant

Leslie Gabriel Valiant est un informaticien théorique britannique né le à Budapest.

Nouveau!!: Théorie de la complexité (informatique théorique) et Leslie Valiant · Voir plus »

LH (complexité)

En informatique théorique, plus précisément en théorie de la complexité, la hiérarchie en temps logarithmique (LH) est la classe de complexité des problèmes de décision qui décidés par des machines de Turing alternantes, avec accès direct, en temps logarithmique et avec un nombre borné d'alternations.

Nouveau!!: Théorie de la complexité (informatique théorique) et LH (complexité) · Voir plus »

Line graph

En théorie des graphes, le line graph L(G) d'un graphe non orienté G, est un graphe qui représente la relation d'adjacence entre les arêtes de G. Le nom line graph vient d'un article de Harary et Norman publié en 1960.

Nouveau!!: Théorie de la complexité (informatique théorique) et Line graph · Voir plus »

Liste d'informaticiens et précurseurs de l'informatique

Cette liste regroupe des informaticiens (concepteur, développeur, chercheur en informatique) ainsi que des mathématiciens ou théoriciens dont les travaux ont établi, avant l'invention des ordinateurs, les bases de l'informatique moderne (travaux sur l'algorithmique, la théorie de l'information ou la théorie de la complexité des algorithmes par exemple).

Nouveau!!: Théorie de la complexité (informatique théorique) et Liste d'informaticiens et précurseurs de l'informatique · Voir plus »

Liste de classes de complexité

Cet article présente une liste de classes de complexité en théorie de la complexité.

Nouveau!!: Théorie de la complexité (informatique théorique) et Liste de classes de complexité · Voir plus »

Liste de problèmes NP-complets

Ceci est une liste des problèmes NP-complets les plus connus en théorie de la complexité des algorithmes, exprimés sous la forme d'un problème de décision.

Nouveau!!: Théorie de la complexité (informatique théorique) et Liste de problèmes NP-complets · Voir plus »

Liste de publications importantes en informatique

Voici une liste de publications importantes en informatique, organisés par domaine.

Nouveau!!: Théorie de la complexité (informatique théorique) et Liste de publications importantes en informatique · Voir plus »

Liste de publications importantes en informatique théorique

Voici une liste de publications importantes en informatique théorique, organisés par domaine.

Nouveau!!: Théorie de la complexité (informatique théorique) et Liste de publications importantes en informatique théorique · Voir plus »

Liste des principales conférences d'informatique théorique

Cette liste des principales conférences d'informatique théorique regroupe ces conférences par thèmes.

Nouveau!!: Théorie de la complexité (informatique théorique) et Liste des principales conférences d'informatique théorique · Voir plus »

Liste des projets BOINC

frameless La liste des projets BOINC est un inventaire des principales caractéristiques de tous les projets informatiques, présents et passés, utilisant le logiciel BOINC.

Nouveau!!: Théorie de la complexité (informatique théorique) et Liste des projets BOINC · Voir plus »

LOGCFL

En théorie de la complexité, LOGCFL (pour Logarithmically Reducible to context-free language en anglais) désigne la classe des problèmes réductibles en espace logarithmique à un langage hors contexte.

Nouveau!!: Théorie de la complexité (informatique théorique) et LOGCFL · Voir plus »

Logique contrainte

En informatique théorique et en théorie des jeux, la logique contrainte (nom original en anglais: constraint logic) est un formalisme proposé par Robert A. Hearn et Erik D. Demaine.

Nouveau!!: Théorie de la complexité (informatique théorique) et Logique contrainte · Voir plus »

Logique des graphes

Dans les domaines mathématiques de la théorie des graphes et de la théorie des modèles finis, la logique des graphes traite de la spécification formelle de propriétés de graphe en utilisant des proposition de la logique mathématique.

Nouveau!!: Théorie de la complexité (informatique théorique) et Logique des graphes · Voir plus »

Logique linéaire

date.

Nouveau!!: Théorie de la complexité (informatique théorique) et Logique linéaire · Voir plus »

Logique mathématique

La logique mathématique ou métamathématique est une discipline des mathématiques introduite à la fin du, qui s'est donné comme objet l'étude des mathématiques en tant que langage.

Nouveau!!: Théorie de la complexité (informatique théorique) et Logique mathématique · Voir plus »

Machine abstraite

En informatique théorique, et notamment en théorie des automates, un automate abstrait ou une machine abstraite est un modèle théorique d'un ordinateur digital et discret.

Nouveau!!: Théorie de la complexité (informatique théorique) et Machine abstraite · Voir plus »

Machine à vecteurs de support

Les machines à vecteurs de support ou séparateurs à vaste marge (en anglais, SVM) sont un ensemble de techniques d'apprentissage supervisé destinées à résoudre des problèmes de discriminationLe terme anglais pour discrimination est, qui a un sens différent en français (se rapporte au). On utilise aussi le terme classement à la place de discrimination, plus proche du terme anglais, et plus compréhensible.

Nouveau!!: Théorie de la complexité (informatique théorique) et Machine à vecteurs de support · 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!!: Théorie de la complexité (informatique théorique) et Machine de Turing · Voir plus »

Machine de Turing alternante

En informatique théorique, et notamment en théorie de la complexité, les machines de Turing alternantes sont une généralisation des machines de Turing non déterministes.

Nouveau!!: Théorie de la complexité (informatique théorique) et Machine de Turing alternante · Voir plus »

Machine de Turing non déterministe

Une machine de Turing non déterministe est similaire à une machine de Turing habituelle, qui, elle, est déterministe, mais s'en différencie dans le fait qu'étant non déterministe elle peut avoir plusieurs transitions activables, pour un état donné.

Nouveau!!: Théorie de la complexité (informatique théorique) et Machine de Turing non déterministe · Voir plus »

Machine de Turing probabiliste

En théorie de la complexité, une machine de Turing probabiliste (ou randomisée) est une machine de Turing qui peut utiliser du hasard.

Nouveau!!: Théorie de la complexité (informatique théorique) et Machine de Turing probabiliste · Voir plus »

Machine de Turing universelle

Une machine de Turing quelconque M réalise un calcul à partir d'une entrée écrite sur son ruban. Une machine de Turing universelle U simule le calcul de M sur l'entrée de M à partir d'une description de M et de l'entrée de M écrits sur le ruban de U. En informatique, plus précisément en informatique théorique, une machine de Turing universelle est une machine de Turing qui peut simuler n'importe quelle machine de Turing sur n'importe quelle entrée.

Nouveau!!: Théorie de la complexité (informatique théorique) et Machine de Turing universelle · Voir plus »

Manuel Blum

Manuel Blum (né à Caracas le) est un informaticien américain, professeur en informatique à l'université Carnegie-Mellon.

Nouveau!!: Théorie de la complexité (informatique théorique) et Manuel Blum · Voir plus »

Marc Snir

Marc Snir est un informaticien israélien et américain, né à Courbevoie, le, qui est titulaire de la chaire Michael Faiman and Saburo Muroga au département d'informatique de l'Université d'Illinois à Urbana-Champaign et enseignant invité à la, tout en étant chercheur en calcul parallèle et chef du projet.

Nouveau!!: Théorie de la complexité (informatique théorique) et Marc Snir · Voir plus »

Marek Karpinski

Marek Karpinski est un informaticien et mathématicien connu pour ses recherches en théorie d'algorithmes et leurs applications, en optimisation combinatoire, en théorie de la complexité et en fondations mathématiques d'informatique.

Nouveau!!: Théorie de la complexité (informatique théorique) et Marek Karpinski · Voir plus »

Mario Szegedy

Márió Szegedy, né le, est un mathématicien et informaticien hongrois.

Nouveau!!: Théorie de la complexité (informatique théorique) et Mario Szegedy · Voir plus »

Mathématiques

Les mathématiques (ou la mathématique) sont un ensemble de connaissances abstraites résultant de raisonnements logiques appliqués à des objets divers tels que les ensembles mathématiques, les nombres, les formes, les structures, les transformations; ainsi qu'aux relations et opérations mathématiques qui existent entre ces objets.

Nouveau!!: Théorie de la complexité (informatique théorique) et Mathématiques · Voir plus »

Mathématiques computationnelles

Une interprétation en noir et blanc de la tablette YBC 7289 de la Yale Babylonian Collection (vers 1800–1600 avant notre ère), montrant une approximation babylonienne de la racine carrée de 2 (1 24 51 10 w: sexagésimal) dans le contexte du théorème de Pythagore pour un triangle isocèle. La tablette donne également un exemple où un côté du carré est 30 et la diagonale résultante est 42 25 35 soit 42,4263888. Les mathématiques computationnelles interviennent dans les recherches mathématiques ainsi que dans des domaines scientifiques où le calcul joue un rôle central et essentiel, et mettent l'accent sur les algorithmes, les méthodes numériques et les calculs symboliquesNational Science Foundation, Division of Mathematical Science,, 2006.

Nouveau!!: Théorie de la complexité (informatique théorique) et Mathématiques computationnelles · Voir plus »

Mathématiques discrètes

Les mathématiques discrètes, parfois appelées mathématiques finies, sont l'étude des structures mathématiques fondamentalement discrètes, par opposition aux structures continues.

Nouveau!!: Théorie de la complexité (informatique théorique) et Mathématiques discrètes · Voir plus »

Matrice bande

En mathématiques, une matrice bande ou une matrice à bande est une matrice creuse dont les coefficients non nuls sont restreints à une bande diagonale, comprenant la diagonale principale et éventuellement une ou plusieurs diagonales de chaque côté.

Nouveau!!: Théorie de la complexité (informatique théorique) et Matrice bande · Voir plus »

Médaille John von Neumann

John von Neumann dans les années 1980 La médaille John von Neumann est une récompense attribuée tous les ans depuis 1992 par l'IEEE à une ou deux personnes en reconnaissance de leurs « accomplissements extraordinaires en sciences et technologies informatiques ».

Nouveau!!: Théorie de la complexité (informatique théorique) et Médaille John von Neumann · Voir plus »

Médaille Konrad-Zuse

La médaille du mérite Konrad-Zuse en informatique, en bref médaille Konrad-Zuse est une distinction créée en 1967 par la Société pour l'informatique.

Nouveau!!: Théorie de la complexité (informatique théorique) et Médaille Konrad-Zuse · Voir plus »

Médiane (statistiques)

En théorie des probabilités et en statistiques, la médiane est une valeur qui sépare la moitié inférieure et la moitié supérieure des termes d’une série statistique quantitative ou d’une variable aléatoire réelle.

Nouveau!!: Théorie de la complexité (informatique théorique) et Médiane (statistiques) · Voir plus »

Métaheuristique

Une métaheuristique est un algorithme d’optimisation visant à résoudre des problèmes d’optimisation difficiles (souvent issus des domaines de la recherche opérationnelle, de l'ingénierie ou de l'intelligence artificielle) pour lesquels on ne connaît pas de méthode classique plus efficace.

Nouveau!!: Théorie de la complexité (informatique théorique) et Métaheuristique · Voir plus »

Méthode de factorisation de Fermat

Pierre de Fermat En arithmétique modulaire, la méthode de factorisation de Fermat est un algorithme de décomposition en produit de facteurs premiers d'un entier naturel.

Nouveau!!: Théorie de la complexité (informatique théorique) et Méthode de factorisation de Fermat · Voir plus »

Michael Garey

Michael Randolph Garey, né le à Manitowoc dans le Wisconsin, est un informaticien américain.

Nouveau!!: Théorie de la complexité (informatique théorique) et Michael Garey · Voir plus »

Michael J. Fischer

Michael John Fischer est un informaticien américain, né le à Ann Arbor (Michigan), qui travaille dans les domaines de calcul distribué, parallélisme (informatique), cryptographie, algorithmique et structures de données et en théorie de la complexité.

Nouveau!!: Théorie de la complexité (informatique théorique) et Michael J. Fischer · Voir plus »

Michael Rabin

Michael Oser Rabin, né le à Breslau en Allemagne, maintenant Wrocław en Pologne) est un informaticien et un logicien israélien. Il a été récipiendaire du prix Turing, la récompense la plus prestigieuse en informatique.

Nouveau!!: Théorie de la complexité (informatique théorique) et Michael Rabin · Voir plus »

Michael Saks

Michael Ezra Saks est un mathématicien et informaticien théoricien américain.

Nouveau!!: Théorie de la complexité (informatique théorique) et Michael Saks · Voir plus »

Michael Shub

Michael Ira Shub (connu également comme Mike Shub), né le à Brooklyn, est un mathématicien américain.

Nouveau!!: Théorie de la complexité (informatique théorique) et Michael Shub · Voir plus »

Michael Sipser

Michael Fredric Sipser est professeur de mathématiques appliquées et chercheur dans le groupe au MIT.

Nouveau!!: Théorie de la complexité (informatique théorique) et Michael Sipser · Voir plus »

Michael Stewart Paterson

Michael Stewart « Mike » Paterson, né en 1942, est un informaticien théoricien britannique, spécialiste en conception et analyse des algorithmes et en théorie de la complexité.

Nouveau!!: Théorie de la complexité (informatique théorique) et Michael Stewart Paterson · Voir plus »

Mihalis Yannakakis

Mihalis Yannakakis est un chercheur en informatique, né le à Athènes.

Nouveau!!: Théorie de la complexité (informatique théorique) et Mihalis Yannakakis · Voir plus »

Minimisation d'un automate fini déterministe

Dans cet automate, tous les états sont accessibles, les états ''c, d'' et ''e'' sont indistinguables, ainsi que les états ''a'' et ''b''. Automate minimal équivalent. Les états indistinguables sont regroupés en un seul état. En informatique théorique, et plus particulièrement en théorie des automates, la minimisation d'un automate fini déterministe est l'opération qui consiste à transformer un automate fini déterministe donné en un automate fini déterministe ayant le nombre minimal d'états et qui reconnaît le même langage rationnel.

Nouveau!!: Théorie de la complexité (informatique théorique) et Minimisation d'un automate fini déterministe · Voir plus »

Modèle standard (cryptologie)

En cryptologie, dans le contexte des preuves de sécurité, le modèle standardAussi parfois appelé « modèle ordinaire » (plain model) ou « modèle nu » (bare model) dans la littérature anglophone.

Nouveau!!: Théorie de la complexité (informatique théorique) et Modèle standard (cryptologie) · Voir plus »

Morpion solitaire

Le morpion solitaire, ou jeu de la croix de malte, est un casse-tête se pratiquant seul.

Nouveau!!: Théorie de la complexité (informatique théorique) et Morpion solitaire · Voir plus »

Moteur de base de données

En informatique, un moteur de base de données ou moteur de stockage (anglais database engine ou storage engine) est un composant logiciel qui contrôle, lit, enregistre et trie des informations dans une ou plusieurs bases de données.

Nouveau!!: Théorie de la complexité (informatique théorique) et Moteur de base de données · Voir plus »

Multi-arbre

En combinatoire et en théorie des ordres, le terme multi-arbre peut décrire l'une des deux structures suivantes: un graphe orienté acyclique dans lequel l'ensemble des sommets accessibles depuis un nœud est toujours un arbre, ou un ensemble partiellement ordonné dans lequel il n'existe pas quatre éléments a, b, c, et d qui forment un sous-ordre en diamant, avec et mais où b et c sont incomparables (un tel ensemble ordonné est aussi appelé diamond-free poset (ou ordre partiel sans diamant)..

Nouveau!!: Théorie de la complexité (informatique théorique) et Multi-arbre · Voir plus »

Naum Z. Shor

Naum Zuselevich Shor (en Наум Зуселевич Шор), souvent cité sous la forme Naum Z. Shor, (–) est un mathématicien soviétique et ukrainien spécialiste en optimisation.

Nouveau!!: Théorie de la complexité (informatique théorique) et Naum Z. Shor · Voir plus »

NC

NC est un sigle qui peut faire référence à.

Nouveau!!: Théorie de la complexité (informatique théorique) et NC · Voir plus »

NC (complexité)

En théorie de la complexité, un domaine de l'informatique théorique, NC (pour) est une classe de complexité faisant intervenir le parallélisme.

Nouveau!!: Théorie de la complexité (informatique théorique) et NC (complexité) · Voir plus »

NE (complexité)

En informatique théorique et notamment en théorie de la complexité, la classe NE est une classe de complexité; c'est l'ensemble des problèmes de décision qui peuvent être décidés par une machine de Turing non déterministe en temps exponentiel avec un exposant linéaire.

Nouveau!!: Théorie de la complexité (informatique théorique) et NE (complexité) · Voir plus »

Neeraj Kayal

Neeraj Kayal (en नीरज कयाल) est un mathématicien et informaticien indien, né à Guwahati en Inde.

Nouveau!!: Théorie de la complexité (informatique théorique) et Neeraj Kayal · Voir plus »

Neil Immerman

Neil Immerman, né le à Manhasset dans l'État de New York, est un informaticien américain, spécialiste de l'informatique théorique, professeur d'informatique à l'université du Massachusetts à Amherst, Computer Science Department, University of Massachusetts Amherst, consulté le 23 janvier 2010.

Nouveau!!: Théorie de la complexité (informatique théorique) et Neil Immerman · Voir plus »

NEXPSPACE

NEXPSPACE est une classe de la théorie de la complexité.

Nouveau!!: Théorie de la complexité (informatique théorique) et NEXPSPACE · Voir plus »

NEXPTIME

En théorie de la complexité, NEXPTIME, ou NEXP, est une classe de complexité, c'est-à-dire un ensemble de problèmes de décision.

Nouveau!!: Théorie de la complexité (informatique théorique) et NEXPTIME · Voir plus »

Nicolas Gauvrit

Nicolas Gauvrit (né le est un universitaire, mathématicien français spécialisé en sciences cognitives et en psychologie.

Nouveau!!: Théorie de la complexité (informatique théorique) et Nicolas Gauvrit · Voir plus »

Nitin Saxena

Nitin Saxena (en नितिन सक्सेना), né le 3 mai 1981 à Allahabad en Inde) est un mathématicien et informaticien théoricien indien. Il est surtout connu pour avoir découvert, alors qu'il était encore étudiant, avec son professeur Manindra Agrawal et son co-étudiant Neeraj Kayal, un algorithme polynomial de test de primalité, appelé d'après leurs initiales le test de primalité AKS.

Nouveau!!: Théorie de la complexité (informatique théorique) et Nitin Saxena · Voir plus »

NL

NL est un code, qui signifie.

Nouveau!!: Théorie de la complexité (informatique théorique) et NL · Voir plus »

NL (complexité)

En informatique théorique, plus précisément en théorie de la complexité, NL est une classe de complexité.

Nouveau!!: Théorie de la complexité (informatique théorique) et NL (complexité) · Voir plus »

Noam Nisan

Noam Nisan, né en 1961, est un chercheur et professeur israélien d'informatique de l'université hébraïque de Jérusalem (HUJI), connu pour son travail en théorie de la complexité, en théorie algorithmique des jeux et en complexité de la communication.

Nouveau!!: Théorie de la complexité (informatique théorique) et Noam Nisan · Voir plus »

Nombre de Shannon

Le nombre de Shannon, soit 10120, est une estimation de la complexité du jeu d'échecs, c'est-à-dire du nombre de parties différentes, ayant un sens échiquéen, possibles.

Nouveau!!: Théorie de la complexité (informatique théorique) et Nombre de Shannon · Voir plus »

Nombre premier

Entiers naturels de zéro à cent. Les nombres premiers sont marqués en rouge. 7 est premier car il admet exactement deux diviseurs positifs distincts. Un nombre premier est un entier naturel qui admet exactement deux diviseurs distincts entiers et positifs.

Nouveau!!: Théorie de la complexité (informatique théorique) et Nombre premier · Voir plus »

Nombre remarquable

En mathématiques, certains nombres se distinguent des autres, jouent un rôle clef, ou apparaissent curieusement dans beaucoup de formules.

Nouveau!!: Théorie de la complexité (informatique théorique) et Nombre remarquable · Voir plus »

NP

Le sigle NP peut signifier.

Nouveau!!: Théorie de la complexité (informatique théorique) et NP · Voir plus »

NP (complexité)

La classe NP est une classe très importante de la théorie de la complexité.

Nouveau!!: Théorie de la complexité (informatique théorique) et NP (complexité) · Voir plus »

NP-complétude faible

En informatique théorique, plus précisément en théorie de la complexité, un problème est faiblement NP-complet s'il est NP-complet mais qu'il admet un algorithme en temps polynomial si on encode les entiers contenus dans les entrées en unaire.

Nouveau!!: Théorie de la complexité (informatique théorique) et NP-complétude faible · Voir plus »

NP-difficile

Mise en évidence d'un problème NP-difficile si Problème P ≟ NP. Un problème NP-difficile est, en théorie de la complexité, un problème appartenant à la classe NP-difficile, ce qui revient à dire qu'il est au moins aussi difficile que les problèmes les plus difficiles de la classe NP.

Nouveau!!: Théorie de la complexité (informatique théorique) et NP-difficile · Voir plus »

NP-facile

Dans la théorie de la complexité, un problème est NP-facile s'il est résoluble en temps polynomial par une machine de Turing déterministe avec oracle, pour un certain problème de décision dans NP.

Nouveau!!: Théorie de la complexité (informatique théorique) et NP-facile · Voir plus »

NP-intermédiaire

En théorie de la complexité, un problème NP-intermédiaire est un problème dans NP, qui n'est ni NP-complet et ni dans P. La classe des problèmes NP-intermédiaires se note NPI.

Nouveau!!: Théorie de la complexité (informatique théorique) et NP-intermédiaire · Voir plus »

NSPACE

En théorie de la complexité, NSPACE désigne une famille de classes de complexité caractérisées par leur complexité en espace sur une machine de Turing non déterministe.

Nouveau!!: Théorie de la complexité (informatique théorique) et NSPACE · Voir plus »

NTIME

En théorie de la complexité, NTIME désigne une famille de classes de complexité caractérisée par leur complexité en temps sur une machine de Turing non déterministe.

Nouveau!!: Théorie de la complexité (informatique théorique) et NTIME · Voir plus »

O

O est la lettre et la voyelle de l'alphabet latin.

Nouveau!!: Théorie de la complexité (informatique théorique) et O · Voir plus »

Oded Goldreich

Oded Goldreich, né le à Tel Aviv, est un chercheur en informatique théorique israélien, professeur à l'Institut Weizmann en Israël, spécialisé dans les preuves à divulgation nulle de connaissance.

Nouveau!!: Théorie de la complexité (informatique théorique) et Oded Goldreich · Voir plus »

Oded Regev

Oded Regev est un mathématicien et informaticien.

Nouveau!!: Théorie de la complexité (informatique théorique) et Oded Regev · Voir plus »

Olga Holtz

Olga Vladimirovna Holtz (née le) est une mathématicienne russe spécialisée en analyse numérique.

Nouveau!!: Théorie de la complexité (informatique théorique) et Olga Holtz · Voir plus »

Oméga (homonymie)

Cet article recense les usages du terme oméga.

Nouveau!!: Théorie de la complexité (informatique théorique) et Oméga (homonymie) · Voir plus »

Omer Reingold

Omer Reingold (עומר ריינגולד), spécialiste en théorie de la complexité des algorithmes, est chercheur principal (Principal Researcher Engineer) au Samsung Research America depuis février 2015, après avoir été chercheur principal (Principal Researcher) au centre de recherche Microsoft à Silicon Valley.

Nouveau!!: Théorie de la complexité (informatique théorique) et Omer Reingold · Voir plus »

Optimisation combinatoire

L’optimisation combinatoire, (sous-ensemble à nombre de solutions finies de l'optimisation discrète), est une branche de l'optimisation en mathématiques appliquées et en informatique, également liée à la recherche opérationnelle, l'algorithmique et la théorie de la complexité.

Nouveau!!: Théorie de la complexité (informatique théorique) et Optimisation combinatoire · Voir plus »

Optimisation de code

En programmation informatique, l'optimisation de code est la pratique consistant à améliorer l'efficacité du code informatique d'un programme ou d'une bibliothèque logicielle.

Nouveau!!: Théorie de la complexité (informatique théorique) et Optimisation de code · Voir plus »

Optimisation linéaire

Optimisation linéaire dans un espace à deux dimensions (''x''1, ''x''2). La fonction-coût ''f''c est représentée par les lignes de niveau bleues à gauche et par le plan bleu à droite. L'ensemble admissible E est le pentagone vert. En optimisation mathématique, un problème d'optimisation linéaire demande de minimiser une fonction linéaire sur un polyèdre convexe.

Nouveau!!: Théorie de la complexité (informatique théorique) et Optimisation linéaire · Voir plus »

Optimisation linéaire en nombres entiers

L'optimisation linéaire en nombres entiers (OLNE) (ou programmation linéaire en nombres entiers (PLNE) ou integer programming (IP) ou Integer Linear Programming (ILP)) est un domaine des mathématiques et de l'informatique théorique dans lequel on considère des problèmes d'optimisation d'une forme particulière.

Nouveau!!: Théorie de la complexité (informatique théorique) et Optimisation linéaire en nombres entiers · Voir plus »

Optimisation multidisciplinaire

L'Optimisation de Conception Multidisciplinaire (OMD ou MDO, Multidisciplinary Design Optimisation, en anglais) est un domaine d'ingénierie qui utilise des méthodes d'optimisation afin de résoudre des problèmes de conception mettant en œuvre plusieurs disciplines.

Nouveau!!: Théorie de la complexité (informatique théorique) et Optimisation multidisciplinaire · Voir plus »

Optimisation sous contraintes distribuée

L'optimisation sous contraintes distribuées (en anglais Distributed Constraint Optimization Problem, DCOP ou DisCOP) est l'alter ego distribué de l'optimisation sous contraintes.

Nouveau!!: Théorie de la complexité (informatique théorique) et Optimisation sous contraintes distribuée · Voir plus »

Oracle (machine de Turing)

Une machine de Turing avec oracle peut faire appel à une boîte noire (oracle). En théorie de la complexité ou de la calculabilité, les machines de Turing avec oracle sont une variante des machines de Turing disposant d'une boîte noire, un oracle, capable de résoudre un problème de décision en une seule opération élémentaire.

Nouveau!!: Théorie de la complexité (informatique théorique) et Oracle (machine de Turing) · Voir plus »

Ordinateur à ADN

L'ordinateur à ADN est une des voies non électroniques actuellement explorées pour résoudre des problèmes combinatoires.

Nouveau!!: Théorie de la complexité (informatique théorique) et Ordinateur à ADN · Voir plus »

Ordinateur quantique

qubits et la deuxième un qubit, les boîtes représentent des opérations, et le diagramme se lit de gauche à droite correspondant à la chronologie des opérationshttps://blogs.msdn.microsoft.com/visualstudio/2018/12/01/qubits-in-qsharp/. Un ordinateur quantique, calculateur quantique, processeur quantique ou système informatique quantique, utilise les propriétés quantiques de la matière, telles que la superposition et l'intrication, afin d'effectuer des opérations sur des données.

Nouveau!!: Théorie de la complexité (informatique théorique) et Ordinateur quantique · Voir plus »

P

P est la et la de l'alphabet latin.

Nouveau!!: Théorie de la complexité (informatique théorique) et P · Voir plus »

P (complexité)

La classe P, aussi noté parfois PTIME ou DTIME(nO(1)), est une classe très importante de la théorie de la complexité, un domaine de l'informatique théorique et des mathématiques.

Nouveau!!: Théorie de la complexité (informatique théorique) et P (complexité) · Voir plus »

P-complet

En théorie de la complexité computationnelle, un problème de décision est P-complet (c.-à-d. complet pour la classe de complexité '''P''' des problèmes en temps polynomial) s'il est dans P et tout problème dans P peut y être réduit par une réduction en espace logarithmique (d'autres réductions sont aussi utilisées, comme NC).

Nouveau!!: Théorie de la complexité (informatique théorique) et P-complet · Voir plus »

P/poly

En 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.

Nouveau!!: Théorie de la complexité (informatique théorique) et P/poly · Voir plus »

Parallélisme (informatique)

Blue Gene L cabinet, un des supercalculateurs massivement parallèles les plus rapides des années 2000. En informatique, le parallélisme consiste à mettre en œuvre des architectures d'électronique numérique permettant de traiter des informations de manière simultanée, ainsi que les algorithmes spécialisés pour celles-ci.

Nouveau!!: Théorie de la complexité (informatique théorique) et Parallélisme (informatique) · Voir plus »

Parallel random access machine

En informatique, PRAM, pour Parallel Random Access Machine, est un modèle abstrait de machine destiné à concevoir des algorithmes pour machines parallèles de modèle MIMD, ou pour de plus rares cas de modèle SIMD.

Nouveau!!: Théorie de la complexité (informatique théorique) et Parallel random access machine · Voir plus »

Partition binaire de l'espace

Partition binaire de l'espace (haut) et arbre BSP correspondant (bas). L'espace contient des segments A, B1, B2, C1, C2, D1, D2, D3. Le nœud racine contient le segment A; les deux sous-arbres correspondent aux zones de part et d'autre de A. Partition binaire d'un espace à trois dimensions pour la construction d'un arbre ''k''-d. La partition binaire de l'espace (ou BSP) est un système utilisé pour diviser l'espace en zones convexes.

Nouveau!!: Théorie de la complexité (informatique théorique) et Partition binaire de l'espace · Voir plus »

Partition d'un entier

En mathématiques, une partition d'un entier (parfois aussi appelée partage d'un entier) est une décomposition de cet entier en une somme d'entiers strictement positifs (appelés parties ou sommants), à l'ordre près des termes (à la différence du problème de composition tenant compte de l'ordre des termes).

Nouveau!!: Théorie de la complexité (informatique théorique) et Partition d'un entier · Voir plus »

Partition en cliques

En théorie des graphes, une couverture par cliques ou une partition en cliques d'un graphe non orienté est une partition des sommets du graphe en cliques, c'est-à-dire en des ensembles de sommets à l'intérieur desquels deux sommets sont adjacents.

Nouveau!!: Théorie de la complexité (informatique théorique) et Partition en cliques · Voir plus »

Patrick C. Fischer

Patrick Carl Fischer (3 décembre 1935 – 26 août 2011) est un informaticien théoricien américain, un des premiers chercheurs en théorie de la complexité informatique et en théorie des bases de données; il a par ailleurs été l'une des cibles de l'Unabomber.

Nouveau!!: Théorie de la complexité (informatique théorique) et Patrick C. Fischer · Voir plus »

Paul E. Schupp

Paul Eugene Schupp, né le, est professeur émérite en mathématiques à l'université de l'Illinois à Urbana-Champaign.

Nouveau!!: Théorie de la complexité (informatique théorique) et Paul E. Schupp · Voir plus »

Paul Spirakis

Paul Spirakis, né le en Grèce sur Academia Europaea.

Nouveau!!: Théorie de la complexité (informatique théorique) et Paul Spirakis · Voir plus »

Paul Vitanyi

Paul Michael Béla Vitányi (né le) est un informaticien néerlandais, professeur d'informatique à l'université d'Amsterdam et chercheur au Dutch Centrum Wiskunde & Informatica.

Nouveau!!: Théorie de la complexité (informatique théorique) et Paul Vitanyi · Voir plus »

PCP

PCP est acronyme de plusieurs choses listées ci-dessous.

Nouveau!!: Théorie de la complexité (informatique théorique) et PCP · Voir plus »

Peter Winkler

Peter Mann Winkler est un mathématicien et informaticien théoricien qui travaille en mathématiques discrètes, théorie de la complexité et théorie des probabilités.

Nouveau!!: Théorie de la complexité (informatique théorique) et Peter Winkler · Voir plus »

PH (complexité)

En théorie de la complexité, PH est l'union des classes de complexité de la hiérarchie polynomiale: PH a été introduite par Larry J. Stockmeyer en 1977.

Nouveau!!: Théorie de la complexité (informatique théorique) et PH (complexité) · Voir plus »

Philip Mirowski

Philip Mirowski, né le à Jackson (Michigan), est un historien et philosophe américain de la pensée économique.

Nouveau!!: Théorie de la complexité (informatique théorique) et Philip Mirowski · Voir plus »

Philippe Flajolet

Philippe Flajolet, né le à Lyon et mort le à Suresnes, est un chercheur français en informatique et en mathématiques.

Nouveau!!: Théorie de la complexité (informatique théorique) et Philippe Flajolet · Voir plus »

Phylo

Fonctionnement participatif: les séquences à améliorer sont extraites du logiciel Multiz, proposées aux joueurs, puis réinjectées dans Multiz. Phylo est un jeu vidéo sur navigateur web de type puzzle publié en 2010 par l'université McGill de Montréal.

Nouveau!!: Théorie de la complexité (informatique théorique) et Phylo · Voir plus »

Physique numérique (théorique)

En physique et en cosmologie, la physique numérique est une collection de points de vue théoriques basés sur l'hypothèse que l'univers est, fondamentalement, descriptible par l'information, et est donc calculable.

Nouveau!!: Théorie de la complexité (informatique théorique) et Physique numérique (théorique) · Voir plus »

Placement-routage

En électronique, le placement-routage est le processus lors duquel les différentes parties d'un circuit électronique ou d'un circuit intégré sont automatiquement positionnées et connectées.

Nouveau!!: Théorie de la complexité (informatique théorique) et Placement-routage · Voir plus »

Plus longue sous-séquence commune

En informatique théorique, la plus longue sous-séquence commune à deux suites, ou deux chaînes de caractères, est une sous-suite extraite des deux suites, et de taille maximum.

Nouveau!!: Théorie de la complexité (informatique théorique) et Plus longue sous-séquence commune · Voir plus »

Point d'articulation (théorie des graphes)

Un graphe qui est une chaîne de 5 sommets. Les sommets rouges (internes) sont des points d'articulations: supprimés, il sépare le graphe en deux parties. En mathématiques, et en particulier en théorie des graphes, un point d'articulation est un sommet d'un graphe non orienté qui, si on le retire du graphe, augmente le nombre de composantes connexes.

Nouveau!!: Théorie de la complexité (informatique théorique) et Point d'articulation (théorie des graphes) · Voir plus »

Polylogarithmique

Une fonction polylogarithmique de n est une fonction polynomiale en le logarithme de sa variable.

Nouveau!!: Théorie de la complexité (informatique théorique) et Polylogarithmique · Voir plus »

Polynôme

Courbe représentative d'une fonction cubique. En mathématiques, un polynôme est une expression formée uniquement de produits et de sommes de constantes et d'indéterminées (aussi appelées variables), habituellement notées X, Y, Z, etc.

Nouveau!!: Théorie de la complexité (informatique théorique) et Polynôme · Voir plus »

PP

PP désigne.

Nouveau!!: Théorie de la complexité (informatique théorique) et PP · Voir plus »

PP (complexité)

PP est un objet de la théorie de la complexité, un domaine de l'informatique théorique.

Nouveau!!: Théorie de la complexité (informatique théorique) et PP (complexité) · Voir plus »

PPA

PPA peut désigner.

Nouveau!!: Théorie de la complexité (informatique théorique) et PPA · Voir plus »

PPA (complexité)

En informatique théorique, plus précisément en théorie de la complexité computationnelle, PPA est une classe de complexité, signifiant "Polynomial Parity Argument" (sur un graphe).

Nouveau!!: Théorie de la complexité (informatique théorique) et PPA (complexité) · Voir plus »

Prasad Raghavendra

Prasad Raghavendra est un mathématicien indien, professeur à l'université de Californie à Berkeley.

Nouveau!!: Théorie de la complexité (informatique théorique) et Prasad Raghavendra · Voir plus »

Preuve de sécurité

En cryptographie, une preuve de sécurité est la preuve qu'un ensemble d’algorithmes cryptographiques (aussi appelé schéma) respecte les définitions de sécurité qui leur sont requises.

Nouveau!!: Théorie de la complexité (informatique théorique) et Preuve de sécurité · Voir plus »

Preuve naturelle

En théorie de la complexité, une preuve naturelle est une démonstration de borne inférieure sur des circuits booléens qui satisfait certaines propriétés.

Nouveau!!: Théorie de la complexité (informatique théorique) et Preuve naturelle · Voir plus »

Preuve vérifiable de manière probabiliste

En théorie de la complexité, une preuve vérifiable de manière probabiliste aussi appelée preuve vérifiable en probabilité ou PCP (pour Probabilistically checkable proof) est une preuve (certificat) qui peut être vérifiée par un algorithme probabiliste, en utilisant un certain nombre de bits aléatoires et en lisant un certain nombre de bits de la preuve.

Nouveau!!: Théorie de la complexité (informatique théorique) et Preuve vérifiable de manière probabiliste · Voir plus »

Principe de Yao

En informatique théorique, le principe de Yao, ou principe min-max de Yao, est un théorème qui établit une relation générale entre les performances des algorithmes probabilistes et des algorithmes déterministes.

Nouveau!!: Théorie de la complexité (informatique théorique) et Principe de Yao · Voir plus »

Prix ACM en informatique

Le prix ACM en informatique est un prix annuel décerné par l'Association for Computing Machinery (ACM) depuis 2007, pour honorer « une contribution novatrice fondamentale à mi-carrière d'un chercheur en informatique qui, par sa profondeur, son impact et ses implications générales, illustre les plus grands succès de la discipline.

Nouveau!!: Théorie de la complexité (informatique théorique) et Prix ACM en informatique · Voir plus »

Prix Donald E. Knuth

Le prix Knuth récompense les scientifiques ayant apporté une contribution exceptionnelle en informatique théorique.

Nouveau!!: Théorie de la complexité (informatique théorique) et Prix Donald E. Knuth · Voir plus »

Prix EATCS

Le prix EATCS est un prix, remis par l'European Association for Theoretical Computer Science (EATCS) à un chercheur pour honorer sa brillante carrière en informatique théorique.

Nouveau!!: Théorie de la complexité (informatique théorique) et Prix EATCS · Voir plus »

Prix Gödel

Le prix Gödel est une distinction créée en 1992 par l'European Association for Theoretical Computer Science (EATCS) et le Special Interest Group on Algorithms and Computation Theory (SIGACT) de l'Association for Computing Machinery (ACM) pour honorer des travaux remarquables d'informatique théorique.

Nouveau!!: Théorie de la complexité (informatique théorique) et Prix Gödel · Voir plus »

Prix Grace-Murray-Hopper

Le prix Grace-Murray-Hopper est un prix de l'Association for Computing Machinery (ACM) créé en 1971.

Nouveau!!: Théorie de la complexité (informatique théorique) et Prix Grace-Murray-Hopper · Voir plus »

Prix Michael-et-Sheila-Held

Le prix Michael-et-Sheila-Held est un annuel décerné par l'Académie nationale des sciences des États-Unis depuis 2018.

Nouveau!!: Théorie de la complexité (informatique théorique) et Prix Michael-et-Sheila-Held · Voir plus »

Prix Turing

Le prix Turing ou, en hommage à Alan Turing (1912-1954), est attribué tous les ans depuis 1966 à une personne sélectionnée pour sa contribution de nature technique faite à la communauté informatique.

Nouveau!!: Théorie de la complexité (informatique théorique) et Prix Turing · Voir plus »

Problème 3-SAT

En informatique théorique, plus précisément en théorie de la complexité, le problème 3-SAT est un problème surtout utilisé pour démontrer que d'autres problèmes sont NP-difficiles.

Nouveau!!: Théorie de la complexité (informatique théorique) et Problème 3-SAT · Voir plus »

Problème à promesse

Dans la théorie de la complexité computationnelle, un problème à promesse est une généralisation d'un problème de décision où l'entrée doit appartenir à un sous-ensemble donné de toutes les entrées possibles (la promesse ou précondition), et la sortie reste binaire.

Nouveau!!: Théorie de la complexité (informatique théorique) et Problème à promesse · Voir plus »

Problème de comptage

En théorie de la complexité et en théorie de la calculabilité, un problème de comptage est un type particulier de problème algorithmique.

Nouveau!!: Théorie de la complexité (informatique théorique) et Problème de comptage · Voir plus »

Problème de couverture par sommets

Il y a 6 couloirs à contrôler et il faut placer le nombre minimal de caméras 360° de façon que chaque couloir soit vu par au moins une caméra. Le nombre minimal est 2 et les deux caméras forment une couverture par sommets. En théorie des graphes et informatique théorique, le problème de couverture minimum par sommets (ou problème du transversal minimum, en anglais) est un problème algorithmique classique.

Nouveau!!: Théorie de la complexité (informatique théorique) et Problème de couverture par sommets · Voir plus »

Problème de décision

En informatique théorique, un problème de décision est une question mathématique dont la réponse est soit « oui », soit « non ».

Nouveau!!: Théorie de la complexité (informatique théorique) et Problème de décision · Voir plus »

Problème de l'évaluation d'un circuit

Exemple d'un circuit avec deux entrées 1 et 0. La sortie vaut 1 (cliquer sur l'image pour voir l'animation qui calcule la sortie). En informatique théorique, plus précisément en théorie de la complexité, le problème de l'évaluation d'un circuit (appelé CIRCUIT VALUE PROBLEM, CVP, CIRCUIT EVALUATION PROBLEM ou CIRCUIT-EVAL en anglais) est le problème de décision qui consiste à calculer la sortie d'un circuit booléen sur des entrées données.

Nouveau!!: Théorie de la complexité (informatique théorique) et Problème de l'évaluation d'un circuit · Voir plus »

Problème de l'isomorphisme de graphes

Le problème est de savoir si deux graphes sont les mêmes. En informatique théorique, le problème de l'isomorphisme de graphes est le problème de décision qui consiste, étant donné deux graphes non orientés, à décider s'ils sont isomorphes ou pas, c'est-à-dire s'ils sont les mêmes, quitte à renommer les sommets.

Nouveau!!: Théorie de la complexité (informatique théorique) et Problème de l'isomorphisme de graphes · Voir plus »

Problème de la clique

C(7,4).

Nouveau!!: Théorie de la complexité (informatique théorique) et Problème de la clique · Voir plus »

Problème de la résiduosité quadratique

En théorie algorithmique des nombres, le problème de la résiduosité quadratique est celui de distinguer, à l'aide de calculs, les résidus quadratiques modulo un nombre composé N fixé.

Nouveau!!: Théorie de la complexité (informatique théorique) et Problème de la résiduosité quadratique · Voir plus »

Problème de la somme de sous-ensembles

Le problème de la somme de sous-ensembles (en anglais: subset sum problem) est un problème de décision important en complexité algorithmique et en cryptologie.

Nouveau!!: Théorie de la complexité (informatique théorique) et Problème de la somme de sous-ensembles · Voir plus »

Problème de recherche

En informatique théorique, et plus particulièrement en théorie de la complexité et en théorie de la calculabilité, un problème de recherche est un problème algorithmique associé à une relation binaire.

Nouveau!!: Théorie de la complexité (informatique théorique) et Problème de recherche · Voir plus »

Problème de satisfaction de contraintes

Les problèmes de satisfaction de contraintes ou CSP sont des problèmes mathématiques où l'on cherche des états ou des objets satisfaisant un certain nombre de contraintes ou de critères.

Nouveau!!: Théorie de la complexité (informatique théorique) et Problème de satisfaction de contraintes · Voir plus »

Problème des huit dames

Le but du problème des huit damesParfois appelé problème des huit reines par traduction de l'anglais, bien que le nom de cette pièce soit Dame en français.

Nouveau!!: Théorie de la complexité (informatique théorique) et Problème des huit dames · Voir plus »

Problème des multiplications matricielles enchaînées

En informatique, un algorithme de multiplication de matrices enchaînées est un algorithme d'optimisation qui sert à trouver un ordre dans lequel calculer un produit de plusieurs matrices A_1\cdot\dots\cdot A_k de façon à minimiser le nombre de multiplications scalaires à effectuer.

Nouveau!!: Théorie de la complexité (informatique théorique) et Problème des multiplications matricielles enchaînées · Voir plus »

Problème des pièces de monnaie

centimes. En mathématiques, le problème des pièces de monnaie, également appelé le problème des pièces de Frobenius ou le problème de Frobenius d'après le mathématicien Georg Frobenius, est un problème diophantien linéaire.

Nouveau!!: Théorie de la complexité (informatique théorique) et Problème des pièces de monnaie · Voir plus »

Problème du sac à dos

En algorithmique, le problème du sac à dos, parfois noté (KP) (de l'anglais Knapsack Problem) est un problème d'optimisation combinatoire.

Nouveau!!: Théorie de la complexité (informatique théorique) et Problème du sac à dos · Voir plus »

Problème du stable maximum

Exemple: organisation d'un dîner. En informatique théorique, le problème du stable maximum ou maximum independent set problem en anglais, est un problème d'optimisation qui consiste étant donné un graphe non orienté à trouver un stable de cardinal maximum, c'est-à-dire un sous-ensemble de sommets du graphe, le plus grand possible, tel que les éléments de ce sous-ensemble ne soient pas voisins.

Nouveau!!: Théorie de la complexité (informatique théorique) et Problème du stable maximum · Voir plus »

Problème du voyageur de commerce

Le problème de voyageur de commerce: calculer un plus court circuit qui passe une et une seule fois par toutes les villes (ici 15 villes). En informatique, le problème du voyageur de commerce, ou problème du commis voyageur, est un problème d'optimisation qui consiste à déterminer, étant donné un ensemble de villes, le plus court circuit passant par chaque ville une seule fois.

Nouveau!!: Théorie de la complexité (informatique théorique) et Problème du voyageur de commerce · Voir plus »

Problème non élémentaire

En théorie de la complexité, un problème non élémentaire est un problème de décision qui n'est pas dans la classe ELEMENTARY.

Nouveau!!: Théorie de la complexité (informatique théorique) et Problème non élémentaire · 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!!: Théorie de la complexité (informatique théorique) et Problème NP-complet · Voir plus »

Problème SAT

consulté le.

Nouveau!!: Théorie de la complexité (informatique théorique) et Problème SAT · Voir plus »

Produit zig-zag de graphes

En théorie des graphes, le produit zig-zag de graphes est une opération sur des graphes réguliers.

Nouveau!!: Théorie de la complexité (informatique théorique) et Produit zig-zag de graphes · Voir plus »

Programmation lettrée

La programmation lettrée (ou programmation littéraire) est une approche de la programmation préconisée par Donald Knuth qui se veut différente du paradigme de programmation structurée des années 1970.

Nouveau!!: Théorie de la complexité (informatique théorique) et Programmation lettrée · Voir plus »

Programming a Computer for Playing Chess

est l'article fondateur des échecs en informatique, écrit par Claude Shannon en 1949.

Nouveau!!: Théorie de la complexité (informatique théorique) et Programming a Computer for Playing Chess · Voir plus »

Project Euler

est un site web proposant une série de problèmes mathématiques conçus pour être résolus à l'aide de programmes informatiques.

Nouveau!!: Théorie de la complexité (informatique théorique) et Project Euler · Voir plus »

Propagation de contraintes

La propagation de contraintes dans le domaine de la programmation par contraintes est le fait de réduire le domaine d'une variable afin de maintenir l'ensemble des valeurs possibles cohérent avec les contraintes du problème.

Nouveau!!: Théorie de la complexité (informatique théorique) et Propagation de contraintes · Voir plus »

Protocole Arthur-Merlin

En théorie de la complexité, un protocole Arthur-Merlin est un système de preuve interactive dans lequel on impose que les lancers de pièces du vérificateur soient publics (c'est-à-dire également connus du démonstrateur).

Nouveau!!: Théorie de la complexité (informatique théorique) et Protocole Arthur-Merlin · Voir plus »

PSPACE

En informatique théorique, plus précisément en théorie de la complexité, PSPACE est la classe de complexité des problèmes de décision décidés par une machine de Turing déterministe avec un espace polynomial.

Nouveau!!: Théorie de la complexité (informatique théorique) et PSPACE · Voir plus »

Puissance parfaite

Représentation graphique du carré puis du cube parfait de 2, ainsi que le carré parfait de 3 En mathématiques, une puissance parfaite est un entier naturel qui peut être exprimé sous la forme d'un carré ou d'une puissance entière supérieure ou égale à 2 d'un entier lui aussi supérieur ou égal à 2.

Nouveau!!: Théorie de la complexité (informatique théorique) et Puissance parfaite · Voir plus »

R

R est la lettre et la consonne de l'alphabet latin.

Nouveau!!: Théorie de la complexité (informatique théorique) et R · Voir plus »

RAIRO Informatique théorique et applications

La revue RAIRO Informatique théorique et applications (en anglais RAIRO Theoretical Informatics and Applications) abrégé en RAIRO ITA ou RAIRO-TIA est une revue de mathématiques à évaluation par les pairs créée sous ce titre en 1958 et publiée tous les trimestres par la société EDP Sciences.

Nouveau!!: Théorie de la complexité (informatique théorique) et RAIRO Informatique théorique et applications · Voir plus »

Rajeev Motwani

Rajeev Motwani (राजीव मोटवानी; -) était un professeur et chercheur en informatique théorique à l'Université Stanford.

Nouveau!!: Théorie de la complexité (informatique théorique) et Rajeev Motwani · Voir plus »

Ran Raz

Ran Raz est un informaticien israélien spécialiste de théorie de la complexité.

Nouveau!!: Théorie de la complexité (informatique théorique) et Ran Raz · Voir plus »

Règle de Cramer

La règle de Cramer (ou méthode de Cramer) est un théorème en algèbre linéaire qui donne la solution d'un système de Cramer, c'est-à-dire un système d'équations linéaires avec autant d'équations que d'inconnues et dont le déterminant de la matrice de coefficients est non nul, sous forme de quotients de déterminants.

Nouveau!!: Théorie de la complexité (informatique théorique) et Règle de Cramer · Voir plus »

Récursivement énumérable

En théorie de la calculabilité, un ensemble d'entiers naturels est récursivement énumérable ou semi-décidable si.

Nouveau!!: Théorie de la complexité (informatique théorique) et Récursivement énumérable · Voir plus »

Réduction (complexité)

En calculabilité et en théorie de la complexité, une réduction est un algorithme transformant une instance d'un problème algorithmique en une ou plusieurs instances d'un autre problème.

Nouveau!!: Théorie de la complexité (informatique théorique) et Réduction (complexité) · Voir plus »

Réduction en espace logarithmique

En théorie de la complexité, une réduction en espace logarithmique est une réduction calculable par une machine de Turing disposant d'un espace de travail logarithmique.

Nouveau!!: Théorie de la complexité (informatique théorique) et Réduction en espace logarithmique · Voir plus »

Réduction polynomiale

Une réduction polynomiale est un outil d'informatique théorique, plus particulièrement de théorie de la complexité.

Nouveau!!: Théorie de la complexité (informatique théorique) et Réduction polynomiale · Voir plus »

Réplication (informatique)

En informatique, la réplication est un processus de partage d'informations pour assurer la cohérence de données entre plusieurs sources de données redondantes, pour améliorer la fiabilité, la tolérance aux pannes, ou la disponibilité.

Nouveau!!: Théorie de la complexité (informatique théorique) et Réplication (informatique) · Voir plus »

Résultats effectifs en théorie des nombres

Pour des raisons historiques et afin d'avoir des applications à la solution des équations diophantiennes, les résultats de la théorie des nombres ont été examinés plus que ceux d'autres branches des mathématiques pour déterminer si leur contenu est effectivement calculable.

Nouveau!!: Théorie de la complexité (informatique théorique) et Résultats effectifs en théorie des nombres · Voir plus »

RE

RE peut faire référence à.

Nouveau!!: Théorie de la complexité (informatique théorique) et RE · Voir plus »

Recherche opérationnelle

La recherche opérationnelle peut être définie comme l'ensemble des méthodes et techniques rationnelles orientées vers la recherche du meilleur choix dans la façon d'opérer en vue d'aboutir au résultat visé ou au meilleur résultat possible ou encore au résultat optimal.

Nouveau!!: Théorie de la complexité (informatique théorique) et Recherche opérationnelle · Voir plus »

Recuit simulé

En algorithmique, le recuit simulé est une méthode empirique (métaheuristique) d'optimisation, inspirée d'un processus, le recuit, utilisé en métallurgie.

Nouveau!!: Théorie de la complexité (informatique théorique) et Recuit simulé · Voir plus »

Représentations d'un groupe fini

En mathématiques, un groupe est une structure algébrique qui consiste en un ensemble muni d'une unique loi de composition interne.

Nouveau!!: Théorie de la complexité (informatique théorique) et Représentations d'un groupe fini · Voir plus »

Richard Bellman

Richard Ernest Bellman (né le à Brooklyn et mort le à Los Angeles) est un mathématicien américain.

Nouveau!!: Théorie de la complexité (informatique théorique) et Richard Bellman · Voir plus »

Richard E. Ladner

Richard Emil Ladner est un informaticien américain connu pour ses contributions à la fois à l'informatique théorique et aux.

Nouveau!!: Théorie de la complexité (informatique théorique) et Richard E. Ladner · Voir plus »

Richard J. Lipton

Richard J. Lipton, naissance le, est un chercheur anglo-américain en informatique reconnu notamment pour son travail en algorithmique et en cryptographie.

Nouveau!!: Théorie de la complexité (informatique théorique) et Richard J. Lipton · Voir plus »

Richard Jozsa

Richard Jozsa (né en 1954) est un mathématicien australien spécialisé en mathématiques appliquées et en théorie de l'informatique quantique.

Nouveau!!: Théorie de la complexité (informatique théorique) et Richard Jozsa · Voir plus »

Richard Karp

Richard Manning Karp (né le à Boston dans le Massachusetts) est un chercheur américain connu notamment pour ses recherches en optimisation combinatoire et théorie de la complexité.

Nouveau!!: Théorie de la complexité (informatique théorique) et Richard Karp · Voir plus »

Richard Stearns

Richard Edwin Stearns, né le à Caldwell dans le New Jersey, est un informaticien américain qui, avec Juris Hartmanis, a reçu en 1993 le prix Turing pour leurs recherches communes sur les bases de la théorie de la complexité des algorithmes.

Nouveau!!: Théorie de la complexité (informatique théorique) et Richard Stearns · Voir plus »

Rod Downey

Rodney Graham Downey (né le 20 septembre 1957), retrieved 19 February 2012.

Nouveau!!: Théorie de la complexité (informatique théorique) et Rod Downey · Voir plus »

Ronald Book

Ronald Vernon Book (né le à Los Angeles et mort le à Santa Barbara, Californie) est un informaticien théoricien américain.

Nouveau!!: Théorie de la complexité (informatique théorique) et Ronald Book · Voir plus »

RP

Le sigle RP peut vouloir dire.

Nouveau!!: Théorie de la complexité (informatique théorique) et RP · Voir plus »

RP (complexité)

Inclusions de classes de complexité probabilistes.En informatique théorique, plus précisément en théorie de la complexité, la classe RP (Randomized Polynomial time) est la classe de complexité des problèmes de décision pour lesquels il existe une machine de Turing probabiliste, en temps polynomial, qui refuse toutes les instances négatives et accepte les instances positives avec une probabilité supérieure à 1/2.

Nouveau!!: Théorie de la complexité (informatique théorique) et RP (complexité) · Voir plus »

Russell Impagliazzo

Russell Graham Impagliazzo (né le à Providence, Rhode Island) est un informaticien et cryptologue américain, spécialisé en théorie de la complexité.

Nouveau!!: Théorie de la complexité (informatique théorique) et Russell Impagliazzo · Voir plus »

Salil Vadhan

Salil Vadhan est un professeur d'informatique théorique et de mathématiques appliquées à l'université Harvard.

Nouveau!!: Théorie de la complexité (informatique théorique) et Salil Vadhan · Voir plus »

Samuel R. Buss

Samuel R. (Sam) Buss est un informaticien et mathématicien américain qui travaille en logique mathématique, théorie de la complexité et en complexité des preuves.

Nouveau!!: Théorie de la complexité (informatique théorique) et Samuel R. Buss · Voir plus »

Sanjeev Arora

Sanjeev Arora (né en à Jodhpur) est un chercheur en informatique théorique indien connu pour son travail en théorie de la complexité et en algorithmique.

Nouveau!!: Théorie de la complexité (informatique théorique) et Sanjeev Arora · Voir plus »

SAT

Sat est le nom de.

Nouveau!!: Théorie de la complexité (informatique théorique) et SAT · Voir plus »

Séquençage de tâches

Le séquençage de tâches (en anglais job sequencing) est un des nombreux modèles d'ordonnancement d'atelier de production.

Nouveau!!: Théorie de la complexité (informatique théorique) et Séquençage de tâches · Voir plus »

SC (complexité)

En informatique théorique, plus précisément en théorie de la complexité, SC est la classe de complexité des problèmes de décision, décidés par un algorithme en temps polynomial et en espace polylogarithmique.

Nouveau!!: Théorie de la complexité (informatique théorique) et SC (complexité) · Voir plus »

Schéma d'approximation en temps polynomial

En informatique, un schéma d'approximation en temps polynomial (en anglais polynomial-time approximation scheme, abrégé en PTAS) est une famille d'algorithmes d'approximation pour des problèmes d'optimisation combinatoire.

Nouveau!!: Théorie de la complexité (informatique théorique) et Schéma d'approximation en temps polynomial · Voir plus »

Scott Aaronson

Scott Joel Aaronson, est un chercheur, professeur et vulgarisateur en informatique théorique, notamment en informatique quantique.

Nouveau!!: Théorie de la complexité (informatique théorique) et Scott Aaronson · Voir plus »

Segmentation en plans

La segmentation en plans est l'identification automatique, par des méthodes informatiques, des bornes des plans dans une vidéo.

Nouveau!!: Théorie de la complexité (informatique théorique) et Segmentation en plans · Voir plus »

Seinosuke Toda

est un chercheur japonais en informatique théorique qui travaille à l'université Nihon à Tokyo.

Nouveau!!: Théorie de la complexité (informatique théorique) et Seinosuke Toda · Voir plus »

Shafi Goldwasser

Shafi Goldwasser (שפרירה גולדווסר, Shafrira Goldwasser) est une informaticienne américano-israélienne, née le à New York.

Nouveau!!: Théorie de la complexité (informatique théorique) et Shafi Goldwasser · Voir plus »

Sharp-P-complet

#P-complet, prononcée "sharp P complet" ou "dièse P complet", est une classe de complexité en théorie de la complexité, un domaine de l'informatique théorique.

Nouveau!!: Théorie de la complexité (informatique théorique) et Sharp-P-complet · Voir plus »

Sheila A. Greibach

Sheila Adele Greibach, née le à New York City), est une informaticienne théoricienne et chercheuse universitaire américaine, notamment en théorie des langages formels, théorie des automates, théorie de la compilation. Elle est professeur émérite en informatique à l'Université de Californie à Los Angeles.

Nouveau!!: Théorie de la complexité (informatique théorique) et Sheila A. Greibach · Voir plus »

Shmuel Safra

Shmuel (Muli) Safra est un professeur et chercheur en informatique théorique, de l'université de Tel Aviv.

Nouveau!!: Théorie de la complexité (informatique théorique) et Shmuel Safra · Voir plus »

Sigma (homonymie)

Pas de description.

Nouveau!!: Théorie de la complexité (informatique théorique) et Sigma (homonymie) · Voir plus »

Sim (jeu)

La zone de jeu Sim est un jeu de papier et crayon pour deux joueurs.

Nouveau!!: Théorie de la complexité (informatique théorique) et Sim (jeu) · Voir plus »

Simulation d'un système à N corps

Une simulation à ''N'' corps de la formation cosmologique d'un amas de galaxies dans un univers en expansion. En physique et en astronomie, une simulation à N corps est une simulation d'un système dynamique de particules, généralement sous l'influence de forces physiques, telles que la gravité (voir problème à ''N'' corps pour d'autres applications).

Nouveau!!: Théorie de la complexité (informatique théorique) et Simulation d'un système à N corps · Voir plus »

Sokoban

vignette est un jeu vidéo de réflexion inventé au Japon.

Nouveau!!: Théorie de la complexité (informatique théorique) et Sokoban · Voir plus »

Somme de radicaux

En théorie de la complexité, il existe un problème ouvert de savoir si certaines informations concernant une somme de radicaux peuvent être calculées en temps polynomial en fonction de la taille d'entrée, c'est-à-dire du nombre de bits nécessaires pour représenter cette somme.

Nouveau!!: Théorie de la complexité (informatique théorique) et Somme de radicaux · Voir plus »

Speedup (homonymie)

Speedup ou Speed Up est une expression anglaise, désignant une accélération.

Nouveau!!: Théorie de la complexité (informatique théorique) et Speedup (homonymie) · Voir plus »

Stable (théorie des graphes)

L'ensemble des sommets en bleu dans ce graphe est un stable maximal du graphe. En théorie des graphes, un stable – appelé aussi ensemble indépendant ou independent set en anglais – est un ensemble de sommets deux à deux non adjacents.

Nouveau!!: Théorie de la complexité (informatique théorique) et Stable (théorie des graphes) · Voir plus »

Standard Template Library

La Standard Template Library (STL) est une bibliothèque C++, normalisée par l'ISO (document ISO/CEI 14882) et mise en œuvre à l'aide des templates.

Nouveau!!: Théorie de la complexité (informatique théorique) et Standard Template Library · 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!!: Théorie de la complexité (informatique théorique) et Stephen Cook · Voir plus »

Steven Rudich

Steven Rudich, né le, est un informaticien théoricien américain qui travaille en théorie de la complexité, cryptographie et combinatoire.

Nouveau!!: Théorie de la complexité (informatique théorique) et Steven Rudich · Voir plus »

Stratégie d'évaluation (informatique)

Un langage de programmation utilise une stratégie d'évaluation pour déterminer « quand » évaluer les arguments à l'appel d'une fonction (ou encore, opération, méthode) et « comment » passer les arguments à la fonction.

Nouveau!!: Théorie de la complexité (informatique théorique) et Stratégie d'évaluation (informatique) · Voir plus »

Structure de données

En informatique, une structure de données est une manière d'organiser les données pour les traiter plus facilement.

Nouveau!!: Théorie de la complexité (informatique théorique) et Structure de données · Voir plus »

Structured Query Language

SQL (sigle pour Structured Query Language, « langage de requêtes structurées ») est un langage informatique normalisé servant à exploiter des bases de données relationnelles.

Nouveau!!: Théorie de la complexité (informatique théorique) et Structured Query Language · Voir plus »

Subhash Khot

Subhash Khot est un chercheur en informatique théorique, professeur au.

Nouveau!!: Théorie de la complexité (informatique théorique) et Subhash Khot · Voir plus »

Suite de Fibonacci

Une juxtaposition de carrés dont les côtés ont pour longueur des nombres successifs de la suite de Fibonacci: 1, 1, 2, 3, 5, 8, 13 et 21. En mathématiques, la suite de Fibonacci est une suite de nombres entiers dans laquelle chaque nombre est la somme des deux nombres qui le précèdent.

Nouveau!!: Théorie de la complexité (informatique théorique) et Suite de Fibonacci · Voir plus »

Symposium on Discrete Algorithms

Le Symposium on Discrete Algorithms ou ACM-SIAM Symposium on Discrete Algorithms (abrégé en SODA, nom qui peut se traduire en Conférence sur les algorithmes discrets) est une conférence académique dans le domaine de l'informatique théorique.

Nouveau!!: Théorie de la complexité (informatique théorique) et Symposium on Discrete Algorithms · Voir plus »

Symposium on Theoretical Aspects of Computer Science

La conférence Symposium on Theoretical Aspects of Computer Science (abrégé en STACS) est une conférence scientifique dans le domaine de l’informatique théorique.

Nouveau!!: Théorie de la complexité (informatique théorique) et Symposium on Theoretical Aspects of Computer Science · Voir plus »

Système de preuve interactive

Un système de preuve interactive est composé de deux machines abstraites: un prouveur et un vérificateur qui s'échangent des messages. En théorie de la complexité des algorithmes, un système de preuve interactive est un protocole formel de démonstration de théorèmes qui fait intervenir deux participants qui échangent des messages.

Nouveau!!: Théorie de la complexité (informatique théorique) et Système de preuve interactive · Voir plus »

Taux d'expansion (théorie des graphes)

En mathématiques, et plus particulièrement en théorie des graphes, le taux d'expansion d'un graphe est une mesure de connectivité de ce graphe Shlomo Hoory, Nathan Linial et Avi Widgerson.

Nouveau!!: Théorie de la complexité (informatique théorique) et Taux d'expansion (théorie des graphes) · Voir plus »

TC (complexité)

En informatique théorique, et plus précisément en théorie de la complexité, TC est la classe de complexité des problèmes de décision reconnus par des circuits avec seuil.

Nouveau!!: Théorie de la complexité (informatique théorique) et TC (complexité) · Voir plus »

Temps de calcul pseudo-polynomial

En 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).

Nouveau!!: Théorie de la complexité (informatique théorique) et Temps de calcul pseudo-polynomial · Voir plus »

Test de primalité de Lucas-Lehmer

Le test de primalité de Lucas-Lehmer est une méthode pour tester la primalité d'un entier, connaissant les facteurs premiers de.

Nouveau!!: Théorie de la complexité (informatique théorique) et Test de primalité de Lucas-Lehmer · Voir plus »

Tetravex

Tetravex est un jeu de réflexion de type puzzle, pour Windows.

Nouveau!!: Théorie de la complexité (informatique théorique) et Tetravex · Voir plus »

Tetris

Tetris est un jeu vidéo de puzzle conçu par l'ingénieur soviétique Alekseï Pajitnov à partir de sur Elektronika 60.

Nouveau!!: Théorie de la complexité (informatique théorique) et Tetris · Voir plus »

TFNP

En théorie de la complexité computationnelle, la classe de complexité TFNP est la classe des problèmes fonctionnels totaux qui peuvent être résolus en temps polynomial non déterministe.

Nouveau!!: Théorie de la complexité (informatique théorique) et TFNP · Voir plus »

Thèse de Church

La thèse de Church est une thèse concernant la définition de la notion de calculabilité.

Nouveau!!: Théorie de la complexité (informatique théorique) et Thèse de Church · Voir plus »

Théorème d'accélération linéaire

Le théorème d'accélération linéaire ou de speedup linéaire est un théorème de théorie de la complexité, un domaine de l'informatique théorique.

Nouveau!!: Théorie de la complexité (informatique théorique) et Théorème d'accélération linéaire · Voir plus »

Théorème d'Immerman-Szelepcsényi

Le théorème d'Immerman-Szelepcsényi est un théorème d'informatique théorique, et notamment de la théorie de la complexité, démontré en 1987 indépendamment par Neil Immerman et Róbert Szelepcsényi, et qui leur a valu d'obtenir conjointement le prix Gödel en 1995.

Nouveau!!: Théorie de la complexité (informatique théorique) et Théorème d'Immerman-Szelepcsényi · 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!!: Théorie de la complexité (informatique théorique) et Théorème de Cook · Voir plus »

Théorème de Courcelle

En algorithmique et en théorie de la complexité, le théorème de Courcelle est le suivant: C'est un métathéorème, dans le sens où il concerne une classe de problèmes algorithmiques.

Nouveau!!: Théorie de la complexité (informatique théorique) et Théorème de Courcelle · Voir plus »

Théorème de Fagin

Le théorème de Fagin est un résultat de théorie de la complexité des algorithmes, montrant l'égalité de la classe NP et de la classe des problèmes exprimables en logique du second ordre existentielle, c'est-à-dire en logique du premier ordre enrichie de quantifications existentielles sur les ensembles.

Nouveau!!: Théorie de la complexité (informatique théorique) et Théorème de Fagin · Voir plus »

Théorème de hiérarchie

En informatique théorique, et plus précisément en théorie de la complexité, il existe plusieurs théorème de hiérarchie.

Nouveau!!: Théorie de la complexité (informatique théorique) et Théorème de hiérarchie · Voir plus »

Théorème de hiérarchie en temps déterministe

Le théorème de hiérarchie en temps déterministe est un énoncé de la théorie de la complexité, un domaine de l'informatique théorique.

Nouveau!!: Théorie de la complexité (informatique théorique) et Théorème de hiérarchie en temps déterministe · Voir plus »

Théorème de Karp-Lipton

En théorie de la complexité, le théorème de Karp–Lipton affirme que si le problème de satisfiabilité booléenne (SAT) est résolu par une famille de circuits booléens avec un nombre polynomial de portes logiques (en la taille de la formule propositionnelle à tester), alors la hiérarchie polynomiale s’effondre au second niveau.

Nouveau!!: Théorie de la complexité (informatique théorique) et Théorème de Karp-Lipton · Voir plus »

Théorème de Mahaney

En informatique théorique, et plus précisément en théorie de la complexité, le théorème de Mahaney dit que s'il existe un langage creux NP-complet, alors P.

Nouveau!!: Théorie de la complexité (informatique théorique) et Théorème de Mahaney · Voir plus »

Théorème de Meyer

Le théorème de Meyer est un résultat de théorie des nombres, qui établit que toute forme quadratique Q à au moins cinq variables sur le corps des rationnels représente zéro (de façon non triviale) dès que Q est non définie, c'est-à-dire que si l'équation Q(x).

Nouveau!!: Théorie de la complexité (informatique théorique) et Théorème de Meyer · Voir plus »

Théorème de Robertson-Seymour

En mathématiques, et plus précisément en théorie des graphes, le théorème de Robertson–Seymour affirme qu'un certain classement partiel entre graphes non orientés possède des propriétés remarquables (c'est un bel ordre).

Nouveau!!: Théorie de la complexité (informatique théorique) et Théorème de Robertson-Seymour · Voir plus »

Théorème de Savitch

Le théorème de Savitch est un théorème de théorie de la complexité, un domaine de l'informatique théorique.

Nouveau!!: Théorie de la complexité (informatique théorique) et Théorème de Savitch · Voir plus »

Théorème de Sipser-Gács-Lautemann

En informatique théorique, plus précisément en théorie de la complexité, le théorème de Sipser-Gács-Lautemann (ou théorème de Sipser-Lautemann ou de Sipser-Gács) est le théorème qui énonce que la classe probabiliste BPP (bounded-error probabilistic polynomial time) est incluse dans la hiérarchie polynomiale.

Nouveau!!: Théorie de la complexité (informatique théorique) et Théorème de Sipser-Gács-Lautemann · Voir plus »

Théorème de Toda

Le théorème de Toda est un résultat en théorie de la complexité, démontré en 1991 par Seinosuke Toda dans son article PP is as Hard as the Polynomial-Time Hierarchy, et qui a valu à son auteur le prix Gödel en 1998.

Nouveau!!: Théorie de la complexité (informatique théorique) et Théorème de Toda · Voir plus »

Théorème des quatre couleurs

Le théorème des quatre couleurs indique qu'il est possible, en n'utilisant que quatre couleurs différentes, de colorier n'importe quelle carte découpée en régions connexes, de sorte que deux régions adjacentes (ou limitrophes), c'est-à-dire ayant toute une frontière (et non simplement un point) en commun reçoivent toujours deux couleurs distinctes.

Nouveau!!: Théorie de la complexité (informatique théorique) et Théorème des quatre couleurs · Voir plus »

Théorème du codage de canal

En théorie de l'information, le théorème du codage de canal aussi appelé deuxième théorème de Shannon montre qu'il est possible de transmettre des données numériques sur un canal bruité avec un taux d'erreur arbitrairement faible si le débit est inférieur à une certaine limite propre au canal.

Nouveau!!: Théorie de la complexité (informatique théorique) et Théorème du codage de canal · Voir plus »

Théorème optimisation/séparation

Le théorème optimisation/séparation est un théorème d'optimisation combinatoire, un domaine des mathématiques et de l'informatique théorique.

Nouveau!!: Théorie de la complexité (informatique théorique) et Théorème optimisation/séparation · Voir plus »

Théorème PCP

En théorie de la complexité, un domaine de l'informatique théorique, le théorème PCP (acronyme de l'anglais probabilistically checkable proof, qui peut se traduire en français par « preuve vérifiable en probabilité ») est une caractérisation de la classe NP dans le contexte d'un système de preuve interactive.

Nouveau!!: Théorie de la complexité (informatique théorique) et Théorème PCP · Voir plus »

Théorie de l'élimination

En algèbre commutative et en géométrie algébrique, la théorie de l'élimination traite de l'approche algorithmique de l'élimination de variables entre polynômes.

Nouveau!!: Théorie de la complexité (informatique théorique) et Théorie de l'élimination · Voir plus »

Théorie de la complexité

Le terme théorie de la complexité peut désigner.

Nouveau!!: Théorie de la complexité (informatique théorique) et Théorie de la complexité · Voir plus »

Théorie des automates

En informatique théorique, l'objectif de la théorie des automates est de proposer des modèles de mécanismes mathématiques qui formalisent les méthodes de calcul.

Nouveau!!: Théorie de la complexité (informatique théorique) et Théorie des automates · Voir plus »

Théorie des bases de données

En informatique, la théorie des bases de données englobe un vaste ensemble de sujets relatifs aux études et recherches dans le domaine théorique des bases de données et de leur systèmes de gestion.

Nouveau!!: Théorie de la complexité (informatique théorique) et Théorie des bases de données · Voir plus »

Théorie des codes

Visualisation bidimensionnelle de la distance de Hamming, une mesure essentielle dans la théorie des codes En théorie de l'information, la théorie des codes traite des codes et de leurs propriétés et de leurs aptitudes à servir sur différents canaux de communication.

Nouveau!!: Théorie de la complexité (informatique théorique) et Théorie des codes · Voir plus »

Théorie des graphes

tracé de graphe. La théorie des graphes est la discipline mathématique et informatique qui étudie les graphes, lesquels sont des modèles abstraits de dessins de réseaux reliant des objets.

Nouveau!!: Théorie de la complexité (informatique théorique) et Théorie des graphes · Voir plus »

Thêta (homonymie)

Thêta (en français) ou theta (en latin et dans de nombreuses langues vivantes) est la lettre de l'alphabet grec (majuscule Θ, minuscule θ).

Nouveau!!: Théorie de la complexité (informatique théorique) et Thêta (homonymie) · Voir plus »

Thomas Vidick

Thomas Vidick (né le 13 juillet 1982) est un informaticien belge spécialisé dans la théorie de la complexité, la cryptographie quantique, la théorie quantique des jeux et l'informatique quantique.

Nouveau!!: Théorie de la complexité (informatique théorique) et Thomas Vidick · Voir plus »

Toniann Pitassi

Toniann Pitassi est une chercheuse en informatique théorique, et en particulier en théorie de la complexité.

Nouveau!!: Théorie de la complexité (informatique théorique) et Toniann Pitassi · Voir plus »

Tournesol (mathématiques)

Un tournesol mathématique peut être représenté comme une fleur. Le noyau du tournesol est la partie brune au milieu, et chaque élément du tournesol est l'union d'un pétale et du noyau. En mathématiques, dans les domaines de la théorie des ensembles et de la combinatoire extrémale, un tournesol ou système \Delta est une famille d'ensembles dont les paires d'éléments distincts ont toutes la même intersection.

Nouveau!!: Théorie de la complexité (informatique théorique) et Tournesol (mathématiques) · Voir plus »

Triangulation d'un polygone

En géométrie algorithmique, la triangulation d'un polygone consiste à décomposer ce polygone en un ensemble (fini) de triangles.

Nouveau!!: Théorie de la complexité (informatique théorique) et Triangulation d'un polygone · Voir plus »

UP

UP peut faire référence à.

Nouveau!!: Théorie de la complexité (informatique théorique) et UP · Voir plus »

UP (complexité)

En théorie de la complexité, UP est la classe de complexité des problèmes de décision décidés par une machine de Turing non ambigüe (machine de Turing non-déterministe avec au plus une seule exécution acceptante pour une entrée donnée).

Nouveau!!: Théorie de la complexité (informatique théorique) et UP (complexité) · Voir plus »

Uriel Feige

Uriel Feige (en, né en 1959) est un informaticien israélien.

Nouveau!!: Théorie de la complexité (informatique théorique) et Uriel Feige · Voir plus »

Usage des lettres grecques en sciences

Cet article présente les différentes utilisations des lettres de l'alphabet grec dans les sciences.

Nouveau!!: Théorie de la complexité (informatique théorique) et Usage des lettres grecques en sciences · Voir plus »

Vérification de modèles

model checking''. En informatique, la vérification de modèles, ou en anglais, est le problème suivant: vérifier si le modèle d'un système (souvent informatique ou électronique) satisfait une propriété.

Nouveau!!: Théorie de la complexité (informatique théorique) et Vérification de modèles · Voir plus »

Vijay Vazirani

Vijay Virkumar Vazirani (विजय वीरकुमार वज़ीरानी) est un chercheur et professeur en informatique indien.

Nouveau!!: Théorie de la complexité (informatique théorique) et Vijay Vazirani · Voir plus »

Viktor Vassiliev

Viktor Anatolievitch Vassiliev (en Виктор Анатольевич Васильев), né le 10 avril 1956 à Moscou, est un mathématicien russe, professeur à l'Université indépendante de Moscou depuis 1991 et chercheur à l'Institut de mathématiques Steklov depuis 1997.

Nouveau!!: Théorie de la complexité (informatique théorique) et Viktor Vassiliev · Voir plus »

Virginia Vassilevska Williams

Virginia Vassilevska Williams, née Virginia Panayotova Vassilevska, est une informaticienne théoricienne et mathématicienne spécialiste en théorie des algorithmes et théorie de la complexité informatique.

Nouveau!!: Théorie de la complexité (informatique théorique) et Virginia Vassilevska Williams · Voir plus »

Vitesse de convergence des suites

En analyse numérique — une branche des mathématiques — on peut classer les suites convergentes en fonction de leur vitesse de convergence vers leur point limite.

Nouveau!!: Théorie de la complexité (informatique théorique) et Vitesse de convergence des suites · Voir plus »

Walter Savitch

Walter John Savitch, né le et mort le, est professeur et chercheur en informatique et informatique théorique.

Nouveau!!: Théorie de la complexité (informatique théorique) et Walter Savitch · Voir plus »

Xi Chen

Xi Chen, né en 1982, est un informaticien théoricien américain, professeur au département d'informatique l'Université Columbia.

Nouveau!!: Théorie de la complexité (informatique théorique) et Xi Chen · Voir plus »

ZPP

ZPP, sigle de trois lettres, peut faire référence à.

Nouveau!!: Théorie de la complexité (informatique théorique) et ZPP · Voir plus »

ZPP (complexité)

ZPP et la relation avec d'autres classes de complexité probabilistes. La classe ZPP, est un objet de la théorie de la complexité, en informatique théorique.

Nouveau!!: Théorie de la complexité (informatique théorique) et ZPP (complexité) · Voir plus »

1972 en informatique

---- Cet article présente les principaux évènements de 1972 dans le domaine informatique.

Nouveau!!: Théorie de la complexité (informatique théorique) et 1972 en informatique · Voir plus »

1973 en informatique

---- Cet article présente les principaux évènements de 1973 dans le domaine informatique.

Nouveau!!: Théorie de la complexité (informatique théorique) et 1973 en informatique · Voir plus »

1993 en informatique

---- Cet article présente les principaux évènements de 1993 dans le domaine informatique.

Nouveau!!: Théorie de la complexité (informatique théorique) et 1993 en informatique · Voir plus »

2-EXPTIME

En informatique théorique, plus précisément en théorie de la complexité, la classe 2-EXPTIME est la classe des problèmes de décision décidés par une machine de Turing déterministe en temps doublement exponentiel, c'est-à-dire en temps O(22p(n)), où p(n) est un polynôme en la taille de l'entrée n. 2-EXPTIME est égale à la classe AEXPSPACE, la classe des problèmes décidés par une machine de Turing alternante en espace exponentiel.

Nouveau!!: Théorie de la complexité (informatique théorique) et 2-EXPTIME · Voir plus »

21 problèmes NP-complets de Karp

Les 21 problèmes NP-complets de Karp ont marqué une étape importante de l'histoire de la théorie de la complexité des algorithmes.

Nouveau!!: Théorie de la complexité (informatique théorique) et 21 problèmes NP-complets de Karp · Voir plus »

Redirections ici:

Classes de complexité P et NP, Complexité des classes P et NP, Complexité informatique, Optimisation difficile, Problème ouvert P = NP, Théorie de la complexité des algorithmes.

Unionpédia est une carte conceptuelle ou réseau sémantique organisée comme une encyclopédie ou un dictionnaire. Il donne une brève définition de chaque concept et de ses relations.

Ceci est une carte mentale en ligne géant qui sert de base pour les schémas conceptuels. Il est libre d'utiliser et de chaque article ou document peut être téléchargé. Il est un outil, ressources ou de référence pour l'étude, la recherche, l'éducation, l'apprentissage ou de l'enseignement, qui peut être utilisé par les enseignants, les éducateurs, les élèves ou étudiants; pour le monde universitaire: à l'école, primaire, secondaire, l'école secondaire, au milieu, un collège, diplôme technique, collégial, universitaire, baccalauréat, de maîtrise ou de doctorat; pour les papiers, des rapports, des projets, des idées, de la documentation, des enquêtes, des résumés, ou une thèse. Voici la définition, l'explication, la description ou la signification de chaque importantes sur lesquelles vous avez besoin d'informations, et une liste de leurs concepts connexes comme un glossaire. Disponible en français, anglais, espagnol, portugais, japonais, chinois, allemand, italien, polonais, néerlandais, russe, arabe, hindi, suédois, ukrainien, hongrois, catalan, tchèque, hébreu, danois, finlandais, indonésien, norvégien, roumain, turc, vietnamien, coréen, thaïlandais, grec, bulgare, croate, slovaque, lituanien, philippin, letton, estonien et slovène. Plus de langues bientôt.

Toutes les informations a été extrait de Wikipédia, et il est disponible sous licence Creative Commons paternité partage à l’identique.

Unionpédia n'est ni approuvée ni affiliée à la Wikimedia Foundation.

Google Play, Android et le logo Google Play sont des marques de Google Inc.

Politique de confidentialité

SortantEntrants