Edición de «Final 23/02/23 (Algoritmos II)»

De Cuba-Wiki
Advertencia: no has iniciado sesión. Tu dirección IP se hará pública si haces cualquier edición. Si inicias sesión o creas una cuenta, tus ediciones se atribuirán a tu nombre de usuario, además de otros beneficios.

Puedes deshacer la edición. Antes de deshacer la edición, comprueba la siguiente comparación para verificar que realmente es lo que quieres hacer, y entonces publica los cambios para así efectuar la reversión.

Revisión actual Tu texto
Línea 11: Línea 11:
Verdadero o Falso.
Verdadero o Falso.


# La precondión y la postcondión de las operaciones de la interfaz tiene que cumplir el invariante de representación.
a) La precondión y la postcondión de las operaciones de la interfaz tiene  
# La complejidad de las operaciones determina el invariante de representación.
  que cumplir el invariante de representación.
# El invariante determina las complejidades de las operaciones
b) La complejidad de las operaciones determina el invariante de representación.
c) El invariante determina las complejidades de las operaciones
 


== Ejercicio 3 ==
== Ejercicio 3 ==
Indique y justifique si son verdaderas o falsas las siguientes afirmaciones:
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
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
# La complejidad del caso promedio de una operación es siempre es menor o igual a la complejidad del peor caso
b) 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
c) 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)
d) La operación de inserción en el métodos de acceso secuencial indexado tiene un peor caso O(log n)
 
== Ejercicio 4 ==
== Ejercicio 4 ==
Decir si es V o F (justificar o dar contraejemplo)
Decir si es V o F (justificar o dar contraejemplo)


# Si f es O(g) y g es Ω(f), f es Θ(g)?
a) Si f es O(g) y g es Ω(f), f es Θ(g)?
# Si f es O(n), entonces para cualquier entrada f es Ω(n)
b) Si f es O(n), entonces para cualquier entrada f es Ω(n)
# Si f es Ω(n), entonces para cualquier entrada f es Θ(n)
c) 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.
d) ?
# 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.
e) Sea S arreglo de claves representado por 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.
  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.
Ten en cuenta que todas las contribuciones a Cuba-Wiki pueden ser editadas, modificadas o eliminadas por otros colaboradores. Si no deseas que las modifiquen sin limitaciones, no las publiques aquí.
Al mismo tiempo, asumimos que eres el autor de lo que escribiste, o lo copiaste de una fuente en el dominio público o con licencia libre (véase Cuba-Wiki:Derechos de autor para más detalles). ¡No uses textos con copyright sin permiso!

Para editar esta página, responde la pregunta que aparece abajo (más información):

Cancelar Ayuda de edición (se abre en una ventana nueva)
Obtenido de «https://www.cubawiki.com.ar/index.php/Final_23/02/23_(Algoritmos_II)»