Esta semana hemos vuelto a la programación y por eso hemos comenzado con esta actividad del libro CSUnplugged: La furgoneta de los helados (Ice Cream Vans).
La actividad consiste en encontrar el menor número de furgonetas que debemos colocar en un mapa para que todas las calles tengan próximas una (cada intersección debe comunicarse al menos con una furgoneta). Y siempre encontrando el menor número de furgonetas para no gastar demasiado dinero en la compra.Habrá que ir probando hasta encontrar la mejor solución, que normalmente nos costará.
Este tipo de problemas es similar a otros que ya hemos hecho como la coloración de mapas. De hecho son tan similares, que si tuviésemos la solución para uno de ellos, lo tendríamos también para el otro. Son llamados NP-completos, porque no se pueden resolver en un tiempo razonable sin un ordenador no determinístico. Son problemas con soluciones de fuerza bruta exponenciales, lo que hace que su mejor solución sea muy complicada (y a veces imposible). Por eso los matemáticos siguen trabajando en encontrar una solución polinómica que hiciera la resolución más sencilla y corta.
Después de esta actividad, hemos seguido con el curso de code.org. Algunos ya están en la etapa 15 (el artista 4), pero en general, casi todos están en la etapa 11 (el artista 3).
