Rompecabezas algorítmicos

Algorithmic Puzzles es un libro de acertijos basados ​​en el pensamiento computacional . Fue escrito por las científicas informáticas Anany y Maria Levitin, y publicado en 2011 por Oxford University Press .

El libro comienza con un "tutorial" que introduce técnicas clásicas de diseño de algoritmos, incluyendo retroceso , algoritmos de divide y vencerás y programación dinámica , métodos para el análisis de algoritmos y su aplicación en ejemplos de rompecabezas. ^{[ 1 ] [ 2 ]} Los rompecabezas se agrupan en tres conjuntos de 50 rompecabezas, en orden creciente de dificultad. Los dos últimos capítulos ofrecen breves pistas y soluciones más detalladas a los rompecabezas, ^{[ 2 ]} y las soluciones constituyen la mayor parte de las páginas del libro. ^{[ 3 ]}

Algunos de los rompecabezas son clásicos muy conocidos, otros son variaciones de rompecabezas conocidos que los hacen más algorítmicos, y otros son nuevos. ^{[ 4 ]} Incluyen:

• Rompecabezas que involucran tableros de ajedrez, incluyendo el rompecabezas de las ocho reinas , los recorridos del caballo y el problema del tablero de ajedrez mutilado ^{[ 1 ] [ 3 ] [ 4 ]}
• Rompecabezas de equilibrio ^{[ 3 ]}
• Rompecabezas de cruce de ríos ^{[ 3 ] [ 4 ]}
• La Torre de Hanoi ^{[ 4 ]}
• Encontrar el elemento faltante en un flujo de datos ^{[ 1 ]}
• El problema de la mediana geométrica para la distancia de Manhattan ^{[ 1 ]}

Los acertijos del libro abarcan un amplio rango de dificultad y, en general, no requieren más que conocimientos matemáticos de nivel de bachillerato. ^{[ 3 ]} William Gasarch señala que agrupar los acertijos únicamente por su dificultad y no por sus temas es en realidad una ventaja, ya que proporciona a los lectores menos pistas sobre sus soluciones. ^{[ 1 ]}

El crítico Narayanan recomienda el libro a cualquier aficionado a los rompecabezas o a cualquiera que desee desarrollar sus habilidades de pensamiento algorítmico. ^{[ 4 ]} El crítico Martin Griffiths sugiere otro grupo de lectores: profesores de escuela e instructores universitarios que buscan ejemplos para ilustrar el poder del pensamiento algorítmico. ^{[ 3 ]} Gasarch recomienda el libro a cualquier científico informático, calificándolo de "una delicia". ^{[ 1 ]}