Estructuras de Datos - I.T.Informática Sistemas

Curso 99/00 - Primera Práctica

Apartado 1

Analizar experimentalmente la complejidad temporal, para el caso promedio (vector con valores al azar), de dos variantes del algoritmo de ordenación por intercambio (ordenación burbuja) que se exponen a continuación:

La primera variante es el algoritmo clásico de la burbuja pero detectando si en el bucle interno se han realizado intercambios o no. Si no se han realizado intercambios se termina el algoritmo puesto que eso significa que el vector ya está ordenado.
La segunda variante hace uso del algoritmo anterior, pero previamente realiza una operación de peinado sobre los datos: Se recorre varias veces el vector, intercambiando los elementos separados d celdas entre sí que se encuentren mal situados. La distancia d disminuye en cada recorrido, finalizando la operación de peinado cuando llegue a tener valor 1. Entonces se llama al algoritmo anterior para que realice efectivamente la ordenación.

Modulo Burbuja Entradas V: Vector[1..N] de TDato Salidas V: Vector[1..N] de TDato Variables I,J : Enteros; Cambio : Booleana Inicio I <- 1 Repetir Cambio <- Falso Para J <- N hasta I+1 incr 1 Si V[J-1] > V[J] entonces Intercambiar(V,J-1,J) Cambio <- Cierto Fin_Si Fin_Para I <- I + 1 Hasta_Que (I = N) O No Cambio Fin Modulo Burbuja_Peinada Entradas V: Vector[1..N] de TDato Salidas V: Vector[1..N] de TDato Variables I,D : Enteros; Inicio D <- Truncar(N/1.3) Repetir Para I <- 1 hasta N-D incr 1 Si V[I] > V[I+D] entonces Intercambiar(V,I,I+D) Fin_Si Fin_Para D <- Truncar(D/1.3) Hasta_Que D < 2 Burbuja(V) Fin

El método de análisis consistirá en implementar los algoritmos incluyendo instrucciones que cuenten el número de operaciones ejecutadas, T(n), para diversos tamaños, n, del vector. Tras obtener estos datos, se probarán distintas funciones de cota, f(n), hasta encontrar una que cumpla , lo que indica que el algoritmo pertenece a .

Nota: Sólo es necesario contar aquellas operaciones en las que interviene un elemento del vector.

Parte opcional: Analizar el comportamiento del segundo algoritmo cuando se cambia el valor 1.3 por otro.

Mostrar información adicional sobre este apartado

Apartado 2

Se dispone de un vector que almacena n puntos, p₁..p_n, el cual se encuentra ordenado por las coordenadas x de los puntos (p_i.x <= p_i+1.x), y se desea encontrar cual es el par de puntos más cercano.

Se define la distancia entre los puntos i y j del vector como . El problema consiste en encontrar los índices i y j que hacen mínima esa distincia. Por supuesto, los índices deben ser distintos, y no necesariamente contiguos.

Una solución obvia, de complejidad O(n²), es medir, para cada punto, la distancia entre él y el resto de puntos del vector, quedándonos con la distancia menor. Encontrar e implementar una solución menos costosa utilizando una estrategia divide y vencerás.

Parte opcional: Analizar matemáticamente el orden de complejidad de la solución obtenida, aplicando suposiciones razonables sobre los datos de entrada (por ejemplo, que se encuentran distribuidos mas o menos uniformemente respecto a la coordenada x).

Cerrar información adicional sobre este apartado

Propuesta de resolución del problema:

El problema de encontrar el par de puntos mas cercanos del conjunto p_a..p_b puede dividirse en los subproblemas de encontrar el par más cercano del subconjunto p_a..p_m y el par más cercano del subconjunto p_m+1..p_b, donde m = (a+b) div 2.
Al resolver los dos subproblemas, obtenemos dos pares de puntos, un par por subconjunto. Nos quedamos con el par más cercano. Supongamos que la distancia de ese par es d.
Ese par puede no ser el más cercano de p_a..p_b si da la casualidad de que existe un par más cercano aún cuyo primer punto esté en p_a..p_m y cuyo segundo punto esté en p_m+1..p_b. Ese par no sería detectado al resolver los subproblemas.
Para tener en cuenta esa situación, comprobamos los pares formados por un primer punto perteneciente a p_a..p_m y el segundo perteneciente a p_m+1..p_b. El punto clave del algoritmo es que no hay que comprobar todos estos puntos, puesto que sabemos que la distancia del par debe ser menor que d (la menor distancia encontrada al resolver los subproblemas).
Por lo tanto sólo se puede obtener un par mínimo con aquellos puntos de p_a..p_m cuya coordenada x esté a una distancia menor que d de p_m+1 (el punto mas cercano de la otra parte) y, analogamente, con aquellos puntos de p_m+1..p_b cuya coordenada x esté a una distancia menor que d de p_m (el punto más cercano de la otra parte).

Apartado 3

Dado un conjunto de n objetos, o₁..o_n, con valores asociados a₁..a_n (enteros positivos no nulos), el problema del reparto equitativo consiste en determinar si se puede dividir el conjunto en dos partes que valgan exactamente lo mismo, y en ese caso, decir a cual de las dos partes pertenece cada objeto.

De forma más rigurosa, el problema se puede definir como encontrar (o demostrar que no existe) un subconjunto, C, del conjunto original de objetos, A, que cumpla:

Implementar una solución al problema obtenida mediante la estrategia de fuerza bruta, y analizar su complejidad espacial y temporal.
Implementar una solución al problema obtenida mediante la estrategia de backtracking.
Implementar una solución al problema planteado (o a un problema equivalente) obtenida mediante la estrategia de programación dinámica, y analizar su complejidad espacial y temporal.

Parte opcional: Analizar experimentalmente (usando las mismas técnicas que en el primer apartado) la solución obtenida por backtracking.

Mostrar información adicional sobre éste apartado

Normas de entrega

Se entregará un disquete con los programas que implementen las soluciones a los distintos problemas propuestos, junto con una hoja donde se indiquen los nombres de los programas y los resultados pedidos correspondientes a cada apartado.
Los programas se pueden implementar en Eiffel, Java o Delphi. Si desea usar otro lenguaje o entorno consulte con el profesor.
Resolver correctamente las partes opcionales de los apartados supone una calificación adicional.
La fecha límite de entrega es el 31 de mayo de 2000.