Ricardo Peña Marí

Es innegable, en este comienzo del siglo XXI, que la aparición de los ordenadores y, sobre todo, su hibridación con las teleco- municaciones configurando la gran red global, ha propiciado una revolucion de las fuerzas productivas de una magnitud desconocida hasta ahora. Nuestra historia comienza casi a la vez que la de la humanidad, pues incluso en la antigua Mesopotamia de hace 3.000 años se emplearon algoritmos -concepto tan ligado hoy a los computadores- para describir ciertos calculos relacionados con transacciones comerciales. Estos han acompañado desde entonces al desarrollo de las matematicas. En el siglo XVII aparecieron las primeras ayudas mecanicas para el calculo en forma de calculadoras de sobremesa y en el XIX se conciben las primeras maquinas programables. Los primeros ordenadores, tal como hoy los conocemos, son, sin embargo, de mediados del siglo XX. A partir de ahi, los algoritmos alcanzan un desarrollo sin precedentes. El libro recorre la historia de los mismos, prestando especial atencion a los tiempos mas recientes. En un cierto momento, situado hacia 1960, el enfasis del libro pasa a describir los lenguajes de programacion, que son los instrumentos apropiados para comunicar los algoritmos a las maquinas que han de ejecutarlos.

Este libro universitario presenta una amplia variedad de estructuras de datos y de métodos algorítmicos con el objetivo de servir como texto base para uno o dos cursos avanzados de programación. El contenido es apropiado para un semestre dedicado a estruc

Esta obra está destinada a quienes quieren mejorar sus métodos de programación y aprender a razonar sobre la corrección y la eficiencia de sus programas. En el libro se describen técnicas tales como el diseño y la verificacion de programas recursivos, la derivacion formal de programas iterativos y la especificacion algebraica de tipos abstractos de datos; se estudian tanto las tecnicas como los fundamentos matematicos de estas y se dan numerosos ejemplos de ellas. Tambien se incluyen un CD-ROM con numerosos ejercicios practicos.

Los computadores permean y controlan todas las facetas de la vida de las sociedades modernas, desde nuestro horno de microondas o nuestro automóvil, hasta los grandes sistemas informáticos de empresas como Amazon o Google. Su capacidad para resolver problemas se la da el software, es decir, el conjunto de programas que contienen sus memorias. Y el software, por desgracia, contiene errores que, a veces, se manifiestan de forma dramatica mediante perdidas economicas o de vidas humanas. El libro comienza recordando ciertos fallos catastroficos debidos al software y analizando cuales fueron sus causas. De menor a mayor complejidad, los siguientes capitulos explican los metodos que los investigadores e ingenieros han ideado para detectar y prevenir tales errores antes de que se manifiesten. El nivel pretendido es divulgativo, si bien ocasionalmente aparecen formulas y programas que ilustran los metodos, que pueden esquivarse sin que ello afecte a la comprension. En paralelo con esta exposicion, se desarrolla una historia real aunque ficcionada en sus detalles por el autor sobre como hizo frente a los errores del software la empresa Amazon Web Services.

Este libro presenta una amplia variedad de estructuras de datos y de métodos algorítmicos con el objetivo de servir como texto base para uno o dos cursos avanzados de programación. El contenido es apropiado para un semestre en estructuras de datos eficientes y otro semestre en metodos algoritmicos. Supone una exposicion previa a dos o tres semestres de asignaturas de programacion donde se hayan tratado los conceptos basicos, la sintaxis y semantica de un lenguaje de programacion, la recursion, las estructuras de datos lineales y las nociones de clase y objeto. Es tambien recomendable una exposicion previa o simultanea al paradigma de programacion funcional, a los fundamentos de la especificacion y verificacion formal de programas y a asignaturas de logica y matematica discreta. En esta segunda edicion se han corregido erratas detectadas en la edicion anterior, se ha actualizado la bibliografia y se añadido una seccion nueva en el capitulo 5 dedicado a la union de dos AVL en tiempo lineal. El enfoque del libro es original por el hecho de que casi las dos terceras partes de los algoritmos se presentan especificados y verificados formalmente en la plataforma Dafny de verificacion asistida. Como material asociado al mismo, se distribuyen los ficheros Dafny con el texto completo de todos los algoritmos, junto con sus especificaciones formales y asertos intermedios necesarios. El lector puede reproducir la verificacion de los programas sin mas que procesarlos con dicha plataforma. Dicho material puede descargarse de la pagina web que el libro tiene en la editorial Garceta: http://www.garceta.es.