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.- Cálculo del n-ésimo término de la sucesión de Fibonacci.

a) Diseñe un algoritmo “Divide y Vencerás” que calcule xⁿ con un coste O(n log n), en términos del número de multiplicaciones efectuadas.

b) Sea F la matriz . Considere el producto del vector (a b) por la matriz F. ¿Cuál es el resultado cuando a y b son dos términos consecutivos de la sucesión de Fibonacci.

c) Utilizando las ideas de los apartados anteriores, desarrolle un algoritmo “Divide y Vencerás” para calcular el n-ésimo término de la sucesión de Fibonacci. Calcule su coste en términos del número de operaciones aritméticas efectuadas.

3.- Juan, “el gorrilla”, ha sido contratado por el Casino DSAS3, sito en el número 13 de la Calle del Percebe (en donde, hasta hace poco, se erigía un antiguo bloque de pisos, habitado por excéntricos inquilinos). Su nuevo trabajo consiste en aparcar los coches de los clientes en el patio interior del inmueble. Dicho patio, reconvertido en parking de lujo, tiene forma de "T", de forma que se pueden aparcar coches en batería en el lado horizontal de dicha "T" y en línea o cordón en el lado vertical de la "T", que sirve además como pasillo de entrada al patio.

Ayude a Juan a encontrar la mejor forma de aparcar los coches, desarrollando un algoritmo que utilice una Heurística Voraz, de forma que consiga colocar la mayor cantidad de coches posibles y, de esta manera, pueda obtener la mayor suma de dinero en propinas.

Nota 1: En el patio solo cabe una hilera de coches en batería y otra a uno de los lados del pasillo de entrada.

Nota 2: Cada coche que llega al casino tiene unas dimensiones específicas A_i x L_i, que ya incluyen el espacio de separación necesario para poder aparcarlo.

4.- La Herencia. El abuelo Milbi Lletes está en las últimas y sus dos nietos le están insistiendo constantemente para que le cuente qué parte de su inmensa fortuna les deja. El abuelo por su parte no suelta prenda, pero sí les comenta que les dejará una parte de su fortuna a partes iguales.

Días más tarde el abuelo pasa a mejor vida y el Notario hace presencia en la mansión "Villa Billete". Una vez leído el testamento y llegando a la parte en la que a los nietos se hace referencia, el notario lee: “Yo Milbi Lletes quiero dejar todo lo contenido en esta lista de bienes indivisibles, cada uno tasado según la relación que se adjunta, a mis dos nietos, Loqui Erotodo y Paca To. El reparto, que queda en manos del notario, debe ser lo más equitativo posible.”.

El notario viendo lo que tardaría en cuadrar dicho problema, inteligente donde los haya, decidió llamar a dos estudiantes de Ampliación de la Programación para resolverlo. Éstos bien aleccionados en sus clases, le preguntaron que en caso de no ser exacta la división qué debían hacer. El notario tras pensarlo decidió que el mayor de los dos obtuviera la mayor parte.

Diseñe un algoritmo basado en Programación Dinámica que realice el reparto de las pertenencias.

Proponga un conjunto [razonable] de condiciones bajo las cuales se puede construir un algoritmo de complejidad polinomial en función del número de bienes a repartir y el coste de estos bienes. Diseñe dicho algoritmo.

5.- Cruzar un Puente Estrecho y Peligroso. Tenemos un grupo de N personas que tienen que cruzar un puente por el que solo pueden ir en fila de a uno, y que además, no soporta más que el peso de dos personas. Sabemos que el grupo solo dispone de una lámpara para alumbrarse y que cada persona p tarda un tiempo t_p en cruzar el puente. Además, cuando dos personas cruzan el puente tienen que llevar la lámpara consigo, y el tiempo que emplean en cruzarlo es el mayor de las dos personas.

Diseñe un algoritmo que devuelva cómo deben cruzar el puente para que el tiempo que empleen en ello sea mínimo. Aplíquelo al caso de un grupo de cinco personas, cuyos tiempos en cruzar el puente de cada componente del grupo son: 1, 3, 6, 8 y 12 minutos.

6.- Backtracking. Resuelva el juego del Sudoku.

7.- Juego: En un grafo, cada vértice tiene un cierto valor, el botín. Dos ladrones, partiendo del mismo vértice y de forma alternativa, podrán ir a cualquiera de los vértices adyacentes que aún tengan botín. Si alguno no pudiera moverse, por no tener botín ninguno de sus adyacentes, pasaría el turno al otro. El juego acaba cuando ninguno de los jugadores pueda moverse. Ganará el que más dinero consiga.

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