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.

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.

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.

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.

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.