Final 10/12/2015 (Algoritmos II)
Esteban Feuerstein, Charlie y Fernando Schapachnik
Ejercicio 1
Explique detalladamente el concepto de igualdad observacional. Relacionar el rol de la igualdad observacional con la axiomatizacion de DameUno : Conj [alfa] → alfa y explique alternativas y dificultades de axiomatizar alternativas.
Ejercicio 2
Explíquele a un matemático como hacer inducción sobre un TAD. Intentelo ahora con un artesano de plaza francia.
Ejercicio 3
Explique detalladamente el rol que juega el invariante de representación en el diseño jerarquico de TADs.
Ejercicio 4
Decir si es V o F (justificar o dar contraejemplo)
- 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.
Ejercicio 5
Vincular la forma general de los algoritmos que utilizan la técnica de divide and conquer con la forma en la que se obtiene la ecuación de recurrenciai que caracteriza la complejidad de un algoritmo recursivo y con los casos del teorema maestro.
