Este libro de ejercicios sobre diseño de algoritmos correctosy eficientes es el resultado de la actividad docente de susautores, profesores de asignaturas de programación durantemuchos años en la Universidad Complutense de Madrid, e intentapaliar el déficit de material docente sobre especificación y verificaciónformal de programas disponible en castellano.
Se hace especial hincapié en la derivación de programas a partirde su especificación. La derivación consiste en la construcción sistemáticadel programa a partir de su especificación, de forma quese garantiza que al final de tal construcción el algoritmo cumple laespecificación y, por tanto, es automáticamente correcto con respectoa esta. También se introducen los conceptos básicos paraanalizar el coste de un programa, puesto que este ingrediente esasimismo útil para construir programas que además de correctossean eficientes.
Cada capítulo empieza con una breve introducción para repasarlos conceptos principales y fijar las notaciones que se utilizan enel desarrollo posterior de las soluciones de los ejercicios; siguecon una serie de ejercicios resueltos con detalle y de dificultadcreciente; y acaba proponiendo nuevos ejercicios que deberíanser resueltos por el estudiante interesado.
Derivación de algoritmos recursivos
5.1. Introducción
5.1.1. Análisis por casos y composición
5.1.2. Técnicas de inmersión
5.1.3. Técnica de desplegado y plegado
5.1.4. Transformación de recursivo lineal a iterativo
5.2. Ejercicios resueltos
5.3. Ejercicios propuestos