Accès plus rapide que le navigateur!
120 relations: Academic Press, Acta Mathematica, Algorithme, Algorithme d'approximation, Algorithme de Bron-Kerbosch, Algorithme de Coppersmith-Winograd, Algorithme glouton, Algorithmica, Amarrage (moléculaire), American Mathematical Society, Arête (théorie des graphes), Arboricité, Arbre phylogénétique, Bio-informatique, Bulletin of the American Mathematical Society, Calcul quantique adiabatique, Chimie, Chimie numérique, Clause de Horn, Clôture (mathématiques), Clique (théorie des graphes), Coloration de graphe, Combinaison sans répétition, Combinatorica, Communications of the ACM, Comparaison asymptotique, Complet (complexité), Complexité dans le pire des cas, Complexité en temps, Complexité paramétrée, Compositio Mathematica, Conjecture de Keller, Couplage (théorie des graphes), Dégénérescence (théorie des graphes), Densité d'un graphe, Discrete and Computational Geometry, Discrete Applied Mathematics, Discrete Mathematics, Fan-in, Fonction ET, Fonction NON, Fonction OU, Fonction polynomiale, Fonction récursive, George Szekeres, Graphe (mathématiques discrètes), Graphe aléatoire, Graphe biparti, Graphe complémentaire, Graphe complet, ..., Graphe cordal, Graphe de comparabilité, Graphe de disques, Graphe de permutation, Graphe non orienté, Graphe parfait, Graphe planaire, Graphe sans triangle, Heuristique (mathématiques), Hypercube, IEEE Transactions on Computers, Information and Computation, Information Processing Letters, Informatique, Israel Journal of Mathematics, Journal of Combinatorial Theory, Journal of Computer and System Sciences, Journal of Graph Algorithms and Applications, Journal of the ACM, Journal of the American Statistical Association, Lexique de la théorie des graphes, Matrice d'adjacence, Mineur (théorie des graphes), NC (complexité), Optimisation SDP, Ordinateur à ADN, Ordre lexicographique, Parallélisme (informatique), Paul Erdős, Plus longue sous-suite strictement croissante, Prédiction de la structure des protéines, Preuve vérifiable de manière probabiliste, Problème 3-SAT, Problème algorithmique, Problème de décision, Problème de la décision, Problème du voyageur de commerce, Problème NP-complet, Problème P ≟ NP, Problème SAT, Proceedings of the National Academy of Sciences, Programmation dynamique, Programmation par contraintes, Racine cubique, Réseau social, Recherche exhaustive, Recherche locale (optimisation), Retour sur trace, Richard Karp, Séparation et évaluation, Schéma d'approximation en temps polynomial, Science (revue), SIAM Journal on Computing, SIAM Journal on Discrete Mathematics, Sommet (théorie des graphes), Sous-graphe, Springer Science+Business Media, Stephen Cook, Symposium on Foundations of Computer Science, Théorème de Cook, Théorème de Kőnig (théorie des graphes), Théorie de la complexité (informatique théorique), Théorie de Ramsey, Théorie spectrale des graphes, The New York Times, The Thomson Corporation, Uriel Feige, Visualisation de données, Voisinage (théorie des graphes), 21 problèmes NP-complets de Karp. Développer l'indice (70 plus) »
Academic Press
Academic Press est une maison d'édition américaine faisant partie du groupe Elsevier.
Nouveau!!: Problème de la clique et Academic Press · Voir plus »
Acta Mathematica
Acta Mathematica (abrégé en Acta Math.) est une revue scientifique à comité de lecture fondée par le mathématicien suédois Gösta Mittag-Leffler en 1882.
Nouveau!!: Problème de la clique et Acta Mathematica · 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!!: Problème de la clique et Algorithme · Voir plus »
Algorithme d'approximation
En informatique théorique, un algorithme d'approximation est une méthode permettant de calculer une solution approchée à un problème algorithmique d'optimisation.
Nouveau!!: Problème de la clique et Algorithme d'approximation · Voir plus »
Algorithme de Bron-Kerbosch
L'ensemble 1, 2, 5 est une clique maximale. En informatique, l'algorithme de Bron–Kerbosch est un algorithme d'énumération pour trouver toutes les cliques maximales d'un graphe non orienté.
Nouveau!!: Problème de la clique et Algorithme de Bron-Kerbosch · Voir plus »
Algorithme de Coppersmith-Winograd
L’algorithme de Coppersmith-Winograd est un algorithme de calcul du produit de deux matrices carrées de taille n dû à Don Coppersmith et Shmuel Winograd en 1987.
Nouveau!!: Problème de la clique et Algorithme de Coppersmith-Winograd · Voir plus »
Algorithme glouton
Un algorithme glouton (en anglais, parfois appelé aussi algorithme gourmand, ou goulu) est un algorithme qui suit le principe de réaliser, étape par étape, un choix optimum local, afin d'obtenir un résultat optimum global.
Nouveau!!: Problème de la clique et Algorithme glouton · Voir plus »
Algorithmica
Algorithmica est une revue mensuelle d'informatique théorique, publiée par Springer.
Nouveau!!: Problème de la clique et Algorithmica · Voir plus »
Amarrage (moléculaire)
Petite molécule amarrée à une protéine. Dans le domaine de la modélisation moléculaire, l’amarrage (en anglais docking) est une méthode qui calcule l'orientation préférée d'une molécule vers une seconde lorsqu'elles sont liées pour former un complexe stable.
Nouveau!!: Problème de la clique et Amarrage (moléculaire) · Voir plus »
American Mathematical Society
L' est une association professionnelle américaine de mathématiciens professionnels, dédiée aux intérêts de la recherche et de l’enseignement des mathématiques, ce qu’elle fait sous forme de différentes publications et conférences, et de prix décernés à des mathématiciens.
Nouveau!!: Problème de la clique et American Mathematical Society · Voir plus »
Arête (théorie des graphes)
Un graphe avec six sommets et sept arêtes. En théorie des graphes, une arête, aussi appelée lien ou ligne, est une liaison entre deux sommets d'un graphe.
Nouveau!!: Problème de la clique et Arête (théorie des graphes) · Voir plus »
Arboricité
En théorie des graphes, l'arboricité (arboricity en anglais) d'un graphe non orienté est le nombre minimum de forêts nécessaires pour couvrir toutes les arêtes.
Nouveau!!: Problème de la clique et Arboricité · Voir plus »
Arbre phylogénétique
archées en vert. Un arbre phylogénétique est un arbre schématique qui montre les relations de parenté entre des groupes d'êtres vivants.
Nouveau!!: Problème de la clique et Arbre phylogénétique · Voir plus »
Bio-informatique
La bioinformatique (ou bio-informatique), est un champ de recherche multidisciplinaire de la biotechnologie où travaillent de concert biologistes, médecins, informaticiens, mathématiciens, physiciens et bioinformaticiens, dans le but de résoudre un problème scientifique posé par la biologie.
Nouveau!!: Problème de la clique et Bio-informatique · Voir plus »
Bulletin of the American Mathematical Society
Le Bulletin of the American Mathematical Society, souvent abrégé Bull.
Nouveau!!: Problème de la clique et Bulletin of the American Mathematical Society · Voir plus »
Calcul quantique adiabatique
Le calcul quantique adiabatique (en anglais, adiabatic quantum computation ou AQC) est une méthode de calcul quantique reposant sur le théorème adiabatique, qui peut être vu comme une sous-classe des méthodes de recuit simulé quantique.
Nouveau!!: Problème de la clique et Calcul quantique adiabatique · Voir plus »
Chimie
La chimie est une science de la nature qui étudie la matière et ses transformations, et plus précisément les atomes, les molécules, les réactions chimiques et les forces qui favorisent les réactions chimiques.
Nouveau!!: Problème de la clique et Chimie · Voir plus »
Chimie numérique
La chimie numérique ou chimie informatique, parfois aussi chimie computationnelle, est une branche de la chimie et de la physico-chimie qui utilise les lois de la chimie théorique exploitées dans des programmes informatiques spécifiques afin de calculer structures et propriétés d'objets chimiques tels que les molécules, les solides, les agrégats atomiques (ou clusters), les surfaces, etc., en appliquant autant que possible ces programmes à des problèmes chimiques réels.
Nouveau!!: Problème de la clique et Chimie numérique · Voir plus »
Clause de Horn
En logique, en particulier en calcul propositionnel, une clause de Horn est une clause comportant au plus un ''littéral positif''.
Nouveau!!: Problème de la clique et Clause de Horn · Voir plus »
Clôture (mathématiques)
On parle de clôture ou de fermeture en mathématiques dans des contextes très divers.
Nouveau!!: Problème de la clique et Clôture (mathématiques) · Voir plus »
Clique (théorie des graphes)
Exemple de graphe possédant une 3-clique (en rouge): les trois sommets de ce sous-graphe sont tous adjacents deux-à-deux. Exemple de « biclique »: le graphe biparti complet K3,3. Une clique d'un graphe non orienté est, en théorie des graphes, un sous-ensemble des sommets de ce graphe dont le sous-graphe induit est complet, c'est-à-dire que deux sommets quelconques de la clique sont toujours adjacents.
Nouveau!!: Problème de la clique et Clique (théorie des graphes) · 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!!: Problème de la clique et Coloration de graphe · Voir plus »
Combinaison sans répétition
Les combinaisons sont un concept de mathématiques, plus précisément de combinatoire, décrivant les différentes façons de choisir un nombre donné d'objets dans un ensemble de taille donnée, lorsque les objets sont discernables et que l'on ne se soucie pas de l'ordre dans lequel les objets sont placés ou énumérés.
Nouveau!!: Problème de la clique et Combinaison sans répétition · Voir plus »
Combinatorica
Combinatorica est une revue mathématique qui publie des articles en combinatoire et en informatique théorique.
Nouveau!!: Problème de la clique et Combinatorica · Voir plus »
Communications of the ACM
Communications of the ACM (CACM) est la principale revue mensuelle de l'Association for Computing Machinery (ACM).
Nouveau!!: Problème de la clique et Communications of the ACM · 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!!: Problème de la clique et Comparaison asymptotique · 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!!: Problème de la clique et Complet (complexité) · Voir plus »
Complexité dans le pire des cas
En informatique, la complexité dans le pire des cas, ou complexité dans le cas le plus défavorable, mesure la complexité (par exemple en temps ou en espace) d'un algorithme dans le pire des cas d'exécution possibles.
Nouveau!!: Problème de la clique et Complexité dans le pire des cas · 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!!: Problème de la clique et Complexité en temps · 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!!: Problème de la clique et Complexité paramétrée · Voir plus »
Compositio Mathematica
Composition Mathematica est une revue de mathématiques bimestrielle revue par les pairs créée par Luitzen Egbertus Jan Brouwer en 1935.
Nouveau!!: Problème de la clique et Compositio Mathematica · Voir plus »
Conjecture de Keller
En géométrie, la conjecture de Keller est la conjecture introduite par en 1930 que dans tout pavage de l'espace euclidien par des hypercubes identiques, on trouve deux hypercubes qui ont une face entière en commun.
Nouveau!!: Problème de la clique et Conjecture de Keller · Voir plus »
Couplage (théorie des graphes)
En théorie des graphes, un couplage ou appariement (en anglais) d'un graphe est un ensemble d'arêtes de ce graphe qui n'ont pas de sommets en commun.
Nouveau!!: Problème de la clique et Couplage (théorie des graphes) · Voir plus »
Dégénérescence (théorie des graphes)
En théorie des graphes, la dégénérescence est un paramètre associé à un graphe non orienté.
Nouveau!!: Problème de la clique et Dégénérescence (théorie des graphes) · Voir plus »
Densité d'un graphe
En mathématiques, et plus particulièrement en théorie des graphes, on peut associer à tout graphe un entier appelé densité du graphe.
Nouveau!!: Problème de la clique et Densité d'un graphe · Voir plus »
Discrete and Computational Geometry
Discrete & Computational Geometry (abrégé en Discrete Comput. Geom.) est une revue scientifique trimestrielle évaluée par les pairs (peer review) et publiée par Springer.
Nouveau!!: Problème de la clique et Discrete and Computational Geometry · Voir plus »
Discrete Applied Mathematics
Discrete Applied Mathematics est une revue mathématique à évaluation par les pairs qui couvre les domaines algorithmiques et mathématiques appliquées des mathématiques discrètes.
Nouveau!!: Problème de la clique et Discrete Applied Mathematics · Voir plus »
Discrete Mathematics
Discrete Mathematics est une revue mathématique bimensuelle à comité de lecture publiée par North-Holland Publishing Company (qui maintenant fait partie de Elsevier).
Nouveau!!: Problème de la clique et Discrete Mathematics · 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!!: Problème de la clique et Fan-in · Voir plus »
Fonction ET
La fonction ET (AND en anglais) est un opérateur logique de l'algèbre de Boole.
Nouveau!!: Problème de la clique et Fonction ET · Voir plus »
Fonction NON
La fonction NON (NOT en anglais) est un opérateur logique de l'algèbre de Boole et exprime un « état » en fonction de conditions.
Nouveau!!: Problème de la clique et Fonction NON · Voir plus »
Fonction OU
La fonction OU ou OU inclusif (OR en anglais) est un opérateur logique de l'algèbre de Boole.
Nouveau!!: Problème de la clique et Fonction OU · Voir plus »
Fonction polynomiale
En mathématiques, une fonction polynomiale (parfois appelée fonction polynôme) est une fonction obtenue en évaluant un polynôme.
Nouveau!!: Problème de la clique et Fonction polynomiale · Voir plus »
Fonction récursive
En informatique et en mathématiques, le terme fonction récursive ou fonction calculable désigne la classe de fonctions dont les valeurs peuvent être calculées à partir de leurs paramètres par un processus mécanique fini.
Nouveau!!: Problème de la clique et Fonction récursive · Voir plus »
George Szekeres
George Szekeres (prononciation hongroise) est un mathématicien hongrois et australien, né en 1911 à Budapest et mort en 2005 à Adélaïde.
Nouveau!!: Problème de la clique et George Szekeres · Voir plus »
Graphe (mathématiques discrètes)
Dans le domaine des mathématiques discrètes, la théorie des graphes définit le graphe, une structure composée d'objets et de relations entre deux de ces objets.
Nouveau!!: Problème de la clique et Graphe (mathématiques discrètes) · Voir plus »
Graphe aléatoire
Graphe orienté aléatoire avec 20 nœuds et une probabilité de présence d'arête égale à 0,1. En mathématiques, un graphe aléatoire est un graphe généré par un processus aléatoire.
Nouveau!!: Problème de la clique et Graphe aléatoire · Voir plus »
Graphe biparti
En théorie des graphes, un graphe est dit biparti si son ensemble de sommets peut être divisé en deux sous-ensembles disjoints U et V tels que chaque arête ait une extrémité dans U et l'autre dans V. Un graphe biparti permet notamment de représenter une relation binaire.
Nouveau!!: Problème de la clique et Graphe biparti · Voir plus »
Graphe complémentaire
Le graphe de Petersen, à gauche et son complémentaire, à droite. En théorie des graphes, le graphe complémentaire ou graphe inversé d'un graphe simple G est un graphe simple H ayant les mêmes sommets et tel que deux sommets distincts de H soient adjacents si et seulement s'ils ne sont pas adjacents dans G. Le graphe complémentaire ne doit pas être confondu avec le complémentaire dans le sens de la théorie des ensembles.
Nouveau!!: Problème de la clique et Graphe complémentaire · Voir plus »
Graphe complet
En théorie des graphes, un graphe complet est un graphe simple dont tous les sommets sont adjacents deux à deux, c'est-à-dire que tout couple de sommets disjoints est relié par une arête.
Nouveau!!: Problème de la clique et Graphe complet · Voir plus »
Graphe cordal
Un cycle, en noir, avec deux cordes, en vert. Si l'on s'en tient à cette partie, le graphe est cordal. Supprimer l'une des arêtes vertes rendrait le graphe non cordal. En effet, l'autre arête verte formerait, avec les trois arêtes noires, un cycle de longueur 4 sans corde. En théorie des graphes, on dit qu'un graphe est cordal si chacun de ses cycles de quatre sommets ou plus possède une corde, c'est-à-dire une arête reliant deux sommets non adjacents du cycle.
Nouveau!!: Problème de la clique et Graphe cordal · Voir plus »
Graphe de comparabilité
Dans la théorie des graphes, un graphe de comparabilité est un graphe non orienté qui relie les paires d'éléments qui sont comparables les uns aux autres dans un ordre partiel donné.
Nouveau!!: Problème de la clique et Graphe de comparabilité · Voir plus »
Graphe de disques
En théorie des graphes, un graphe de disques (ou disk graph en anglais) est le graphe d'intersection d'une collection de disques.
Nouveau!!: Problème de la clique et Graphe de disques · Voir plus »
Graphe de permutation
En théorie des graphes, un graphe de permutation est un graphe non orienté dont les sommets représentent les éléments d'une permutation, et dont les arêtes relient les paires de sommets qui sont inversés dans la permutation.
Nouveau!!: Problème de la clique et Graphe de permutation · Voir plus »
Graphe non orienté
Exemple de graphe non orienté à 5 sommets. En théorie des graphes, un graphe non orienté G.
Nouveau!!: Problème de la clique et Graphe non orienté · Voir plus »
Graphe parfait
En théorie des graphes, le graphe parfait est une notion introduite par Claude Berge en 1960.
Nouveau!!: Problème de la clique et Graphe parfait · Voir plus »
Graphe planaire
Dans la théorie des graphes, un graphe planaire est un graphe qui a la particularité de pouvoir se représenter sur un plan sans qu'aucune arête (ou arc pour un graphe orienté) n'en croise une autre.
Nouveau!!: Problème de la clique et Graphe planaire · Voir plus »
Graphe sans triangle
En théorie des graphes, un graphe sans triangle est un graphe qui ne possède pas de triplet d'arêtes formant un triangle.
Nouveau!!: Problème de la clique et Graphe sans triangle · 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!!: Problème de la clique et Heuristique (mathématiques) · Voir plus »
Hypercube
Un hypercube est, en géométrie, un analogue n-dimensionnel d'un carré (n.
Nouveau!!: Problème de la clique et Hypercube · Voir plus »
IEEE Transactions on Computers
La revue IEEE Transactions on Computers est une revue scientifique couvrant tous les aspects de l'architecture matérielle des ordinateurs, à parution mensuelle et à évaluation par les pairs.
Nouveau!!: Problème de la clique et IEEE Transactions on Computers · Voir plus »
Information and Computation
Information and Computation est une revue scientifique informatique mensuelle publiée par Elsevier (anciennement Academic Press).
Nouveau!!: Problème de la clique et Information and Computation · Voir plus »
Information Processing Letters
Information Processing Letters est une revue scientifique dans le domaine de l'informatique dont les articles sont évalués par les pairs.
Nouveau!!: Problème de la clique et Information Processing Letters · 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!!: Problème de la clique et Informatique · Voir plus »
Israel Journal of Mathematics
L est une revue scientifique de mathématiques générales fondée en 1963, faisant suite au.
Nouveau!!: Problème de la clique et Israel Journal of Mathematics · Voir plus »
Journal of Combinatorial Theory
Le Journal of Combinatorial Theory, Series A et Series B est une revue mathématique se spécialisant en analyse combinatoire et autres questions associées; elle est publiée par Elsevier Science.
Nouveau!!: Problème de la clique et Journal of Combinatorial Theory · 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!!: Problème de la clique et Journal of Computer and System Sciences · Voir plus »
Journal of Graph Algorithms and Applications
Le Journal of Graph Algorithms and Applications est une revue scientifique en libre accès à évaluation par les pairs qui couvre le domaine des algorithmes des graphes et le tracé de graphes.
Nouveau!!: Problème de la clique et Journal of Graph Algorithms and Applications · Voir plus »
Journal of the ACM
Journal of the ACM (Journal de l'ACM) est la revue scientifique majeure de l'Association for Computing Machinery (ACM).
Nouveau!!: Problème de la clique et Journal of the ACM · Voir plus »
Journal of the American Statistical Association
Le Journal of the American Statistical Association est une revue académique de statistiques publiée par la Société américaine de statistique.
Nouveau!!: Problème de la clique et Journal of the American Statistical Association · Voir plus »
Lexique de la théorie des graphes
; Acyclique: graphe ne contenant pas de cycle.
Nouveau!!: Problème de la clique et Lexique de la théorie des graphes · Voir plus »
Matrice d'adjacence
En mathématiques, en théorie des graphes, en informatique, une matrice d'adjacence pour un graphe fini à sommets est une matrice de dimension dont l'élément non diagonal est le nombre d'arêtes liant le sommet au sommet.
Nouveau!!: Problème de la clique et Matrice d'adjacence · Voir plus »
Mineur (théorie des graphes)
La notion de mineur d'un graphe est un concept de théorie des graphes.
Nouveau!!: Problème de la clique et Mineur (théorie des graphes) · 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!!: Problème de la clique et NC (complexité) · Voir plus »
Optimisation SDP
En mathématiques et en informatique théorique, l'optimisation SDP ou semi-définie positive, est un type d'optimisation convexe, qui étend l'optimisation linéaire.
Nouveau!!: Problème de la clique et Optimisation SDP · Voir plus »
Ordinateur à ADN
L'ordinateur à ADN est une des voies non électroniques actuellement explorées pour résoudre des problèmes combinatoires.
Nouveau!!: Problème de la clique et Ordinateur à ADN · Voir plus »
Ordre lexicographique
En mathématiques, un ordre lexicographique est un ordre que l'on définit sur les suites finies d'éléments d'un ensemble ordonné (ou, de façon équivalente, les mots construits sur un ensemble ordonné).
Nouveau!!: Problème de la clique et Ordre lexicographique · 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!!: Problème de la clique et Parallélisme (informatique) · Voir plus »
Paul Erdős
Paul Erdős, né Pál Erdős le à Budapest et mort le à Varsovie, est un mathématicien hongrois.
Nouveau!!: Problème de la clique et Paul Erdős · Voir plus »
Plus longue sous-suite strictement croissante
La recherche d'une plus longue sous-suite strictement croissante dans une suite finie est un problème classique en algorithmique.
Nouveau!!: Problème de la clique et Plus longue sous-suite strictement croissante · Voir plus »
Prédiction de la structure des protéines
La prédiction de la structure des protéines est l'inférence de la structure tridimensionnelle des protéines à partir de leur séquences d'acides aminés, c'est-à-dire la prédiction de leur pliage et de leur structures secondaire et tertiaire à partir de leur structure primaire.
Nouveau!!: Problème de la clique et Prédiction de la structure des protéines · 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!!: Problème de la clique et Preuve vérifiable de manière probabiliste · 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!!: Problème de la clique et Problème 3-SAT · Voir plus »
Problème algorithmique
Un problème algorithmique est, en informatique théorique, un objet mathématique qui représente une question ou un ensemble de questions auxquelles un ordinateur devrait être en mesure de répondre.
Nouveau!!: Problème de la clique et Problème algorithmique · 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!!: Problème de la clique et Problème de décision · Voir plus »
Problème de la décision
En logique mathématique, on appelle problème de la décision ou, sous son nom d'origine en allemand, Entscheidungsproblem, le fait de déterminer de façon mécanique (par un algorithme) si un énoncé est un théorème de la logique égalitaire du premier ordre, c’est-à-dire s'il se dérive dans un système de déduction sans autres axiomes que ceux de l'égalité (exemples: système à la Hilbert, calcul des séquents, déduction naturelle).
Nouveau!!: Problème de la clique et Problème de la décision · 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!!: Problème de la clique et Problème du voyageur de commerce · 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!!: Problème de la clique et Problème NP-complet · Voir plus »
Problème P ≟ NP
Représentation visuelle des deux configurations possibles. Le problème est une conjecture en mathématiques, et plus précisément en informatique théorique, considérée par de nombreux chercheurs comme une des plus importantes conjectures du domaine, et même des mathématiques en général.
Nouveau!!: Problème de la clique et Problème P ≟ NP · Voir plus »
Problème SAT
consulté le.
Nouveau!!: Problème de la clique et Problème SAT · Voir plus »
Proceedings of the National Academy of Sciences
, abrégé en Proc.
Nouveau!!: Problème de la clique et Proceedings of the National Academy of Sciences · Voir plus »
Programmation dynamique
En informatique, la programmation dynamique est une méthode algorithmique pour résoudre des problèmes d'optimisation.
Nouveau!!: Problème de la clique et Programmation dynamique · Voir plus »
Programmation par contraintes
La programmation par contraintes (PPC, ou CP pour constraint programming en anglais) est un paradigme de programmation apparu dans les années 1970 et 1980 permettant de résoudre des problèmes combinatoires de grande taille tels que les problèmes de planification et d'ordonnancement.
Nouveau!!: Problème de la clique et Programmation par contraintes · Voir plus »
Racine cubique
Courbe représentative de la fonction racine cubique sur '''R'''. En mathématiques, la racine cubique d'un nombre réel y est l'unique nombre réel x dont le cube (c'est-à-dire la puissance 3e) vaut y; en d'autres termes, y.
Nouveau!!: Problème de la clique et Racine cubique · Voir plus »
Réseau social
En sciences humaines et sociales, l'expression réseau social.
Nouveau!!: Problème de la clique et Réseau social · Voir plus »
Recherche exhaustive
La recherche exhaustive ou recherche par force brute est une méthode algorithmique qui consiste principalement à essayer toutes les solutions possibles.
Nouveau!!: Problème de la clique et Recherche exhaustive · Voir plus »
Recherche locale (optimisation)
En algorithmique, la recherche locale est une méthode générale utilisée pour résoudre des problèmes d'optimisation, c'est-à-dire des problèmes où l'on cherche la meilleure solution dans un ensemble de solutions candidates.
Nouveau!!: Problème de la clique et Recherche locale (optimisation) · Voir plus »
Retour sur trace
En informatique, plus précisément en algorithmique, le retour sur trace ou retour arrière (appelé aussi backtracking en anglais) est une famille d'algorithmes pour trouver des solutions à des problèmes algorithmiques, notamment de satisfaction de contraintes.
Nouveau!!: Problème de la clique et Retour sur trace · 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!!: Problème de la clique et Richard Karp · Voir plus »
Séparation et évaluation
Un algorithme par séparation et évaluation, ou en anglais, est une méthode générique de résolution de problèmes d'optimisation combinatoire.
Nouveau!!: Problème de la clique et Séparation et évaluation · 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!!: Problème de la clique et Schéma d'approximation en temps polynomial · Voir plus »
Science (revue)
Science est une revue scientifique généraliste américaine hebdomadaire qui publie des articles dans tous les domaines scientifiques (biologie, chimie, physique, mathématiques, anthropologie, archéologie).
Nouveau!!: Problème de la clique et Science (revue) · Voir plus »
SIAM Journal on Computing
La revue SIAM Journal on Computing (abrégée en SICOMP) est une revue scientifique centrée sur les aspects mathématiques et formelles de l’informatique.
Nouveau!!: Problème de la clique et SIAM Journal on Computing · Voir plus »
SIAM Journal on Discrete Mathematics
Le SIAM Journal on Discrete Mathematics est une revue mathématique revue par les pairs trimestrielle éditée par la Society for Industrial and Applied Mathematics (SIAM).
Nouveau!!: Problème de la clique et SIAM Journal on Discrete Mathematics · Voir plus »
Sommet (théorie des graphes)
Dans ce graphe, les sommets 4 et 5 sont voisins alors que les sommets 3 et 5 sont indépendants. Le degré du sommet 4 est égal à 3. Le sommet 6 est une feuille. En théorie des graphes, un sommet, aussi appelé nœud et plus rarement point, est l'unité fondamentale d'un graphe.
Nouveau!!: Problème de la clique et Sommet (théorie des graphes) · Voir plus »
Sous-graphe
En théorie des graphes, un sous-graphe est un graphe contenu dans un autre graphe.
Nouveau!!: Problème de la clique et Sous-graphe · Voir plus »
Springer Science+Business Media
Springer Science+Business Media ou Springer (anc. Springer Verlag) est un groupe éditorial et de presse spécialisée d'origine allemande.
Nouveau!!: Problème de la clique et Springer Science+Business Media · 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!!: Problème de la clique et Stephen Cook · Voir plus »
Symposium on Foundations of Computer Science
La conférence Annual IEEE Symposium on Foundations of Computer Science (abrégé en FOCS) est une conférence scientifique dans le domaine de l’informatique théorique.
Nouveau!!: Problème de la clique et Symposium on Foundations of Computer Science · 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!!: Problème de la clique et Théorème de Cook · Voir plus »
Théorème de Kőnig (théorie des graphes)
Exemple d'un graphe biparti avec un couplage maximum (en bleu) et une couverture de sommets minimale (en rouge), tous les deux de taille 6. Le théorème de Kőnig est un résultat de théorie des graphes qui dit que, dans un graphe biparti, la taille du transversal minimum (i. e. de la couverture par sommets minimum) est égale à la taille du couplage maximum.
Nouveau!!: Problème de la clique et Théorème de Kőnig (théorie des graphes) · Voir plus »
Théorie de la complexité (informatique théorique)
P est la classe des problèmes décidés en temps polynomial par une machine de Turing déterministe. La théorie de la complexité est le domaine des mathématiques, et plus précisément de l'informatique théorique, qui étudie formellement le temps de calcul, l'espace mémoire (et plus marginalement la taille d'un circuit, le nombre de processeurs, l'énergie consommée…) requis par un algorithme pour résoudre un problème algorithmique.
Nouveau!!: Problème de la clique et Théorie de la complexité (informatique théorique) · Voir plus »
Théorie de Ramsey
En mathématiques, et plus particulièrement en combinatoire, la théorie de Ramsey, nommée d'après Frank Ramsey, tente typiquement de répondre à des questions de la forme: « combien d'éléments d'une certaine structure doivent être considérés pour qu'une propriété particulière se vérifie ? ».
Nouveau!!: Problème de la clique et Théorie de Ramsey · Voir plus »
Théorie spectrale des graphes
En mathématiques, la théorie spectrale des graphes s'intéresse aux rapports entre les spectres des différentes matrices que l'on peut associer à un graphe et ses propriétés.
Nouveau!!: Problème de la clique et Théorie spectrale des graphes · Voir plus »
The New York Times
(prononcé en anglais), abrégé NYT, est un quotidien new-yorkais fondé en 1851, publié en anglais, espagnol, et chinois.
Nouveau!!: Problème de la clique et The New York Times · Voir plus »
The Thomson Corporation
The Thomson Corporation était un groupe canadien multimédia devenu en 2008 Thomson Reuters.
Nouveau!!: Problème de la clique et The Thomson Corporation · Voir plus »
Uriel Feige
Uriel Feige (en, né en 1959) est un informaticien israélien.
Nouveau!!: Problème de la clique et Uriel Feige · Voir plus »
Visualisation de données
''Carte figurative des pertes successives en hommes de l'armée française dans la campagne de Russie 1812-1813'', par Charles Minard, 1869. La visualisation des données (ou dataviz ou représentation graphique de données) est un ensemble de méthodes permettant de résumer de manière graphique des données statistiques qualitatives et surtout quantitatives afin de montrer les liens entre des ensembles de ces données.
Nouveau!!: Problème de la clique et Visualisation de données · Voir plus »
Voisinage (théorie des graphes)
En théorie des graphes on dit que deux sommets d'un graphe non-orienté sont voisins ou adjacents s'ils sont reliés par une arête.
Nouveau!!: Problème de la clique et Voisinage (théorie des graphes) · 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!!: Problème de la clique et 21 problèmes NP-complets de Karp · Voir plus »
Redirections ici:
3 sat vers clique, 3-SAT vers clique, 3-sat vers clique.
