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.
RESUMEN DE CONTENIDO:
1 Análisis de algoritmos y problemas: principios y ejemplos
2 Abstracción de datos y estructuras de datos básicas
3 Recursión e inducción
4 Ordenamiento
5 Selección y argumentos de adversario
6 Conjuntos dinámicos y búsquedas
7 Grafos y recorridos de grafos
8 Problemas de optimización de grafos y algoritmos codiciosos
9 Cierre transitivo, caminos más cortos de todos los pares
10 Programación dinámica
11 Cotejo de cadenas
12 Polinomios y matrices
13 Problemas NP-completos
14 Algoritmos paralelos
A Ejemplos y técnicas en Java
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.
RESUMEN DE CONTENIDO:
1 Análisis de algoritmos y problemas: principios y ejemplos
2 Abstracción de datos y estructuras de datos básicas
3 Recursión e inducción
4 Ordenamiento
5 Selección y argumentos de adversario
6 Conjuntos dinámicos y búsquedas
7 Grafos y recorridos de grafos
8 Problemas de optimización de grafos y algoritmos codiciosos
9 Cierre transitivo, caminos más cortos de todos los pares
10 Programación dinámica
11 Cotejo de cadenas
12 Polinomios y matrices
13 Problemas NP-completos
14 Algoritmos paralelos
A Ejemplos y técnicas en Java
Contraseña: www.facebook.com/groups/RecursosProgramacion
