Final 01/08/2016 (Algoritmos II)

El ejercicio 1 definía M como el conjunto de matrices infinitas de booleanos como entes matemáticos, es decir, como funciones de N x N -> {0,1}, y M' como el conjunto de instancias de un TAD Matriz infinita de booleanos. Un observador y tres generadores. Te preguntaba si se podía hacer inducción sobre M' y si podías usarlo para probar propiedades sobre M, la relación entre M y M', y si podías probar propiedades sobre M, qué particularidad tenían.

El ejercicio 2 preguntaba si toda implementación del TAD conjunto($\alpha$) puede proveer las funciones dameUno y sinUno (y estaban las pre y pos ahí.), si se podía, te preguntaba cómo lo implementarías sobre una lista enlazada, y si no, dar funciones parecidas que permitan recorrer el conjunto (sin usar iteradores). Y después preguntaba ventajas y desventajas de contar con iteradores para recorrer conjuntos.

El ejercicio 3 era de complejidad, te pedía que la definieras y qué mide, que definieras la notación de órdenes y dieras ejemplos de cómo se usa... Y después daba una demostración por inducción de que la sumatoria de unos desde i=1 hasta n era O(1), y te preguntaba si estaba bien y mal, y por qué... (La demo lo planteaba para n=1, y después como HI, desde i=1 hasta n es O(1), y la planteaba para n+1, la separaba en 1 + O(1)).

El ejercicio 4 te pedía que probaras o describieras la posibilidad de implementaciones de colas de prioridad con:

• Insertar en O(1) y sacar mínimo en O(n).
• Insertar en O(n) y sacar mínimo en O(1).
• Las dos en O(log n)
• Las dos en O(log(log n))