grafos

PRÓLOGO

La algoritmia es uno de los pilares de la programación y su relevancia se muestra
en el desarrollo de cualquier aplicación, más allá de la mera construcción de
programas. Este es un libro introductorio sobre análisis y diseño de algoritmos que
pretende exponer al lector las técnicas básicas para su diseño e implementación, así
como presentar unas herramientas que le permitan medirsu efectividad y
eficiencia.
Objetivos
Si bien es cierto que es amplia la bibliografía existente sobre algoritmia, no es
menos cierto que casi toda obedece a un mismo esquema general. Se presentan las
técnicas básicas de resolución de problemas en base a unos ejemplos clásicos, para
después dejar propuesta al lector una colección de problemas sobre cada tema. Pero
ocurre que casi todos losautores proponen los mismos problemas y pocos llegan a
resolverlos, lo que hace que los estudiantes de algoritmos pierdan de alguna forma
las enseñanzas que se extraen de ellos.
Esto no sería importante si los problemas propuestos fueran meramente
ejercicios que repiten fielmente los métodos enseñados. Sin embargo éste no es el
caso, pues cada ejercicio proporciona un nuevo enfoque paraabordar los problemas
o permite combinar algunas de las técnicas, lo que enriquece el estudio de los
métodos y algoritmos tratados.
Por otro lado, nuestra experiencia en la enseñanza de las asignaturas
relacionadas con la algoritmia nos ha hecho ver la importancia que tiene el
disponer de una metodología de diseño que permita abordar la resolución de los
problemas de una forma unificada ycoherente.
Esta obra nace con la intención de llenar un vacío en la bibliografía sobre estos
temas. En primer lugar ofreciendo un método de diseño general aplicable a cada
una de las técnicas, y en segundo lugar proporcionando una amplia selección de
ejemplos y problemas resueltos. A lo largo de todo el texto se ha prestado una
atención especial a la integración del diseño de los algoritmos con elanálisis de su
eficiencia.
Organización del texto
El libro está estructurado en siete capítulos. El primero, la complejidad de los
algoritmos, está dedicado a analizar algoritmos desde el punto de vista de su
eficiencia. Cubre tanto el cálculo del número de operaciones elementales de los
programas como el estudio de sus casos peor, mejor y medio y las cotas asintóticas
de crecimiento. Estecapítulo también comprende la resolución de ecuaciones en
recurrencia, que permiten determinar la eficiencia de los algoritmos recursivos.

VIII

TÉCNICAS DE DISEÑO DE ALGORITMOS

En el segundo capítulo presentamos los principales algoritmos de ordenación.
Debido a su extensión y a la importancia que en otros ámbitos adquiere el
problema de ordenación hemos decidido dedicarle un capítuloindependiente, aún a
sabiendas de que cualquier algoritmo de ordenación obedece a alguna técnica de
diseño, y por tanto podía haberse estudiado en un capítulo posterior.
Por la naturaleza de la materia tratada en estos dos primeros capítulos,
decidimos darle una estructura al estilo de la bibliografía usual. La mayoría de los
textos presentan los conceptos teóricos básicos, desarrollan unnúmero reducido de
problemas ya clásicos, y dejan al lector una amplia colección de problemas sin
resolver. Sin embargo, no hemos querido quedarnos solamente ahí. Uno de
nuestros objetivos ha sido que nada debe quedar propuesto y no resuelto, y por ello
ofrecemos la solución a todos los problemas planteados. Esto permite ejercitar los
conocimientos adquiridos, aclarar algunos de los conceptosestudiados y plantear
variaciones sobre los métodos.
Los capítulos tercero al séptimo describen y desarrollan las principales técnicas
de diseño de algoritmos. Estos cinco capítulos forman el núcleo principal del libro,
y están estructurados de la misma forma. Cada tema comienza con una breve
introducción teórica en la que se exponen los fundamentos de la técnica tratada y el
tipo de...