Actividad 3 - Algoritmo Paralelo. Aplicación en 3 Lenguajes de Programación

Para nuestra 3ª actividad, implementaremos el algoritmo paralelo descrito en la Actividad 2, en 3 lenguajes de programación diferentes.

Cabe mencionar que la paralelización como tal sera implementada por medio de hilos, los cuales se ejecutan simultaneamente efectuando las operaciones de "acomodar" los números de nuestro arreglo.

Diagrama de Flujo

Ejemplo en Java 

 Para el ejemplo en java, utilizamos una sola clase, la cual implementa los metodos de la clase Runnable y nos permite instanciarla como un hilo independiente, cada vez que se ejecuta el metodo run()

Para el acomodo de los objetos utilizamos el metodo de ordenamiento QuickSort

Ejemplo en Ruby 

 Implementacion de hilos en Ruby

Metodo de ordenamiento QuickSort en Ruby

Ejemplo en Python 

 Implementacion de hilos en Python

Metodo de ordenamiento QuickSort en Python

Actividad 2 - Algoritmo Paralelo (QuickSort)

Una de las más importantes utilidades de los multi-computadores es su uso en la computación algorítmica para obtener velocidad y eficacia. Se propone el diseño e implementación de un algoritmo paralelo que implemente las metodologías de Divide y Vencerás aplicado al QuickSort.

Divide y Vencerás 

La estrategia Divide y Vencerás consiste en descomponer un problema en subproblemas más simples del mismo tipo, resolverlos de forma independiente y una vez obtenidas las soluciones parciales combinarlas para obtener la solución del problema original. 

QuickSort

El ordenamiento rápido (quicksort en inglés) es un algoritmo creado por el científico británico en computación C. A. R. Hoare basado en la técnica de divide y vencerás, que permite, en promedio, ordenar n elementos en un tiempo proporcional a n log n.(fuente)

El algoritmo trabaja de la siguiente forma:

• Elegir un elemento de la lista de elementos a ordenar, al que llamaremos pivote.
• Re-situar los demás elementos de la lista a cada lado del pivote, de manera que a un lado queden todos los menores que él, y al otro los mayores. Los elementos iguales al pivote pueden ser colocados tanto a su derecha como a su izquierda, dependiendo de la implementación deseada. En este momento, el pivote ocupa exactamente el lugar que le corresponderá en la lista ordenada.
• La lista queda separada en dos sublistas, una formada por los elementos a la izquierda del pivote, y otra por los elementos a su derecha.
• Repetir este proceso de forma recursiva para cada sublista mientras éstas contengan más de un elemento. Una vez terminado este proceso todos los elementos estarán ordenados.

Como se puede suponer, la eficiencia del algoritmo depende de la posición en la que termine el pivote elegido.

• En el mejor caso, el pivote termina en el centro de la lista, dividiéndola en dos sublistas de igual tamaño. En este caso, el orden de complejidad del algoritmo es O(n·log n).
• En el peor caso, el pivote termina en un extremo de la lista. El orden de complejidad del algoritmo es entonces de O(n²). El peor caso dependerá de la implementación del algoritmo, aunque habitual mente ocurre en listas que se encuentran ordenadas, o casi ordenadas. Pero principal mente depende del pivote, si por ejemplo el algoritmo implementado toma como pivote siempre el primer elemento del array, y el array que le pasamos está ordenado, siempre va a generar a su izquierda un array vacío, lo que es ineficiente.
• En el caso promedio, el orden es O(n·log n).

No es extraño, pues, que la mayoría de optimizaciones que se aplican al algoritmo se centren en la elección del pivote.

La implementación del método Divide y Vencerás sobre el algoritmo de QuickSort, quedaría representada por la siguiente imagen:

Donde: 

1. Tendremos un arreglo de números inicial.
2. Seleccionaremos el primer número de la lista el cual sera nuestro pivote.
3. Un nuevo proceso acomodara los números menores al pivote en un nuevo arreglo y los mayores al pivote en otro arreglo.
4. Crearemos nuevos procesos para los siguientes arreglos, siguiendo esta metodología hasta llegar a las "hojas" de nuestro árbol.
5. Al terminar, los procesos devolverán su correspondiente resultado ya ordenado al proceso principal el cual únicamente los acomodara y dará un resultado.

En la práctica, este algoritmo se maneja de forma iterativa, nosotros buscamos mejorar el tiempo de respuesta en este de por si rápido algoritmo de ordenamiento por medio de la paralelización.

Laboratorio

Equipo # 1

Integrantes

• Alma Dalia Del Angel Castillo
• Lucia Guadalupe Moyeda Cornejo
• Alexis Eliud Villegas Rodríguez
• Mario Alberto Mena Ocariz

Listado de Compromisos

Compromisos de entrega de actividades

Actividad	Fecha Entrega	Descripción	Estado	Calificacion
1	14/02/2013	Diseño, estructuración y puesta en linea del Blog	Completo	95
2	21/02/2013	Algoritmo en Paralelo	Completo	100
3	28/02/2013	Aplicación en 3 Lenguajes de Programación	Completo
4	07/03/2013	Análisis y Conclusion de las Aplicaciones	Pendiente
5	11/04/2013	Algoritmo Distribuido	Pendiente
6	18/04/2013	Manejo de Memoria y Recursos	Pendiente
7	25/04/2013	Objetivos del Sistema Distribuido	Pendiente
8	02/05/2013	Presentación del Caso de Aplicación y Detalles	Pendiente
9	09/05/2013	Fases y Planeación de la Implementación	Pendiente
10	16/05/2013	Resultado Final, Evidencias y Conclusión	Pendiente

Actividades

Actividad 1
Descripción:	Crear Blog de Laboratorio, crear estructura.
Status:	Completo
Fecha de Finalización:	14/02/2013
Calificación:	95
Actividad 2
Descripción:	Investigar y documentar el uso de un Algoritmo Paralelo.
Status:	Completo
Fecha de Finalización:	21/02/2013
Calificación:	100
Actividad 3
Descripción:	Aplicación en 3 Lenguajes de Programación.
Status:	Completo
Fecha de Finalización:	28/02/2013
Calificación:	Pendiente

Proyecto

Descripción
Objetivo
Bitácora
Gráfico Gantt
Implementación
Calificación

Proyecto

Proyecto

Descripción
Objetivo
Bitácora
Gráfico Gantt
Implementación
Calificación

Alma Dalia Del Angel Castillo

Fecha de Nacimiento: 29 de Enero de 1992

Lugar de Nacimiento: Cd. Victoria, Tamp.

Lugar de Residencia: Monterrey, Nuevo León

Ocupación: Estudiante

Intereses personales: Gusto por la Tecnología, especialmente el área de Inteligencia Artificial y Redes Neuronales Artificiales, también gusto por la electrónica y robótica. Me apasionan los videojuegos de género RPG y de estrategia, así como la música y los deportes. Actualmente estudio en la Facultad de Ingeniería Mecánica y Eléctrica, específicamente la carrera de Ingeniería en Tecnología del Software.

Objetivos particulares con respecto a clases: Conocer, saber diferenciar y saber implementar un sistema distribuido y/o uno paralelo, saber optimizarlo y trabajar con uno para de esta manera poder trabajar con uno de estos sistemas en alguna industria en un futuro no muy lejano.

Alexis Eliud Villegas Rodríguez

Alexis Eliud Villegas Rodríguez

Fecha de Nacimiento: 31 de julio de 1992

Lugar de Nacimiento: Monterrey, Nuevo León

Lugar de Residencia: Monterrey, Nuevo León

Ocupación: Estudiante

Intereses personales:Sencillo,ocioso y curioso por la tecnología.  Me gusta mucho el desarrollo en dispositivos móviles(Smarthphone) en especial Android. Aficionado al diseño y con una gran creatividad e imaginación para explotarlo.

Actualmente soy un  estudiante de la Facultad de Ingeniería Mecánica y Eléctrica, en la carrera de Ingeniería de Tecnología  de Software.

Objetivos particulares con respecto a clases: El uso de un sistema distribuido y paralelo para poder identificar mediante la practica las diferencias notables en dichos sistemas al igual aplicar el uso de una red neuronal inteligente para crear un sistema adaptativo para el uso con 2 sistemas.

Mario Mena

Mario Mena

Lugar de Nacimiento: México,D.F.

Ocupación: Estudiante

Intereses personales: Gusto por la Tecnología, Biología y un poco de Sociología; me interesa sobre manera el área de desarrollo enfocado a Redes Neuronales Artificiales e Inteligencia Artificial. Aficionado a los videojuegos de contenido artístico y diferente, apasionado de la buena comida y las pláticas interesantes con mucho contenido intelectual.

Actualmente estudio en la Facultad de Ingeniería Mecánica y Eléctrica, específicamente la carrera de Ingeniería en Tecnología del Software.

Objetivos particulares con respecto a clases: Mi principal objetivo es obtener los conocimientos básicos y necesarios para desarrollar sistemas que implementen las tecnologías de Distribución y/o Paralelismo, con lo cual pretendo desarrollar a corto plazo soluciones integrales para usos generales en la industria o áreas de investigación.