Computabilidad, complejidad computacional y verificación de programas

Abstract

Computabilidad, Complejidad Computacional y Verificación de Programas contiene lasquince clases que conforman la asignatura Teoría de la Computación y Verificación deProgramas, una introducción a la teoría de la computabilidad y complejidadcomputacional de problemas y la teoría de correctitud de programa. El libro es una suerte de segunda edición reducida deTeoría de la Computación y Verificación de Programas, de los mismos autores, editadoen 2010 por la EDULP conjuntamente con McGraw-Hill, el cual incluye además de lasclases de la asignatura básica, las de Teoría de la Computación y Verificación deProgramas Avanzada.El nuevo trabajo excluye principalmente la complejidad espacial, la verificaciónde los programas no determinísticos y concurrentes, el empleo de la lógica temporalpara verificar los programas reactivos, y la semántica denotacional de los lenguajes deprogramación, tópicos tratados en la obra anterior. De todos modos, en la presentepublicación hay secciones, breves, dedicadas a la jerarquía espacial, la terminación conhipótesis de fairnes de los programas no determinísticos, y la verificación de losprogramas concurrentes con memoria compartida, desarrolladas de la manera en quedichos temas son referenciados en la asignatura básica.