Final 23/02/23 (Algoritmos II)
Ejercicio 1
Responder Verdadero o Falso. Justificar.
- Lo que hace que una operación sea un observador básico es que deba escribirse en base a los generadores.
- Sí una operación rompe la congruencia debe ser transformada en observador básico.
- Dos instancias del mismo TAD pueden ser observacionalmente iguales y aun así ser distinguibles por una operación.
- 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
Verdadero o Falso.
- La precondión y la postcondión de las operaciones de la interfaz tiene que cumplir el invariante de representación.
- La complejidad de las operaciones determina el invariante de representación.
- El invariante determina las complejidades de las operaciones
Ejercicio 3
Indique y justifique si son verdaderas o falsas las siguientes afirmaciones:
a) El análisis “del potencial” y el “del banquero” son técnicas para demostrar la *complejidad promedio de una operación de una estructura de datos b) La complejidad del caso promedio de una operación es siempre es menor o igual a la complejidad del peor caso c) Las Skip lists son estructuras de datos que tienen un peor caso de inserción y búsqueda igual a los AVLs d) La operación de inserción en el métodos de acceso secuencial indexado tiene un peor caso O(log n)
Ejercicio 4
Decir si es V o F (justificar o dar contraejemplo)
a) Si f es O(g) y g es Ω(f), f es Θ(g)? b) Si f es O(n), entonces para cualquier entrada f es Ω(n) c) Si f es Ω(n), entonces para cualquier entrada f es Θ(n) d) ? e) Sea S arreglo de claves representado por max-heap.
Sean S[i] y S[j] claves del heap / i < j y S[i] < S[j] → el arreglo obtenido intercambiar S[i] y S[j] sigue siendo max-heap.
f) Sea S arreglo de claves representado por max-heap.
Sean S[i] y S[j] claves del heap / i < j y S[i] > S[j] → el arreglo obtenido intercambiar S[i] y S[j] sigue siendo max-heap.
