Solución de problemas con algoritmos y estructuras de datos usando Python

Por Brad Miller y David Ranum, Luther College

Traducido por Mauricio Orozco-Alzate, Universidad Nacional de Colombia - Sede Manizales

• Tareas

• 1. Introducción
  • 1.1. Objetivos
  • 1.2. Para comenzar
  • 1.3. ¿Qué son las ciencias de la computación?
  • 1.4. ¿Qué es programación?
  • 1.5. ¿Por qué estudiar estructuras de datos y tipos abstractos de datos?
  • 1.6. ¿Por qué estudiar algoritmos?
  • 1.7. Repaso de Python básico
  • 1.8. Comencemos con los datos
    • 1.8.1. Tipos de datos atómicos incorporados
    • 1.8.2. Tipos de datos de colecciones incorporados
  • 1.9. Entrada y salida
    • 1.9.1. Formato de cadenas
  • 1.10. Estructuras de control
  • 1.11. Manejo de excepciones
  • 1.12. Definición de funciones
  • 1.13. Programación orientada a objetos en Python: Definición de clases
    • 1.13.1. Una clase Fraccion
    • 1.13.2. Herencia: Compuertas lógicas y circuitos
  • 1.14. Resumen
  • 1.15. Términos clave
  • 1.16. Preguntas de discusión
  • 1.17. Ejercicios de programación
• 2. Análisis
  • 2.1. Objetivos
  • 2.2. ¿Qué es análisis de algoritmos?
  • 2.3. Notación O-grande
  • 2.4. Un ejemplo de detección de anagramas
    • 2.4.1. Solución 1: Marcado de verificación
    • 2.4.2. Solución 2: Ordenar y comparar
    • 2.4.3. Solución 3: Fuerza bruta
    • 2.4.4. Solución 4: Contar y comparar
  • 2.5. Desempeño de las estructuras de datos de Python
  • 2.6. Listas
  • 2.7. Diccionarios
  • 2.8. Resumen
  • 2.9. Términos clave
  • 2.10. Preguntas de discusión
  • 2.11. Ejercicios de programación
• 3. Estructuras de datos básicas
  • 3.1. Objetivos
  • 3.2. ¿Qué son estructuras lineales?
  • 3.3. ¿Qué es una pila?
  • 3.4. El tipo abstracto de datos Pila
  • 3.5. Implementación de una pila en Python
  • 3.6. Paréntesis balanceados
  • 3.7. Símbolos balanceados (Un caso general)
  • 3.8. Conversión de números decimales a números binarios
  • 3.9. Expresiones en notaciones infija, prefija y sufija
    • 3.9.1. Conversión de expresiones infijas a notaciones prefija y sufija
    • 3.9.2. Conversión general de notación infija a notación sufija
    • 3.9.3. Evaluación de expresiones en notación sufija
  • 3.10. ¿Qué es una cola?
  • 3.11. El tipo abstracto de datos Cola
  • 3.12. Implementación de una cola en Python
  • 3.13. Simulación: la patata caliente
  • 3.14. Simulación: Tareas de impresión
    • 3.14.1. Pasos principales de la simulación
    • 3.14.2. Implementación en Python
    • 3.14.3. Discusión
  • 3.15. ¿Qué es una cola doble?
  • 3.16. El tipo abstracto de datos Cola Doble
  • 3.17. Implementación de una cola doble en Python
  • 3.18. Verificador de palíndromos
  • 3.19. Listas
  • 3.20. El tipo abstracto de datos Lista No Ordenada
  • 3.21. Implementación de una lista no ordenada: Listas enlazadas
    • 3.21.1. La clase Nodo
    • 3.21.2. La clase ListaNoOrdenada
  • 3.22. El tipo abstracto de datos Lista Ordenada
  • 3.23. Implementación de una lista ordenada
    • 3.23.1. Análisis de las listas enlazadas
  • 3.24. Resumen
  • 3.25. Términos clave
  • 3.26. Preguntas de discusión
  • 3.27. Ejercicios de programación
• 4. Recursividad
  • 4.1. Objetivos
  • 4.2. ¿Qué es recursividad?
  • 4.3. Cálculo de la suma de una lista de números
  • 4.4. Las tres leyes de la recursividad
  • 4.5. Conversión de un entero a una cadena en cualquier base
  • 4.6. Marcos de pila: Implementación de la recursividad
  • 4.7. Visualización de la recursividad
  • 4.8. El triángulo de Sierpinski
  • 4.9. Problemas recursivos complejos
  • 4.10. Las torres de Hanoi
  • 4.11. Exploración de un laberinto
  • 4.12. Programación dinámica
  • 4.13. Resumen
  • 4.14. Términos clave
  • 4.15. Preguntas de discusión
  • 4.16. Glosario
  • 4.17. Ejercicios de programación
• 5. Ordenamiento y búsqueda
  • 5.1. Objetivos
  • 5.2. Búsqueda
  • 5.3. La búsqueda secuencial
    • 5.3.1. Análisis de la búsqueda secuencial
  • 5.4. La búsqueda binaria
    • 5.4.1. Análisis de la búsqueda binaria
  • 5.5. Transformación de claves (hashing)
    • 5.5.1. Funciones hash
    • 5.5.2. Solución de colisiones
    • 5.5.3. Implementación del tipo abstracto de datos Vector Asociativo
    • 5.5.4. Análisis de la transformación de claves
  • 5.6. Ordenamiento
  • 5.7. El ordenamiento burbuja
  • 5.8. El ordenamiento por selección
  • 5.9. El ordenamiento por inserción
  • 5.10. El ordenamiento de Shell
  • 5.11. El ordenamiento por mezcla
  • 5.12. El ordenamiento rápido
  • 5.13. Resumen
  • 5.14. Términos clave
  • 5.15. Preguntas de discusión
  • 5.16. Ejercicios de programación
• 6. Árboles y algoritmos de árboles
  • 6.1. Objetivos
  • 6.2. Ejemplos de árboles
  • 6.3. Vocabulario y definiciones
  • 6.4. Implementación
  • 6.5. Representación de lista de listas
  • 6.6. Nodos y referencias
  • 6.7. Árbol de análisis
  • 6.8. Recorridos de árboles
  • 6.9. Colas de prioridad con montículos binarios
  • 6.10. Operaciones de montículos binarios
  • 6.11. Implementación de un montículo binario
    • 6.11.1. La propiedad de estructura
    • 6.11.2. La propiedad de orden del montículo
    • 6.11.3. Operaciones con montículos
  • 6.12. Árboles binarios de búsqueda
  • 6.13. Operaciones de un árbol de búsqueda
  • 6.14. Implementación de un árbol de búsqueda
  • 6.15. Análisis de árboles de búsqueda
  • 6.16. Árboles binarios de búsqueda equilibrados
  • 6.17. Desempeño de un árbol AVL
  • 6.18. Implementación de un árbol AVL
  • 6.19. Resumen de implementaciones del TAD Vector Asociativo
  • 6.20. Resumen
  • 6.21. Términos clave
  • 6.22. Preguntas de discusión
  • 6.23. Ejercicios de programación
• 7. Grafos y algoritmos de grafos
  • 7.1. Objetivos
  • 7.2. Vocabulario y definiciones
  • 7.3. El tipo abstracto de datos grafo
  • 7.4. Una matriz de adyacencia
  • 7.5. Una lista de adyacencia
  • 7.6. Implementación
  • 7.7. El problema de la escalera de palabras
  • 7.8. Construcción del grafo de la escalera de palabras
  • 7.9. Implementación de la búsqueda en anchura
  • 7.10. Análisis de la búsqueda en anchura
  • 7.11. El problema de la gira del caballo
  • 7.12. Construcción del grafo de la gira del caballo
  • 7.13. Implementación de la gira del caballo
  • 7.14. Análisis de la gira del caballo
  • 7.15. Búsqueda en profundidad general
  • 7.16. Análisis de la búsqueda en profundidad
  • 7.17. Ordenamiento topológico
  • 7.18. Componentes fuertemente conectados
  • 7.19. Problemas de la ruta más corta
  • 7.20. El algoritmo de Dijkstra
  • 7.21. Análisis del algoritmo de Dijkstra
  • 7.22. Algoritmo de Prim del árbol de expansión
  • 7.23. Resumen
  • 7.24. Términos clave
  • 7.25. Preguntas de discusión
  • 7.26. Ejercicios de programación

Agradecimientos

Nosotros los autores, Brad Miller y David Ranum, estamos muy agradecidos con Franklin Beedle Publishers por permitirnos que esta versión interactiva esté disponible libremente. Esta versión en línea está dedicada a la memoria de nuestro primer editor, Jim Leisy, que quiso que “cambiáramos el mundo”.

El traductor, Mauricio Orozco-Alzate, agradece a la Universidad Nacional de Colombia - Sede Manizales por permitirle emprender el proyecto de traducción como una de sus actividades académicas de su año sabático 2017-2018. La tarea se facilitó en gran medida gracias a la excelente herramienta de traducción gratuita de Google.

Índices y tablas

• Index

• Module Index

• Search Page

Problem Solving with Algorithms and Data Structures using Python by Bradley N. Miller, David L. Ranum is licensed under a Creative Commons Attribution-NonCommercial-ShareAlike 4.0 International License.

You have attempted of activities on this page