Durante esta actividad, los alumnos serán capaces de:
Esta actividad promueve las siguientes habilidades, valores y actitudes: análisis y síntesis, capacidad de resolver problemas, creatividad, y uso eficiente de la informática y las telecomunicaciones.
Esta actividad puede ser elaborada de manera individual o en parejas.
En la parte superior de cada archivo fuente coloca en comentarios los datos personales de los autores de la tarea. Por ejemplo:
/*-------------------------------------------------------------------- * Práctica 7: Fork/Join * Fecha: 6-May-2014 * Autores: * 1166611 Pepper Pots * 1160611 Anthony Stark *--------------------------------------------------------------------*/
Los siguientes problemas fueron tomados de [PACHECO] pp. 267 y 268.
Supongamos que lanzamos dardos al azar a un tablero cuadrado, que mide dos metros de cada lado l, y que contiene un círculo que mide un metro de radio r, tal como se muestra en la siguiente figura:
El área del cuadrado es l × l = 2 × 2 = 4, mientras que el área del círculo es π × r 2 = π × 12 = π. Si los puntos en los que caen los dardos están distribuidos de manera uniforme (y siempre dentro del cuadrado), entonces se cumple aproximadamente con la siguiente relación:
número de tiros dentro del círculo π
_______________________________________ = ___
número total de tiros 4
Podemos utilizar esta fórmula para estimar el valor de pi utilizando un generador de número aleatorios:
public static double sequentialMonteCarlo(int n) { Random rnd = new Random(); int sum = 0; for (int i = 0; i < n; i++) { // Generar dos números aleatorios entre -1 y 1. double x = rnd.nextDouble() * 2 - 1; double y = rnd.nextDouble() * 2 - 1; // Aplicar teorema de Pitágoras. double h = x * x + y * y; // Verificar si el tiro cayó dentro del círculo. if (h <= 1) { sum++; } } return 4 * ((double) sum / n); }
A este algoritmo se le llama método de “Monte Carlo” debido a que involucra eventos aleatorios (los tiros de dardos).
Crea el archivo MonteCarloTask.java y escribe en éste una clase llamada edd.util.MonteCarloTask, la cual debe heredar de la clase java.util.concurrent.RecursiveTask<V>, con el fin de paralelizar el problema anterior. Prueba tu código con el archivo MonteCarlo.java. La salida esperada al ejecutar el programa en un sistema con dos núcleos debe ser similar a la siguiente (los resultados y tiempos pueden variar):
Resultado secuencial = 3.141503 Ts = 19.96 seg. Resultado paralelo = 3.141528 Tp = 10.79 seg. Sp = Ts / Tp = 1.8492
Count Sort (ordenamiento por conteo) es un algoritmo de ordenamiento que puede ser implementado de manera secuencial como se muestra a continuación:
public static void sequentialCountSort(int a[]) { final int n = a.length; final int[] temp = new int[n]; for (int i = 0; i < n; i++) { int count = 0; for (int j = 0; j < n; j++) { if (a[j] < a[i]) { count++; } else if (a[i] == a[j] && j < i) { count++; } } temp[count] = a[i]; } System.arraycopy(temp, 0, a, 0, n); }
Para cada elemento a[i] del arreglo a, contamos el número de elementos del arreglo que son menores a a[i]. Posteriormente insertamos a[i] a un arreglo temporal usando como índice el resultado del conteo correspondiente. Solo hay un pequeño detalle que cuidar, ya que si hay elementos repetidos en el arreglo a éstos ocuparían la misma localidad dentro del arreglo temporal. Pare evitar este problema, el código incrementa el contador para elementos iguales en base a sus índices. Es decir, si a[i] == a[j] y j < i, entonces consideramos a a[j] como “menor que” a[i].
Una vez que concluye el algoritmo, sobre-escribimos el arreglo original con el contenido del arreglo temporal usando el método System.arraycopy().
Crea el archivo CountSortAction.java y escribe en éste una clase llamada edd.util.CountSortAction, la cual debe heredar de la clase java.util.concurrent.RecursiveAction, con el fin de paralelizar el problema anterior. Prueba tu código con el archivo CountSort.java. La salida esperada al ejecutar el programa en un sistema con dos núcleos debe ser similar a la siguiente (los tiempos pueden variar):
Antes de ordenamiento secuencial, arreglo ordenado: false Después de ordenamiento secuencial, arreglo ordenado: true Ts = 60.36 seg. Antes de ordenamiento paralelo, arreglo ordenado: false Después de ordenamiento paralelo, arreglo ordenado: true Tp = 28.99 seg. Sp = Ts / Tp = 2.0824
Coloca los dos archivos MonteCarloTask.java y CountSortAction.java dentro de un archivo ZIP llamado practica7.zip. Sube este último archivo usando el Sistema de Entrega de Tareas Automatizado. No se aceptan tareas por ningún otro medio.
Fecha límite: Martes, 6 de mayo.
Esta actividad será evaluada usando los siguientes criterios:
| 100 | La actividad cumple con todos los requerimientos. |
|---|---|
| -10 | No se incluyó en comentario los datos de los autores. |
| 10 | El programa fuente no compila. |
| 50-90 | El programa produce algunos errores al momento de correrlo. |
| DA | La solución es un plagio. |