Fundamentos de programación con Módula-2 (14)

 

6.2.2.2 Escritura mediante bucle de líneas
La segunda alternativa de diseño consiste en plantear la escritura del triángulo como un bucle de imprimir líneas de números, una tras otra. El refinamiento correspondiente será:

            Imprimir el triángulo hasta N —>
                 WHILE quedan números DO
                    Imprimir la siguiente línea
                 END

Para ir imprimiendo cada línea necesitaremos conocer el rango de números que le corresponde. Usaremos unas variables similares a las de la alternativa anterior, para mantener el número de la línea, y el primer y último número de esa línea:

            VAR   linea, primero, ultimo: INTEGER;

Al comienzo del bucle estas variables tendrán los valores correspondientes a la última línea impresa. Los valores iniciales serán:

            linea := 0;
            primero := 0;
            ultimo := 0;

Ahora podemos refinar los elementos del bucle:

            quedan números —> ultimo < N

            imprimir la siguiente línea —>
                   actualizar los límites
                   imprimir los números

            actualizar los límites —>
                   linea := linea + 1;
                   primero := ultimo + 1;
                   ultimo := ultimo + linea;

            imprimir los números —>
                   FOR k := primero TO ultimo DO
                      WriteInt( k, 5 )
                   END;
                   WriteLn

Con esto se completa el programa; pero antes de presentarlo en su conjunto es preciso realizar alguna corrección. Dicha corrección es debida a que al calcular los límites de una línea de números no se ha tenido en cuenta que la última línea puede no estar completa. El último número de la línea no debe ser nunca mayor que el último de la serie completa. Escribiremos, por tanto:

             actualizar los límites —>
                  INC( linea );
                  primero := ultimo+1;
                  ultimo := ultimo + linea;
                  IF ultimo > N THEN
                      ultimo := N
                  END;

Ahora sí se puede construirse el programa Floyd2, y presentarlo debidamente documentado tal como se hace en el siguiente listado. El resultado de la ejecución de este programa es idéntico al de la variante anterior. Ambos programas son equivalentes desde el punto de vista de su utilización.

(*************************************************************************
*
*    Programa: Floyd2
*
*    Descripción:
*      Este programa imprime el triángulo de Floyd con los números
*      correlativos de 1 a N. El valor de N se lee como dato.
*
*************************************************************************)
MODULE Floyd2;

(*========================================================================
    IMPORTACIÓN Y DECLARACIONES DEL PROGRAMA
========================================================================*)
  FROM InOut IMPORT WriteLn, WriteString, ReadInt, WriteInt;
  VAR
    N: INTEGER;                (* último número a imprimir *)
    k: INTEGER;                (* cotandor de números *)
    linea: INTEGER;            (* contador de línea *)
    primero: INTEGER;            (* primer número de la línea *)
    ultimo: INTEGER;            (* último número de la línea *)

BEGIN

(*=======================================================================
    PARTE EJECUTABLE DEL PROGRAMA
=======================================================================*)
  (*– leer el límite de la serie –*)
    WriteString( "Límite de la serie: " );
    ReadInt( N );
    WriteLn;

  (*– imprimir el triángulo mediante un bucle de líneas –*)
    k := 0;
    linea := 0;
    primero := 0;
    ultimo := 0;
    WHILE ultimo < N DO
      (*– actualizar los límites –*)
    linea := linea+1;
    primero := ultimo+1;
    ultimo := ultimo + linea;
    IF ultimo > N THEN
      ultimo := N
    END;
      (*– imprimir los número –*)
    FOR k := primero TO ultimo DO
      WriteInt( k,5 )
    END;
    WriteLn
    END
END Floyd2.


6.3 Verificación de programas

Ya se ha indicado que uno de los objetivos de la programación es la corrección. Un programa es correcto si produce siempre resultados de acuerdo con la especificación del programa. Evidentemente, sólo 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.

En la práctica, la verificación de un programa se hace muchas veces mediante ensayos. Un ensayo consiste en ejecutar el programa con unos datos preparados de antemano y para los cuales se sabe cuál ha de ser el resultado a obtener. Si al ejecutar el programa no se obtienen los resultados esperados, se sabrá que hay algún error, y el programa se examina para determinar la causa del error y eliminarla. Este proceso se llama depuración (en inglés "debugging").

Si la ejecución produce los resultados esperados, entonces el ensayo no suministra ninguna información acerca de la corrección del programa. Puede ser que el programa sea correcto, y no tenga errores, pero también puede ocurrir que el programa contenga errores que sólo se pongan de manifiesto con otros datos de ensayo diferentes.

La única manera de verificar con seguridad la corrección de un programa es demostrar formalmente que el programa cumple con sus especificaciones. Para ello es necesario escribir esas especificaciones con toda precisión en forma de expresiones lógicas, y luego realizar una demostración lógico-matemática de que el programa las cumple. A continuación se exponen algunas ideas sobre cómo puede ser este proceso de demostración.

6.3.1 Corrección parcial y total
Usando las expresiones y reglas de la lógica, y conociendo la semántica (significado) de las acciones, es posible demostrar si un programa es o no correcto. Para programas que siguen el modelo imperativo el proceso de demostración se realiza en dos partes:

1) CORRECCIÓN PARCIAL: si el programa termina el resultado es correcto.

2) CORRECCIÓN TOTAL: para todo dato de entrada válido el programa termina.

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

  • Anotar el comienzo y final del programa con aserciones (afirmaciones, formalizadas como expresiones lógicas) correspondientes a las condiciones iniciales y al resultado deseado.
  • Anotar los puntos intermedios del programa con asersiones similares respecto al estado del cómputo 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.

En particular, la corrección parcial se consigue al demostrar que al llegar al final del programa ha de cumplirse la aserción correspondiente al resultado deseado.

La corrección total se consigue añadiendo la demostración de que todos los bucles del programa terminan tras un número finito de repeticiones. Para demostrar la terminación se puede:

  • 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.

De esta manera tras un cierto número de repeticiones se alcanzará la cota o límite de dicha función, y el bucle terminará.

6.3.2 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. A continuación anotaremos detrás de la sentencia las condiciones que podamos demostrar que se cumplen después de su ejecución, y que será las siguientes:

  • Las condiciones anteriores en las que no intervenga la variable asignada.
  • La condición de que la variable tiene el valor asignado.

Las condiciones se suelen anotar entre llaves { }. Por ejemplo:

{ (x > y) AND (a > b) AND (a > x) }
a := 36
{ (x > y) AND (a = 36) }

En la anotación final hemos suprimido las condiciones iniciales (a > b) y (a > x), ya que estas variables no son afectadas por la asignación, y hemos añadido la nueva condición (a = 36) impuesta por la ejecución sentencia de asignación.

6.3.3 Razonamiento sobre el esquema de selección
Para analizar el comportamiento de un fragmento de programa correspondiente a un esquema de selección, comenzaremos por anotar delante de dicho esquema las condiciones que sepamos que se cumplen inmediatamente antes de examinar la condición.

 Figura(6_1)
      Figura 6.1 Razonamiento sobre un esquema de selección.

Puesto que la condición de selección decide la continuación por una u otra vía de las dos posibles, deduciremos que al comienzo de la alternativa "SI" se cumplirán las condiciones iniciales y además la condición de selección, y que al comienzo de la alternativa "NO" se cumplirán las condiciones iniciales y no se cumplirá la condición selección. La Figura 6.1 (a) refleja gráficamente estas anotaciones.

En la parte de terminación del esquema anotaremos las condiciones que se deduzcan de la ejecución de cada alternativa en particular; y anotaremos como condición a la salida que ha de cumplirse alguna de las condiciones de terminación, correspondientes a las dos alternativas posibles, tal como se indica en la Figura 6.1 (b).

Aplicaremos esta técnica de razonamiento a  un fragmento de programa que calcule en m el máximo de dos números a y b. Dicho fragmento podría ser:

IF a > b THEN
   m := a
ELSE
   m := b
END

Anotando las condiciones al comienzo, tendremos:

IF a > b THEN
   { a > b }
   m := a
ELSE
   { a <= b }
   m := b
END

Razonando sobre cada sentencia de asignación, de acuerdo con las propiedades matemáticas del máximo de dos valores, tendremos:

IF a > b THEN
   { a > b }
   m := a
   { (a > b) AND (maximo = a) }   ===> m = Max(a,b)
ELSE
   { a <= b }
   m := b
   { (a <= b) AND (maximo = b) }   ===> m = Max(a,b)
END

Simplificando, podremos anotar las condiciones de salida que nos interesan:

IF a > b THEN
   m := a
   { m = Max(a,b) }
ELSE
   m := b
   { m = Max(a,b) }
END
{ m = Max(a,b) }

6.3.4 Razonamiento sobre bucles: invariante, terminación
Para analizar el comportamiento de un fragmento de programa correspondiente a un esquema de iteración habremos de identificar las condiciones que deben cumplirse siempre inmediatamente antes de examinar la condición de repetición. Estas condiciones constituyen el llamado invariante del bucle. En la Figura 6.2 se representa el diagrama de flujo de un bucle tipo WHILE, en que el invariante es la condición { p }.

Figura(6_2)
     Figura 6.2 Razonamiento sobre un esquema de iteración.

Razonando como en el esquema de selección, deduciremos que al comienzo de cada repetición de la acción del bucle habrá de cumplirse el invariante y además la condición de repetición; y que al terminar las repeticiones y salir del bucle se cumplirá el invariante y además no se cumplirá la condición de repetición.

La identificación del invariante puede ser complicada. No se trata simplemente de anotar todas las condiciones que sabemos que se cumplen al llegar al bucle por primera vez, sino precisamente aquellas que además se seguirán cumpliendo después de cada repetición. La denominación de invariante responde al hecho de que estas condiciones no cambian al ejecutar la acción del bucle.

Como ejemplo, analizaremos un fragmento de programa para calcular en f el factorial de un número n (n! = 1x2x3..xn). Para ello se usará un contador k que vaya tomando los valores de 1 a n:

k := 1;
f := 1;
WHILE k<n DO
   k := k + 1;
   f := f * k
END

Usaremos como invariante { (k <= n) AND (f = k!) }. Esto es válido para los casos en que (n>=1). Las anotaciones en el bucle serán:

k := 1;
f := 1;
{ (k <= n) AND (f = k!) }
WHILE k<n DO
{ (k < n) AND (f = k!) }
   k := k + 1;
{ (k <= n) AND (f = (k-1)!) }
   f := f * k
{ (k <= n) AND (f = k!) }
END
{ (k = n) AND (f = k!) }     ===> f = n!

La demostración de las anotaciones es sencilla, conociendo propiedades matemáticas tales como:

1! = 1
(k < n)  —> (k+1 <= n)
k! = (k-1)! x k
(k <= n) AND (k >= n) —> k=n

El análisis anterior sólo es válido si (n >= 1). Falta comprobar la corrección para el caso (n = 0), ya que para (n < 0) el factorial no está definido. Sabiendo que 0! = 1, y comprobando que si (n = 0) el bucle no se ejecuta nunca, y la variable f conserva su valor inicial f = 1 = 0! tenemos la demostración completa.

Los razonamientos anteriores corresponden sólo a la demostración de corrección parcial. Para demostrar la corrección total hay que demostrar que el bucle termina siempre tras un número finito de repeticiones. Hay que buscar una función monótona acotada que varíe con cada repetición del bucle.

En este caso la función es sencillamente k. A cada repetición k aumenta una unidad. La cota superior para la que ya no se repite el bucle es n. Tras un cierto número de repeticiones k alcanzará forzosamente dicha cota y las iteraciones finalizarán.


6.4 Eficiencia de programas. Complejidad algorítmica.

Ya se ha dicho que el objetivo prioritario de la programación es la corrección. La eficiencia sólo debe tenerse en cuenta si es un factor decisivo o importante en cada caso. Aunque en la primera redacción de un programa no conviene prestar excesiva atención a los aspectos de eficiencia, tampoco debe descuidarse totalmente este aspecto. Por esta razón se presentan a continuación los elementos básicos de la eficiencia de programas, y una descripción informal de algunas técnicas para analizar dicha eficiencia.

6.4.1 Medidas de eficiencia
La eficiencia de un programa se analiza un función de la cantidad de recursos que consume durante su ejecución. Un programa eficiente consume pocos recursos, mientras que un programa menos eficiente consumirá una mayor cantidad de recursos. Esto quiere decir que establecer una medida de la eficiencia de los programas equivale a establecer una medida de los recursos usados durante su ejecución.

Las principales medidas de recursos empleados son:

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

En muchos casos estos dos factores son mutuamente dependientes. Es decir, se pueden desarrollar programas que obtengan los resultados en menos tiempo, a costa de usar una mayor cantidad de memoria para almacenar datos, y viceversa.

En lo que sigue atenderemos exclusivamente a la primera de las dos medidas mencionadas. Un programa se considerará tanto más eficiente cuanto menos tiempo tarde en ejecutarse. Los programas poco eficientes tardarán mucho tiempo en dar los resultados. Hablaremos, por tanto, de la eficiencia en tiempo de un programa.

El tiempo de ejecución de un programa depende, en la mayoría de los casos, de los datos particulares con los que opera. Esto quiere decir que la eficiencia de un programa debe establecerse no como una magnitud fija para cada programa, sino como una función que nos dé el tiempo de ejecución para cada tamaño o cantidad de los datos que deba procesar.

Esta idea nos lleva, por su parte, a la necesidad de establecer previamente una medida del tamaño de los datos o tamaño del problema, para, en función de ella, establecer la medida de la eficiencia del programa que los procesa.

El tamaño del problema se puede expresar bien por la cantidad de datos a tratar, o bien por los valores particulares de los datos. Por ejemplo, para un programa que obtenga el valor medio o la suma de una serie de datos, el número de datos a sumar o promediar es una buena medida del tamaño del problema. En cambio, para un programa que calcule una potencia de un número, el tamaño significativo puede ser el valor del exponente.

La función que da el tiempo de ejecución según el tamaño del problema se dice que mide la complejidad algorítmica del programa.

6.4.2 Análisis de programas
La determinación de la eficiencia (o complejidad) de un programa se hace analizándolos siguientes elementos:

1) Cuánto tarda en ejecutarse cada instrucción básica del lenguaje utilizado.

2) Cuántas instrucciones de cada clase se realizan durante una ejecución del programa.

Para simplificar, consideraremos que cada operación elemental del lenguaje de programación: suma, resta, lectura, escritura, asignación de valor, decisión  según condición, etc…, dura una unidad de tiempo. Con esta simplificación, el análisis de la eficiencia de un programa se centra en establecer cuántas instrucciones se ejecutan en total, dependiendo del tamaño o cantidad de los datos a procesar.

Al realizar el análisis mencionado nos encontraremos con que el número preciso de instrucciones ejecutadas depende de los valores particulares de los datos, incluso para un tamaño fijo del problema. En este caso se pueden adoptar al menos dos criterios diferentes para realizar el análisis de eficiencia:

  • Analizar el comportamiento, en promedio.
  • Analizar el comportamiento en el peor caso.

Utilizaremos el segundo criterio, por ser el más sencillo de aplicar, para analizar algunos ejemplos de programas. Con este criterio el análisis de complejidad (número de instrucciones ejecutadas) de los esquemas básicos de los programas es el siguiente:

1) La complejidad de un esquema secuencial es la suma de las complejidades de sus acciones componentes.

2) La complejidad de un esquema de selección equivale a la de la alternativa más compleja, es decir, de ejecución más larga, más la complejidad de la evaluación de a condición de selección.

3) La complejidad de un esquema de iteración se obtiene sumando la serie correspondiente al número de instrucciones en las repeticiones sucesivas.

Veamos cómo es este análisis en algunos casos concretos. Tomemos como ejemplo el siguiente fragmento de programa que obtiene el máximo de dos números:

maximo := a;
IF a < b THEN
   maximo := b
END

El esquema global es una secuencia de dos acciones: una asignación, seguida de un esquema condicional (IF). Anotaremos el programa con el número de instrucciones correspondientes a cada sentencia, para lo cual contaremos el número de operadores (+,-,*,<,:=, etc.) y decisiones (IF, ELSIF,WHILE, etc.). Aplicando las reglas para los esquemas tendremos:

maximo := a;                                1
IF a < b THEN         2   )
   maximo := b        1   )                  3 (Regla 2)
END
                                Total = 4            (Regla 1)

La complejidad en este caso es fija, y no depende de una medida de tamaño del problema.

A continuación analizaremos un bucle que obtiene en f el factorial de un número k. Anotaremos el programa con el número de instrucciones de cada sentencia:

k := 1;                                                              1
f := 1;                           \                                   1
WHILE k<n DO        2    |
   k := k + 1;            2    |                             6(n-1) (Regla 3)
   f := f * k                2    |
END                             /
                                        Total =        6n – 4 (Regla 1)

Para calcular el número de instrucciones del bucle se ha multiplicado el número de instrucciones en cada repetición por el número de repeticiones. La complejidad aparece expresada en función del valor de n, que en este caso resulta una medida natural del tamaño del problema.

6.4.3 Crecimiento asintótico
En los análisis de eficiencia (o complejidad) se considera muy importante la manera como la función de complejidad va aumentando con el tamaño del problema. Lo que interesa es la forma de crecimiento del tiempo de ejecución, y no tanto el tiempo particular empleado. Como ejemplo podemos comparar dos programas, uno que tarde un tiempo 100N en resolver un problema de tamaño N, y otro que tarde un tiempo N^2. La comparación puede hacerse escribiendo una tabla con los tiempos de cada uno para diferentes tamaños del problema.

      Tamaño        100N            N^2
         1               100              1
         2               200              4
         3               300              9
         10             1.000           100
         100           10.000          10.000
         1.000        100.000        1.000.000

Al principio de la tabla el primer programa parece menos eficiente que el segundo, ya que tarda mucho más tiempo, pero a medida que aumenta el tamaño del problema ambos programas llegan a tardar lo mismo (para tamaño 100), y a partir de ahí el segundo programa demuestra ser mucho menos eficiente que el primero.

La menor eficiencia del segundo programa para tamaños grandes del problema no cambia el hecho de que se modifique el coeficiente multiplicador. Si el primer programa tardase 10 veces más (1.000N en lugar de 100N), acabaría igualmente por resultar mejor que el segundo a partir de un cierto tamaño del problema.

Lo que importa es la forma de la función, que en el primer caso es lineal, y en el segundo es cuadrática. La forma en que crece la función para tamaños grandes se dice que es su comportamiento asintótico, y se representa mediante la notación:

            O( f(n) )

siendo n el tamaño del problema, f la forma o función de crecimiento asintótico, y O (que se lee O-mayúscula) indica el orden de crecimiento. Algunas formas de crecimiento típicas, y sus valoraciones habituales, son las siguientes:

O( 1 )                     Complejidad constante. Ideal.
O( log n )                Crecimiento logarítmico. Muy eficiente.
O( n )                     Complejidad lineal. Muy eficiente.
O( n log n)              Eficiente.
O( n^2 )                  Complejidad cuadrática. Menos eficiente.
O( n^k )                  Complejidad polinómica. Poco eficiente.
O( 2^n )                  Complejidad exponencial. Muy poco eficiente.

Las valoraciones indicadas son, por supuesto, muy imprecisas. Hay muchos problemas que sólo pueden resolverse mediante programas de complejidad elevada, poco eficientes según esta valoración, pero adecuados para esos problemas. Los problemas que sólo pueden resolverse con programas de complejidad exponencial se consideran intratables en la práctica para tamaños grandes del problema.

Anuncios

Responder

Introduce tus datos o haz clic en un icono para iniciar sesión:

Logo de WordPress.com

Estás comentando usando tu cuenta de WordPress.com. Cerrar sesión /  Cambiar )

Google photo

Estás comentando usando tu cuenta de Google. Cerrar sesión /  Cambiar )

Imagen de Twitter

Estás comentando usando tu cuenta de Twitter. Cerrar sesión /  Cambiar )

Foto de Facebook

Estás comentando usando tu cuenta de Facebook. Cerrar sesión /  Cambiar )

Conectando a %s