1.- Calcule la complejidad tanto de forma analítica como experimental de los siguientes métodos de ordenación: Burbuja, Inserción Directa, Selección Directa, Montículo, Quicksort, Mergesort y método de Shell. Los conjuntos de datos sobre los que se trabajará serán de 10.000, 100.000 y 1.000.000 elementos enteros. Recopile datos sobre distintas máquinas.

2.- Se tienen n puntos en el plano. Diseñe un algoritmo “Divide y Vencerás” que devuelva el par de puntos cuya distancia entre ambos es mínima.

3.- Disponemos de un conjunto de placas rectangulares de tipo R, cada una de dimensiones A x L. Se desean recortar n piezas rectangulares de dimensiones a_i x l_i, de tal forma que se minimice el número de las placas de tipo R de las que se ha obtenido alguna pieza. Diseñe una Heurística Voraz que resuelva el problema.

4.- Dado un plano del metro, supuesto que conocemos el tiempo que tarda cada tren en recorrer cada trayecto entre dos estaciones contiguas de una misma línea, el tiempo que está parado en el andén en cada estación, y también, el tiempo que tardamos en efectuar un transbordo de una línea a otra en cada una de las estaciones en las que esto es posible. Diseñe algoritmos que resuelvan los problemas que se indican a continuación:

a) Determinar el camino mínimo (en tiempo) entre dos estaciones dadas de la red. Utilice Programación Dinámica.

b) Resuelva el problema del apartado a), supuesto que no podamos hacer más de k transbordos. Utilice Backtracking.

5.- Juego de los Buhoneros. Dos buhoneros se han apostado sus carromatos a ver quien vende más botellas del milagroso bálsamo del Dr. Bestfit. La comarca sobre la que han hecho la apuesta tiene un conjunto de aldeas, unidas por caminos angostos y pedregosos que bordean las montañas. Disponen del mapa con las aldeas y los caminos que los comunican, con el coste de desplazamiento entre dos aldeas contiguas, que es el peaje (monetario) a pagar a ABACO (Asociación de BAndidos de la COmarca). De la misma forma, y teniendo en cuenta la población de cada aldea, y el nivel de convicción que tiene cada uno sobre los vecinos de cada aldea, saben cuantas botellas venderá cada uno en una aldea (suele ser distinta para cada uno).

Por experiencia saben que no deben visitar dos veces la misma aldea, ni siquiera pasar por ella, porque si los aldeanos no perciben una mejoría en sus males, la emprenden a pedradas con el buhonero y su carromato, destrozándolo.

El mecanismo del juego es el que sigue: Pluma de Águila (puesto que lleva una en su sombrero) visita una aldea un día, y Pico de Oro descansa, y el día siguiente, es Pico de Oro el que visita otra aldea, y Pluma de Águila descansa, y así sucesivamente, hasta que ambos no tienen posibilidades de ganar más dinero.

Puesto que hay dificultades para saber cuando no deben pasar por una aldea (entre las “virtudes” del bálsamo milagroso no se encuentra la de la comunicación telepática), han acordado jugar sobre el mapa de la comarca que tienen, ya que en el mismo se recogen todos los datos necesarios para jugar.

Diseñe una función que dada una posición del juego la evalúe y devuelva la decisión a tomar.

6.- Don Quijote y Sancho Panza cabalgan de nuevo.

Don Quijote y Sancho se han decidido a emprender nuevas aventuras. Su fama ha llegado a los más recónditos lugares, sobre pasando los límites de La Mancha, y extendiéndose más allá de las tierras de Castilla y Aragón. Han estado sopesando hacer Las Américas, porque las verdaderas aventuras están donde ningún mortal puso el pie, pero han desistido porque ninguno de los dos es muy amigo de andar sobre el agua.

Continuamente les llegan mensajes desesperados de gentes que no ven solución a sus males y precisan la desinteresada ayuda de un esforzado caballero. No pueden atender a todas las peticiones puesto que no disponen de tanto tiempo como quisieran, y tampoco las fuerzas son las mismas que en sus años mozos. Pero están resueltos a desfacer el máximo número de entuertos que puedan en el tiempo de que disponen y con las fuerzas que les acompañan.

Si algo han aprendido nuestros hombres de sus experiencias pasadas es que necesitan saber donde ir y que las aventuras que emprendan no deben sobrepasar sus fuerzas. Por ello, se han provisto de un mapa en el que han anotado datos que consideran esenciales para culminar con éxito sus aventuras. Así por distintas averiguaciones saben el tiempo T_ij que tardan en ir de un lugar i a otro j, y los esfuerzos Q_ij de don Quijote, y S_ij de Sancho, que les supone ir de i a j.

Así que cargados cada uno con fuerzas F_Q, don Quijote, y F_S, Sancho, y sabiendo que disponen de un tiempo T, puesto que se han comprometido con sus más próximos para estar de vuelta en su casas y celebrar un año más el aniversario de su primera salida, en ese lugar de La Mancha...

Pero nuestros hombres no saben cuál es el camino que tienen que seguir para lograr su propósito de desfacer el mayor número de entuertos, según las consideraciones anteriores. Aunque ha querido el destino que el día anterior al señalado para su partida un viajero ha llegado al lugar de La Mancha, con extrañas vestimentas, y algunos artilugios que de vez en cuando lanzan algún gruñido.

A cambio de un buen caldo, alguna conversación y la promesa de un techo bajo el que pasar la noche les ha proporcionado el camino a seguir, tras estar manipulando la caja que lleva consigo un rato, y lanzar entre tanto, algún que otro improperio a la misma. Improperios que a Sancho le han recordado los tiempos en que a don Quijote le sorbieron el seso los libros de Caballerías.

Interrogado el viajero por cómo sabía la solución al problema, respondió que venía de un tiempo en el que había máquinas que surcaban los cielos, y que con una caja como la que el llevaba podía hablar con otros de lejanas tierras, y resolver problemas como los de ellos tenían, con el uso de la Programación Dinámica y el Backtracking. Porque él había ido a la Universidad y seguido un curso de Ampliación de Programación, entre otras materias.

Sancho Panza al oír semejantes nombres, le ha dicho poco más o menos lo mismo que lo que le dijo a Sansón Carrasco con la gramática. Y ha empezado a sospechar que lo que quiere el viajero es comida y cama gratis. Pero don Quijote le ha aceptado sin recelos cuando les ha contado sus peripecias.

Para el viajero todo empezó cuando bajó a una cueva a rescatar unas doncellas cuyos lamentos se oían a distancia, y que en sus sollozos y lamentos, suplicaban las liberaran de su cautiverio, y al salir de la cueva no encontró sino lagunas en las que el agua hacía mucho ruido, que bien pudiera confundirse con los lamentos de las doncellas.

Los ojos de don Quijote comenzaron a brillar, por fin había encontrado evidencia de lo que en tiempos pasados pensó, y le dijo a Sancho. Y alabando la determinación del viajero, para socorrer gente en apuros, para lo que recordó lo que en cierta ocasión le dijo a Sancho:

“La libertad, Sancho, es uno de los más preciosos dones que a los hombres dieron los cielos; con ella no pueden igualarse los tesoros que encierra la tierra ni el mar encubre; por la libertad, así como por la honra, se puede y debe aventurar la vida, y, por el contrario, el cautiverio es el mayor mal que puede venir a los hombres.”

Don Quijote está resuelto a no perder un momento y partir a desfacer el mayor número de entuertos en el tiempo T de que dispone.

También es cierto que el viajero continuamente les preguntaba a nuestros hombres si eran reales, y no fruto de algún sueño o alucinación que a veces tenía resolviendo problemas de programación.

Si vos hubiérais sido el viajero ¿qué programa, basado en Programación Dinámica o Backtracking, habríais creado para ayudar a don Quijote y Sancho?

OPCIONAL

7.- Cierre Convexo. Dado un conjunto de n puntos del plano. Diseñe un algoritmo Divide y Vencerás que compute el cierre convexo del mismo. Calcule la complejidad del algoritmo desarrollado.