Final 13/12/2016 (Algoritmos II)

Ejercicio 1

Se pide construir una doble cola de prioridad que satisfaga:

a) min y max en Error al representar (SVG o PNG como alternativa (MathML puede ser habilitado mediante plugin de navegador): respuesta no válida («Math extension cannot connect to Restbase.») del servidor «https://en.wikipedia.org/api/rest_v1/»:): {\displaystyle O(1)}

b) desencolar min y max en log(n)

c) borrar min, borrar max en log(n)

d) ingresar m elementos en Error al representar (SVG o PNG como alternativa (MathML puede ser habilitado mediante plugin de navegador): respuesta no válida («Math extension cannot connect to Restbase.») del servidor «https://en.wikipedia.org/api/rest_v1/»:): {\displaystyle O( min\{ n + m, m *log(n) \})}

Ejercicio 2

Explicar la interfaz y estructura de representación de un modulo que implemente el TAD conjunto ordenado. Proveer las funciones necesarias para garantizar todas las cosas necesarias en tiempo eficiente. Insertar, buscar y borrar en O(log(n)). Recorrer de forma iterativa todo en tiempo lineal. No olvidar conceptos de aliasing y de argumentos.

Ejercicio 3

Analizar los siguientes peores casos. Si se puede utilizar el teorema maestro, utilizarlo. Justificar.

a) Error al representar (SVG o PNG como alternativa (MathML puede ser habilitado mediante plugin de navegador): respuesta no válida («Math extension cannot connect to Restbase.») del servidor «https://en.wikipedia.org/api/rest_v1/»:): {\displaystyle T(N)= 4 T(N/2) + 3 N^2}

b) Error al representar (SVG o PNG como alternativa (MathML puede ser habilitado mediante plugin de navegador): respuesta no válida («Math extension cannot connect to Restbase.») del servidor «https://en.wikipedia.org/api/rest_v1/»:): {\displaystyle T(N)= 16 T(N/4) + (N^2)/log(N)}

c) Error al representar (SVG o PNG como alternativa (MathML puede ser habilitado mediante plugin de navegador): respuesta no válida («Math extension cannot connect to Restbase.») del servidor «https://en.wikipedia.org/api/rest_v1/»:): {\displaystyle T(N)= 2^N T(N/8) + 1}

d) Error al representar (SVG o PNG como alternativa (MathML puede ser habilitado mediante plugin de navegador): respuesta no válida («Math extension cannot connect to Restbase.») del servidor «https://en.wikipedia.org/api/rest_v1/»:): {\displaystyle T(N)= 3 T(N/2) + N^2 log(n)}

e) Error al representar (SVG o PNG como alternativa (MathML puede ser habilitado mediante plugin de navegador): respuesta no válida («Math extension cannot connect to Restbase.») del servidor «https://en.wikipedia.org/api/rest_v1/»:): {\displaystyle T(N) = 16 T(N/2) + F(N) log(n)} donde Error al representar (SVG o PNG como alternativa (MathML puede ser habilitado mediante plugin de navegador): respuesta no válida («Math extension cannot connect to Restbase.») del servidor «https://en.wikipedia.org/api/rest_v1/»:): {\displaystyle F(N)= N^3} (si n par) Error al representar (SVG o PNG como alternativa (MathML puede ser habilitado mediante plugin de navegador): respuesta no válida («Math extension cannot connect to Restbase.») del servidor «https://en.wikipedia.org/api/rest_v1/»:): {\displaystyle N^2} (sino)

f) Error al representar (SVG o PNG como alternativa (MathML puede ser habilitado mediante plugin de navegador): respuesta no válida («Math extension cannot connect to Restbase.») del servidor «https://en.wikipedia.org/api/rest_v1/»:): {\displaystyle T(N) = 3 T(N/2) + F(N)} donde Error al representar (SVG o PNG como alternativa (MathML puede ser habilitado mediante plugin de navegador): respuesta no válida («Math extension cannot connect to Restbase.») del servidor «https://en.wikipedia.org/api/rest_v1/»:): {\displaystyle F(N)= N^3} (si n par) Error al representar (SVG o PNG como alternativa (MathML puede ser habilitado mediante plugin de navegador): respuesta no válida («Math extension cannot connect to Restbase.») del servidor «https://en.wikipedia.org/api/rest_v1/»:): {\displaystyle N^2} (sino)

Ejercicio 4

Se brinda un TAD Conjunto especificado con los siguientes cambios significativos:

Obs:
 secu()

Igualdad Observacional:

c =obs c' <=> secu(c) =obs secu(c')

Otras Operaciones:

oneOff(c) = prim(secu(c))

Axiomas:

esPermutacion(c,secu(c))= true   // axiomatizacion de Secu() es

A) Explicar si está o no bien especificado, y si es correcto respecto a la especificación de la cátedra.

B) suponer correcto. ¿Qué aspectos te parecen mejores o peores?

C) Justificar si puede demostrar esto:

Ag(n, Ag(n_1, ... ( Ag(n_k, vacío())...)) =obs Ag(m, Ag(m_1, ... ( Ag(m_k, vacío())...))
<=> 
Add(n, Ag(n_1, ... ( Add(n_k, vacío())...)) =obs Add(m, Add(m_1, ... ( Add(m_k, vacío())...))

Donde Add es el generador que reemplaza el comportamiento de Ag en la nueva especificación.

D)

DameUno(Ag(n, Ag(n_1, ... ( Ag(n_k, vacío())...))) =obs oneOff(Add(n, Ag(n_1, ... ( Add(n_k, vacío())...)))