Diseño de Algoritmos con Implementaciones en Pascal y C

Um projeto de Nivio Ziviani, Ph.D. Professor Emérito do Departamento de Ciência da Computação Universidade Federal de Minas Gerais

Una traducción de Joaquín Adiego

Editora: Pioneira Thomson


» Prefacio

Este libro presenta una introducción al estudio de los algoritmos computacionales. Las principales técnicas de diseño de algoritmos se muestran mediante una explicación detallada de algoritmos y estructuras de datos para utilizar el ordenador eficientemente. Estas explicaciones se dan de la manera más sencilla posible, pero sin perder la profundidad ni el rigor matemático.

En general, el contenido está enfocado para ser utilizado como libro de texto en asignaturas que traten sobre algoritmos y estructuras de datos. Pero como se presentan muchas implentaciones prácticas de algortimos, el texto también es útil para profesionales que trabajen en el desarrollo de sistemas computacionales y de aplicaciones informáticas. Los algoritmos se elaboran mediante refinamientos sucesivos hasta obtener una implementación en lenguaje Pascal, lo que permite que cualquier persona con un mínimo de experiencia en programación pueda interpretar el código.

Contenido

El libro presenta las principales técnicas utilizadas en la implementación de estructuras de datos y algoritmos para la ordenación y búsqueda en memoria pricipal y secundaria, grafos, procesamiento de cadenas de caracteres y problemas NP-completo y heurísticas. La temática está agrupada en nueve capítulos, cada uno con el siguiente contenido: (i) concepto de algoritmo, estructura de datos y tipo abstracto de datos, medida del tiempo de ejecución de un programa, técnicas de análisis de ejecución de algortimos, el lenguaje Pascal; (ii) paradigmas en el diseño de algoritmos; (iii) estructura de datos básicas: listas lineales, pilas y colas; (iv) métodos de ordenación en memoria principal\/: por inserción, por selección, shellsort, quicksort, heapsort y ordenación parcial; (v) métodos de búsqueda en memoria principal: búsqueda secuencial, búsqueda binaria, árboles de búsqueda, hashing universal y hashing perfecto; (vi) métodos de búsqueda en memoria secundaria: secuencial indexada y árboles B; (vii) algortimos en grafos: representación, búsqueda en profundidad, búsqueda en anchura, ordenación topológica, componentes fuertemente conectados, árbol generador mínimo y caminos más cortos; (viii) proceso de cadenas de caracteres: búsqueda exacta y aproximada de patrones, compresión de textos en lenguaje natural; (ix) problemas NP-completo: clases NP-difícil, transformación polinomial, teorema de Cook, algortimos exponenciales empleando prueba y error, heurísticas y algortimos aproximados para el problema del viajante.

El lenguaje de programación que se ha utilizado para mostrar el refinamiento final de los algoritmos presentados es Pascal. La ventaja de utilizar Pascal es que permite entender los programas con facilidad y facilita su traducción a otros lenguajes de programación. Además, todos los algortimos implementados en lenguaje Pascal también se encuentran implementados en lenguaje C. Cada programa en Pascal que aparece en un capítulo tiene su correspondiente programa en C en el Apéndice correspondiente.

Las palabras o frases que aparecen en negrita en el texto se encuentran en el índice analítico. Lo que permite utilizar el libro como si se tratara de hipertexto, posibilitando una lectura no lineal basada en asociaciones de ideas y conceptos. Las palabras o frases en negrita actúan como puertas virtuales que abren caminos para otras informaciones.

Al Profesor

El material que se presenta es adecuado para ser utilizado como libro de texto en cursos de grado, postgrado y ampliación de formación para programadores en el área de Algortimos y Estructuras de Datos. Es recomendable que el estudiante haya realizado un curso previo de programación (o tener experiencia equivalente) en un lenguaje de alto nivel, como Pascal o C, así como poseer conocimientos sobre el manejo de sistemas de computación.

Se han utilizado versiones preliminares de este libro en asignaturas de la Universidad Federal de Minas Gerais, a saber:

  • Algoritmos y Estructuras de Datos I, asignatura presente en las Ingenierías de Informática, Control y Automática, Eléctrica, Electónica y Mecánica, con una carga horaria de 60 horas y un semestre de duración. Además del estudio de un primer lenguaje de programación, habitualmente Pascal o Java, también se estudian los tipos abstractos de datos; introducción al análisis de algoritmos; inducción matemática; algoritmos recursivos; listas lineales, pilas y colas.
  • Algoritmos y Estructuras de Datos II, asignatura presente en las Ingenierías de Informática, Control y Automática, Eléctrica, Electónica y Mecánica, con una carga horaria de 60 horas y un semestre de duración. Trata sobre los siguientes temas: introducción al análisis de algoritmos; ordenación en memoria principal: selección directa, inserción directa, shellsort, quicksort, heapsort, mergesort, radixsort y ordenación parcial; búsqueda en memoria principal: secuencial, binaria y transformación de clave (hashing); árboles de búsqueda: sin balancear, balanceados, tries y patricia; ordenación externa; búsqueda en memoria secundaria: memoria virtual, indexado secuencial y árboles B.
  • Algoritmos y Estructuras de Datos III, asignatura presente en las Ingenierías de Informática, Control y Automática, Eléctrica, Electónica y Mecánica, con una carga horaria de 60 horas y un semestre de duración. Trata sobre los siguientes temas: estudio avanzado del análisis y diseño de algoritmos; paradigmas de diseño de algoritmos; algoritmos en grafos; problemas NP-completo, heurísticas y algoritmos aproximados; procesamiento de cadenas de caracteres.
  • Diseño y Análisis de Algoritmos, asignatura ofertada entre los cursos de maestría y doctorado en Ciencias de Computación, con una carga horaria de 60 horas. Trata sobre los siguientes temas: técnicas de análisis de algoritmos; paradigmas de diseño de algoritmos; algoritmos en grafos; problemas NP-completo, heurísticas y algoritmos aproximados; procesamiento de cadenas de caracteres; algoritmos paralelos.

Habitualmente, la didactica de algoritmos se divide en temas o problemas-tipo. En este libro ocurre lo mismo. Sin embargo, un curso avanzado sobre diseño de algoritmos se puede dividir en paradigmas de diseño de algoritmos, en lugar de dividirlo en temas o problemas-tipo. Si este fura el caso, el Capítulo 2 se puede utilizar como guía. Este cambio en la forma de enseñar puede conseguir mejores diseños y realza la importancia del análisis de algortimos.

Al final de cada capítulo se incluyen ejercicios y el Apéndice K contiene las soluciones para la mayor parte de los ejercicios propuestos. Algunos ejercicios son del tipo respuestas cortas, para poner a prueba los conocimientos básicos expuestos en la parte teórica. Para otros ejercicios se debe desarrollar una respuesta más elaborada, pudiendo exigir al lector un trabajo de varios días y realizarlo en casa o en el laboratorio. Por lo tanto, los ejercicios propuestos se pueden utilizar en pruebas y trabajos prácticos para la evaluación del aprendizaje.

Al final de cada capítulo también se incluye un breve comentario sobre la literatura relacionada, indicando las principales referencias bibliográficas para cada tema, sólo se muestra una pequeña descripción de la bibliografía y se intentan comentar las referencias más significativas en cada momento.

Para cada capítulo se encuentran disponibles un conjunto de transparencias pensadas para ser utilizadas por el profesor en el aula. Cada conjunto de transparencias sigue fielmente el texto correspondiente del libro, y cuyo formato es el de una transparencia por página. Para facilitar la distribución de copias impresas a los alumnos existe un conjunto equivalente que contiene cuatro transparencias por página. Las transparencias están en formato PostScript y PDF, de manera que pueden ser proyectadas directamente utilizando un navegador (browser), con el uso de un visualizador de ficheros PostScript o con un visualizador de ficheros PDF. Las transparencias se pueden descargar directamente en la sección correspondiente de desde este mismo sitio.

Al Estudiante

El estudio del comportamiento de los algoritmos tiene un papel decisivo en el diseño de algoritmos eficientes. Las técnicas de análisis de algoritmos se consideran como una parte integral del proceso moderno para la resolución de problemas, permitiendo escoger, de forma racional, uno entre los diferentes algoritmos alternativos que pueden estar disponibles para un mismo fin. Por eso en este libro se muestra información relacionada sobre las características de ejecución de cada algoritmo que se presenta. Los algoritmos se desarrollan mediante refinamientos sucesivos, paso a paso, procurando hacer que los más difíciles se puedan entender con facilidad. Además, se le ha dado un gran énfasis a los principales paradigmas de diseño de algoritmos. El deseo del autor es que este libro proporcione al alumno una iniciación agradable en el área de análisis y diseño de algoritmos.

En relación a los prerrequisitos necesarios para la lectura de este libro, lo ideal es tener alguna experiencia en programación de ordenadores. En particular, es necesario entender los procesos recursivos y saber trabajar con estructuras de datos sencillas utilizando vectores y punteros. La parte matemática empleada para presentar los resultados analíticos es autocontenida y exige muy poco conocimiento matemático para que pueda ser entendida. Algunas partes del texto requieren de pequeños conocimientos de cálculo elemental y matemática discreta.

Al Profesional

Este texto también se puede utilizar como manual para programadores que ya estén familiarizados con el tema, pues se presentan implementaciones de algoritmos de uso común. La mayoría de los algoritmos que se muestran tienen una gran aplicación práctica y a lo largo del texto se discuten diferentes aspectos relacionados con la implementación. Para muchos problemas, se muestran varias soluciones alternativas y en muchas ocasiones existe un estudio comparativo del comportamimento de los algoritmos implementados para cada alternativa.

Los algoritmos propuestos se han implementado completamente en Pascal y C, y las operaciones relacionadas se describen a través de ejemplos de ejecución. Los códigos en Pascal y C se pueden obtener directamente en la sección correspondiente de este mismo sitio, en el caso de encontrarnos con procedimientos en Pascal y C éstos están acompañados de un programa principal que permite ejecutar una pequeña prueba de forma inmediata.

Cambios en la Segunda Edición

Se han realizado muchos cambios respecto a la primera edición. Tan sólo con comparar los índices se puede ver que se han introducido varias secciones nuevas. Sin embargo, el mayor cambio estriba en la incorporación de cuatro capítulos nuevos. Otro cambio significativo está relacionado con la adición de ejercicios nuevos, así como la solución de una parte de los ejercicios propuestos.

No obstante, el nuevo material incorporado a la segunda edición mantiene todas las características de la primera edición, que son las de presentar las principales técnicas de diseño de algoritmos y estructuras de datos, intentando que las explicaciones sean lo más sencillas posible manteniendo además la profundidad y el rigor matemático.

A continuación se presenta un resumen de las principales modificaciones en esta segunda edición:

  • Se han corregido adecuadamente todos los errores de los que se tenía constancia.
  • Se han añadido cuatro capítulos nuevos:
    • Capítulo 2, que presenta los paradigmas de diseño de algoritmos.
    • Capítulo 7, que presenta algortimos en grafos. Los algoritmos usan operadores de un tipo abstracto de datos, lo permite implementarlos de manera independiente a la forma de representar el grafo.
    • Capítulo 8, que presenta algoritmos eficientes para el emparejamiento exacto y aproximado de cadenas de caracteres, así como algoritmos de compresión de texto en lenguaje natural.
    • Capítulo 9, que está dedicado al estudio de la teoría de complejidad, cubriendo problemas NP-completo, heurísticas y algoritmos aproximados.
  • Se han ampliado algunos capítulos de la primera edición con secciones nuevas que tratan las siguientes cuestiones:
    • Ordenación parcial (Sección 4.1.7).
    • Mezcla polifásica (Sección 4.2.4).
    • Quicksort externo (Sección 4.2.5).
    • Hashing perfecto (Sección 5.5.4).
  • Se han ampliado algunas secciones de la primera edición con contenidos nuevos que hablan de las siguientes cuestiones:
    • Paso de parámetros (Sección 1.5).
    • Notaciones Θ, o, &omega (Sección 1.3.1).
    • Nuevos operadores sobre colas de prioridad utilizando montículos (Sección 4.1.5).
    • Nuevo algoritmo para obtener la función hash universal (Sección 5.5).
  • Se han añadido decenas de problemas nuevos.
  • Un apéndice que contiene la solución de muchos de los problemas propuestos al final de cada capítulo.
  • Practicamente todas las secciones han sufrido modificaciones de edición para corregir, simplificar o clarificar explicaciones, algoritmos, implementaciones en Pascal y C, y rehacer figuras por motivos de estandarización.

Agradecimientos de la Primera Edición

La versión inicial de este texto se escribió con la intención de ser utilizada en el curso Estructuras de Datos y Algoritmos de la I Escuela Brasileño-Argentina de Informática en febrero de 1986, publicado por la Editorial de Unicamp y con el título Projeto de Algoritmos e Estruturas de Dados. Me gustaría agradecer a Carlos José Pereira de Lucena y a Routo Terada por acordarse de mi para participar en la I Escuela Brasileño-Argentina de Informática que constituyó la simiente del desarrollo de este texto. Me gustaría agradecer a Cilio Rosa Ziviani, Cleber Hostalácio de Melo, José Monteiro da Mata, Lilia Tavares Mascarenhas, Luiz Carlos de Abreu Albuquerque, Regina Helena Bastos Cabral y a Rosângela Fernandes sus contribuciones para la primera edición del texto.

Muchos amigos y colegas me ayudaron en la elaboración de este libro. Agradezco a todos la ayuda prestada y las críticas constructivas realizadas. El Departamente de las Ciencias de Computación de la Universidad Federal de Minas Gerais me ha proporcionado un excelente ambiente de trabajo. Mis alumnos de extensión, grado, especialización y postgrado, especialmente los alumnos de las asignaturas Técnicas de de Programación, Algoritmos y Estructuras de Datos y Diseño y Análisis de Algoritmos contribuyeron significativamente.

Se han corregido varios errores detectados como consecuencia de una lectura cuidadosa llevada a cabo por varias personas, especialmente Alberto Henrique Frade Laender, Eduardo Fernandes Barbosa, José Nagib Cotrim &Acute;rabe, Márcio Luiz Bunte de Carvalho, Osvaldo Sérgio Farhat de Carvalho, Roberto Márcio Ferreira de Souza y Virgílio Augusto Fernandes Almeida, a los cuales me gustaría expresar mi agradecimiento. También me gustaría expresar mi más sincero agradecimiento a Cristina Duarte Murta por la lectura crítica de todo el texto, por probar los programas en Pascal y por la ejecución de lso programas, que permitió realizar un estudio comparativo de los algoritmos de ordenación.

La versión en C de los algoritmos existe gracias al paciente trabajo de traducción de los programas en Pascal realizado por Maurício Antônio de Castro Lima y Wagner Toledo Corrêa, llevado a cabo con la ayuda del programa p2c para la tradicción automática de programas en Pascal a programas en C, desarrollado por Dave Gillespie, del California Institute of Technology, EUA. El formato del libro se ha realizado con LaTeX, un conjunto de macros para TeX. Un agradecimiento muy especial para Márcio Luiz Bunte de Carvalho por la inmensa ayuda durante todo el proceso de formateo del texto, incluyendo la creación de entornos especiales en LaTeX para el presente texto, contando con la colaboración en esta etapa de Murilo Silva Monteiro. Un agradecimiento muy especial para Maria, esposa y compañera, Patricia y Paula,nuestras hijas.

Agradecimientos de la Segunda Edición

Quiero agradecer a los amigos y colegas que han contribuido a la calidad de este libro, en especial a Alberto Henrique Frade Laender, Antônio Alfredo Loureiro, Berthier Ribeiro-Neto, Dorgival Olavo Guedes Neto, Gonzalo Navarro, Jussara Marques de Almeida, Letícia Simonetti Garcia, Márcio Luiz Bunte de Carvalho, Mariza Bigonha, Renato Antonio Celso Ferreira, Roberto da Silva Bigonha y Virgilio Augusto Fernandes Almeida. A Ricardo Baeza-Yates le agradezco la sugerencia de escribir el capítulo sobre los paradigmas de diseño de algoritmos y las líneas de presentación del libro. Un agradecimiento especial para Wagner Meira Jr. por las diferentes sugerencias y por la primera lectura crítica de todo lo que se escribía.

De todos los profesores que me enseñaron el mundo de los algoritmos, quiero agradecer en particular a Antônio Luz Furtado, Frank Tompa, Gaston Gonnet, Ian Munro y Pal Larson.

Esta segunda edición se ha realizado en un ambiente excelente para la elaboración de un libro de texto, el departamento de Ciencia de Computación de la Universidad Federal de Minas Gerais. Los estudiantes de grado y postgrado han contribuido significativamente y tienen mi agradecimiento. De entre los profesores de las asignaturas Algoritmos y Estructuras de Datos II, Algortimos y Estructuras de Datos III y Diseño y Análisis de Algoritmos, quiero agradecer en particular a Bruno Augusto Vivas e Pôssas, Claudine Santos Badue, Cláudio Ricardo Guimarães Sant'Ana, Cristina Duarte Murta, Daniel Tavares de Castro, Edleno Silva de Moura, Fabrício Benevenuto de Souza, Helvécio Guimarães Ribeiro, Ilmério Reis, Maria Cláudia Guimarães Guatimosim, Maria Dalva Resende, Patricia Seno Fusaro, Robert Pereira Pinto, Rodrigo Lima Carceroni y Sérgio Augusto ávila Maria.

También tienen mi agradecimiento los estudiantes de post-grado que me ayudaron en la elaboración de la presente segunda edición, entre los que se encuentran Adriano César Machado Pereira, Bruno Dias Abrahão, Bruno Diniz de Paula, Cristiane Amorim Mendes, Fernando Caixeta Sanches, Flávia Perigrinelli Ribeiro, Goedson Teixeira Paixão, Gustavo Menezes Siqueira, Ligiane Alves de Souza, Márcio Drumond Araújo, Pavel Calado, Patricia Correia Saraiva, Ramurti Barbosa y Wesley Dias Maciel. Un agradecimiento especial para los siguientes estudiantes: Bruno Augusto Vivas e Pôssas, por el trabajo realizado con las respuestas de los ejercicios; Charles Ornelas Almeida, por la creación del estilo de LaTeX, el diseño de todas las figuras del libro, formateo de todo el texto, prueba de programas y su participación en la sección de hashing perfecto; Davi de Castro Reis, por el estudio comparativo de los algoritmos de ordenación parcial; Fabiano Cupertino Botelho, por la redacción de la sección de Quicksort externo, su participación en la redacción y creación de los programas sobre compresión de texto y su trabajo en las respuestas de los ejercicios; Juliano Palmieri, por su participación en la redacción y creación de los programas de compresión de texto; Leonardo Henrique Machado, por su soporte computacional y Thierson Couto Rosa, por la traducción de los programas a lenguaje C y su trabajo en las respuestas de los ejercicios.

Entre las personas que gentilmente dieron a conocer errores en la primera edición quisiera agradecer a André Gustavo dos Santos, Bruno Muller Júnior, Daniel Pablo Herschel, Daniel Walter Berns, Frederico Paiva Quintão, Gustavo Cota Guimarães Mendonça, Héctor Alejandro Virgolini, Ichiro Aoki, Juan Luis Almará, Kêmio de Oliveira Couto, Klaus de Geus, Luis Joaquin Vazquez, Marco Aurélio de Souza Mendes, Maria Gabriela Maidana y Pablo Velo.

Asimismo quiero citar al personal del Hotel Aquário, en la playa de Ubu, Espírito Santo, en donde estuve alojado varios periodos de una semana durante el año 2003 para trabajar en el libro, a quien le agradezco el trato tan cariñoso que recibí. Agradezco a Gabriela da Silva Conceição la divulgación de esta edición durante el Congreso de la Sociedad Brasileña de Computación de 2003. Alexandre Guimarães Dias, Geraldo Felício de Oliveira, Gustavo Moura de Oliveira y Orlando Rodrigues da Silva encuadernaron varias versiones preliminares del libro, tienen mi agradecimiento por ello.

Un agradecimiento especial para Carlos Eduardo Corradi Fonseca, por su forma de ser y por su competencia y brillantez en el ejercicio profesional.

Ha sido importante el apoyo recibido por parte del CNPq - Conselho Nacional de Desenvolvimento Científico e Tecnológico e da FINEP - Financiadora de Estudos e Projetos, mediante los siguiente proyectos: PRONEX/FINEP/CNPq/SIAM - Sistemas de Información en Entornos de Computación Móviles, proceso CNPq 00418.00/00; CNPq/CT-INFO/GERINDO - Adminstración y Recuperación de Información en Documentos, proceso CNPq 55.2087/02-5 y Bolsa de investigación - Entornos para Recuperación de Información en el WWW, proceso CNPq 520.916/94-8.

Trabajar con Pioneira Thomson ha sido un placer. Desde los primeros contactos, la divulgación de la segunda edición, la fase de revisión y formateo del texto hasta la impresión final del libro, siempre he tenido un soporte ágil, competente y profesional.

Nivio Ziviani
Belo Horizonte
Diciembre de 2003


Produzido por Tambor Comunicação