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


| Presentación

Al-Khorezmi nunca pensó que su apellido, que significa "un nativo de Khorezmi", sería el origen de unas palabras más importantes que él mismo, como álgebra, logaritmo y algoritmo. Gracias a este poco conocido matemático árabe del siglo IX, hoy en día tenemos conocimiento de conceptos tan básicos como el número cero, que procede de la India, o de la mayor parte de las matemáticas desarrolladas en Grecia.

¿Y sobre algoritmos? Los algoritmos y las estructuras de datos forman el núcleo de la ciencia de computación, siendo los componentes básicos de cualquier software. Al mismo tiempo, el aprendizaje de la programación está íntimamente ligado a los algoritmos, ya que un algoritmo es la abstracción de un programa. Por lo tanto, aprender algoritmos es crucial para cualquier persona que desee desarrollar software de calidad.

Los paradigmas de programación están asociados de forma natural a las técnicas de diseño y las asignaturas introductorias de informática son, generalmente, asignaturas de introducción a los algoritmos. Inicialmente, el concepto de algoritmo se apoya en las técnicas básicas de programación. Cuando la complejidad de los problemas y su análisis se hacen importantes, como en el caso de este libro, el estudio de algoritmos requiere lógica, matemática discreta y fundamentos teóricos como la teoría de autómatas y lenguajes formales.

Pero aprender algoritmos no es una tarea sencilla, se deberá tener una buena combinación de conocimientos matemáticos y de sentido común. Citando a Knuth: la mejor teoría está inspirada en la práctica y la mejor práctica está inspirada en la teoría. El equilibrio entre teoría y práctica es siempre una tarea difícil.

Este libro, en su segunda edición, muestra ese equilibrio entre teoría y práctica. Los tres primeros capítulos divulgan las bases necesarias para realizar un buen diseño de algoritmos: técnicas de diseóo, herramientas de análisis y estructuras de datos elementales. En particular, el capítulo 2, nuevo en esta edición, cubre los principales paradigmas del diseño de algortimos que antes se utilizaban en otros capítulos para resolver diferentes problemas. Para diseñar algoritmos de manera adecuada es esencial conocer paradigmas tales como inducción, recursividad, divide y vencer´s o la utilización de heurísticas.

Los siguientes tres capítulos cubren los dos problemas algorítmicos más importantes: ordenación y búsqueda. En ambos casos, se han considerado versiones para memoria principal y memoria secundaria. La ordenación y la búsqueda en memoria secundaria son los principales pilares de las bases de datos.

Los dos capítulos que siguen cubren dos tipos de estructuras de datos muy importantes: grafos y cadenas. Los grafos aparecen en muchas aplicaciones prácticas. Por otro lado, la búsqueda y la compresión de cadenas de caracteres forman la base para el proceso de documentos y, últimamente, para los motores de búsqueda en la Web.

El último capítulo cubre problemas de gran complejidad computacional, en los que todos los algoritmos conocidos requieren un tiempo exponencial. Una alternativa a este problema es encontrar soluciones con un error limitado, obteniendo los llamados algoritmos aproximados. De esta manera se intercambia la calidad de la respuesta por un menor tiempo de proceso.

Estos tres últimos capítulos también son nuevos, ampliando el ámbito de este libro. Además se han incluido nuevos ejercicios, muchos con soluciones, convirtiendo el contenido en un recurso didáctico mucho más valioso, un verdadero libro de texto.

Doy fe que este libro es un clásico en Brasil. Esta nueva edición va a fortalecer esa posición para el beneficio de todos los profesores y estudiantes relacionados con el mundo de los algoritmos.

Ricardo Baeza-Yates
Santiago, Chile
Diciembre de 2003


Produzido por Tambor Comunicação