Estructuras de Datos - I.T.Informática Gestión

Curso 00/01 - Primera Práctica

Analizar experimentalmente la complejidad temporal, para el caso promedio (vectores con valores al azar), de las 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, al cual se le ha añadido una condición de salida adicional: Terminar cuando no se hallan realizado intercambios en el bucle interno (en ese caso el vector ya está ordenado).
• La segunda variante comienza realizando 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, terminando la operación de peinado cuando llegue a tener el valor 1. Entonces se llama al algoritmo anterior para que realice efectivamente la ordenación.

El método de análisis consistirá en implementar los algoritmos incluyendo instrucciones que cuenten el número de operaciones ejecutadas, T, en las que interviene algún elemento del vector. El algoritmo se ejecutará para diversos tamaños del vector, obteniendo una tabla de valores de T en función de n (es recomendable ejecutar el programa varias veces, 100 como mínimo, para cada tamaño dado y calcular el valor medio de T(n) y su desviación estándar).
Tras obtener estos datos, se probarán distintas funciones de cota, f(n), hasta encontrar una que cumpla , lo que será un indicio que el algoritmo pertenece a .

La documentación que se debe aportar consistirá en:

• Los programas con que se ha realizado la evaluación (en disquete).
• Para cada algoritmo, la función de cota encontrada, f(n), y la constante de proporcionalidad, T(n)/f(n).
• Las tablas con los valores medios y la constante de proporcionalidad en función de los tamaños del vector, n, con los que se ha probado el algoritmo (sólo para la función de cota propuesta). Indicar también el número de repeticiones realizadas para cada tamaño del vector.
• El ánalisis del comportamiento del algoritmo cuando se cambia el valor 1.3 por otro (si el algoritmo mejora, empeora, cambia su función de cota, etc.).

Se dispone de un vector que almacena n puntos, p₁..p_n, ordenado por sus coordenadas horizontales, (p_i.x <= p_i+1.x), y se desea encontrar cual es el par de puntos que estén separados por una distancia mínima.

Se define la distancia entre dos puntos i y j del vector como . El problema consiste en encontrar los índices i y j que hacen mínima esa distancia. Por supuesto, los índices deben ser distintos, y no necesariamente contiguos. En el caso en que varios pares de puntos estuvieran separados por la misma distancia mínima, cualquiera de ellos serviría como solución.
Una solución obvia, de complejidad O(n²), es medir, para cada punto, la distancia entre él y el resto de puntos del vector, manteniendo la información del resultado menor. Encontrar e implementar una solución menos costosa utilizando una estrategia divide y vencerás.

La documentación que se debe aportar consistirá en:

• Los programas que resuelven el problema (en disquete).
• Un esquema básico que indique la manera en que se ha aplicado la estrategia divide y vencerás al problema
• Analizar, siguiendo el método expuesto en el problema anterior, el comportamiento del algoritmo cuando las coordenadas de los puntos son valores aleatorios, proponiendo una función de cota que de cuenta del número de comparaciones de distancias entre puntos realizadas en función del tamaño del vector. Indicar el rango de tamaños del vector que se han comprobado.

Desarrollar un programa que obtenga, para una determinada competición deportiva, la quiniela con mayor probabilidad de obtener un pleno y cuyo coste sea menor que uno dado.

Una quiniela consiste en realizar un pronóstico sobre el resultado de cada uno de n partidos. En cada partido se enfrentan dos equipos, uno de ellos juega en casa, y el resultado puede ser victoria, empate o derrota (siempre desde la perspectiva del equipo que juega en casa).

Disponemos de tres vectores, v₁..v_n, e₁..e_n y d₁..d_n, donde los valores v_i, e_i, d_i, indican, respectivamente, la probabilidad de que el partido i acabe en victoria, empate o derrota. Por supuesto, se cumple que para todo i que v_i+e_i+d_i = 1.

Para simplificar el problema supondremos que hacer un pronóstico sobre un partido consiste en proporcionar un valor en el rango de 1 a 7, con el significado mostrado en la tabla siguiente:

Se supondrá que el precio de una quiniela donde todos los pronósticos sean simples es de 1 euro. Se puede apreciar que cada pronóstico doble debe duplicar el precio de la quiniela, ya que escribir un pronóstico doble para el partido i equivale a presentar dos quinielas con el resto de pronósticos iguales y un pronóstico simple con cada uno de los dos casos pronosticados en el partido i. Igualmente, cada pronóstico triple debe triplicar el coste.

Por lo tanto, el coste de una quiniela con a pronósticos dobles y b pronósticos triples será de 2^a·3^b euros. Supondremos que el precio máximo que nos podemos permitir pagar por la quiniela son C euros.

La probabilidad de que tengamos un pleno en la quiniela (todos los pronósticos sean correctos) será igual al producto de las probabilidades de acertar cada pronóstico. El objetivo será encontrar la quiniela con mayor probabilidad de tener un pleno pero cuyo precio no supere el valor C.

Se deberá presentar la siguiente documentación:

• El programa que resuelve el problema (en disquete).
• Un esquema básico que indique la estrategia utilizada para resolver el problema y cómo se ha aplicado a su resolución.
• Una estimación teórica del orden de complejidad del algoritmo.

Como parte opcional, se propone el adaptar el problema anterior a las características de la quiniela futbolística española.

• Las prácticas constarán de dos partes, la documentación solicitada en los enunciados (en papel) y los programas asociados (en disquete), y se entregarán en el examen teórico de la asignatura (convocatorias ordinaria y extraordinaria).
• Los programas se pueden implementar en Eiffel, Java o Delphi. Si desea usar otro lenguaje o entorno consulte con el profesor.