Diferencia entre revisiones de «Final 10/12/2015 (Algoritmos II)»
(agregado final de algo 2 10/12/15) |
Sin resumen de edición |
||
| Línea 16: | Línea 16: | ||
== Ejercicio 5 == | == 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 | 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. | ||
Revisión del 04:27 11 dic 2015
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 recurrencia que caracteriza la complejidad de un algoritmo recursivo y con los casos del teorema maestro.
