Collection · Informatique théorique
Problèmes NP-complets
Dans Sciences
42 cartes7 joueurs l'ont commencée
Collection « Problèmes NP-complets » sur Wikicard : 42 cartes tirées de Wikipédia, dont Optimisation linéaire en nombres entiers, Problème SAT, Coloration de graphe. Terminée, elle donne un badge brodé « Argent », généré pour elle par IA.
Ses cartes
Coloration de grapheÉpiqueLa 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.
Problème du voyageur de commerceÉpiqueLe 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…
Problème SATÉpiqueLe problème SAT ou problème de satisfaisabilité booléenne est le problème de décision, qui, étant donné une formule de logique propositionnelle, détermine s'il existe une…Optimisation linéaire en nombres entiersÉpiqueL'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…
Problème du sac à dosRareLe problème du sac à dos, parfois noté (KP) (de l'anglais Knapsack Problem) est un problème d'optimisation combinatoire.
- Problème de bin packingRareLe problème de bin packing a été largement étudié dans la communauté de recherche opérationnelle.
- 21 problèmes NP-complets de KarpRareLes 21 problèmes NP-complets de Karp ont marqué une étape importante de l'histoire de la théorie de la complexité des algorithmes.
Problème de couverture par sommetsRareProblème de couverture par sommets est notamment présente dans le chapitre 14 de la traduction par N.
Problème de la cliqueRareLe problème de la clique est un problème algorithmique qui consiste à trouver des cliques (sous-ensembles de sommets tous adjacents deux à deux, également appelés sous-graphes…
- Problème 3-SATPeu communeLe problème 3-SAT est un problème surtout utilisé pour démontrer que d'autres problèmes sont NP-difficiles.
Problème de couverture par ensemblesPeu communeLe problème de couverture par ensembles (Set Cover problem en anglais) est un problème d'algorithmique particulièrement important car c'est l'un des 21 problèmes NP-complets de…
- Coupe maximumPeu communeUne coupe maximum est une coupe contenant au moins autant d'arêtes que n'importe quelle autre coupe.
Problème de tournées de véhiculesPeu communeLe problème de tournées de véhicules (aussi appelé VRP pour Vehicle Routing Problem) est une classe de problèmes de recherche opérationnelle et d'optimisation combinatoire.Problème de la couverture exactePeu communeLe problème de la couverture exacte (exact cover en anglais) consiste à couvrir un ensemble d'éléments, chaque élément étant couvert par exactement un sous-ensemble.
- Problème de partitionPeu communeLe problème de partition est le problème de décision qui, étant donné un multiensemble S d'entiers naturels, détermine s'il existe une partition de S en deux sous-ensembles S1 and…
- Séquençage de tâchesPeu communeLe séquençage de tâches (en anglais job sequencing) est un des nombreux modèles d'ordonnancement d'atelier de production.
Ensemble dominantPeu communeUn ensemble dominant (ou dominating set en anglais) d'un graphe G = ( S, A ) est un sous-ensemble D de l'ensemble S des sommets tel que tout sommet qui n'appartient pas à D…
- Problème de la somme de sous-ensemblesPeu communeLe 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.
- Satisfiability modulo theoriesPeu communeEn informatique et en logique mathématique, un problème de satisfiabilité modulo des théories (SMT) est un problème de décision pour des formules de logique du premier ordre avec…
- Liste de problèmes NP-completsPeu communeCeci 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.
Problème du stable maximumPeu communeLe 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…
- Coupe-cycles de sommetsPeu communeUn coupe-cycles de sommets, ou feedback vertex set en anglais, est un ensemble de sommets d'un graphe, tel que le retrait de ces nœuds laisse le graphe acyclique.
- Partition en cliquesPeu communeUne 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…
- Problème du rendu de monnaiePeu communeLe problème du rendu de monnaie est un problème d'algorithmique.
Appariement à 3 dimensionsPeu communeUn 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,…
- Set packingPeu communeSet packing est un problème d'optimisation combinatoire NP-complet.
- Problème de l'emplacement d'installationsCommuneLe problème d'emplacement d'installations (anglais : facilities location problem) est un problème de recherche opérationnelle et de géométrie algorithmique.
Feedback arc setCommuneUn feedback arc set (FAS) est un ensemble d'arcs qui, lorsqu'il est supprimé du graphe, le transforme en graphe acyclique.
- Ensemble intersectantCommuneL'ensemble intersectant (en anglais Hitting Set Problem) est un problème NP-complet de la théorie combinatoire des ensembles.
Problème de la plus longue chaîneCommuneLe problème de la plus longue chaîne (ou le problème du plus long chemin dans le cas d'un graphe orienté) consiste à déterminer la plus longue chaîne élémentaire dans un graphe.
- K-centreCommuneK-centre (k-center problem en anglais) est un problème d'optimisation combinatoire, une branche de l'algorithmique.
Problème de l'isomorphisme de sous-graphesCommuneLe problème de l'isomorphisme de sous-graphes est le problème de décision suivant : étant donnés deux graphes G et H, déterminer si G contient un sous-graphe isomorphe à H.
- K-médianeCommuneK-médiane, ou k-median en anglais, est un problème d'optimisation combinatoire, une branche de l'algorithmique.
Nombre achromatiqueCommuneLe nombre achromatique ψ(G) d'un graphe G est le nombre maximum de couleurs possibles dans une coloration complète de G.
Triangulation de grapheCommuneLa triangulation de graphe est un problème d'algorithmique et de théorie des graphes.Nombre d'intersectionCommuneLe nombre d'intersection d'un graphe G = ( V , E ) {\displaystyle G=(V,E)} est le nombre minimal d'éléments nécessaires pour représenter G {\displaystyle G} sous forme de graphe…
- Dimension bipartieCommuneLa dimension bipartie d'un graphe G = (V, E) non orienté est le nombre minimum de sous-graphes bipartis complets nécessaires pour couvrir toutes les arêtes de E.
- Problème de couverture maximaleCommuneLe problème de couverture maximale consiste à couvrir un nombre maximal d'éléments avec au plus k sous-ensembles mis à disposition.
- Nombre domatiqueCommuneLe nombre domatique d'un graphe est son nombre maximum d'ensembles dominants disjoints deux à deux.
- Problème de satisfiabilité de circuitCommuneEn informatique théorique, le problème de satisfaisabilité d'un circuit (aussi connu sous le nom de CIRCUIT-SAT, CircuitSAT, CSAT, etc.) est le problème de décision consistant à…
- Code identifiant d'un grapheCommuneEn mathématiques, et plus précisément en théorie des graphes, un code identifiant d’un graphe est un sous-ensemble de ses sommets tel que chaque sommet du graphe est identifié de…
- Problème du k-supplierCommuneLe problème du k-supplier minimum est un problème algorithmique de théorie des graphes.
Ouvrez des paquets de cartes tirées de Wikipédia, terminez vos collections pour gagner leur badge brodé, défiez d'autres joueurs en Joute. Gratuit, sans avantage payant.