Final 27/2/2015 (Algoritmos II)

Plantilla:Back Esteban Feuerstein y Flavia Bonomo

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) Sí 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) Sí 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

• a) Dar la propiedad que hace que los ABB sean AVLs. O sea, el invariante. (en castellano)
• b) Dar un algoritmo lineal que verifique sí un ABB cumple con el invariante del AVL. Justificar la complejidad obtenida.
• c) Mostrar un ejemplo de AVL donde el borrando genera más de una rotación.

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