COLORIAGE PROBLÈME DU

ALGORITHMIQUE

  • Écrit par 
  • Philippe COLLARD, 
  • Philippe FLAJOLET
  •  • 6 831 mots
  •  • 3 médias

Dans le chapitre « Algorithmes combinatoires »  : […] Entrent dans la catégorie des problèmes combinatoires , en informatique, les problèmes qui consistent à déterminer, pour une donnée  d , si est satisfaite une condition : où : ( a ) S( d ) est l'espace de recherche (l'espace des solutions potentielles) de taille exponentielle en la taille de d  ; ( b ) Q est une condition facilement vérifiable algorithmiquement (c'est-à-dire en un temps polynomial […] Lire la suite

APPEL KENNETH (1932-2013)

  • Écrit par 
  • Melinda C. SHEPHERD
  •  • 380 mots

Le mathématicien américain Kenneth Appel apporta, avec son confrère Wolfgang Haken, la preuve du problème dit des quatre couleurs en 1976. Kenneth Ira Appel naît le 8 octobre 1932, dans le quartier new-yorkais de Brooklyn. Il étudie les mathématiques au Queens College de New York, où il décroche une licence en 1953, puis à l’université du Michigan, où il passe un doctorat en 1959. Dès l’obtenti […] Lire la suite

GRAPHES PARFAITS THÉORÈME FORT DES

  • Écrit par 
  • Vincent BARRÉ
  •  • 716 mots

Vous organisez un colloque dans lequel plusieurs conférences sont données simultanément (dans des salles différentes et à des horaires imposés par les orateurs) et vous cherchez à occuper le moins de salles possibles (car vous devez les louer). Une méthode permettant de réaliser un tel planning consiste à construire un graphe G dans lequel les conférences seront représentées par des sommets tandi […] Lire la suite

INFORMATIQUE ET VÉRITÉ MATHÉMATIQUE

  • Écrit par 
  • Jean-Paul DELAHAYE
  •  • 1 990 mots
  •  • 1 média

Dans le chapitre « Preuves mathématiques classiques avec ordinateur »  : […] Si l'ordinateur peut conduire à de quasi-certitudes en dehors de la méthode hilbertienne, il peut aussi produire des preuves mathématiques classiques. Plusieurs cas sont possibles, que nous allons présenter en insistant sur ce qui les distingue. Certaines techniques de démonstration automatique produisent des démonstrations qu'aucun humain n'avait découvertes sans aide informatique, mais qui, une […] Lire la suite

QUATRE COULEURS PROBLÈME DES

  • Écrit par 
  • Jean MAYER
  •  • 2 243 mots
  •  • 2 médias

Dans le chapitre « Position du problème »  : […] On veut colorier une carte géographique tracée sur le plan (ou la sphère) de manière que deux régions voisines soient toujours de couleurs différentes. Précisons que chaque région est connexe (d'un seul tenant) et que deux régions voisines ont au moins une ligne frontière en commun. Dans ces conditions, les cartographes ont constaté que toute carte pouvait être coloriée avec quatre couleurs au p […] Lire la suite


Affichage 

Problème du coloriage

Problème du coloriage

dessin

Le problème du coloriage 

Crédits : Encyclopædia Universalis France

Afficher

Problème du coloriage

Problème du coloriage
Crédits : Encyclopædia Universalis France

dessin