Metodologia de Desarrollo de Programas II

Desarrollar programas por refinamientos sucesivos

Esta técnica es parte de las recomendaciones de una metodología general de desarrollo de programas denominada programación estructurada.

Esta técnica consiste en expresar inicialmente el programa a desarrollar como una acción global, que si es necesario se ira descomponiendo en acciones mas sencillas hasta llegar a acciones simples que pueden ser expresadas directamente como sentencias del lenguaje de programación.

Desarrollo de un esquema secuencial:

Para desarrollar una acción compuesta según un esquema secuencial se necesitara:

• Identificar las acciones componentes de la secuencia.
• Identificar las variables necesarias para disponer de la información adecuada al comienzo de cada acción, y almacenar el resultado.
• Identificar el ordenen que deben ejecutarse dichas acciones.

Metodología de desarrollo de un esquema de selección

Un esquema de selección consiste en plantear una acción compuesta como la realización de una acción entre varias posibles, dependiendo de ciertas condiciones, es decir, se trata de elegir para realizar una sola entre varias posibles alternativas.

Hay que hacer:

• Identificar cada una de las alternativas del esquema y las acciones correspondientes
• Identificar las condiciones para seleccionar una alternativa u otra.

Metodología de desarrollo de un esquema de iteración:

Una iteración o bucle consiste en la repetición de una acción o grupo de acciones hasta conseguir el resultado deseado. Para desarrollar un esquema de iteración dentro de un programa deberemos identificar cada uno de sus elementos componentes. Al hacerlo hay que identificar simultáneamente las variables adecuadas para almacenar la información necesaria.

• Identificar las acciones útiles a repetir, y las variables necesarias.
• Precisar el significado de estas variables al comienzo y final de cada repetición
• Identifica como actualizar la información al pasar de cada iteración a la siguiente. Puede ser necesario introducir nuevas variables.
• Identificar la condición de terminación. Puede ser necesario introducir nuevas variables e incluso acciones adicionales para mantenerlas actualizadas
• Identificar los valores iniciales de las variables y si es necesaria alguna acción para asignárselos antes de entrar en el bucle.

Ejemplos de desarrollo de programas
Un programa es correcto si produce siempre resultados de acuerdo con la especificación del programa. Evidentemente, solo tiene sentido hablar de corrección si antes de escribir el programa se ha escrito de manera precisa la especificación del comportamiento que se espera que tenga.

La única manera de verificar con seguridad la corrección de un programa es demostrar formalmente que el programa cumple con sus especificaciones.

Corrección parcial y total:

• Corrección parcial: si el programa termina, el resultado es correcto
• Corrección total: para todo dato de entrada valido el programa termina.

La base de la comprobación de corrección parcial es:

• Anotar el comienzo y final del programa con aserciones (afirmación, formalizadas como expresiones lógicas) correspondientes a las condiciones iniciales y al resultado deseado.
• Anotar los puntos intermedios del programa con aserciones similares respeto al estado del computo en ese punto.
• Demostrar que si se cumple una aserción en un punto del programa y se siguen cada una de las líneas de ejecución posible hasta llegar a otro punto con aserción, dicha aserción ha de cumplirse, según las reglas de la lógica y de acuerdo con las acciones realizadas.
• La corrección total se consigue añadiendo la demostración de que todos los bucles del programa terminan tras un numero finito de repeticiones.
• Asociar a cada bucle una función monótona (siempre creciente o decreciente) y que debe tener un valor acotado para que el bucle se repita

Razonamiento sobre sentencias de asignación:

• Para analizar el comportamiento de un fragmento de programa correspondiente a una sentencia de asignación, comenzaremos por anotar delante de dicha sentencia todas las condiciones que sabemos que se cumplen inmediatamente antes de ejecutarla.
• Las condiciones anteriores en las que no intervenga la variable asignada
• La condición de que la variable tiene el valor asignado.

Eficiencia de programas. Complejidad Algorítmica

Medidas de eficiencia
El tiempo que tarda en ejecutarse un programa. La cantidad de memoria usada para almacenar datos

Análisis de programas:
La determinación de la eficiencia de un programa se hace analizando los siguiente elementos

• Cuanto tarda en ejecutarse cada instrucción básica del lenguaje utilizado
• Cuantas instrucciones de cada clase se realizan durante una ejecución del programa

Con el criterio del numero de instrucciones ejecutadas de los esquemas básicos de los programas es el siguiente:

• La complejidad de un esquema secuencial es la suma de las complejidades de sus acciones componentes
• La complejidad de un esquema de selección equivale a la de l alternativa mas compleja, es decir, de ejecución mas larga, mas la complejidad de la evaluación de la condición de selección.
• La complejidad de un esquema de iteración se obtiene sumando la serie correspondiente al numero de instrucciones en las repeticiones sucesivas.
• Crecimiento asintótico: Los problemas que solo pueden resolverse con programas de complejidad exponencial se consideran intratables en la practica para tamaños grandes del problema.