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.

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 ordernarlos (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.

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.

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".