Ejercicios Finales de algoritmos

Héctor Tejeda Villela

3 de julio del 2002

Ejercicios

3    

Dado un árbol binario G=(V,E), la distancia entre dos nodos es la longitud del camino que los conecta (suponemos que la distancia entre dos vecinos es 1). Construir una matriz A cuya entrada $A_{ij}$ sea la distancia entre los nodos entre $v_i$ y $v_j$ del árbol. Diseñar un algoritmo cuadrático que construya esta matriz cuando el árbol se da como una matriz de adyacencia.

Solución

Figura 1: Arbol Binario

1. Se toma el nodo raíz de la matriz de adyacencia, para la cual la matriz de distancias es la siguiente:

   	A
   A	0

2. Se leen ahora los hijos de la raíz, para hacerlo se lee el renglón en la matriz de adyacencia. Se agrega a la matriz de distancias cada hijo, sumando 1 al renglón padre, por lo que para el nodo B se tiene:

   	A	B
   A	0	1
   B	1	0

   Al agregar el siguiente nodo hijo C la matriz que se obtiene es:

   	A	B	C
   A	0	1	1
   B	1	0	2
   C	1	2	0

   Como se puede observar se obtiene una matriz simétrica, por lo que sólo es necesario hacer el cálculo en la parte inferior y se pueden transponer el renglón en la columna correspondiente.

3. Una vez que se hayan revisado todos los hijos de la raíz, se procede a revisar los hijos del primer hijo de la raíz y así sucesivamente hasta terminar con todos los nodos de la matriz de adyacencia. Es importante observar que se debe recorrer la matriz en la forma "breadth first search".

   	A	B	C	D
   A	0	1	1	2
   B	1	0	2	1
   C	1	2	0	3
   D	2	1	3	0

   Por lo anterior, se tiene que para obtener los valores del k-ésimo renglón hijo, se suma 1 a los elementos del renglón padre, donde la posición $n_{ii}$ siempre es cero, y como la matriz es simétrica se transpone el renglón en k-ésima columna.

   Se puede observar que se requieren hacer 1+2+ ... + n operaciones (sumas) para obtener la matriz de adyacencias, por lo que se harán n(n+1)/2 operaciones, por lo que el algoritmo es $O(n^2)$.

7    

Dado un arreglo de enteros A[1 ... n], tal que $\forall i, 1 \leq i < n$. Se cumple que $\vert A[i]-A[i+1]\vert \leq 1$. Sea A[1]=x y A[n]=y y x < y. Diseñe un algoritmo de búsqueda para encontrar j tal que A[j]=z, para algún valor z acotado por $x \leq z \leq y$. ¿Cuál es el máximo número de comparaciones que hace su algoritmo?

Solución

Si se toma un elemento central del arreglo de enteros, por ejemplo $a = A[ \lfloor n/2 \rfloor ]$. Si $a \leq z$, entonces z deberá estar en el arreglo entre A[1] y $A[ \lfloor n/2 \rfloor ]$. Lo anterior es cierto por las condiciones de los datos del arreglo, donde la diferencia máxima entre dos datos consecutivos es 1 y la mínima es 0, por lo que en el subarreglo se tienen todos los enteros entre x e a, que es lo mismo para el caso del arreglo dado, en donde se tienen todos los enteros que estan entre x e y. En el caso de que a < z, entonces, z deberá aparecer entre $A[ \lfloor n/2 \rfloor + 1]$ y A[n]. En cualquiera de los dos casos, se debe seguir revisando mientras $a \ne z$, el peor caso en donde se realiza el máximo de comparaciones es cuando el valor que se busca esta en uno de los extremos y es único, por lo que el número máximo de comparaciones es $\lceil \mbox{log}_2n \rceil$. Un caso práctico que ilustra lo anterior es con los siguientes valores y se busca la posición del valor 2:

2,3,3,3,3,3,3,3,3,3

8    

La entrada es un conjunto S de números reales. Diseñe un algoritmo O(n) para encontrar un número que no esté en el conjunto S. Pruebe que la cota mínima del número de pasos para resolver el problema es $\Omega(n)$

Solución

El algoritmo debe realizar una búsqueda secuencial en todo el conjunto para garantizar que no se encuentra en el conjunto S. Para probar que la cota mínima de pasos es $\Omega(n)$, si se revisan menos elementos se requiere que el conjunto este ordenado, en donde se hacen O(n log n) comparaciones en promedio, las que deben ser sumadas a los pasos para encontrar si un número esta en el conjunto, por lo que tendremos en este caso $\Omega(n)$. Por lo tanto la única forma es revisar todo el conjunto para determinar si un valor no se encuentra.

12   

La entrada es una secuencia de números reales $x_1, x_2, \ldots, x_n$ con n par. Diseñe un algoritmo que divida el conjunto en n/2 pares de la siguiente manera: para cada par calcular la suma de sus componentes. Si $s_1, s_2, \ldots, S_{n/2}$ denota las n/2 sumas, el algoritmo debe encontrar la partición que minimiza el máximo de las $s_i$.

Solución

Para ilustrar el algoritmo supondremos la siguiente secuencia de 4 números S = -1, 3, -4, 0. La cual se divide en un conjunto de 2 pares. El total de pares que se pueden formar son $C^4_2$, por lo que se pueden tener los siguientes subconjuntos:

{ -1+3, -4+0 }, {-1+(-4), 3+0} y {-1+0,3+(-4)}

o bien,

{ -4, 2 }, { -5, 3} y {-1,-1}

donde la partición que minimiza el máximo de las $s_i$ es la tercera. Se puede observar que para obtener esta partición se puede ordenar en primer lugar la secuencia de números (-4, -1, 0, 3) y luego formar parejas por los extremos, es decir, el elemento 1 con el elemento n, el 2 con n-1, etc.

Falta por demostrar que lo anterior funciona para cualquier caso. Supóngase que hay otra partición mejor, en la cual no se encuentran aparejadas $x_1$ y $x_n$. Si en la partición mencionada $x_1$ esta emparejada con $x_i$ y $x_n$ con $x_j$, Entonces se puede cambiar la partición de tal forma que $x_1$ forme pareja con $x_n$ y $x_j$ con $x_i$, sin incrementar el máximo de las $s_i$, lo cual es una contradicción, ya que se decrementan, como se puede ver en el ejemplo.

16   

Sea A un algoritmo que encuentra el k-ésimo elemento más grande utilizando una sucesión de comparaciones. Probar que A posee suficiente información para determinar cuales elementos son más grandes que el k-ésimo más grande y cuales son más pequeños que el k-ésimo más grande, es decir, es posible partir el conjunto alrededor del k-ésimo sin hacer más comparaciones que las que ya hizo A.

Solución

Supongamos que el algoritmo A encuentra que $x_i$ es el k-ésimo elemento más grande haciendo un sucesión de comparaciones cuyos resultados no pueden determinar si algún elemento $x_j$ es mayor o menor que $x_i$. Esto significa que la salida de las comparaciones es consistente con $x_j$ siendo igual a un valor $y>x_i$ y a un valor $z<x_i$. Pero en ambos casos nos permiten obtener otro k-ésimo elemento más grande, lo cual es una contradicción.