Final 23/02/23 (Algoritmos II)

Ejercicio 1

Responder Verdadero o Falso. Justificar.

1. Lo que hace que una operación sea un observador básico es que deba escribirse en base a los generadores.
2. Sí una operación rompe la congruencia debe ser transformada en observador básico.
3. Dos instancias del mismo TAD pueden ser observacionalmente iguales y aun así ser distinguibles por una operación.
4. 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.

1. La precondión y la postcondión de las operaciones de la interfaz tiene que cumplir el invariante de representación.
2. La complejidad de las operaciones determina el invariante de representación.
3. El invariante determina las complejidades de las operaciones

Ejercicio 3

Indique y justifique si son verdaderas o falsas las siguientes afirmaciones:

1. 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
2. La complejidad del caso promedio de una operación es siempre es menor o igual a la complejidad del peor caso
3. Las Skip lists son estructuras de datos que tienen un peor caso de inserción y búsqueda igual a los AVLs
4. 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)

1. Si f es O(g) y g es Ω(f), f es Θ(g)?
2. Si f es O(n), entonces para cualquier entrada f es Ω(n)
3. Si f es Ω(n), entonces para cualquier entrada f es Θ(n)
4. La complejidad del mejor caso de un algoritmo para un cierto problema es menor que cualquier limite inferior para el problema.
5. 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.
6. 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.