Algoritmos y Estructuras de Datos I: Programación Imperativa - ALIPSO.COM: Monografías, resúmenes, biografias y tesis gratis.
Aprende sobre marketing online, desarrollo de sitios web gratis en Youtube
Suscribite para recibir notificaciones de nuevos videos:
Viernes 29 de Marzo de 2024 |
 

Algoritmos y Estructuras de Datos I: Programación Imperativa

Imprimir Recomendar a un amigo Recordarme el recurso

Algoritmos y Estructuras de Datos I Facultad de Ciencias Exactas y Naturales. Universidad de Buenos Aires Primer Cuatrimestre de 2000. Práctica 4 Programación Imperativa. Sintaxis del Lenguaje. Declaración de variables y constantes. Declaración de funciones. Lenguaje de Estados. Estructura formal de un programa imperativo. Extensión al lenguaje de estados.

Agregado: 17 de JULIO de 2003 (Por Michel Mosse) | Palabras: 5652 | Votar | Sin Votos | Sin comentarios | Agregar Comentario
Categoría: Apuntes y Monografías > Computación > Programación >
Material educativo de Alipso relacionado con Algoritmos Estructuras Datos Programación Imperativa
  • Parques Nacionales y datos detallados sobre varios animales.: ...
  • Oficios: a banco para que informe sobre datos de una cuenta corriente (art. 25 cpcc).:
  • Mandatos: oficio al registro de procesos universales.haciendo saber renuncia de mandato en una sucesion.:

  • Enlaces externos relacionados con Algoritmos Estructuras Datos Programación Imperativa

    Algoritmos y Estructuras de Datos I

    Facultad de Ciencias Exactas y Naturales

    Universidad de Buenos Aires

    Primer Cuatrimestre de 2000

    Práctica 4

    Programación Imperativa

    Fecha sugerida de finalización: 15 /06 /2000.

    Sintaxis del Lenguaje

    Sentencias del lenguaje:

    <sentencia> ::= skip

    | <VarID> := <expresión>

    | if <expresión_booleana> then <sec_sentencia>

    else <sec_sentencia> fi

    | while <expresión_booleana> do <sec_sentencia> od

    | ret_value := <expresión>

    <sec_sentencia> ::= <sentencia>;

    | <sec_sentencia>; <sentencia>;

    <expresión> ::= <expresión_booleana> | <expresión_integer> | <expresión_char>

    <expresión_booleana> ::= True

    | False

    | <variable_booleana>

    | ( <expresión_booleana> )

    | not <expresión_booleana>

    | <expresión_booleana> [and | or ] <expresión booleana>

    <expresión_integer> ::= <constante_integer>

    | <variable_integer>

    | ( <expresión_integer> )

    | <expresión_integer> [ + | - | * | div | mod] <expresión_integer>

    <expresión_char> ::= A | a | B | b | C | c | ... | Z | z

    | _ | . | , | ; | ( | ) ( _ es el caracter blanco)

    | 0 | 1 | ... | 9

    Declaración de variables y constantes:

    <declaración> ::= const

      <sec_const_declaración>

    var

      <sec_var_declaración>

    <sec_var_declaración> ::= <var_declaración>;

    | <sec_var_declaración>; <var_declaración>;

    <sec_const_declaración> ::= <const_declaración>;

    | <sec_const_declaración>; <const_declaración>;

    <var_declaración> ::= <VarId> : <Tipo> [:= <expresión>]

    <const_declaración> ::= <ConstId> : <Tipo> := <expresión>


    Declaración de funciones:

    <función> ::= function <NombreFunción> (<ListaParam>) : <TipoDevolución>

    <declaración>

    <sec_sentencia>

    endfunction

    Nota: <sec_sentencia> debe contener al menos una sentencia de la forma

    ret_value := <expresión>

    siendo <expresión> del mismo tipo que <TipoDevolución>. No es necesario declarar a ret_value ya que ésta es automáticamente declarada con el tipo de retorno declarado en la función. La función retornará como resultado el valor de la última asignación realizada sobre ret_value.

    <ListaParam> ::= <IdParam> : <Tipo>

    | <ListaParam>, <IdParam> : <Tipo>

    <Tipo> ::= integer | bool | char | lista de <Tipo> | arreglo de <Tipo>

    <TipoDevolución> ::= integer | bool | char | lista de <Tipo>

    (Las listas y los arreglos son definidos más adelante.)

    La evaluación de una función de tipo <TipoDevolución> es una <expresión_tipo>.

    Nota: Tener en cuenta que las funciones no pueden devolver el tipo arreglo.

    Ejemplo:

    function SumaLoca(x: integer, y: integer) : integer

    const

    A : integer := 4;

    var

    t : bool := False;

    b : integer;

    if t then

    b := A + A + A;

    while (b > 2) do

    b := b - 1;

    od;

    else

    skip;

    fi;

    ret_value := (x+y);

    endfunction

    Además, Suma (3, 7) es una <expresión_integer>.

    Lenguaje de Estados:

    Para describir un instante de la ejecución de un programa, utilizaremos predicados. Estos definen un conjunto de posibles valores que pueden tomar las variables de dicho programa, es decir, un conjunto de posibles estados. Estos predicados los escribiremos entre llaves.

    Se pueden usar expresiones del lenguaje de la lógica de primer orden, extendido con cualquier función escrita en el lenguaje funcional. Para evitar posibles confusiones con las funciones del lenguaje imperativo se agrega una ´f´ minúscula y un guión bajo delante de las funciones del lenguaje funcional.

    Sólo pueden aparecer libres dentro de un estado las variables que fueron declaradas previamente dentro de una función o procedimiento (esto incluye a los parámetros).

    En una función los parámetros son pasados por copia, por lo tanto, al finalizar la función no se reflejan los cambios realizados en los parámetros, dado que se trabajó con copias. Por lo tanto, la postcondición de una función describe los posibles estados que poseen las variables inmediatamente antes de finalizar la función. Esto significa que si en la postcondición aparecen variables que, o bien son locales a la función o bien son parámetros de la misma, sus valores sólo tienen sentido en el contexto de la función (en el caso de variables locales a la función, éstas ni siquiera serán visibles fuera de ella).

    Además, se puede utilizar:

    {x = X0} [X0 es el valor que toma la variable x en cierto momento. Escribiremos las variables con
    minúsculas y la representación de sus valores con mayúsculas.]

    Ejemplos:

    { ("y) ( y < x Þ Primo (x) ) Ù Par (w) Ù w mod 5 = W0 }

    Donde Primo y Par son predicados.

    { ( N0>M0 Ù ret_value = f_mcd(N0,M0) ú (N0<=M0 Ù ret_value= M0) }

    Donde mcd es una función en lenguaje funcional

    Estructura formal de un programa imperativo

    Toda función (o procedimiento como veremos más adelante) implementada en lenguaje imperativo tiene una precondición (lo llamaremos P) que indica que condiciones deben cumplirse para que la función se ejecute correctamente, esto es que valores tienen los parámetros y si éstos deben cumplir con algún requisito en particular. También debemos indicar cual es la postcondición (lo llamaremos Q) de la función, esto es, que resultado devolverá en caso de que se cumplan los requisitos especificados en P. Especificar tanto la precondición como la postcondición permiten conocer de forma no ambigua que es lo que hace la función facilitando su correcto uso para los usuarios de la misma o su correcta implementación para los responsables de realizarla.

    En el caso de que la función posea un ciclo es muy importante especificar formalmente cual es la precondición del ciclo (lo llamaremos Pc), su invariante (lo llamaremos I), la guarda del ciclo (la llamaremos B), la función variante (la llamaremos fv) y la postcondición del ciclo (lo llamaremos Qc). Esta especificación formal nos permitirá deducir fácilmente como implementar el código del ciclo y además verificar que el ciclo funcione correctamente y nos acerque a la postcondición de la función. En todo momento debemos explicitar el valor de las variables de nuestro programa. Esto nos permitirá verificar que nuestro programa es correcto, es decir, que realiza lo que la especificación determina.

    Veamos un ejemplo de una función enriquecida con el lenguaje de estados:

    function sumaN (n : Integer ) : Integer

    P º { n = N Ù N>0 }

    var

    acum: Integer := 0;

    i: Integer :0 ;

    Pc º { acum = 0 Ù i= 0 Ù n= N Ù N>0 }

    notar que en el Pc aparecen nuevas variables que necesitamos para la implementación del ciclo.

    I º { acum = f_sumaN(i) Ù 0<=i<=n Ù n= N Ù N>0}

    B º { i<n }

    fv = n - i debe ser estrictamente decreciente y acotada inferiormente

    se debe cumplir { I }

    while i<n do

    se debe cumplir { I Ù B }

    i := i + 1,

    acum := acum + i;

    se debe cumplir{ I }

    od;

    se debe cumplir { I Ù ØB } º { acum = fsumaN(i) Ù i=n } y como se ve esto debe implicar Qc

    Qc º { acum = f_suma(N) Ù n= N Ù N>0}

    ret_value = acum;

    Q º { ret_value = f_sumaN(N) }

    Endfunction

    Definimos en gofer:

    sumaN :: Int -> Int

    sumaN 0 = 0

    sumaN (n+1) = (n+1) + sumaN n

    Es importante verificar que el invariante debe cumplirse en todas las fases del ciclo: antes de entrar, apenas entra, antes de salir, y terminado el ciclo. Además finalizado el ciclo, la negación de la guarda del ciclo y el invariante deben cumplirse y deben implicar a la postcondición del ciclo. También hay que verificar que la función variante sea siempre decreciente mientras se cumpla la condición del ciclo.

    Se debe evitar el uso de ciclos anidados, porque complican innecesariamente la confección y verificación de los invariantes trayendo como posible consecuencia errores no detectados en la implementación. En el caso de que se deba realizar un programa que posea un ciclo dentro de otro, lo más aconsejable es implementar una función auxiliar que provea la funcionalidad del ciclo interior.

    Ejercicio 1

    1.1 Dada la función Producto(n:integer,m:integer):integer que devuelve el producto entre m y n, indicar :

    i. Cual es la precondición adecuada para la función

    a)       P º {n=N0 Ù m=M0}

    b)       P º TRUE

    ii. Cual es la postcondición adecuada para la función

    a)       Q º {ret_value = m*n}

    b)       Q º {ret_value = M0*N0}

    c)       Q º TRUE

    iii. Suponiendo que la idea de implementación de la función es la siguiente:

    Realizar un ciclo que sume el parámetro m tantas veces como lo indica el valor absoluto del parámetro n. Indicar cuales son los Pc, Qc, I, B y Fv que mejor se adecuan a la idea de este ciclo. Suponer una precondición donde vale que: n = n0 Ù m = m0

    a) Pc º P

    B º {i £ f_abs m}

    I º {ret_value = n * i}

    Fv = m-i

    Qc º Q

    b) Pc º {ret_value = 0 Ù i =0 Ù n = n0 Ù m = m0}

    B º {i < f_abs n }

    I º {ret_value = m*i Ù 0 £ i £ (f_abs n) Ù n = n0 Ù m = m0}

    Fv = (f_abs n) - i

    Qc º {ret_value = (f_abs n) * m Ù n = n0 Ù m = m0}

    c)  Pc º {ret_value = 0 Ù i =0 Ù n = n0 Ù m = m0}

    B º {i £ n}

    I º {ret_value = m*i Ù 1 £ i £ n Ù n = n0 Ù m = m0}

    Fv = abs n - i

    Qc º {ret_value = n * m}

    Nota: Definimos la función abs :: Int ® Int como:

    abs n = if n > 0 then n else -n.

    iv. Chequear que las opciones elegidas en los puntos anteriores concuerdan con el siguiente programa..

    function Producto(n:integer,m:integer):integer

    var

    i:integer

    i := 0;

    ret_value := 0;

    while i<Abs(n) do

    i = i + 1;

    ret_value = ret_value + m;

    od;

    if n ³ 0 then skip

     else ret_value = -ret_value

    fi;

    endfunction

    function Abs(n:integer):integer

    if n > 0 then ret_value = n

    else ret_value = -n

    fi

    endfunction

    Escribir la precondición y postcondición adecuadas para la función Abs.

    a.           Dada la función Es_Primo(n: integer): bool que devuelve TRUE si n es primo y FALSE en caso contrario indicar:

    i. Cual es la precondición adecuada para la función

    a)       P º {n=N0 }

    b)       P º {TRUE}

    ii. Cual es la postcondición adecuada para la función

    a)       Q º {n=N0 }

    b)       Q º { (ret_value = TRUE Ù Es_primo(N0) ) ú (ret_value = FALSE ) }

    c)       Q º { (ret_value = f_primo(N0) ) }

    Siendo Es_Primo un predicado y primo una función de lenguaje funcional

    Ejercicio 2

    Escribir el código de las siguientes funciones respetando la especificación de estados dada. Las funciones en lenguaje funcional se corresponden con las realizadas en ejercicio 2 de la práctica 2.

    i.                     Potencia(n:integer,m:integer):integer

    P º {n = N0 Ù m = M0 Ù (N0 = 0 Þ M0 ¹ 0) Ù M0 ³ 0}

    Pc º {i = 0 Ù ret_value = 1 Ù P}

    B º {i < m}

    I º {ret_value = f_potencia n i Ù 0 £ i £ m Ù n = N0 Ù m = M0 Ù (N0 = 0 Þ M0 ¹ 0) Ù M0 ³ 0}

    Fv = m - i

    Qc º Q º {ret_value = f_potencia N0 M0}

    ii.                    Factorial(n:integer):integer

    P º {n = N0 Ù N0 ³ 0}

    Pc º {i = 0 Ù ret_value = 1 Ù P}

    B º {i < n}

    I º {ret_value = f_factorial i Ù 0 £ i £ n Ù n = N0 Ù N0 ³ 0 }

    Fv = n - i

    Qc º Q º {ret_value = f_factorial N0}

    iii.                  Fibonacci(n:integer):integer

    P º {n = N0 Ù N0 ³ 0}

    Pc º {i = 1 Ù a=1 Ù b=0 Ù ret_value = 1 Ù P}

    B º {i < n}

    I º {ret_value = a+b a=f_N_fibonacci i Ù b = f_N_fibonacci (i-1) Ù 0 £ i £ n Ù n = N0 Ù N0 ³ 0}

    Fv = n - i

    Qc º {ret_value = a+b Ù a=f_N_fibonacci N0 Ù b = f_N_fibonacci (N0-1) Ù n = N0 Ù N0 ³ 0}

    Q º {ret_value = f_ N_fibonacci N0}

    Ejercicio 3

    Dadas las siguientes funciones expresadas en lenguaje coloquial, indicar cuales es la precondición y postcondición adecuada para cada una.

    a)       La función RaizEnesima, que recibe el número al que se le quiere calcular la raíz (n), y el índice (i).

    i)                     { n= N0}

    ii)                   { ret_value = f_raizEnesima I0 N0 Ù j = 0 }

    iii)                  {TRUE}

    iv)                 { ret_value = f_raizEnesima I0 ret_value0 }

    v)                   { i=I0  Ù n=N0 Ù ret_value = ret_value0 }

    vi)                 { ret_value = f_raizEnesima I0 N0 Ù i = 0 }

    vii)                { i=I0  Ù n=N0 Ù I0 > 0 Ù ( par(I0) Þ N0 ³ 0) }

    viii)              { i=I0  Ù n=N0 Ù N0 > 0 Ù ret_value = ret_value0 }

    ix)                  { ret_value = f_raizEnesima I0 N0 }

    a)       La función menorPrimoTresCifras, que devuelve el menor número primo de tres cifras

    i)                     {TRUE}

    ii)                   { i=I0  Ù n=N0 Ù ( par(I0) Þ N0 ³ 0) }

    iii)                  { ret_value = N0 }

    iv)                 { ret_value = 101 }

    v)                   { Par (8) }

    vi)                 { ret_value = f_menorPrimo3Cifras( a ) }

    Ejercicio 4

    i.                     Determinar si la siguiente especificación concuerda con el código de programa dado. Justificar.

    P º{ n = N0 Ù m = M0 Ù N0 <= M0 }

    Pc º { i = n Ù ret_value º false Ù n = N0 Ù m = M0 Ù N0 <= M0 }

    I º { (ret_value º ($k)((n <= k < i - 1) Ù es_cuadrado(k))) Ù (n <= i <= m + 1)

      Ù n = N0 Ù m = M0 Ù N0 <= M0 }

    B º ( i <= m )

    Fv = m - i

    Qc º Q º{ ret_value º ($k)(( N0 <= k <= M0) Ù es_cuadrado?(k)) }

    Donde es_cuadrado?(k) º ($j) (j*j = k)

    Function Hay_algun_cuadrado(n: integer, m: integer):bool

    Var:

    i :integer;

    temp: integer;

    If m > n then

    temp := n;

    n := m;

    m := temp;

    fi

    i = m;

    ret_value := false;

    while (i > n) do

    ret_value := ret_value ú Cuadrado?(i);

    i := i - 1;

    od

    endfunction

    Nota: La función Cuadrado? devolverá True si el número pasado como parámetro es un cuadrado perfecto.

    ii.                    En caso de no encontrar concordancia en el ejercicio i.), escribir un código que respete los estados dados y enunciar los estados con los cuales se corresponde el código de programa descripto en el punto anterior.

    En caso contrario, pensar otra manera de plantear y resolver el mismo problema.

    Ejercicio 5

    Dada la función SumaMenores cuya idea de implementación es la siguiente:

    Dados dos números naturales n y m , se devuelve la suma de todos los números naturales menores o iguales al primero que son múltiplos del segundo.

    Por ejemplo:

    SumaMenores(8,2) = 20 (2+4+6+8)

    SumaMenores(10,3) = 18 (3+6+9)

    SumaMenores(10,12) = 0

    Para ello, utiliza un ciclo que implementa la idea de la función.

    Decidir cuáles de los siguientes P, Pc, I, Fv, B, Qc Q se adecuan a la idea de este ciclo y de esta función y cuáles no. Justificar en cada caso.

    a)

    i)

    P º {ret_value = 0}

    Pc º P

    B º {n > 0}

    I º {n ³ 0 Ù ret_value = f_SumMenMul N0 M0}

    Fv º n

    Qc º {n=0 Ù ret_value = f_SumMenMul N0 M0}

    Q º Qc

    ii)

    P º {n=N0 Ù m =M0}

    Pc º {ret_value = 0 }

    B º {n > 0}

    I º {n ³ 0 Ù ret_value = f_SumMenMul n m}

    Fv º n

    Qc º {n=0 Ù ret_value = f_SumMenMul n m}

    Q º {ret_value = f_SumMenMul N0 M0}

    iii)

    P º {n=N0 Ù m=M0}

    Pc º {ret_value=0 Ù m = M0}

    B º {n > 0}

    I º {n ³ 0 Ù ("i)(n £ i £ N0 Ù Multiplo(i, M0) Þ ret_value = ret_value + i) Ù m = M0}

    Fv º n

    Qc º {n=0 Ù ("i)(0 £ i £ N0 Ù Multiplo(i, M0) Þ ret_value = ret_value + i) Ù m = M0}

    Q º {("i)(0 £ i £ N0 Ù Multiplo(i, M0) Þ ret_value = ret_value + i)}

    iv)

    P º {n=N0 Ù m =M0}

    Pc º {ret_value = 0 Ù m = M0 Ù n=N0}

    B º {n > 0}

    I º {n ³ 0 Ù ret_value = (f_SumMenMul N0 M0) - (f_SumMenMul n M0) Ù m = M0}

    Fv º n

    Qc º {n=0 Ù ret_value = f_SumMenMul N0 M0 Ù m = M0}

    Q º {ret_value = f_SumMenMul N0 M0}

    Donde SumMenMul es:

    SumMenMul::Nat ® Nat ®Nat

    SumMenMul 0 m = 0

    SumMenMul n m = (if Divide_a(n,m) then n else 0) + (SumMenMul (n-1) m)

    b) Escribir el código de esta función.

    c) Verificar que el cuerpo del ciclo, en las sucesivas iteraciones, preserva el invariante.

    Ejercicio 6

    Escribir el código de las siguientes funciones respetando la especificación de estados dada. No utilizar las funciones DIV y MOD. Especificar los invariantes y las funciones variantes en los casos en los cuales incluyan ciclos. En cada caso especificar la precondición y postcondición del ciclo y demostrar los siguientes puntos:

    ¨        Vale el invariante antes de entrar al ciclo.

    ¨        El cuerpo del ciclo preserva el invariante.

    ¨        La función variante es monótona decreciente y posee un cota inferior mayor o igual a cero.

    ¨        I Ù ØB => Q

    i.                    Resto(n:integer,m:integer):integer

    P º {n = N0 Ù m = M0 Ù M0 > 0}

    Q º {ret_value = f_resto N0 M0}

    ii.                  División_entera (n: integer, m: integer) : integer

    P º { n = N0 Ù m = M0 Ù M0 > 0}

    Q º { ret_value = fdiv N0 M0}

    iii.                 MCD (n: integer, m: integer) : integer, que devuelve el máximo común divisor de n y m.

    P º { n = N0 Ù m = M0 Ù Ø (N0 = 0 Ù M0 = 0) }

    Q º { ret_value = f_mcd N0 M0}

    Ejercicio 7

    Escribir el código y los estados de las siguientes funciones. Demostrar los mismos puntos que en el ejercicio anterior.

    i.                         Num_combinatorio (n: integer, m: integer) : integer

    ii.                      Divisor (n: integer, m: integer) : bool, que determina si el primer parámetro divide al segundo.

    iii.                  Cuadrado_perfecto (n: integer) : bool

    iv.                  Suma_divisores (n: integer) : integer, que devuelve la suma de los divisores de n.

    v.                   Primo (n: integer) : bool

    vi.                  Siguiente_primo (n: integer) : integer, que devuelve el primer primo mayor que n.

    vii.                Cantidad_de_primos (n: integer) : integer, que devuelve la cantidad de primos entre 0 y el parámetro.

    Arreglos y Listas

    En Programación Funcional utilizábamos listas para modelar cualquier colección de elementos del mismo tipo, en donde interesa el orden en que los elementos son agregados, y se permitían elementos repetidos.

    En Programación Imperativa es necesario utilizar alguno de los tipos permitidos en el lenguaje para escribir esas listas usadas en Funcional. Vamos a trabajar con dos estructuras:

    ü       Aquellas de las que podemos calcular su tamaño en el momento de la definición. Las llamamos arreglos o vectores.

    ü       Aquellas de las que no sabemos el tamaño hasta que no terminamos de armarlas. Las llamamos listas.

    Dado que sólo diferenciamos arreglos y listas según lo descripto en las propiedades anteriores, no consideramos una estructura más costosa que la otra. Sólo nos interesa, ante un problema, elegir en forma adecuada entre una y otra; para ello basta identificar si se sabe el tamaño o no.

    El tamaño de los arreglos sólo puede definirse a partir de constantes. Los arreglos se pueden asignar entre arreglos de igual tamaño. Una lista se puede asignar a cualquier otra lista. Una función puede recibir arreglos y listas como parámetro, y devolver sólo una lista. No es posible para una función devolver un arreglo.

    A continuación, se extiende la Sintaxis del Lenguaje, agregándole la manera de declarar y utilizar los arreglos y las listas.

    Arreglos:

    Declaración:

    <Nombre_Arreglo>[0..<constante_integer>] : arreglo de <Tipo>

    Esta línea (declaración) se agrega como una opción más en la definición de <var_declaración> en la Sintaxis del Lenguaje. El valor de <constante_integer> debe ser mayor que cero.

    Importante: Notar que la dimensión del arreglo es fijada en la definición del mismo y no puede ser cambiada luego. Dicha dimensión solo puede ser declarada a partir de una constante. No es posible utilizar variables.

    Asignación de un elemento:

    <Nombre_Arreglo>[<expresión_integer>] := <expresión>

    El valor de la <expresión_integer> debe ser mayor o igual a cero y menor que la dimensión (tamaño) del arreglo.

    Asignación completa:

    <Nombre_Arreglo1> = <Nombre_Arreglo2>

    Ambos arreglos deben ser del mismo tipo y deben tener el mismo tamaño.

    Inspección:

    <Nombre_Arreglo>[<expresión_integer>] : <expresión>

    El valor de la <expresión_integer> debe ser mayor o igual a cero, y menor que la dimensión del arreglo.

    La inspección de un arreglo de tipo <Tipo> es una <expresión_tipo>.

    Dimensión:

    dim (<Nombre_Arreglo>) : integer

    Estas tres líneas (asignación, inspección y dimensión) se agregan como nuevas opciones en la definición de <sentencia> en la Sintaxis del Lenguaje.

    Ejemplo:

    function Egoman(a : arreglo de integer) : bool

    var b[0..5] : arreglo de integer;

    b[0] = 5;

    b[b[0] - 4] = a[0];

    b[2] = a[dim (a)-1];

    ret_value = True;

    endfunction

    En el ejemplo, b[0], b[b[0] - 4], a[0], etc., son todas <expresión_integer>.

    Nota Importante: Las funciones NO pueden retornar arreglos

    Extensión al lenguaje de estados

    Referir un elemento del arreglo: <Nombre_Arreglo>[<expresión_integer>] 

    Dimensión del arreglo: dim(<Nombre_Arreglo>)

    No es posible utilizar directamente funciones del lenguaje funcional que operan sobre listas (por ejemplo take) para operar sobre arreglos. Para poder hacerlo se utilizará la notación especial A^n, donde A es un arreglo de tipo <Tipo> y n es una expresión de tipo integer. A^n denota la lista de longitud n cuyos elementos son los primeros n elementos del arreglos A (en el mismo orden) siendo n una <expresión_integer> mayor que cero y menor que dim(A).

    Ejemplo:

    { ret_value = f_suma take (A^dim(a) 4) }

    siendo suma una función en lenguaje funcional que toma una lista de enteros y retorna su suma.

    Listas:

    Declaración:

    <Nombre_Lista> : lista de <Tipo>

    Esta línea (declaración) se agrega como una opción más en la definición de <var_declaración> en la Sintaxis del Lenguaje.

    Procedimientos:

    Agregar (<Nombre_Lista>, <expresión>) (Agrega al principio de la lista.)

    Cola (<Nombre_Lista>) (Elimina el primer elemento de la lista.)

    <Nombre_Lista1> := <Nombre_Lista2>

    Notar que Agregar y Cola modifican la misma lista que es tomada como parámetro. Esta es una diferencia fundamental con la programación funcional, ya que en esta última esto no es posible.

    Inspección:

    primero(<Nombre_Lista>) : <expresión> (retorna el primer elemento de

    la lista)

    La inspección de una lista de tipo <Tipo> es una <expresión_tipo>.

    Longitud:

    long (<Nombre_Lista>) : integer (retorna la longitud de la lista)

    Agregar, Cola, Primero, y Longitud se agregan como nuevas opciones en la definición de <sentencia> en la Sintaxis del Lenguaje.

    Ejemplo:

    function Egoman2() : bool

    var

    L : lista de integer; /* L = [ ] */

    i : integer;

    Agregar (L, 1); /* L = [ 1 ] */

    Agregar (L, 4); /* L = [ 4, 1 ] */

    Agregar (L, long (L) + 1); /* L = [ 3, 4, 1 ] */

    i:=Primero(L) /* i = 3 */

    Cola (L); /* L = [ 4, 1 ] */

    while not (long (L) == 0) do

    Cola(L)

    od;

    /* L = [ ] */

    ret_value = True;

    endfunction

    Extensión al lenguaje de estados

    En el caso de las listas se puede utilizar cualquier función de Gofer que opere sobre listas.


    Ejercicio 8

    Dadas las siguientes funciones expresadas en lenguaje coloquial, indicar cual es la precondición y postcondición adecuada para cada una.

    a)       La función normaDos, que recibe un arreglo (a), cuyas posiciones representan las coordenadas de un vector, y calcula la raíz de la sumatoria del cuadrado de todos los elementos.

    i)                     { a=A0 }

    ii)                   { ret_value = normaDos A0 }

    iii)                  {TRUE}

    iv)                 { a=A0 Ù ret_value = ret_value0 }

    v)                   { ret_value = f_normaDos A0^ Dim( A0 ) }

    vi)                 { ret_value = }

    a)       La función partirLista, que recibe una lista (l) y un natural(n) que indica alguna posición dentro de la misma y devuelve otra lista que contiene en el medio al elemento que indica la posición del parámetro, a la derecha de éste todos los elementos menores y a la izquierda todos los elementos mayores o iguales.

    i)                     { l=L0 Ù n=N0  Ù N0 < Long(L0) }

    ii)                   { l=L0  Ù n=N0}

    iii)                  {TRUE}

    iv)                 { ret_value = f_partirLista L0 }

    v)                   { ( f_mismosElementos L0 ret_value ) Ù ("i) ( 0 £i £ Long(L0) Þ

    (i < N0 Ù ( f_iesimo ret_value i ) < ( f_iesimo L0 N0 )) ú

    (i ³ N0 Ù ( f_iesimo ret_value i) ³ (f_iesimoL0 N0)) }

    vi)                 { l=L0  Ù n=N0 Ù N0 >0 }

    vii)                { l=L0 Ù ret_value = ret_value0 }

    viii)              { ("i) ( 0 £i £ Long(L0) Þ (i < N0 Ù (f_iesimo ret_value i) < (f_iesimo L0 N0)) ú

    (i ³ N0 Ù (f_iesimo ret_value i) ³ (f_iesimo L0 N0)) }

    Ejercicio 9

    a) Explicar coloquialmente que hace la función dadas las siguientes precondiciones y postcondiciones:

    i. P { n = N0 }

    Q { n = N0 Ù ret_value = ( N0 ¹ 0 Ù (f_Abs N0 ) ¹ 1 Ù

    ( "k ) ( 2 £ k < (f_Abs N0 ) Þ Ø Divide_a ( k , N0 ) ) ) }

    Divide_a ( x , y ) es un predicado que es verdadero cuando el primer parámetro divide al segundo y falso en caso contrario. Abs es una función especificada en funcional que devuelve el valor absoluto del entero pasado como parámetro. El parámetro n es de tipo integer.

    ii. P { n = N0 }

    Q { n = N0 Ù Primo( ret_value ) Ù ret_value > N0 Ù ( "k ) ( N0 £ k < ret_value Þ Ø Primo( k ) )}

    Primo (x) es un predicado que es verdadero si el número es primo y falso en caso contrario. El parámetro n es de tipo integer.

    iii. P { a = A0 }

    Q { a = A0 Ù ret_value = ( "k ) ( 0 £ k < dim( A0 ) Þ Par ( A0 [k] ) ) }

    Par (x) es un predicado que es verdadero si el número es par y falso en caso contrario. El parámetro a es de tipo arreglo de integer.

    iv. P { a = A0 Ù n = N0}

    Q { a = A0 Ù ( ( 0 £ ret_value < dim( A0 ) Ù ( "k ) ( 0 £ k < ret_value Þ A0 [k] ¹ N0 ) Ù

    A0 [ret_value] = N0 ) ú ( ret_value = -1 Ù ( "k ) ( 0 £ k < dim( A0 ) Þ A0 [k] ¹ N0 ) ) )}

    El parámetro a es de tipo arreglo de integer y el parámetro n es de tipo integer.

    b) Dadas las siguientes modificaciones en los estados, explicar si el comportamiento de la función podría ser diferente y en el caso de que pueda serlo, explicar de que manera:

    i.                    

    1. P { n = N0 }

    Q { ret_value = ( "k ) ( 2 £ k < (f_Abs N0 ) Þ Ø Divide_a ( k , N0 ) )}

    2. P { n = N0 }

    Q { ret_value = Primo( N0 ) }

    ii .

    1. P { n = N0 }

    Q { Primo( ret_value ) Ù ( "k ) ( N0 £ k < ret_value Þ Ø Primo( k ) )}

    2. P { n = N0 }

    Q { Primo( ret_value ) }

    iii.

    P { a = A0 }

    Q { a = A0 Ù ret_value = ( "k ) ( 0 £ k < dim( A0 ) Þ Divide_a ( 2 , A0[k] ) ) }

    iv.

    P { a = A0 Ù n = N0}

    Q { a = A0 Ù ( ( 0 £ ret_value < dim( A0 ) Ù ( "k ) ( 0 £ k < ret_value Þ A0 [k] ¹ N0 ) Ù

    A0 [ret_value] = N0 ) ú ( ret_value = -1 ) )}

    Ejercicio 10

    Escribir las siguientes funciones, con sus correspondientes precondición y postcondición. Escribir el invariante y la función variante en los casos que tengan ciclos.

    i.                    AgregarAtras(L:lista de integer, elem: integer): lista de integer, que retorna una nueva lista con el elemento elem agregado atrás. (Hint: Tomar en cuenta que al pasar de una lista a otra con el agregar por adelante, la lista se invertirá!)

    ii.                  i-esimo(L: lista de integer) : integer, que retorna el iésimo elemento de la lista.

    Ejemplo: i-esimo([1,2,3],0) = 1, i-esimo([1,2,3],2) = 3

    iii.                 Asignar (L:lista de integer, pos: integer, elem: integer): lista de integer, que retorna una nueva lista igual a la original excepto que en la posición pos estará asignado el elemento elem. En el caso que pos sea mayor que long(L) , se retornará la lista original..

    iv.                Comienzo (L: lista de integer) : lista de integer,
    y último (L: lista de integer) : integer
    Ejemplos: Comienzo ([1, 2, 3]) es [1, 2] y último ([1, 2, 3]) es 3.

    v.                  Reverse (A: arreglo de integer) : lista de integer
    Ejemplo: Reverse ([1, 2, 3]) es la lista [3, 2, 1].

    vi.                Capicúa (A: arreglo de integer) : bool
    Ejemplo: Capicúa ([1, 2, 3, 2, 1]) es True.

    Ejercicio 11

    Escribir las siguientes funciones, con sus respectivas precondición y postcondición. Escribir el invariante y la función variante en los casos que incluyan ciclos.

    iv.                Limpiar_duplicados, que a partir de una lista de enteros devuelve otra compuesta por las primeras apariciones de los elementos que estaban en la primera, manteniendo el orden que tenían en ésta.

    Ejemplo: Limpiar_duplicados ([1, 3, 8, 3, 9, 8, 1]) devuelve [1, 3, 8, 9]

    v.                  Apariciones, que a partir de una lista de enteros devuelve otra lista de enteros, conformada de la siguiente manera: en las posiciones impares figuran los mismos enteros de la lista original, en el mismo orden y filtrando los duplicados. Además, en la siguiente posición de cada uno de ellos (es decir, en las posiciones pares) figura la cantidad de veces que éste aparece en la lista original.

    Ejemplo: Apariciones ([1, 3, 8, 3, 9, 8, 1]) devuelve [1, 2, 3, 2, 8, 2, 9, 1]

    vi.                Elevar_al_cuadrado, que a partir de un arreglo de enteros devuelve una lista, compuesta por los elementos que aparecen en el primero elevados al cuadrado (manteniendo el orden).

    Ejemplo: Elevar_al_cuadrado ([1, 3, 8, 3]) devuelve [1, 9, 64, 9]

    vii.               Ordenar, que toma un arreglo de enteros y devuelve una lista , igual al arreglo original, pero ordenado en forma decreciente. Ejemplo: Ordenar ([1, 3, 8, 3, 2]) devuelve [8, 3, 3, 2, 1]

    Ejercicio 12

    Definir las siguientes funciones, con sus respectivas precondición y postcondición, usando listas de caracteres. Escribir el invariante y la función variante en los casos que incluyan ciclos.

    i.                    Prefijo (L: lista de char, M: lista de char) : bool,
    y Sufijo (L: lista de char, M: lista de char) : bool

    Ejemplos: Prefijo ([a, b, c], [a, b, c, d]) es True, y Prefijo ([a, b, c], [a, c, d, b]) es False.
    Sufijo ([c], [c, d, b, a]) es False, y Sufijo ([b, c, a], [d, b, c, a]) es True.

    ii.                  Subcadena (L: lista de char, M: lista de char) : bool, que verifica si el primer parámetro está contenido en el segundo.

    iii.                 Sacar_primero (L: lista de char, M: lista de char) : lista de char, que elimina la primera aparición del primer parámetro en el segundo.

    Ejemplos: Sacar_primero ([c, a], [a, c, a, d, c, a]) devuelve [a, d, c, a].

    Sacar_primero ([a, c], [a, b, c]) devuelve [a, b, c].

    iv.                Sacar_todos (L: lista de char, M: lista de char) : lista de char, que elimina las apariciones del primer parámetro en el segundo.

    Ejemplos: Sacar_todos ([c, a], [a, c, a, d, c, a]) devuelve [a, d].

      Sacar_todos ([a, c], [a, a, c, c, a, b, c]) devuelve [a, c, a, b, c].


    Votar

    Ingresar una calificación para del 1 al 10, siendo 10 el máximo puntaje.

    Para que la votación no tenga fraude, solo se podrá votar una vez este recurso.

    Comentarios de los usuarios


    Agregar un comentario:


    Nombre y apellido:

    E-Mail:

    Asunto:

    Opinión:



    Aún no hay comentarios para este recurso.
     
    Sobre ALIPSO.COM

    Monografias, Exámenes, Universidades, Terciarios, Carreras, Cursos, Donde Estudiar, Que Estudiar y más: Desde 1999 brindamos a los estudiantes y docentes un lugar para publicar contenido educativo y nutrirse del conocimiento.

    Contacto »
    Contacto

    Teléfono: +54 (011) 3535-7242
    Email:

    Formulario de Contacto Online »