Final 25/02/2016 (Algoritmos II)

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

Se cuenta con n elementos que contienen una clave primaria y una secundaria. Hay m<<n claves secundarias distintas. Proponga dos formas eficientes y distintas que permitan ordenar los n elementos, en base a las dos claves (primero la primaria, luego la secundaria). Una de las dos formas tiene que utilizar solo arreglos.

Ejercicio 3

Explicar por qué la función de abstracción no es sobreyectiva sobre el conjunto de términos. ¿Hay algún conjunto para el que sí lo sea?

Ejercicio 4

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.

Ejercicio 5

Enumerar y describir los tipos de recursión que se pueden eliminar con las técnicas vistas en la materia. Dar una esquematización (descripción general) de como aplicaría cada una.