Metodología y Tecnología de la Programación

Algoritmos Deterministas. Paso de Parámetros. Reglas de Verificación. Iteraciones. Subprogramas

  • Enviado por: Beto
  • Idioma: castellano
  • País: España España
  • 7 páginas
publicidad
publicidad

Ejercicio 1

Ejercicio 2

Ejercicio 3

Ejercicio 4

TOTAL

Ejercicio 1: [30 puntos: respuesta acertada = +2, respuesta incorrecta = -2]

Complete las siguientes frases con las alternativas especificadas. Si existen varias alternativas verdaderas, márquelas todas.

  • Un algoritmo determinado o determinista es:

  • El que tiene fin

  • El que responde del mismo modo ante las mismas condiciones

  • El que tiene distintas soluciones

  • El que determina los errores de un programa

  • ¿Son correctas las siguientes afirmaciones?

  • La depuración permite comprobar formalmente que un programa cumple su especificación

  • La verificación formal permite comprobar de forma rigurosa que un programa cumple su especificación

  • La verificación formal permite determinar si un programa es sintácticamente correcto.

  • Ninguna de las respuestas anteriores es cierta

  • El desarrollo descendente es:

  • El proceso de extracción de las características esenciales del problema, ignorándose los detalles superfluos

  • El proceso de descomposición de un problema por niveles cada vez más específicos

  • El proceso de desarrollo de un programa poniendo énfasis en el decremento progresivo de variables

  • La aplicación del refinamiento progresivo al proceso de construcción de un programa

  • Se recomienda usar el mecanismo de paso de parámetros por referencia

  • en funciones que no devuelvan ningún valor

  • en procedimientos que devuelvan varios valores

  • en procedimientos que sirvan para leer entradas del usuario

  • en funciones recursivas

  • Metodología y Tecnología de la Programación
    La siguiente regla de verificación implica que, en cada paso de la verificación formal

  • cualquier precondición p2 puede sustituirse por una precondición más débil p1

  • cualquier postcondición q2 puede sustituirse por una postcondición más fuerte q1

  • cualquier precondición p2 puede sustituirse por una precondición más fuerte p1

  • cualquier postcondición q2 puede sustituirse por una postcondición más débil q1

  • Si al principio de un programa se declara una variable global y en un procedimiento se utiliza el mismo nombre para declarar una variable, ¿qué sucederá?

  • El compilador detectará un error sintáctico.

  • Se detectará un error durante la ejecución del programa.

  • El compilador entenderá que se trata de una misma variable para todos los efectos.

  • El compilador entenderá que se trata de dos variables distintas para todos los efectos.

  • Las recomendaciones acerca del correcto desarrollo de procedimientos preconizan que:

  • La comunicación del subprograma con el exterior se debe realizar exclusivamente mediante parámetros

  • Todas las variables que se manejen en el procedimiento deben ser globales

  • Todas las variables que se manejen en el procedimiento deben ser locales al mismo

  • Ninguna de las respuestas anteriores es cierta

  • Se recomienda el uso de una función cuando:

  • El subprograma no devuelve ningún valor

  • El subprograma realiza un cálculo cuyo resultado ha de devolverse

  • El subprograma devuelve más de un valor

  • Ninguna de las respuestas anteriores es cierta

  • Deben utilizarse bucles REPEAT cuando:

  • No se sabe de antemano cuántas veces se ejecutará el cuerpo del bucle

  • Se sabe de antemano que el cuerpo del bucle se ejecuta n veces, n"1

  • En el cuerpo del bucle hay estructuras iterativas anidadas

  • Se sabe que el cuerpo del bucle ha de ejecutarse al menos una vez

  • La relación entre iteración y recursión es la que sigue

  • Cualquier subprograma recursivo puede expresarse mediante un subprograma iterativo

  • Cualquier subprograma iterativo puede expresarse mediante un subprograma recursivo

  • Ningún subprograma iterativo puede expresarse mediante un subprograma recursivo (y viceversa), porque recursión e iteración no tienen nada que ver

  • Existen subprogramas iterativos que no se pueden expresar por un subprograma recursivo

  • Ejercicio 2: [ 15 puntos]

    Determine si son correctas cada una de las siguientes expresiones. Si es errónea, indique el motivo de ello. Cuando sea correcta, indique el valor resultante y su tipo de datos. Cuando proceda, indique todos los tipos posibles para la variable x.

  • x <> pred (succ (x))

  • Solución: Expresión correcta. El resultado es FALSE, de tipo boolean. x puede ser de cualquiera de los tipos ordinales.

  • ln(x) and x

  • Solución: Expresión errónea. El operador AND (conjunción lógica) está definido para el tipo boolean y ln(x) nunca va ser de ese tipo.

  • 5 - 2 * 9 div 5 / 3 + 5

  • Solución: Expresión correcta. El resultado es 9.0, de tipo real.

  • x mod 2 = 1 or exp(x) < 1.5

  • Solución: Expresión errónea. El operador OR (disyunción lógica) está definido para el tipo boolean y las expresiones implicadas deben ir encerradas entre paréntesis.

    (x mod 2 = 1) or (exp(x) < 1.5)

  • sqrt(ord(false and x))

  • Solución: Expresión correcta. El resultado es 0.0, de tipo real. x tiene que ser de tipo boolean.

    Ejercicio 3: [ 15 puntos]

    ¿Qué escribe el siguiente bucle anidado en pantalla ? Consiga el mismo resultado con una única instrucción de iteración (sin anidar).

    i:= 1;

    WHILE i<=4 DO BEGIN

    k := i;

    s := 0;

    REPEAT

    s := s + i;

    k := k-1

    UNTIL k = 0;

    WriteLn(s);

    i := i + 1

    END; {While}

    Solución:

    En pantalla aparece: 1

    4

    9

    16

    Teniendo en cuenta que se sabe de antemano cuántas veces ha de ejecutarse el cuerpo del bucle (cuatro), se debería utilizar una instrucción FOR, como se muestra a continuación, para obtener el mismo resultado.

    FOR i:=1 TO 4 DO

    WriteLn(Sqr(i));

    Ejercicio 4: [ 40 puntos]

    Los números de Lukas, una variación de los números de Fibonacci, vienen dados por la sucesión:

    1,3,4,7,11,18,29,47, ....

  • Obtenga una definición recurrente para determinar el i-ésimo número de Lukas, luci , siendo i"0.

  • Escriba una función recursiva lucasRec, que dado un índice i"0, devuelva el i-ésimo número de Lukas, es decir:

  • lucasRec(0) = 1; lucasRec(1) = 3; lucasRec(2) = 4 etc.

  • Escriba una función iterativa lucasIter, que dado un índice i"0, devuelva el i-ésimo número de Lukas. Si utiliza variables locales, añada comentarios breves explicando su papel en el subprograma.

  • ¿Cuál de las dos funciones es más eficiente computacionalmente? Razone brevemente su respuesta.

  • Solución:

    a)

    1 si i = 0 Casos

    lucasRec(i) = 3 si i = 1 bases

    lucasRec(1-1) + lucasRec(i-2) si i " 2 Caso recursivo

    b)

    FUNCTION LucasRec (i : integer) : integer;

    {Precondición: i >= 0 }

    {Postcondición: LucasRec = i-simo número de Lukas}

    BEGIN

    IF i = 0 THEN

    LucasRec := 1 {Caso base 1}

    ELSE IF i = 1 THEN

    LucasRec := 3 {Caso base 2}

    ELSE

    LucasRec := LucasRec (i-1) + LucasRec (i-2)

    END; { LucasRec }

    c)

    FUNCTION LucasIter (i:integer):integer;

    {Precondición: i >= 0 }

    {Postcondición: LucasIter = i-simo número de Lukas}

    VAR

    a, {variable auxiliar que contendrá el número de Lukas i-esimo}

    a1,a2, {variables auxiliares que contendrán los números de Lukas i-1 e i-2}

    j:integer; {índice del bucle FOR}

    BEGIN

    IF i = 0 THEN

    LucasIter := 1

    ELSE IF i = 1 THEN

    LucasIter := 3

    ELSE BEGIN {i " 2}

    a:=3; {Inicialización de las variables}

    a1:=1;

    FOR j:= 2 TO i DO BEGIN

    a2:=a1;

    a1:=a;

    a := a1+a2

    END; {FOR}

    LucasIter := a

    END; { ELSE }

    END; { LucasIter }

    d)

    La versión iterativa es más eficiente, porque la función recursiva realiza VARIAS veces la MISMA llamada. Por ejemplo: LucasRec (4) llama:

    • una vez a LucasRec (3)

    • dos veces a LucasRec (2)

    • tres veces a LucasRec (1)

    • dos veces a LucasRec (0)

    Cada llamada a la función recursiva lleva asociada una tabla de activación con los datos locales de cada versión llamada. Estas tablas se almacenan en una pila en memoria y pueden representar un gran consumo de espacio si el número de llamadas crece.

    La versión iterativa calcula cada número de Lukas sólo una vez, guardándolo en una variable mientras que es útil

    Metodología y Tecnología de la Programación

    Primer parcial

    9 de febrero del 2000

    Pág. 5 / 1

    Metodología y Tecnología de la Programación

    Metodología y Tecnología de la Programación

    APELLIDOS: NOMBRE:

    ESPECIALIDAD: TURNO:

    Duración: 2 h.