Este libro fue escrito para un curso completo sobre algoritmos; cuenta con suficiente material como
para adoptar diversas orientaciones.
El objetivo del mismo incluye tres aspectos. Pretende enseñar algoritmos que se aplicarán en
la resolución de problemas reales que se presentan a menudo en aplicaciones para computadora,
enseñar principios y técnicas básicos de complejidad computacional (comportamiento de peor
caso y caso promedio, consumo de espacio y cotas inferiores de la complejidad de un problema),
e introducir las áreas de los problemas NP-completos y los algoritmos paralelos.
Otra de las metas del libro, no menos importante que enseñar los temas que contiene, es desarrollar
en el lector el hábito de siempre responder a un algoritmo nuevo con las preguntas: ¿Qué
tan bueno es? ¿Hay una manera mejor? Por ello, en lugar de presentar una serie de algoritmos
completos, “sacados de la manga”, con su análisis, el libro normalmente comenta primero un problema,
considera una o más estrategias para resolverlo (como podría hacer el lector que enfrenta
el problema por primera vez) y luego comienza a desarrollar un algoritmo, lo analiza y lo modifica
o lo rechaza hasta obtener un resultado satisfactorio. (Los enfoques alternativos que finalmente
se rechazan también se examinan en los ejercicios; para el lector es útil saber por qué se les rechazó.)
Preguntas del tipo de ¿Cómo puede hacerse esto de forma más eficiente? ¿Qué estructura de
datos sería útil en este caso? ¿En qué operaciones debemos concentrarnos para analizar este algoritmo?
¿Qué valor inicial debe asignarse a esta variable (o estructura de datos)?, aparecen a
menudo en todo el texto. Por lo general damos la respuesta inmediatamente después de la pregunta,
pero sugerimos a los lectores hacer una pausa antes de continuar la lectura y tratar de idear su
propia respuesta. El aprendizaje no es un proceso pasivo.
Tenemos la esperanza de que los lectores también aprendan a visualizar cómo se comporta
en la realidad un algoritmo con diversas entradas; es decir, ¿Qué ramas sigue? ¿Qué patrón de
crecimiento y encogimiento siguen las pilas? ¿Cómo afecta al comportamiento presentar las entradas
en diferentes formas (por ejemplo, enumerando los vértices o aristas de un grafo en distintos
órdenes)? Tales preguntas se plantean en algunos de los ejercicios, pero no hacemos hincapié
en ellas en el texto porque requieren un estudio minucioso de los pormenores de un gran número
de ejemplos.
Casi todos los algoritmos que presentamos tienen utilidad práctica; decidimos no hacer hincapié
en los que tienen un buen comportamiento asintótico pero no se desempeñan bien con entradas
de tamaño útil (aunque sí incluimos algunos por su importancia). Los algoritmos específicos
se escogieron por diversas razones que incluyen la importancia del problema, la ilustración de técnicas de análisis, la ilustración de técnicas (como la búsqueda primero en profundidad) que dan
pie a numerosos algoritmos, y la ilustración del desarrollo y mejoramiento de técnicas y algoritmos
(como los programas Unión-Hallar).
.jpg)
CONTRASEÑA DEL ARCHIVO
dakalimdor1993
.jpg)
.jpg)
