Análisis de Estructuras de Datos y Algoritmos con Python (2ª edición)

📚 Resumen del contenido

Este libro es un clásico texto de enseñanza sobre estructuras de datos y algoritmos utilizando Python. Cubre repaso de los fundamentos de Python, análisis de algoritmos (notación O grande), estructuras de datos básicas (pila, cola, lista), recursividad, búsqueda y ordenamiento, algoritmos de árboles y grafos. A través de listas de código práctico, ayuda a los lectores a comprender cómo implementar eficientemente diversos tipos abstractos de datos mediante Python.

Solo comprendiendo profundamente las estructuras de datos y los algoritmos se puede dominar realmente Python.

Autor: Bradley Miller (profesor emérito de ciencias de la computación en el Ludus College, Estados Unidos), David Ranum (ingeniero de software cognitivo en IBM Watson)

Agradecimientos: Gracias a nuestros colegas Steve Hubbard por sus valiosos comentarios sobre la primera edición y nuevos materiales para esta nueva versión; también gracias a colegas de todo el mundo que nos han enviado correcciones y sugerencias por correo electrónico. Agradecemos especialmente a Mary, Bob y otros empleados del café Java John's en Decora, por permitirnos convertirnos en "autores residentes" durante nuestras vacaciones. Asimismo, agradecemos la agradable colaboración con los empleados de Franklin, Beedle & Associates (especialmente Jim Leisy y Tom Sumner). Finalmente, agradecemos especialmente a nuestras esposas, Jane Miller y Brenda Ranum, cuyo amor y apoyo hicieron posible la realización de este libro.

🎯 Objetivos de aprendizaje

1. Comprender la relación entre ciencia de la computación, algoritmos y programación, y dominar los conceptos de tipos abstractos de datos (ADT) y ocultación de información.
2. Dominar el uso de los tipos de datos integrados de Python (listas, tuplas, conjuntos, diccionarios) y estructuras de control (bucles, ramificaciones, manejo de excepciones).
3. Entender los fundamentos de la programación orientada a objetos en Python: definición de clases, métodos constructor, sobrecarga de operadores (como la suma de fracciones), aplicación del algoritmo de Euclides, y diferencias entre igualdad profunda y superficial.
4. Comparación de múltiples soluciones algorítmicas: ser capaz de explicar cuatro enfoques para detectar anagramas (conteo, ordenación, fuerza bruta, conteo) junto con sus respectivas complejidades temporales.
5. Cuantificación del rendimiento de contenedores en Python: conocer la eficiencia en notación O grande de operaciones principales en listas (List) y diccionarios (Dict) de Python, y distinguir la diferencia de rendimiento entre pop() y pop(i).
6. Capacidad de validación de rendimiento: poder diseñar experimentos usando el módulo timeit para verificar la coherencia entre la complejidad teórica y el tiempo real de ejecución.
7. Comprender y distinguir las características lógicas de estructuras lineales de datos (pila, cola, cola doble, lista).
8. Ser capaz de implementar pilas, colas y colas dobles personalizadas usando colecciones básicas de Python (como listas).
9. Dominar aplicaciones de pilas en procesamiento de expresiones (conversión de notación infija a postfija, evaluación postfija) y colas en simulaciones de sistemas (simulación de impresora).
10. Dominar los tres principios clave de la recursividad: ser capaz de identificar y escribir funciones recursivas que incluyan caso base, evolución de estado y llamada recursiva.

🔹 Lección 1: Fundamentos de programación en Python y abstracción orientada a objetos

Resumen: Este módulo tiene como objetivo guiar a los estudiantes desde los fundamentos teóricos de la ciencia de la computación hacia la práctica de programación en Python. Primero se definen los conceptos centrales de ciencia de la computación, algoritmos y tipos abstractos de datos (ADT), seguidos por una explicación profunda de los tipos de datos integrados de Python, estructuras de control y manejo de excepciones. Finalmente, se muestra el poder de la programación orientada a objetos (POO) en la abstracción de procesos y datos mediante la construcción de una clase Fraction y una jerarquía de herencia de "puertas lógicas".

Resultados de aprendizaje:

• Comprender la relación entre ciencia de la computación, algoritmos y programación, y dominar los conceptos de tipos abstractos de datos (ADT) y ocultación de información.
• Dominar el uso de los tipos de datos integrados de Python (listas, tuplas, conjuntos, diccionarios) y estructuras de control (bucles, ramificaciones, manejo de excepciones).
• Entender los fundamentos de la programación orientada a objetos en Python: definición de clases, métodos constructor, sobrecarga de operadores (por ejemplo, suma de fracciones), aplicación del algoritmo de Euclides, y diferencias entre igualdad profunda y superficial.

🔹 Lección 2: Análisis de algoritmos y rendimiento de contenedores en Python

Resumen: Este módulo explora en profundidad cómo evaluar la eficiencia de los algoritmos mediante la notación O grande, utilizando la detección de anagramas como ejemplo para mostrar la evolución desde O(n!) hasta O(n) en complejidad. Además, el curso analiza cuantitativamente el rendimiento de las operaciones comunes en las estructuras de datos centrales de Python (listas y diccionarios), con el fin de ayudar a los desarrolladores a tomar decisiones óptimas sobre selección de contenedores y diseño de algoritmos en entornos reales.

Resultados de aprendizaje:

• Comparación de múltiples soluciones algorítmicas: ser capaz de explicar cuatro enfoques para detectar anagramas (conteo, ordenación, fuerza bruta, conteo) junto con sus respectivas complejidades temporales.
• Cuantificación del rendimiento de contenedores en Python: conocer la eficiencia en notación O grande de operaciones principales en listas (List) y diccionarios (Dict) de Python, y distinguir la diferencia de rendimiento entre pop() y pop(i).
• Capacidad de validación de rendimiento: poder diseñar experimentos usando el módulo timeit para verificar la coherencia entre la complejidad teórica y el tiempo real de ejecución.

🔹 Lección 3: Estructuras lineales básicas: pilas, colas y listas enlazadas

Resumen: Este módulo explora en profundidad cuatro estructuras lineales básicas: pila (Stack), cola (Queue), cola doble (Deque) y lista (List). El núcleo de las estructuras lineales radica en mantener un orden relativo entre elementos, siendo su principal diferencia el modo en que se añaden y eliminan elementos. Al implementar estos tipos abstractos de datos (ADT) en Python, los estudiantes aprenderán a resolver problemas algorítmicos reales mediante principios como LIFO (último en entrar, primero en salir) y FIFO (primero en entrar, primero en salir), como conversión de expresiones, simulación de sistemas y gestión de memoria en listas enlazadas.

Resultados de aprendizaje:

• Comprender y distinguir las características lógicas de las estructuras lineales de datos (pila, cola, cola doble, lista).
• Ser capaz de implementar pilas, colas y colas dobles personalizadas usando colecciones básicas de Python (como listas).
• Dominar aplicaciones de pilas en procesamiento de expresiones (conversión de infijo a postfijo, evaluación postfija) y colas en simulaciones de sistemas (simulación de impresora).

🔹 Lección 4: Principios de algoritmos recursivos e introducción a la programación dinámica

Resumen: Este módulo explora en profundidad los principios fundamentales de los algoritmos recursivos, comenzando con los tres principios básicos de la recursividad, y mostrando mediante ejemplos como conversiones numéricas, geometría fractal, y resolución de acertijos clásicos (torre de Hanoi y laberintos) el mecanismo subyacente de las llamadas recursivas —los marcos de pila. Finalmente, se introduce el concepto de programación dinámica (Dynamic Programming), demostrando cómo técnicas como la memorización pueden resolver problemas de cálculo repetido en recursividad, logrando así una mejora sustancial en el rendimiento algorítmico.

Resultados de aprendizaje:

• Dominar los tres principios clave de la recursividad: ser capaz de identificar y escribir funciones recursivas que incluyan caso base, evolución de estado y llamada recursiva.
• Comprender el mecanismo de ejecución subyacente: entender cómo el stack de llamadas de Python gestiona variables locales y rutas de retorno durante la recursividad.
• Tener capacidad de modelado de problemas complejos: ser capaz de aplicar ideas de recursividad y retroceso para resolver problemas no lineales como la torre de Hanoi y el recorrido en laberintos.

🔹 Lección 5: Técnicas de búsqueda, hashing y algoritmos de ordenamiento

Resumen: Este módulo se centra en tecnologías centrales del procesamiento de datos en ciencia de la computación: búsqueda, hashing (hashing) y ordenamiento. Incluye desde búsquedas secuenciales básicas hasta búsquedas binarias eficientes, explora en profundidad la construcción de tablas hash (Hash Tables), métodos de resolución de colisiones y la implementación del tipo abstracto de datos Map (Mapa). Asimismo, se analizan detalladamente los algoritmos de ordenamiento burbuja, shell y fusión, examinando sus lógicas internas y rendimiento.

Resultados de aprendizaje:

• Comprender y comparar escenarios de aplicación y complejidades temporales entre búsqueda secuencial y búsqueda binaria (O(n) frente a O(\log n)).
• Dominar el diseño de funciones hash (método de plegado, método del cuadrado central) y mecanismos de resolución de colisiones (sondeo lineal, sondeo cuadrático, enlace).
• Ser capaz de simular manualmente y codificar los algoritmos de ordenamiento burbuja, shell y fusión, comprendiendo la aplicación de la estrategia divide y vencerás en el ordenamiento.

🔹 Lección 6: Estructuras de árboles: montículos binarios, árboles de búsqueda y árboles balanceados (AVL)

Resumen: Este módulo explora en profundidad una de las estructuras de datos más centrales en ciencia de la computación: el árbol. Comenzamos con términos básicos y la implementación de árboles binarios, avanzando gradualmente hacia aplicaciones avanzadas como los árboles de análisis de expresiones y sus métodos de recorrido. Luego, estudiamos dos variantes altamente eficientes: el montículo binario, utilizado para colas de prioridad, y el árbol de búsqueda binario (BST), ideal para búsquedas eficientes. Finalmente, exploramos los árboles AVL, manteniendo el factor de equilibrio mediante rotaciones para resolver el deterioro de rendimiento del BST en casos peores.

Resultados de aprendizaje:

• Poder definir con precisión los términos centrales de los árboles (raíz, aristas, caminos, altura, etc.) y describir la propiedad recursiva de los árboles binarios.
• Dominar los algoritmos clave para implementar montículos binarios, árboles de búsqueda binarios y árboles AVL en Python (como inserción, eliminación, rotación y reequilibrio).
• Ser capaz de ejecutar y explicar tres algoritmos de recorrido de árboles, y utilizar árboles de análisis para procesar expresiones matemáticas.

🔹 Lección 7: Algoritmos de teoría de grafos: búsqueda, caminos más cortos y árboles generadores mínimos

Resumen: Este módulo explora en profundidad los fundamentos de la teoría de grafos y su implementación eficiente en Python. Cubre el tipo abstracto de datos de grafos (matriz de adyacencia y lista de adyacencia), algoritmos de búsqueda básicos (BFS y DFS) y sus aplicaciones clásicas. Finalmente, avanza hacia algoritmos en grafos ponderados: caminos más cortos (Dijkstra) y árboles generadores mínimos (Prim).

Resultados de aprendizaje:

• Comprender y comparar las dos principales representaciones de grafos (matriz de adyacencia y lista de adyacencia) en cuanto a rendimiento y escenarios de uso.
• Dominar los principios del algoritmo de búsqueda por amplitud (BFS) y búsqueda por profundidad (DFS), y resolver problemas de búsqueda de caminos y recorridos completos.
• Ser capaz de aplicar algoritmos de grafos para resolver dependencias lógicas complejas (orden topológico) y conectividad de redes (componentes fuertemente conexos, árboles generadores mínimos).

🔹 Lección 8: Repaso temático: cifrado RSA, listas saltadas y cuantificación de imágenes con octábolos

Resumen: Este módulo explora la transición de aplicaciones desde estructuras de datos básicas hasta algoritmos complejos en informática. Cubre la implementación interna de listas en Python (ArrayList) y el análisis amortizado, algoritmos recursivos de teoría de números para soportar el cifrado RSA, la construcción de listas saltadas para mejorar la eficiencia de búsquedas en diccionarios, y el principio de cuantificación de colores en imágenes digitales mediante octábolos.

Resultados de aprendizaje:

• Comprender la disposición en memoria de ArrayList y la derivación matemática del análisis amortizado (Amortized Analysis).
• Dominar los principios matemáticos centrales del cifrado RSA, incluyendo el teorema de congruencia, residuos potenciales y el algoritmo extendido de Euclides.
• Ser capaz de describir la estructura jerárquica de las listas saltadas, su proceso constructivo probabilístico y su eficiencia de búsqueda de O(\log n).