jikcj

Análisis de Programas
Un programa escrito en cualquier lenguaje, como cualquier objeto diseñado para realizar determinada tarea, ha de probarse que cumple bien el objetivo para el cual ha sido elaborado. Un programador ingenuo puede pensar que con haber realizado algunas pruebas complicadas siendo el resultado satisfactorio, el programa ha mostrado su buena manufactura. No es así. Esas son solomuestras particulares, puntuales de que el programa funciona bien para esas entradas de prueba, pero no para cualquier entrada. Para demostrar, en general, que el programa funciona bien, es necesario que dada una entrada cualquiera, la salida del programa sea conforme lo que se esperaba que hiciera. Si el programa es para la realización del producto de números enteros se espera que el resultado demultiplicar cualesquiera par de enteros sea correcto; junto con ello si las entradas no son números enteros que el programa lo rechace y lo indique. Utilizando lógica de primer orden es posible hacer un análisis general del flujo de ejecución de una clase de programas, dada una entrada y hasta la salida. Los programas que no se invocan a si mismos durante la ejecución forman la clase para lacual este análisis es adecuado.

El análisis de un programa consiste en revisar las relaciones que se establecen durante el flujo del mismo dada una entrada y hasta la salida. Las especificaciones del programa establecen de principio las relaciones a darse durante su ejecución. Las relaciones de entrada - salida en un programa tienen que ver con los siguientes aspectos:
• Terminación delprograma
• Respuesta del programa
• Correctitud del programa
• Equivalencia con otros programas
• Especialización del programa

Para considerar estos aspectos se parte de una entrada dada al programa. La terminación se refiere a si dada la entrada la secuencia de instrucciones del programa logra un estado de parada, en tanto lo que el programa proporcionacomo salida es la respuesta; si la salida es conforme a las especificaciones del programa entonces éste es correcto. Dos programas son equivalentes si dada la misma entrada las salidas son iguales. Un programa es una especialización de otro si considerando un subconjunto de las entradas al programa original, es posible modificarlo de tal manera que el programa modificado se ejecute a mayor velocidadsobre el subconjunto de entradas.

Utilizando lógica de primer orden la verificación de estos aspectos puede hacerse de la siguiente manera: haciendo una descripción mediante un conjunto de axiomas del flujo de ejecución del programa, de la entrada y de las operaciones involucradas. A partir de estos axiomas el objetivo es deducir (derivar) las fórmulas que describen la terminación, respuestay correctitud del programa, así como su equivalencia con otro y una especialización. Del cumplimiento o no de estas derivaciones se desprende el resultado del análisis.

La terminación del programa estaría dada por una cláusula de parada, la cual describe las condiciones de terminación del programa. Cláusula de parada puede haber más de una, cada una de las cuales es una respuesta de salidadada por el programa. Si la fórmula que describe las especificaciones del programa junto con una fórmula de parada es consecuencia lógica de los axiomas entonces el programa es correcto. La equivalencia se prueba si dados los axiomas de ejecución de los dos programas y compartiendo los axiomas de realización y entrada, estos tienen como consecuencia lógica a los predicados de parada de los dosprogramas.

El flujo de ejecución del programa se hace mediante diagramas de estados y transiciones, es decir mediante diagramas típicos de autómatas de Turing. Las transiciones indican las condiciones que se deben satisfacer para que el control de un programa pase de un estado a otro. Si dado el estado inicial existe una secuencia de transiciones entre estados que conduzca a un estado final, el...