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 1.000, 10.000 y 100.000 elementos enteros. Recopile datos sobre distintas máquinas.

2.- Tenemos un tablero cuadrado de dimensión 2^m (tiene, pues 2^2m celdas) y una tesela en forma de L, como puede observarse en la figura. Diseñe un algoritmo Divide y Vencerás, que cubra todo el tablero utilizando teselas en forma de L como las de la figura, supuesto que ya tenemos cubierta una casilla.

3.- Marcos es el encargado de colocar los cuadros en el Museo Artístico Nacional. El director de este museo tiene la mala costumbre de cambiar los cuadros demasiado a menudo y Marcos está harto de trabajar para colocar y recolocar los cuadros una y otra vez. El museo tiene S salas de dimensión A_j x L_j metros, para cada sala j. Cada sala puede tener hasta cuatro puertas, que dan a salas contiguas. Todas las puertas miden P metros. Cada cuadro tiene una anchura C_i. Diseñe una heurística voraz que ayude a Marcos a colocar los N cuadros de la exposición de manera que se utilice el menor número de salas posible.

Nota 1: No se puede colocar un cuadro encima de otro.

Nota 2: Considere que en el ancho de cada cuadro C_i ya está incluido el espacio de separación entre cuadro y cuadro.

4.- Problema Simplificado de Transporte. Se tienen dos almacenes A₁ y A₂, y n comercios c₁, c₂,..., c_n. En cada almacén hay e₁ y e₂, respectivamente, unidades indivisibles de un producto; y en cada comercio se necesitan v_j (j= 1, 2,..., n). Además, se verifica:

El coste de transporte de A_i a C_j viene dado por la función Coste_ij(x), donde x es el número de unidades transportadas.

Se pide la solución óptima, i.e., de coste mínimo, para el problema de abastecimiento a los comercios, por un método de Programación Dinámica.

5.- Resuelva el problema 3 por un método basado en Backtracking.

6.- El puzzle diabólico. Con las piezas planas que se muestran a continuación se pretende formar un cuadrado, teniendo en cuenta que las piezas se pueden girar (solo en incrementos de 90º) y que pueden ser volteadas. Diseñe un algoritmo que encuentre la solución.

Solución:

7.- El juego de las reinas. Darío, “el presi”, entre sus múltiples actividades sociales dentro de la prisión, se ha inventado un nuevo juego con el que está intentando ganar vales de tabaco a sus compañeros de reclusión. El juego que Darío se ha inventado se basa en el problema de las n damas de ajedrez que deben ser colocadas en un tablero de n x n celdas sin que se ataquen entre ellas, sabiendo que la dama del ajedrez ataca a todas las piezas que se encuentren en su misma fila, columna o alguna de las dos diagonales que pasan por la casilla en la que se encuentra la dama.

En el juego cada jugador, va colocando una dama, y sólo una, en su turno, siempre que la dama colocada no ataque a ninguna de las damas anteriormente colocadas. Aquel jugador que no puede colocar una dama, pierde el juego. Construya un algoritmo que dada una configuración del juego la evalúe, y devuelva la decisión que produce el resultado indicado.