Colorindo o mapa da Grã-Bretanha e da Irlanda
- Trata-se de um problema de colorir o mapa da Grã-Bretanha e da Irlanda.
- É preciso colorir de modo que regiões adjacentes não tenham a mesma cor.
- É possível selecionar e aplicar cores com cliques.
Opinião do GN⁺
- Este problema é um exemplo de teoria dos grafos, conhecido como problema de coloração (
coloring problem).
- Para engenheiros de software iniciantes, ele ajuda a entender algoritmos e estruturas de dados.
- Para resolver esse problema, é possível usar
backtracking ou um algoritmo guloso (greedy algorithm).
- Um problema semelhante é o "teorema das quatro cores" (
four color theorem), segundo o qual todo grafo planar pode ser colorido com quatro cores.
- Por meio desse problema, é possível melhorar a capacidade de resolução de problemas e de projeto de algoritmos.
1 comentários
Comentários do Hacker News
Vi com duas crianças e ambas gostaram. Não entendi a parte sobre provas de conhecimento zero, mas a parte do teorema das quatro cores foi interessante. Colorimos mapas com as crianças e ficamos curiosos sobre a aplicação em espaços não euclidianos. Na esfera, no máximo quatro cores; no toro, são necessárias sete cores.
É preciso explicitar as três cores usadas na primeira etapa e, na terceira etapa, verificar que as cores reveladas são diferentes entre si e pertencem a uma dessas três cores.
A expressão "muito difícil" pode induzir ao erro. Soa como se, com esforço suficiente, fosse possível chegar à resposta.
Eu já sabia que quatro cores são suficientes para qualquer mapa arbitrário, mas foi muito gratificante tentar desenhar um mapa que exigisse cinco cores. Isso me fez entender intuitivamente algo que eu só conhecia na teoria.
Acho que seria bom entrar em contato com museus sobre temas científicos. Os museus MINT na Alemanha lidam bastante com exposições desse tipo. Parece algo de que as crianças também poderiam gostar.
A interação e o fluxo foram bons, mas o exemplo de prova de conhecimento zero foi difícil de entender. Conheço o conceito, mas não tenho certeza de que o exemplo realmente seja uma prova. Parece que, ao simplificar o processo, algum elemento importante ficou de fora.
A República da Irlanda não faz parte do Reino Unido. O termo "Ilhas Britânicas" seria mais apropriado. Essa distinção é importante.
Sei que é impossível criar um mapa de cinco cores, mas foi divertido tentar. Fiquei me perguntando se isso é um bug. Não entendo por que não são três cores.
Este foi um dos exemplos educacionais mais legais que já experimentei. Gostei do aviso de que o mapa de cinco cores era "muito difícil". Isso fica muito mais marcante do que apenas ouvir que quatro cores bastam para todos os mapas. Queria que ensinassem assim na escola.
A expressão "os matemáticos acreditam que a prova está correta" não é apropriada. A prova foi formalmente verificada por computador. Isso pode dar a impressão de que os matemáticos não têm plena confiança na prova.