ALGORITMOS PYTHON-páginas-1

Vista previa del material en texto

Walter Bel
Algoritmos y estructuras
de datos en Python
Un enfoque ágil y estructurado
Índice
Introducción 9
CAPÍTULO I
Una breve introducción a algoritmos, estructuras de datos y Python 11
CAPÍTULO II
Auto llamadas con algoritmos recursivos 19
CAPÍTULO III
Analizando algoritmos en búsqueda de eficiencia 27
CAPÍTULO IV
Buscar es más fácil cuando las cosas están ordenadas 43
CAPÍTULO V
Representando modelos reales con tipos de datos abstractos 67
CAPÍTULO VI
Desde la cima de la pila, intentando evitar el desbordamiento 77
CAPÍTULO VII
Por favor espere su turno en la cola que será atendido 87
CAPÍTULO VIII
Como vagones de un tren enlazamos elementos para construir una lista enlazada 101
CAPÍTULO IX
Utilizando mapas para acceder rápidamente a los datos con tablas hash 119
CAPÍTULO X
Desde la raíz hasta las hojas, entendiendo los árboles desde otro punto de vista 135
CAPÍTULO XI
Pintando nodos de color rojo y negro, ¡conozcamos los árboles rojinegros! 173
CAPÍTULO XII
Simplifiquemos las cosas usando montones, ¡montículos para todo! 187
CAPÍTULO XIII
Conectando puntos. Cómo formar una red conocida como grafo 199
CAPÍTULO XIV
Técnicas de diseño de algoritmos, intentando desarrollar algoritmos eficientes 237
Introducción
El contenido de este libro se enfoca en dos ejes temáticos troncales del área programación fuertemen-
te relacionados, algoritmos y estructuras de datos, está orientado a lectores que tengan conocimientos 
básicos de programación –que se darán por sentado en este libro– y destinado principalmente para 
estudiantes de carreras informáticas. Ambos son partes de los tres pilares fundamentales del desa-
rrollo de sistemas: diseño, programación –o desarrollo– y almacenamiento. Dentro del segundo de 
estos pilares es donde tienen mayor relevancia los algoritmos y las estructuras de datos.
Es un punto crítico elegir la estructura de datos apropiada que almacenará la información en memo-
ria principal de acuerdo al dominio del problema a tratar, para que los algoritmos de búsqueda y orde-
namiento que se utilicen sean eficientes, sobre todo cuando el volumen de datos es grande y es necesa-
rio que el sistema responda en buen tiempo. Respecto al tercero de los pilares, –el almacenamiento–, 
los distintos motores de bases de datos utilizan diversas estructuras de datos para su administración 
interna, como árboles para hacer consultas e índices hash que permiten optimizar las consultas, el 
acceso a memoria secundaria y también a los datos, en el caso de las bases de datos claves-valor.
Es fundamental conocer estos aspectos para poder determinar con buen criterio la elección de una 
base de datos para el desarrollo de un sistema. O en el caso que la persistencia sea en un archivo, se 
deben conocer los algoritmos y estructuras de datos que permiten administrar, buscar y ordenar es-
tos datos en un tiempo aceptable de respuesta, siempre esperando que sea el menor posible, ya que 
en estos casos es crucial el tiempo de acceso a la memoria secundaria –es decir el acceso al disco–.
Por su parte el pilar de diseño o ingeniería de software es esencial para que el desarrollo del siste-
ma sea exitoso. Para esto, además de los aspectos mencionados, se requiere una visión global del 
sistema, como también de sus requerimientos, arquitectura y tecnologías que se utilizarán para el 
desarrollo del mismo al momento de modelarlo. Las estructuras de datos son fundamentales para 
establecer el nexo que permite intercambiar información entre las capas de frontend –o presenta-
ción– y la de backend –o persistencia–.
Respecto a los algoritmos, existen diversos factores que condicionan su programación: eficiencia 
(referido a las técnicas, tiempos y recursos utilizados), forma de estructurarlo o escribirlo (referido 
a la tabulación, organización y legibilidad del código), estilo de escritura o nomenclatura utilizada, 
uso de buenas prácticas y documentación dentro del código. A excepción del primero, el resto se 
puede controlar con la ayuda de un Entorno de Desarrollo Integrado (IDE) y un poco de experiencia 
como desarrollador. En relación a la eficiencia de los algoritmos, es necesario comprender cómo 
poder analizar y medir dicha eficiencia para poder comparar con criterio algoritmos similares que 
utilicen distintas técnicas, es decir, que sirvan para resolver un mismo problema. Estos contenidos 
se abordarán en detalle en los capítulos II, III, IV y XIV.
En cuanto a las estructuras de datos cabe señalar que son recursos o herramientas disponibles en 
todo lenguaje de programación. Permiten almacenar o agrupar un conjunto de elementos o datos. 
Muchas de estas estructuras de datos son utilizadas internamente por los distintos tipos de bases de 
datos para gestionar la información (que es la manera más utilizada para almacenar información 
desde la década de 1980) y por los sistemas operativos para gestionar los distintos recursos de una 
computadora. Es importante entender que no existe una estructura de datos mejor que las demás, 
cada una tiene sus ventajas y desventajas. Por este motivo, es imprescindible que el programador 
comprenda cómo funciona cada una y cuándo es conveniente utilizarlas para sacarles mayor pro-
vecho. En ocasiones, suele ocurrir que es necesario trabajar con más de una estructura de datos a la 
vez, combinándolas en un mismo algoritmo. Además nos sirven como nexo entre los datos dentro 
de nuestro algoritmo (en memoria principal) y los datos almacenados físicamente en disco (ya sea 
en una base de datos o en un archivo). Desde el capítulo V al XIII se presentarán y analizarán en 
detalle las distintas estructuras de datos y cómo se modelan.
En resumen, el énfasis está puesto en comprender cómo funcionan los algoritmos y estructuras de 
datos, con el objetivo de poder implementar todos los conceptos planteados en cada capítulo. De 
esta manera, el lector podrá llevar a la práctica los conceptos teóricos y fortalecer sus habilidades 
de programador, adquirir experiencia para decidir con criterio cómo y cuándo utilizar los distintos 
tipos de algoritmos y estructuras de datos. Para ello, al final de cada capítulo se facilitará una guía 
de ejercicios para comenzar a incorporar estos recursos y desarrollar el pensamiento algorítmico.