Examen Parcial #1

      Duración: dos horas. Lea bien el examen antes de hacerlo. El examen es a libro abierto. Cuenta la documentación. Cuenta la redacción y la ortografía. Cuentan las convenciones. Puede hacer el examen con lápiz. ¡No haga más de lo que se le pide! ¡CONTESTE TODAS LAS PREGUNTAS!

1) [35 pts] Considere las siguientes implementaciones equivalentes de la función BinSearch().

FUNCTION BinSearch(                   TYPE
  {+} VAR A: TArray;                    TArray = ARRAY[1..100] OF REAL;
  {+}  m,n : TIndex;                    TIndex = WORD;
  {+}     v: REAL                     CONST
) {>>>>>>>}: TIndex;                    NULL = 0;
{ RESULTADO
  Devuelve el índice "i" en que se encuentra el valor "v" en
  el arreglo "A[]".
  - A[m..n] debe estar ordenado con valores no decrecientes.
  - Sólo busca en el subarreglo A[m..n].
  - Si no existe "i" tal que A[i]=v, entonces retorna NULL. }

VAR                                        VAR
  mid: TIndex;                               mid: TIndex;
BEGIN { rBinSearch }                       BEGIN  { iBinSearch }
  IF m>n THEN BEGIN
    rBinSearch := NULL;                      WHILE m<=n DO BEGIN
    EXIT;
  END;
  mid := (m+n) DIV 2;                          mid := (m+n) DIV 2;

  IF A[mid] = v THEN BEGIN                     IF A[mid] = v THEN BEGIN
    rBinSearch := mid;                           iBinSearch := mid;
    EXIT;                                        EXIT;
  END                                          END

  ELSE IF A[mid] < v THEN BEGIN                ELSE IF A[mid] < v THEN BEGIN
    rBinSearch := rBinSearch(A,mid+1,n,v);       m := mid+1;
  END                                          END

  ELSE BEGIN { A[mid] > v }                    ELSE BEGIN { A[mid] > v }
    rBinSearch := rBinSearch(A,m,mid-1,v);       n := mid-1;
  END;                                         END;

                                             END;    { WHILE }
                                             iBinSearch := NULL;
END;  { rBinSearch }                       END;  { iBinSearch }

1.a) [10 pts] Calcule la complejidad de tiempo de rBinSearch().

1.b) [5 pts] Calcule la complejidad de tiempo de iBinSearch().

1.c) [5 pts] Calcule la complejidad de espacio de rBinSearch().

1.d) [5 pts] Calcule la complejidad de espacio de iBinSearch().

1.e) [10 pts] Compare las dos implementaciones, y diga cuáles ventajas tiene cada una sobre la otra.

2) [35 pts] En esta pregunta usted trabajará con matrices ralas, o sea, con matrices que tienen una gran cantidad de valores iguales.

2.a) [1 pts] Defina qué es una matriz rala. Incluya un ejemplo de una matriz rala. [Nota: permita que el valor que se repite en la matriz pueda no ser 0]. ¿Es la matriz identidad una matriz rala?

2.b) [3 pts] Haga el diagrama (dibujo, o modelo, como quiera que usted lo llame) de una matriz rala representada por un vector de listas, en que cada lista contiene los valores de una columna de la matriz (ojo: ¡no filas!).

2.c) [3 pts] Represente la matriz rala usando un vector de tríos de valores, en donde el 3-tuple (i,j,v) indica que el valor "M[i,j]" de la matriz "M[]" es "v", o sea, que "M[i,j] = v".

2.d) [3 pts] Describa usando un diagrama otra forma (sustancialmente) diferente de representar la matriz rala.

2.e) [5 pts] Explique cómo implementar el método TMatrix.Transpuesta() para la matriz rala representada con la lista de valores de las columnas.

2.f) [5 pts] Explique cómo implementar el método TMatrix.Transpuesta() para la matriz rala representada con el vector de tríos de valores.

2.g) [5 pts] Explique cómo implementar el método TMatrix.Transpuesta() para la representación que usted propone en su respuesta 2.d).

2.h) [10 pts] Compare la complejidad en tiempo y espacio de las tres versiones del método TMatrix.Transpuesta(), y diga cuál de las tres representaciones es mejor para una aplicación en que esta operación es la más utilizada. Su análisis debe ser cualitativo, aunque debe sustentar sus razones cuantitativamente.

3) [30 pts] Implemente la función Homomorfo(T1,T2), que recibe dos árboles n-arios cuyos nodos tienen valores numéricos y dice si son homomorfos, esto es, si existe un reordenamiento de cada uno de los nodos hijos de T1 que lo transforme en un árbol igual a T2.

    2
   / \
  3   6
 /|\   \
1 9 4   8

    2
   / \
  6   3
 /   /|\
8   9 4 1

   2
  / \
6     3
 \   /|\
  8 1 9 4

3.a) [5 pts] Especifique con exactitud su función Homomorfo(T1,T2).

3.b) [10 pts] Implemente Homomorfo(T1,T2).

3.c) [10 pts] Calcule la complejidad en tiempo y espacio de Homomorfo(T1,T2).

3.d) [5 pts] Diga cómo generalizar Homomorfo(T1,T2) a árboles no numéricos.

En su implementación puede usar las operaciones usuales del ADT Arbol.

Adolfo Di Mare <adolfo@di-mare.com>.
Copyright © 1996
Derechos de autor reservados © 1996