Computabilidad, complejidad computacional y verificación de programas

Abstract

<i>Computabilidad, Complejidad Computacional y Verificación de Programas</i> contiene las quince clases que conforman la asignatura Teoría de la Computación y Verificación de Programas, una introducción a la teoría de la computabilidad y complejidad computacional de problemas y la teoría de correctitud de programas, que dicto en la Licenciatura en Informática de la Facultad de Informática de la Universidad Nacional de La Plata desde hace varios años. El libro es una suerte de segunda edición reducida de <i>Teoría de la Computación y Verificación de Programas</i>, de los mismos autores, editado en 2010 por la EDULP conjuntamente con McGraw-Hill, el cual incluye además de las clases de la asignatura básica, las de Teoría de la Computación y Verificación de Programas Avanzada, asignatura que también dicto en la misma carrera desde hace tiempo. El nuevo trabajo excluye principalmente la complejidad espacial, la verificación de los programas no determinísticos y concurrentes, el empleo de la lógica temporal para verificar los programas reactivos, y la semántica denotacional de los lenguajes de programación, tópicos tratados en la obra anterior. De todos modos, en la presente publicación hay secciones, breves, dedicadas a la jerarquía espacial, la terminación con hipótesis de fairnes de los programas no determinísticos, y la verificación de los programas concurrentes con memoria compartida, desarrolladas de la manera en que dichos temas son referenciados en la asignatura básica.