NOMBRES – Curiosités, Théorie et Usages

 

Accueil                           DicoNombre            Rubriques           Nouveautés      Édition du: 27/06/2021

Orientation générale        DicoMot Math          Atlas                   Actualités                       M'écrire

Barre de recherche          DicoCulture              Index alphabétique        Références      Brèves de Maths  

             

Histoire des maths

 

Débutants

Général

BILAN

des connaissances

 

Glossaire

Général

 

 

INDEX

Histoire

 

Crises

23 Pb. de Hilbert

7 Pb. Clay

Les 17 équations

10 Pb. d'Apollonius

21 Pb. de Karp

4 Pb. Landau

Les 15 algorithmes

 

Sommaire de cette page

>>> Ensembles

>>> Logique

>>> Graphes

>>> Optimisation

 

 

 

 

Les 21 problèmes

NP-complets de Karp

 

Domaine de la théorie de la complexité des algorithmes.

Sujets: combinatoire, graphes

Contributeur Richard Karp (né en 1935) en 1972. Prix Turing en 1985.

Le regroupement par thèmes est mon propre choix.

 

Voir Problème du voyageur de commerce et problème P = NP

 

 

Ensembles

 

PARTITION

Problème de partition: il s'agit de partager exactement (partitionner) un ensemble de nombres entiers en deux sous-ensembles tels que la somme des nombres de l'un soit égale à la somme des nombres de l'autre.

 

Exemple: {1, 2, 2, 3, 3, 4, 5} => {1, 2, 3, 4} et {2, 3, 5}.

 

SET COVERING

 

 

 

 

 

 

EXACT COVER

On dispose de sous-ensembles. Avec eux, il s'agit de retrouver tous les éléments d'un autre ensemble en utilisant une quantité minimale de ces sous ensembles.

Exemple: {1,2}, {3,5},{1,2,3},{4,5,6,7} pour{1,2,3,4,5,6}
=> couverture: {1,2,3} et {4,5,6,7}

 

Une couverture exacte est celle réalisées avec des sous-ensembles disjoints (aucun éléments communs).

Exemple: {1,2}, {3,5},{3,4},{4,5,6} pour{1,2,3,4}
=> couverture exacte: {1,2} et {3,4}

 

HITTING SET

Le problème de l'ensemble intersectant consiste à trouver un sous-ensemble contenant au moins un élément de chacun des ensembles d'une famille.

De plus, la quantité d'éléments est limitée.

 

3-DIMENSIONAL MATCHING

Appariement à 3 dimensions: on dispose de trois ensembles disjoints (X, Y, Z) et d'un jeu de contraintes. Le problème consiste à décider s'il existe un ensemble (U) de triplets associant un élément de chaque ensemble (X, Y, Z) sous contrainte avec une quantité minimale d'éléments.

 

Exemple: comment associer des hommes, des femmes et des chats en triplets homme-femme-chat avec des contraintes de compatibilité (certains n'aiment pas les chats ou les gros nez …)

 

 

Logique

 

 

SATISFIABILITY

Problème SAT: problème de décision, qui, étant donné une formule de logique (avec des Et, Ou, Non …), détermine s'il existe une valeur des variables qui rend la formule vraie.

Exemple:

La réponse est "vrai" ou "faux" sans se soucier de la valeur des variables.

 

3-SAT

Forme particulière du problème SAT avec trois variables par clause logique.

Exemple:

Illustration naïve

Les carrés de la figure sont nommés a ou b au choix. Les ronds ont trois bras. Chacun doit être relié à un carré a ou b au moins. Un problème 3-SAT se pose la question: est-il possible de nommer les carrés de sorte que chaque rond soir relié à un carré de type a, au moins? Résolution évidente ici.

Voir Énigme des trois maisons

 

 

 

Graphes

 

CHROMATIC NUMBER

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.

Le nombre minimal de couleurs est appelé nombre chromatique.

 

VERTEX COVER

Le problème de couverture par sommets consiste, étant donné un graphe, à trouver un ensemble minimum de sommets pour couvrir toutes les arêtes.

 

CLIQUE

CLIQUE COVER

Problème de la clique: problème algorithmique qui consiste à trouver des cliques dans un graphe.

Clique: sous-ensemble de sommets d'un graphe tous adjacents les uns aux autres, également appelés sous-graphe complet.

Le problème de la couverture par cliques est le problème algorithmique qui consiste à trouver une couverture par cliques minimale.

 

FEEDBACK ARC SET

 

FEEDBACK NODE SET

Préoccupation qui consiste à supprimer des arcs du graphe pour éliminer des circuits indésirables.

Préoccupation qui consiste à supprimer des nœuds du graphe pour éliminer des circuits indésirables.

 

DIRECTED HAMILTONIAN CIRCUIT

UNDIRECTED HAMILTONIAN CIRCUIT

 

Un chemin hamiltonien est un chemin qui passe par tous les sommets une fois et une seule.

Rappel: un graphe eulérien est un chemin qui passe par toutes les arêtes une fois et une seule

MAX-CUT

Problème de la coupe maximum: comment partitionner un graphe en deux graphes complémentaires de sorte que la quantité d'arcs soit maximale dans les deux sous-graphes.

 

Optimisation

 

STEINER TREE

Un arbre relie tous les points d'un réseau. Si la longueur totale est minimale, il s'agit d'un arbre de Steiner.

 

KNAPSACK

Problème du sac à dos: problème d'optimisation du contenu d'un sac à dos.

Comment obtenir un poids minimum et une valeur maximale avec des objets de poids et de valeurs connus.

Voir Optimisation linéaire.

SET PACKING

Empaquetage d'ensemble

Problème d'un sac à dos multidimensionnel où les poids des objets sont égaux à 0 ou 1 et où les capacités du sac sont toutes égales à 1.

 

0-1 INTEGER PROGRAMMING

Optimisation linéaire (ou programmation linéaire) ne faisant intervenir que des nombres entiers pour la fonction de coût comme pour les contraintes.

Similitude avec équations diophantiennes

JOB SEQUENCING

Séquençage de tâches ou planification: sous contraintes de durée, de coûts, de ressources, etc.

Comment ordonnancer les tâches ?

Des pénalités sont infligées en cas de dépassement. Quelle est la séquence des tâches qui minimalise les pénalités ?

Voir Énigmes de rythme de travail

 

 

 

 

Suite

*    Les 7 problèmes de la fondation Clay

*    Dix problèmes de maths difficiles, résolus

*    Problèmes NP

*    HistoireIndex

Voir

*      Courbe de Hilbert

*      Théorie des nombres

*      Calcul mental

*      Géométrie

*      Infinis

*      Gravitation

*    Relativité

DicoNombre

*    Nombre 21

Sites

*      21 problèmes NP-complets de Karp – Wikipédia

*      Linearly-growing Reductions of Karp's 21 NP-complete Problems** – Cornell University

*      NP-Hard problem** – Jeff Erickson

Cette page

http://villemin.gerard.free.fr/Wwwgvmm/Histoire/Karp.htm