PDF de programación - PRÓLOGO

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 medir su 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 los autores 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 para abordar 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 y coherente.
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 el aná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. Este capí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

los pormenores de su diseño y

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ítulo independiente, 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 un nú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 conceptos estudiados 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 problemas que resuelve. En segundo lugar se presenta un esquema o
método general de funcionamiento de los algoritmos que produce dicha técnica. A
continuación se desarrolla una colección de problemas que permiten mostrar las
distintas formas de aplicación de la técnica estudiada. Conforme se avanza en los
problemas se discuten
los detalles de
implementación, algo normalmente muy descuidado por otros autores pero que sin
embargo nosotros consideramos fundamental. Por eso hemos desarrollado los
ejemplos hasta el final, tratando de no dejar ningún cabo suelto; nuestra
experiencia nos muestra que tras un esquema de resolución aparentemente sencillo
se pueden ocultar serios problemas de implementación a la hora de codificarlo. Y
un problema no está resuelto hasta que el algoritmo que lo soluciona no finaliza su
ejecución, y en un tiempo razonable.
Disponer de una amplia gama de problemas permite al lector observar de forma
muy completa el funcionamiento de cada una de las técnicas, sus ventajas e
inconvenientes, y lo que es más importante, a través de estos ejemplos es posible
introducir de manera natural y justificada los conceptos más relevantes de cada
técnica.
Otra ventaja que ofrece este trabajo frente a otros textos existentes es la
utilización de un lenguaje de programación concreto, en este caso Modula-2.
Aunque es cierto que el uso de pseudo-código permite la independencia de los
algoritmos desarrollados frente a una máquina o compilador concreto, desde
nuestro punto de vista se pierden dos aspectos fundamentales. Por un lado el uso de
un pseudo-código puede ocultar algunos detalles de implementación que luego
complican la codificación de los programas. Por otro lado, el uso de un lenguaje
determinado permite ejecutar los programas obtenidos y así corroborar los
resultados previamente calculados de manera teórica, algo que no podemos olvidar
en una ciencia aplicada como la algoritmia.
En particular, el uso de Modula-2 se debe a varias razones. Si bien es cierto que
cualquier lenguaje imperativo podría ser un candidato válido, sus características en
cuanto a modularidad, ocultación y sistema de tipos permiten realizar diseños
sencillos y robustos, necesarios para representar con claridad y de forma precisa la

PRÓLOGO

IX

estructura de los algoritmos. Además, los programas resultantes son de fácil
comprensión y no plantean serias dificultades para ser traducidos a otros lenguajes
imperativos como pueden ser Pascal o C. Por otro lado, también hemos tenido en
cuenta que Modula-2 es un lenguaje ampliamente utilizado para la enseñanza de la
programación, especialmente en el ámbito universitario.

Recomendaciones de uso
Hemos pretendido que este libro sea autocontenido, al menos en lo que
concierne a las materias de algoritmia. Sin embargo, no hemos creído necesario
introducir en él conceptos básicos de otras materias como el análisis matemático o
el álgebra, que se utilizan a lo largo del texto. Por otro lado, también se supone que
el lector sabe programar con cierta soltura utilizando un lenguaje imperativo y que
conoce las estructuras y tipos de datos básicos.
El diseño del libro se ha realizado de manera que pueda ser utilizado como base
para cualquiera de las asignaturas introductorias a la algoritmia. De ahí su
estructura y organización, así como la didáctica con la que se desarrollan los temas.
De esta forma, y para un mejor aprovechamiento de la obra, nos gustaría hacer
algunas recomendaciones en cuanto a su uso.
Primero, el alumno ha de asegurarse de que ha comprendido y asimilado los
conceptos teóricos con los que se inicia cada uno de los capítulos. Una vez
comprendido el funcionamiento de la técnica concreta puede comenzar intentando
los problemas propuestos en el capítulo correspondiente. Si un problema no sale,
debe intentarse otro y volver al primero más tarde. Quizá entonces se consiga dar
con la clave para su solución. Tampoco ha de desanimarse con los problemas
complicados. Tan importante es el hecho de encontrar la solución de un problema,
como el camino recorrido hasta encontrarla .
Se recomienda estudiar las técnicas de diseño siguiendo un orden similar al
utilizado en el libro. Este orden no es caprichoso, sino que recorre las distintas
técnicas de acuerdo al tipo de problemas que resuelven y a la complejidad de los
algoritmos resultantes. Ahora bien, los problemas no están ordenados respecto a su
dificultad, así que el alumno es libre de escoger el orden en el que los intenta. Sin
embargo, y con el objeto de racionalizar el trabajo y la comprensión de lo expuesto,
la solución de cada ejercicio va precedida por una clave que indica su clasificación
en cuanto a grado de dificultad:



☺


Problema fácil. Su resolución no debe plantear ninguna dificultad.
Problema de nivel medio. Su resolución no es inmediata, pero puede
solucionarse tras un poco de reflexión.

Problema interesante o bien que supone cierta dificultad. Presenta algún

concepto nuevo o una variación sobre la técnica en cuestión.

Hay que decir que esta clasificación no tiene un carácter absoluto en todo el
libro, sino que es relativa a cada una de las técnicas cubiertas por este trabajo, y al
nivel de conocimientos que se le supone o exige a los alumnos en cada uno de los
temas.
Como última recomendación en cuanto al uso de esta obra, mencionaremos que
es aconsejable el estudio de otros t