Teaching

La informática es mucho más que la informática de usuario que casi toda la gente conoce. El área más desconocida es la informática teórica, es decir, la base matemática de la informática. Por ello, en esta introducción no abarcamos todos los aspectos de la informática, sino que nos centramos en el concepto de algoritmo y de su formalización, sus límites y su coste.

El primer capítulo ofrece una visión panorámica de las distintas ramas de la informática y de su historia. El segundo capítulo introduce el concepto fundamental de algoritmo y su formalización matemática. Los algoritmos se concretan en forma de programas cuando se elige un lenguaje de programación, tema al que se dedica el tercer capítulo. El cuarto capítulo estudia la complejidad de los algoritmos y de los problemas que estos resuelven, es decir, su coste en términos de los recursos de tiempo y espacio utilizados.

Aunque los temas relacionados con la especificación y verificación formal de programas no gozan de mucha popularidad, es importante su inclusión en los temarios, sobre todo haciendo más hincapié en la derivación de programas a partir de su especificación, de forma que se obtiene un algoritmo correcto por construcción.

Con el presente libro se intenta contribuir a paliar este déficit, pero además en un formato apropiado para los alumnos que demandan como complemento a los "libros de teoría" y a los apuntes de clase, un libro de ejercicios resueltos.

De esta forma, cada capítulo comienza con una breve introducción cuyo objetivo es repasar los conceptos principales y fijar las notaciones que se utilizan en el desarrollo posterior de las soluciones de los ejercicios. La parte principal de cada capítulo consiste en una serie de ejercicios resueltos de dificultad creciente. Además, al final de cada capítulo se proponen nuevos ejercicios para resolver por el lector.

Este manual surge con la intención de ofrecer una colección de ejercicios resueltos sobre estructuras de datos y algoritmos.

La primera parte se dedica a las estructuras de datos. Empieza con dos capítulos genéricos sobre especificación algebraica de tipos abstractos de datos y su implementación, y continua con las estructuras de datos más habituales: pilas, colas, listas árboles binarios y generales, árboles de búsqueda y tablas, colas con prioridad y montículos, así como grafos. Esta parte termina con un capítulo de aplicaciones donde se usan las estructuras anteriores de diferentes formas.

La segunda parte, la de algoritmos, se organiza alrededor de la clasificación habitual de métodos algorítmicos: divide y vencerás, método voraz, programación dinámica, vuelta atrás y ramificación y poda.