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).

Mostrar información adicional sobre este apartado

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.

Cerrar información adicional sobre éste apartado

Puntos clave del problema propuesto:

La forma más conveniente de representar una solución al problema es mediante una secuencia x₁..x_n, donde cada x_i puede tomar el valor 0 (el objeto o_i pertenece a la primera parte) o 1 (el objeto o_i pertenece a la segunda parte). De esa forma, comprobar si una solución es válida se puede hacer así:

Generalmente no se aplicará la fórmula directamente, es más eficiente llevar sumas parciales en los algoritmos.
El punto clave del problema es que si existe una solución, el valor de cada parte debe ser igual al valor del conjunto original dividido por dos. Si llamamos al valor del conjunto original, sólo existirá una solución si S es divisible por 2 y conseguimos encontrar un subconjunto cuyo valor sea S/2 (la suma de los elementos que no pertenecen también valdrá S/2).
Lo anterior se puede usar como criterio en la solución por backtracking: Si se parte de que ningún objeto pertenece al subconjunto, y se van incorporando objetos, cuando el valor sea superior a S/2 se puede descartar ese camino hacia la solución.
Con el planteamiento original del problema no se puede aplicar facilmente la estrategia de programación dinámica. Pero si lo cambiamos al problema equivalente de comprobar si existe un subconjunto cuya suma valga un determinado valor (en este caso S/2), se puede aplicar programación dinámica de una manera muy sencilla.

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.