Edición de «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:

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

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