Colorier la carte de la Grande-Bretagne et de l’Irlande
- Il s’agit d’un problème consistant à colorier la carte de la Grande-Bretagne et de l’Irlande.
- Il faut la colorier de sorte que les régions adjacentes n’aient pas la même couleur.
- Il est possible de choisir une couleur et de l’appliquer par clic.
L’avis de GN⁺
- Ce problème est un exemple de théorie des graphes, connu sous le nom de problème de coloration (
coloring problem).
- Pour un ingénieur logiciel débutant, il aide à comprendre les algorithmes et les structures de données.
- Pour résoudre ce problème, on peut utiliser le backtracking ou un algorithme glouton (
greedy algorithm).
- Un problème similaire est le théorème des quatre couleurs (
four color theorem), selon lequel tout graphe planaire peut être colorié avec quatre couleurs.
- Ce problème permet d’améliorer les capacités de résolution de problèmes et de conception d’algorithmes.
1 commentaires
Commentaire Hacker News
Je l’ai regardé avec mes deux enfants et ils ont tous les deux adoré. La partie sur les preuves à divulgation nulle de connaissance, je ne l’ai pas comprise, mais celle sur le théorème des quatre couleurs était intéressante. En coloriant des cartes avec les enfants, on s’est demandé si cela s’appliquait aussi aux espaces non euclidiens. Sur une sphère, quatre couleurs au maximum suffisent, et sur un tore, il en faut sept.
Il faut expliciter les trois couleurs utilisées à la première étape, puis vérifier à la troisième étape que les couleurs révélées sont toutes différentes et qu’elles font bien partie de ces trois couleurs.
L’expression « très difficile » peut prêter à confusion. On dirait qu’avec assez d’efforts, on finira par trouver la réponse.
Je savais que quatre couleurs suffisent pour n’importe quelle carte, mais essayer de dessiner une carte qui nécessite cinq couleurs a été très gratifiant. Cela m’a permis de comprendre intuitivement quelque chose que je ne connaissais jusque-là qu’en théorie.
Ce serait une bonne idée de contacter des musées consacrés aux thèmes scientifiques. Les musées MINT en Allemagne présentent beaucoup d’installations de ce genre. Je pense que les enfants apprécieraient aussi.
L’interaction et le déroulé étaient bons, mais l’exemple de preuve à divulgation nulle de connaissance était difficile à comprendre. Je connais le concept, mais je ne suis pas sûr que l’exemple constitue vraiment une preuve. On a l’impression que des éléments importants ont disparu lors de la simplification du processus.
La république d’Irlande ne fait pas partie du Royaume-Uni. Le terme « îles Britanniques » serait plus approprié. Cette distinction est importante.
Je sais qu’il est impossible de créer une carte à cinq couleurs, mais c’était amusant d’essayer. Je me demande si c’est un bug. Je ne comprends pas pourquoi ce n’est pas trois couleurs.
C’était l’un des exemples pédagogiques les plus remarquables que j’aie jamais vus. J’ai apprécié l’avertissement disant qu’une carte à cinq couleurs est « très difficile ». C’est bien plus mémorable que d’entendre simplement que quatre couleurs suffisent pour toutes les cartes. J’aimerais qu’on enseigne comme ça à l’école.
La formulation « les mathématiciens pensent que la preuve est correcte » n’est pas appropriée. La preuve a été formellement vérifiée par ordinateur. On pourrait croire que les mathématiciens n’ont pas totalement confiance dans la preuve.