Uno de nuestros libros de Python más interesantes durante el último año ha sido Classic Computer Science Problems in Python de David Kopec.
Para aquellos que aún no han tenido tiempo de familiarizarse con este libro, ofrecemos su reseña, escrita según la edición original en octubre de 2019. También puede consultar una pequeña discusión en Reddit . Además, todos pueden comentar sobre la impresión adicional; para esto, se coloca una boleta de votación al final del artículo.
Me gustó mucho el libro "Problemas clásicos de la informática en Python" de David Kopec. Realmente aborda muchos problemas diversos, información detallada con la que no me he encontrado antes. Solo algunos ejemplos: redes neuronales, problemas de satisfacción de restricciones, algoritmos genéticos, algoritmo minimax. A diferencia de muchos otros libros sobre algoritmos y problemas de programación, este libro muestra programas completos (pero pequeños) que puede explorar fácilmente por su cuenta.
Disfruto aprendiendo algoritmos. Trabajé en el libro " Carrera de Programador ", tomé varios cursos MOOC, en particular, " Diseño y Análisis de Algoritmos " del profesor Tim Rafgarden . Sin embargo, en el libro de Kopec también había tales algoritmos, cuya mención no había visto antes.
CAPÍTULOS QUE MÁS ME GUSTARON
Redes neuronales . Mi sección favorita del libro es sobre redes neuronales. El autor describe la creación de una red neuronal en toda regla. Mientras tanto, describe cómo funcionan todas sus partes, en general y en particular. Describe cómo se organizan las neuronas y las capas, cómo funciona la función de activación, cómo se usa la propagación hacia atrás durante el entrenamiento, cómo se corrigen los pesos.
Finalmente, la red neuronal se utiliza como ejemplo de iris de Fisher. Este es un conjunto de datos clásico, compilado en la década de 1930, con 150 especímenes de flores pertenecientes a diferentes tipos de iris (50 especímenes cada uno). Cada espécimen va acompañado de cuatro valores numéricos: la longitud del lóbulo del perianto externo; el ancho del lóbulo exterior del perianto; la longitud del lóbulo interno del perianto; el ancho del lóbulo del perianto interno. Los valores se normalizan primero. Luego se crea una malla de tres capas. Hay cuatro neuronas en la capa de entrada (una para cada categoría de valores de entrada de la muestra), en la capa oculta hay seis neuronas y en la capa de salida hay tres neuronas (una para cada tipo de iris considerado).
Se seleccionaron al azar 140 de 150 muestras, que luego se utilizaron para entrenar la red. El entrenamiento se ejecuta en 140 muestras en 50 iteraciones. Luego, la red se utiliza para predecir a cuál de las tres especies de iris pertenecen las 10 muestras restantes. En la mayoría de los casos, la red identifica correctamente al menos 8 de cada 10 muestras, y con bastante frecuencia, y las 10.
Me gustó mucho esta experiencia: programar una red neuronal completa desde cero sin recurrir a bibliotecas de aprendizaje automático. Experimenté con este programa por un tiempo (todo el código del libro está publicado en GitHub). Por ejemplo, imprimí una copia impresa de todos los pesos en todas las neuronas después de que la red estuvo completamente entrenada. Quería ver si habría alguna similitud entre los pesos entre diferentes carreras. Los pesos resultaron ser sorprendentemente diferentes de una carrera a otra, aunque el éxito predictivo en todos los casos siguió siendo similar. Tal vez esta sea una verdad elemental, pero estaba muy interesado en ver esto por mí mismo.
Búsqueda de adversarios... En este capítulo, se nos presenta el algoritmo minimax. Encuentra el mejor movimiento en un juego de suma cero con dos oponentes. La idea es analizar movimientos potenciales, hablando en nombre de uno u otro oponente; cada oponente reacciona al último de los movimientos realizados hasta que el juego termina (o se alcanza la profundidad máxima de recursión). En el primer ejemplo del libro, la IA está jugando al tic-tac-toe. En este caso, se puede analizar completamente la secuencia completa de movimientos, ya que el tamaño del campo de juego es de solo 3 por 3 celdas.
Como en los otros capítulos, aquí se desarrolla primero la estructura general, que luego se considera en relación con los casos complejos. Después del ejemplo con tic-tac-toe, el juego " Cuatro seguidos ". En este caso, la evaluación de movimientos es mucho más difícil que en "Tic-Tac-Toe", por lo que aquí la búsqueda en profundidad se limita a tres movimientos. Recurrí mucho a este capítulo, ya que nunca antes había visto una descripción del algoritmo minimax.
Tareas de satisfacción... Aquí también se desarrolla un marco general, que luego se utiliza para resolver varios problemas. En el corazón de esta estructura se encuentra el retroceso recursivo. El primer problema resuelto en este capítulo es la tarea de colorear el mapa de Australia. ¿Es posible arreglárselas con solo tres colores y colorear el mapa de modo que las áreas adyacentes a ambos lados de cualquier borde entre regiones sean de diferente color? (Respuesta: si). La segunda tarea es colocar ocho reinas en el tablero de ajedrez, asegurándose de que ninguna reina sea atacada por ninguna otra. La tercera tarea es organizar la lista de palabras en una cuadrícula para formar un cuadrado para buscar palabras. Finalmente, la estructura se utiliza para resolver el clásico rompecabezas cripto-aritmético ENVIAR + MÁS = DINERO. El objetivo es averiguar a qué dígito corresponde cada letra para que la igualdad aritmética resultante sea correcta.
Me gustó este capítulo porque contiene muchos ejemplos muy diversos, y también porque no he usado previamente este enfoque para resolver tales problemas (al menos de manera sistemática).
Algoritmos genéticos . Antes de leer este capítulo, solo tenía una idea muy general de cómo funcionan los algoritmos genéticos. El código de este capítulo demuestra una clase de cromosomas que es instanciada por genes seleccionados al azar. Un cromosoma puede evaluar su propia adaptabilidad al entorno e implementa el mestizaje (una combinación de sí mismo con otro cromosoma del mismo tipo), y también muta (hace pequeños cambios completamente aleatorios en sí mismo).
El algoritmo comienza con una población aleatoria. En cada generación de esta población, el algoritmo comprueba (utilizando la función de aptitud) si hay una solución suficientemente buena (la aptitud está por encima de un valor umbral determinado). Si no existe tal solución, entonces se crea una nueva generación a través de operaciones repetidas de cruce de pares de individuos (cuanto mayor sea la aptitud de cada individuo, más probable es que estos individuos entren en acción). Además, se seleccionan varios individuos para mutaciones. Ahora estos nuevos individuos dan lugar a una nueva población y, nuevamente, se prueban sus funciones de aptitud. El ciclo se repite durante un número determinado de generaciones.
Los siguientes problemas se consideran como ejemplos: maximizar una expresión matemática, el rompecabezas "ENVIAR + MÁS = DINERO" mencionado anteriormente y ordenar los elementos en una lista para minimizar el tamaño de la lista cuando se comprime. El mérito de este capítulo, como muchos otros, es que todos los conceptos se muestran en el contexto de una solución compacta pero completa.
Buscar... Los algoritmos de este capítulo no eran nuevos para mí (a excepción de A *), pero el capítulo sigue siendo interesante gracias a los ejemplos que se dan en él. El autor demuestra los principios de Breadth First Search y Depth First Search usando el ejemplo de salir del laberinto. Los laberintos son cuadrículas ordinarias de 9 por 9 celdas cada una, en las que se colocan obstáculos al azar. Se muestra en la pantalla utilizando solo caracteres ASCII. Con la ayuda de algoritmos, se encuentra un camino a través de la cuadrícula, en diagonal, evitando obstáculos. El camino que se encuentra de esta manera también se dibuja a través del laberinto.
Puede cambiar fácilmente estos programas para probar cómo funcionan los algoritmos en diferentes escenarios. Después de familiarizarse con Breadth First Search, el autor habla sobre A *. La diferencia es que los caminos se dibujan usando una heurística (distancia euclidiana), que se usa como guía y le dice qué caminos dibujar primero. El último ejemplo de este capítulo utiliza una función de búsqueda para ayudarte a conseguir tres misioneros y tres ogros en una canoa a través de un río. La limitación es que el número de caníbales no puede exceder el número de misioneros ya sea en la orilla o en el bote, de lo contrario los caníbales se comerán a los misioneros. Creo que esta es una aplicación muy inteligente e interesante del algoritmo de búsqueda.
OTROS CAPITULOS
Otros capítulos contienen algoritmos con los que ya estoy familiarizado.
Tareas sencillas (primer capítulo). El primer capítulo contiene muchos pequeños ejemplos. Primero describe las diferentes formas de calcular los números de Fibonacci (en particular, recursivo, con memorización, iterativo y con un generador de Python). La siguiente sección trata sobre la manipulación de bits para compresión y cifrados XOR. Finalmente, necesitaremos la recursividad en este capítulo para resolver el problema de las torres de Hanoi.
Problemas gráficos . El Capítulo 4 analiza los algoritmos de gráficos para encontrar la ruta más corta y el árbol de expansión mínimo, utilizando un mapa de los Estados Unidos como ejemplo. También se considera el algoritmo de Dijkstra.
Agrupación de K-medias... Este capítulo le muestra cómo agrupar puntos de datos en un número predeterminado de grupos en función de la distancia relativa desde cada punto al centro del grupo. Los ejemplos de este capítulo no me interesaron tanto como los de los otros capítulos.
Otras tareas . El capítulo final trata sobre el problema de la mochila, el problema del viajante y los mnemotécnicos de los números de teléfono.
QUE ADJUNTARIAS
Todos los programas usan las sugerencias de tipo de Python. Tengo una actitud doble hacia esos consejos. Por un lado, los tipos contribuyen a una mejor comprensión del programa. Pero, por otro lado, no estoy acostumbrado a verlos en Python, y algunas veces tuve que entender estas sugerencias antes de empezar a entender la lógica del programa.
Si quiere quejarse de una sección, entonces la que habla de programación dinámica. En mi opinión, carece de integridad. La programación dinámica es algo complicado, y si la va a utilizar en soluciones del mundo real, necesitará ejemplos adicionales sobre este tema.
CONCLUSIÓN
Las principales razones por las que realmente me gustó este libro son la amplitud de los algoritmos considerados, completos (al mismo tiempo, soluciones compactas) que son fáciles de investigar por sí mismos, así como interesantes ejemplos seleccionados para ilustrar los algoritmos.