Para comenzar se ilustrarán los tres aspectos de la algorítmica a través del problema de las torres de Hanoi: diseño, análisis y optimalidad. Se analizará la noción de algoritmo y cuáles son las maneras para medir su eficiencia. En el camino aparecerá un paradigma de solución de problemas muy importante: la recursividad, y se verá la utilidad de la técnica de inducción. Pero primero se trabajará con un ejemplo sencillo: colorear mapas.
Recuérdese la prueba por inducción para el problema de colorear mapas. El argumento es éste: suponiendo que se puede colorear cualquier mapa de n países con seis colores, es posible hacer lo mismo para cualquier mapa de n + 1 países.
Así que a Arcadio se le ocurre un algoritmo muy sencillo para colorear un mapa, con ayuda de amigos. Cuando Arcadio desea colorear un mapa, primero busca un país, digamos X, que tenga a lo más cinco vecinos. Luego copia su mapa a otro papel, pero borra X. Le pasa el mapa a Úrsula y le pide que lo coloree con seis colores. Cuando ella se lo regresa, usa esos colores para colorear su mapa original y colorea a X con un color distinto al de sus vecinos. Éste es todo el algoritmo, ya que Úrsula hace lo mismo. Borra un país de igual manera y le pide ayuda a su hermanito para que coloree lo que queda del mapa. Eventualmente, después de borrar países del mapa, queda uno con sólo seis países, y para colorearlo no hace falta pedir ayuda a nadie.
Colorea con seis (mapa de n países)
Si n es seis o menos, asignar un color a cada país, entre uno y seis.
De otro modo, colorea con seis (mapa de n − 1 países quitando algún país X que tenga a lo más cinco vecinos). Colorea X con un color distinto al de sus vecinos.
Éste es un ejemplo de algoritmo recursivo, que se ejecuta él mismo una y otra vez, pero cada vez con entradas más pequeñas, hasta llegar a una tan chica que se resuelve trivialmente. Para probar que un algoritmo de este tipo es correcto, la técnica de la inducción es ideal, como se ve en este ejemplo, donde el algoritmo sigue la estructura de la prueba por inducción paso a paso.
¿Qué tan eficiente es el algoritmo? Al parecer bastante, ya que para colorear n países se pide ayuda n veces. El único detalle es que cada vez que se pide ayuda hay que localizar un país con cinco vecinos como máximo. Esto se puede evitar y obtener un algoritmo cuyo tiempo de ejecución sea proporcional a n.4
