Algoritmos y Estructuras de Datos I

Facultad de Ciencias Exactas y Naturales

Universidad de Buenos Aires

Primer Cuatrimestre de 2000

Práctica 5

Procedimientos

Fecha sugerida de finalización: 7 /7 /2000.

Declaración de procedimientos: (Continuación de la sintaxis definida en la Práctica 4.)

<procedimiento> ::= procedure <NombreProcedimiento> (<ListaParamInOut>)

<declaración>

<sec_sentencia>

endprocedure

<ListaParamInOut> ::= [in | out | in-out] <IdParam> : <Tipo>

| <ListaParamInOut>, [in | out | in-out] <IdParam> : <Tipo>

En los procedimientos no existe la variable ret_value, ya que un procedimiento no devuelve ningún valor.

El llamado a un procedimiento es una <sentencia>.

Nota: En los ejercicios donde se pide definir funciones o procedimientos se deben escribir las precondiciones y postcondiciones de cada uno. Además hay que plantear los invariantes y las funciones variantes en los casos en los cuales incluyan ciclos y realizar todas las demostraciones correspondientes.

Ejercicio 1

Dado un procedimiento que recibe una matriz cuadrada y la invierte, indicar cual es la precondición, y postcondición adecuadas.

i)                     { ret_value = f_invertirMatriz M₀ }

ii)                   { n m = N₀ M₀}

iii)                  { f_esMatrizIdentidad? ( f_multiplicarMatrices N₀ m n) }

iv)                 { n = N₀ Ù m = M₀}

v)                   { n m = N₀ M₀ Ù esSimetrica?( in/out: N₀ M₀ ) }

vi)                 { f_esMatrizIdentidad? ( f_multiplicarMatrices M₀ m ) }

vii)                TRUE

viii)              { n m = invertirMatriz(in/out: N₀M₀) }

ix)                  { ("i)("j) ( 1 £i £ Dim(nm) Ù 1 £j £ Dim(nm) Þ ( i =j Ù valor(nm,i,j) = 1 )ú ( Ø(i = j) Ù valor(nm,i,j) = 0 ) ) }

x)                    { m = M₀ Ù f_esNoSingular? M₀ }

xi)                  { f_esLaInversa? n m }

xii)                 { ret_value = invertirMatriz(in/out N₀M₀) }

Ejercicio 2

Dado un procedimiento cuyas Precondición y Postcondición son las siguientes :

I P º { L = L₀ }

Q º { Par( f_Long( L ) ) Ù ElementosPares ( L , L₀ ) Ù ParesDistintos(L) Ù ( " i ) ( 0 £ i < f_Long( L )-1

Ù Par ( i ) Þ f_Iésimo ( L , i + 1 ) = f_Apariciones ( f_Iésimo( L , i ) , L₀ ) ) }

donde :

ElementosPares ( L , M ) º ( " i ) ( $ j ) ( 0 £ i < f_Long( L ) Ù Par ( i ) Ù 0 £ j < f_Long( M ) Þ

( $ j ) (0 £ j < f_Long( M ) Ù f_Iésimo( L, i ) = f_Iésimo( M, j ) ) ) Ù

( " i ) ( $ j ) ( 0 £ j < f_Long( L ) Ù Par ( j ) Ù 0 £ i < f_Long( M ) Þ

( $ j ) ( 0 £ j < f_Long( L ) Ù Par ( j ) Ù f_Iésimo( L, i ) = f_Iésimo( M, j ) ) )

ParesDistintos( L ) º ( " i )(" j ) ( 0 £ i < f_Long( L ) Ù Par ( i ) Ù 0 £ j < f_Long( L ) Ù Par ( j ) Ù i¹j Þ

f_Iésimo( L, i ) ¹ f_Iésimo( L, j ) )

Long( L ) es una función que devuelve la longitud de la lista pasada como parámetro

Iésimo( L , n ) es una función que devuelve el elemento de la lista L que está en la posición n

Apariciones( n, L ) es una función que devuelve la cantidad de apariciones del elemento n en la lista L

Explicar coloquialmente cual cuál es el comportamiento del procedimiento.

Explicar que qué sucedería si se realizaran los siguientes cambios :

i. Q º { Par( f_Long( L ) ) Ù ParesDistintos(L) Ù ( " i ) ( 0 £ i < f_Long( L ) - 1

Ù Par ( i ) Þ f_Iésimo ( L , i + 1 ) = f_Apariciones ( f_Iésimo( L , i ) , L₀ ) ) }

ii. Q º { Par( f_Long( L ) ) Ù ElementosPares ( L , L₀ ) Ù ( " i ) ( 0 £ i < f_Long( L ) - 1

Ù Par ( i ) Þ f_Iésimo ( L , i + 1 ) = f_Apariciones ( f_Iésimo( L , i ) , L₀ ) ) }

iii. Q º { ElementosPares ( L , L₀ ) Ù ParesDistintos(L) Ù ( " i ) ( 0 £ i < f_Long( L ) - 1

Ù Par ( i ) Þ f_Iésimo ( L , i + 1 ) = f_Apariciones ( f_Iésimo( L , i ) , L₀ ) ) }

Ejercicio 3

Escribir los siguientes procedimientos:

i.                     El procedimiento Incrementar que recibe un entero y le suma 1.

ii.                    Un procedimiento que recibe dos enteros y los devuelve ordenados: el mayor en el primer parámetro y el menor el segundo.

iii.                  Un procedimiento que recibe un entero; si éste es par lo divide por dos, y si es impar lo deja como está.

iv.                  Un procedimiento que recibe tres enteros, los suma y al resultado lo multiplica por el primer entero. El resultado final se guarda en el primer parámetro.

v.                   Un procedimiento que incrementa todos los elementos del arreglo de enteros pasado como parámetro, usando el procedimiento del punto i.

Ejercicio 4

Dados dos arreglos de enteros que representan dos polinomios (los enteros del arreglo representan los coeficientes del polinomio), definir procedimientos para:

i.                     Obtener un tercer vector que represente al polinomio obtenido al sumarlos.

ii.                    Obtener un tercer vector que represente al polinomio obtenido al multiplicarlos.

iii.                  Evaluar un polinomio en un punto.

iv.                  Evaluar la suma de dos polinomios en un punto, usando el los puntos i y iii.

Evaluar la suma de dos polinomios en un punto, usando el punto iii.

Ejercicio 5

Ahora, los polinomios están representados mediante una lista, en la cual las posiciones pares indican exponentes y las impares coeficientes. Por ejemplo, [2,1,0,3,5,2] = 2X⁵ + X² + 3(X⁰). Con esta nueva representación, definir un procedimiento Ordenar que toma un polinomio y lo modifica, dejando en la primera posición el coeficiente de grado cero y así sucesivamente. PorUn ejemplo, Ordenar debe satisfacer: {L = [1,2,0,3,5,2]}; Ordenar(L); {L == [0,3,1,2,5,2]}.

Ejercicio 6

i.                     Escribir el procedimiento Ordenar_Arreglo, que ordena los elementos del arreglo de enteros pasado como parámetro.

ii.                    Escribir el procedimiento Ordenar_Arreglo, usando el procedimiento del Ejercicio 13.ii.

Ayuda: Es importante utilizar funciones o procedimientos auxiliares para resolver un problema (la demostración de la corrección del programa también se ve simplificada).