Final 20/09/17 (Algoritmos II)

Tomado por Carlos Gustavo Lopez Pombo

El final se aprueba con 3 ejercicios bien. La nota intenta reflejar los conocimientos generales demostrados en el examen y no la suma aritmética de puntos. Todos los ejercicios tienen un peso equivalente en la nota final.

Ejercicio 1

Realice un análisis detallado de los casos del teorema maestro y justifique la conclusión de estos en relación a la condición que satisface.

Soluciones

El teorema maestro afirma que, dada una función de la forma $T(N)={\begin{cases}d&{\text{si }}N=1\\aT(N/b)&{\text{sino}}\end{cases}}$ que describa la cantidad de pasos a tomar en un algoritmo con entrada N, siendo d una constante, N,a,b pertenecientes a N, entonces:

1. Si $f(N)\in O(N^{log_{b}(a)-\epsilon })$ para algún $\epsilon >0\implies T(N)\in \Theta (N^{log_{b}(a)})$
2. Si $f(N)\in \Theta (N^{log_{b}(a)})\implies T(N)\in \Theta (N^{log_{b}(a)}*log(N))$
3. Si $f(N)\in \Omega (N^{log_{b}(a)+\epsilon })$ para algún $\epsilon >0$, y $\exists c<1:a*f(N/b)\leq c*f(N)$ desde algún N suficientemente grande para adelante $\implies T(N)\in \Theta (f(N))$

Intuitivamente, los casos se pueden justificar así:

1. Si la función f tiene menor complejidad que la parte recursiva, entonces la complejidad dominante será la de la recursión.
2. Si la función f tiene una complejidad similar, ninguna de las dos domina a la otra, y entonces cada una aporta a la complejidad final.
3. Si la función f tiene mayor complejidad que la parte recursiva, entonces la complejidad dominante será la de f; pero esto solo pasa cuando las llamadas recursivas a $a*T(N/b)$ no ocasionan una llamada a $a*f(N/b)$ que sea mayor al f(N) anterior. Si fuese así, la complejidad será aún más dependiente de N, y entonces el teorema maestro no nos ayuda.

La complejidad de la parte recursiva siendo $O(N^{log_{b}(a)})$ sale de la cantidad de casos base a los que se llegan llamando recursivamente a $a*T(N/b)$. Si $a=b$, se partirá el problema en b partes pero se harán a veces esas partes, con lo cual se llegará a una cantidad de casos base igual al N original, para mostrar un ejemplo.

Ejercicio 2

Explique la forma general de un algoritmo de Divide & Conquer. ¿Cualquier algoritmo recursivo es un algoritmo de Divide & Conquer? ¿Qué condiciones se espera que se satisfagan para que se justifique la aplicación de la técnica algorítmica? Ejemplifique un caso.

Soluciones

En JPG

Un mejor ejemplo de por qué usar D&C es el caso del algoritmo de Strassen para multiplicar matrices, que tiene una complejidad de O(N^2.8074) vs O(N^3) del algoritmo común. El ejemplo de sorting dado no es tan bueno ya que hay algoritmos no D&C para ordenar que tienen la misma complejidad de mergesort, por ejemplo, heapsort.

Ejercicio 3

Decimos que un algoritmo de ordenamiento es estable si a lo largo de la ejecución los elementos que ya se encuentran en la posición que les corresponde nunca son intercambiados. Detalle cuáles de los algoritmos de ordenamiento que conoce son estables y justifique.

Soluciones

En JPG (parte 1) (parte 2)

La definición de estabilidad dada no es la típica, es más, con la definición dada por Charlie, solamente selection sort es estable, ya que hay contraejemplos para insertion, merge y bubble sort ya que dependen de como se implementen.

Ejercicio 4

Dada la necesidad de diseñar el TAD Conjunto que es utilizado en un contexto como herramientas de para recorrer sus elementos. Proponga una interfaz apropiada. ¿Coincide con la propuesta en el TAD? Justifique.

Soluciones

En JPG (No está tan bien la solución en realidad, el lenguaje de diseño creo que no está bien usado)

Ejercicio 5

Explique detalladamente el concepto de observador básico y cómo interviene en la definición de las otras operaciones a fin de preservar las características fundamentales del lenguaje.

Soluciones

En JPG