Final 10/03/17 (Algoritmos II)

Esteban Feuerstein 4 hs

Para considerarse aprobado deben estar bien al menos 3 ejercicios.

Ejercicio 1

Responder Verdadero o Falso. Justificar.

• a) Lo que hace que una operación sea un observador básico es que deba escribirse en base a los generadores.
• b) Si una operación rompe la congruencia debe ser transformada en observador básico.
• c) Dos instancias del mismo TAD pueden ser observacionalmente iguales y aun así ser distinguibles por una operación.
• d) Si un enunciado dice "Siempre que vale A sucede inmediatamente B y B no puede suceder de ninguna otra manera" y la correspondiente axiomatización incluye las operaciones A y B entonces el TAD está mal escrito.

Soluciones(no corregidas por un prof.)

a) Falso: Cualquier operación podría escribirse en base a los generadores, aunque no es recomendable. Que un observador básico deba escribirse en base a los generadores es sólo una consecuencia de serlo. Pero lo que define un observador básico es su capacidad de dividir el universo de instancias del tipo en clases de equivalencia.

b) Verdadero

c) Falso: Cualquier operación que distinga instancias del TAD debe pertenecer al conjunto de observadores básicos o no existir, porque el TAD debe ser una congruencia.

d) Verdadero: es comportamiento automático.

Ejercicio 2

En cada uno de los siguientes escenarios, indique qué método de ordenamiento de los estudiados en clase utilizaría y porque.

• a) Se tiene un arreglo de naturales A[1..n] y se desea ordenarlos (de mayor a menor) solamente sí la suma de los k elementos más grandes es menor que X. Se desea realizar ésta tarea de forma eficiente, dandola por terminada lo antes posible si la condición no se cumple. (La verificación forma parte de la tarea, no se debe verificar la condición antes de empezar a ordenar)

• b) Se tiene un arreglo redimensionable de naturales A[1..n] y se desea ordenarlos. Sin embargo, durante el proceso de ordenamiento es posible que se agreguen nuevos elementos al final del arreglo.

Soluciones

a) Hacer max_heapify del arreglo, sumar los k primeros, y en base a eso decidir si ordenar o no. Esto sería $O(N+K*log(N))$ en el caso que no haya que ordenar, $O(N*log(N))$ para cuando sí haya que ordenar.

b) Usaría un Heap Sort, ya que permite ordenar el arreglo en $O(n*log(n))$, y la inserción cuesta solamente $O(log(n))$. No se me ocurre un método mejor.

Ejercicio 3

Decir si es Verdadero o Falso (justificar o dar contraejemplo)

Sea S el arreglo de claves representado por como un max-heap.

• a) Sean S[i] y S[j] claves del heap / i < j y S[i] < S[j] → el arreglo obtenido al intercambiar S[i] y S[j] sigue siendo max-heap.

• b) Sean S[i] y S[j] claves del heap / i < j y S[i] > S[j] → el arreglo obtenido al intercambiar S[i] y S[j] sigue siendo max-heap.

Soluciones

a) Falso. Un contraejemplo sería el del heap representado por el arreglo [10, 3, 9, 2, 1, 8, 7]. Si tomamos i = 2 y j = 3, S[i] = 3 y S[j] = 9 => i < j y S[i] < S[j]. Si intercambiamos S[i] con S[j], los hijos del nodo con valor 3 pasarían a ser los antiguos hijos del nodo con valor 9, que eran los nodos con valores 8 y 7. Como 8 y 7 son mayores que su nuevo padre 3, el invariante del max-heap se pierde.

b) Falso. El contraejemplo es muy parecido al anterior. Tomemos el heap representado por el arreglo [10, 9, 3, 8, 7]. Si tomamos i = 2 y j = 3, S[i] = 9 y S[j] = 3 => i < j y S[i] > S[j]. Si intercambiamos ahora los dos valores, el nodo con valor 3 pasará a ser el padre de los nodos con valores 8 y 7, y se romperá la invariante del max-heap.

Ejercicio 4

• a) ¿Cuántos caracteres DISTINTOS tiene que tener un texto como mínimo para que alguno de ellos reciba un código de longitud k en una codificación de Huffman (con k>1)? Jusificar.
• b) ¿Cuántos caracteres en total tiene que tener un texto como mínimo para que algún caracter reciba un código de longitud k en una codificación de Huffman (con k>1)? Justificar
• c) Responder a) y b) para códogs de longitud fija. Justificar.

Ejercicio 5

Considerar una tabla hash con direccionamiento abierto, en la cual se marca de forma diferenciada las posiciones que contienen un elemento, aquellas que nunca contuvieron un elemento y aquellas que en algún momento tuvieron un elemento pero fue borrado. Describir los algoritmos de inserción, búsqueda y borrado y analizar sus complejidades asintóticas. Comparar con la versión de hashing en la cual no se puede distinguir los borrados de "vacio".