PDF de programación - Computabilidad, complejidad computacional y verificación de programas

Libros de Cátedra

Computabilidad, complejidad
computacional y verificación
de programas
Ricardo Rosenfeld
Jerónimo Irazábal

FACULTAD DE
INFORMÁTICA

COMPUTABILIDAD, COMPLEJIDAD COMPUTACIONAL

Y VERIFICACIÓN DE PROGRAMAS



Ricardo Rosenfeld y Jerónimo Irazábal



2013




Rosenfeld, Ricardo
Computabilidad, complejidad computacional y verificación de programas / Ricardo
Rosenfeld y Jerónimo Irazábal ; con prólogo de Ricardo Rosenfeld. - 1a ed. -
La Plata : Universidad Nacional de La Plata, 2013.
E-Book.

ISBN 978-950-34-0970-1

1. Informática. 2. Computación. I. Irazábal, Jerónimo II. Rosenfeld, Ricardo ,
prolog. III. Título
CDD 005.3



Fecha de catalogación: 12/06/2013



Diseño de tapa: Dirección de Comunicación Visual de la UNLP



Universidad Nacional de La Plata – Editorial de la Universidad de La Plata

47 N.º 380 / La Plata B1900AJP / Buenos Aires, Argentina
+54 221 427 3992 / 427 4898
[email protected]
www.editorial.unlp.edu.ar

Edulp integra la Red de Editoriales Universitarias Nacionales (REUN)

Primera edición, 2013
La Plata, Buenos Aires, Argentina
ISBN 978-950-34-0970-1
© 2013. UNLP-Edulp

Los autores

Ricardo Rosenfeld



Fac. de Informática, UNLP

[email protected]



Jerónimo Irazábal


Fac. de Informática, UNLP
[email protected]



Ricardo Rosenfeld obtuvo en 1983 el título de Calculista Científico de la Facultad de

Ciencias Exactas de la Universidad Nacional de La Plata (UNLP), Argentina, y en 1991

completó los estudios de la Maestría en Ciencias de la Computación del Instituto de

Tecnología Technión, Israel. Desde 1991 se desempeña como Profesor en la UNLP, en

las áreas de teoría de la computación y verificación de programas. Previamente, entre

1984 y 1990, fue docente en la UNLP (lenguajes y metodologías de programación), en

la Universidad de Buenos Aires (verificación y derivación de programas), en la Escuela

Superior Latinoamericana de Informática (algorítmica, estructuras de datos, teoría de

compiladores), y en el Instituto de Tecnología Technión de Israel (programación). Es

además uno de los socios de Pragma Consultores, empresa regional dedicada a la

tecnología de la información, ingeniería de software y consultoría de negocios. Con

Jerónimo Irazábal publicó en 2010 el libro Teoría de la Computación y Verificación de

Programas, editado por la EDULP en conjunto con McGraw-Hill.

Jerónimo Irazábal obtuvo en 2009 el título de Licenciado en Informática de la Facultad

de Informática de la UNLP, y actualmente se encuentra desarrollando un Doctorado en

Ciencias Informáticas en la misma Facultad, centrado en los lenguajes de dominios

específicos. Desde 2005 es docente en la UNLP, en las áreas de teoría de la

computación, verificación de programas y lógica. Además es becario del Consejo

Nacional de Investigaciones Científicas y Técnicas (CONICET), y su lugar de trabajo es

el Laboratorio de Investigación y Formación en Informática Avanzada (LIFIA).

Anteriormente participó en la creación de la compañía Eureka Consulting S.A.,

dedicada al desarrollo de software. Es co-autor, con Ricardo Rosenfeld, del libro Teoría

de la Computación y Verificación de Programas.

Índice general



Prólogo



Parte 1. Computabilidad



Clase 1. Máquinas de Turing



Clase 2. Jerarquía de la computabilidad

Clase 3. Indecidibilidad



Clase 4. Reducciones de problemas

Clase 5. Misceláneas de computabilidad

Notas y bibliografía para la Parte 1



Parte 2. Complejidad computacional



Clase 6. Jerarquía de la complejidad temporal

Clase 7. Las clases P y NP



Clase 8. Problemas NP-completos



Clase 9. Otras clases de complejidad



Clase 10. Misceláneas de complejidad computacional

Notas y bibliografía para la Parte 2



Parte 3. Verificación de programas



Clase 11. Métodos de verificación de programas

Clase 12. Verificación de la correctitud parcial

Clase 13. Verificación de la terminación



Clase 14. Sensatez y completitud de los métodos de verificación

Clase 15. Misceláneas de verificación de programas

Notas y bibliografía para la Parte 3



Epílogo



Índice de definiciones

Índice de teoremas

Índice de ejemplos

Índice de ejercicios



1

5

7

27

41

54

79

96

101

104

117

132

154

178

197

204

207

227

238

253

265

297

304

305

305

306

308

Prólogo



Computabilidad, Complejidad Computacional y Verificación de Programas 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

Teoría de la Computación y Verificación de Programas, 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.

A sólo tres años de la publicación anterior, este libro se justifica por varias razones:



 Se profundiza en determinados contenidos, por ejemplo en la jerarquía temporal

y la sensatez y completitud de los métodos de verificación de programas, que

por cuestiones de espacio, dada la abundancia de temas tratados, en el trabajo de

2010 no se pudieron presentar de una manera más extensa.

 Se modifica la exposición de algunos temas, por ejemplo la caracterización de

los problemas de la clase NP y las definiciones iniciales de la verificación de

programas, a partir de la lectura de nuevos trabajos o de cambios en la

modalidad del dictado de las clases respectivas. Asimismo, y ahora con respecto

a todo el material, la presentación de los temas es más discursiva que en el libro

anterior.


Ricardo Rosenfeld y Jerónimo Irazábal 1

 Se desarrollan más ejemplos, más que nada los relacionados con las reducciones

de problemas tanto en la parte dedicada a la computabilidad como en la parte

dedicada a la complejidad computacional (en este último caso se trata de las

reducciones polinomiales).

 Se adapta más fielmente la forma del libro a la del dictado de la asignatura

asociada. La estructura general consiste en tres partes (computabilidad,

complejidad computacional y verificación de programas). Cada parte está

compuesta por cinco clases, y sus componentes básicos son definiciones,

teoremas, ejemplos y ejercicios. La quinta clase de cada parte presenta

misceláneas de la disciplina considerada.



Por lo demás, las características de este trabajo son muy similares a las del trabajo

anterior. Se asume que los lectores ya han adquirido cierta madurez matemática, y

sólidos conocimientos en algorítmica, estructuras de datos, y lenguajes y paradigmas de

programación. Las quince clases están dirigidas principalmente a los estudiantes de los

últimos años de las carreras de computación, a los graduados que desean introducirse en

la teoría de la computación y la teoría de correctitud de programas, y naturalmente a los

docentes que dictan o quieran dictar contenidos afines. En particular, a estos últimos les

recomiendo no obviar ningún tema cuando desarrollen esta asignatura; si el material

completo resulta excesivo, podrían prescindir de algunos ejemplos, priorizando las

necesidades de los estudiantes.

El libro se puede tomar como un viaje imaginario a lo largo del universo de problemas.

Se arranca en los confines de dicho universo y se viaja hacia su interior (algo así como

se muestra en la figura de la página siguiente). En un primer tramo se atraviesan