Final 10/12/2015 (Algoritmos II)

Esteban Feuerstein, Charlie y Fernando Schapachnik

Tomaron lo mismo en las 3 fechas menos el item 2 en la última.

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.

En el final del 21/12 la cambiaron por: Explíquele a un matemático POR QUÉ se puede hacer inducción estructural sobre cualquier TAD.

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)

1. 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.
2. 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 recurrencia que caracteriza la complejidad de un algoritmo recursivo y con los casos del teorema maestro.