Informatica

Resolución de Problemas en Paralelo
Coromoto León Hernández Sociedad, Ciencia, Tecnología y Matemáticas. 28 de Marzo de 2003 URL: http://nereida.deioc.ull.es/

A mis padres

¿A qué tipo de problemas hace referencia el título?
Problemas de Optimización
Existe una entrada de tamaño n en la que están los candidatos a formar parte de la solución Existe un subconjunto de esos n candidatos quesatisface ciertas restricciones (soluciones factibles) Hay que obtener la solución factible que minimiza o maximiza una cierta función objetivo (solución óptima)

28/03/2003

Sociedad, Ciencia, Tecnología y Matemáticas

¿Cómo podemos abordar la resolución de un problema dado?
Con lápiz y papel Con un ordenador secuencial Con una máquina paralela

28/03/2003

Sociedad, Ciencia, Tecnologíay Matemáticas

&

∈
'

§ ¥ ¢ ¨¦¤ £¡  

'

$ % #¤ ¢¢ " ¦¤  ¢ ¦¤ ! § ¥ ¢ ¡    © 9 ( 8£531) 76 4 20

28/03/2003

Sociedad, Ciencia, Tecnología y Matemáticas

¿Cómo proponemos resolverlos?
Un Algoritmo es un conjunto ordenado de operaciones que deben efectuarse para resolver un problema dado.

28/03/2003

Sociedad, Ciencia, Tecnología y Matemáticas

Proceso deresolución
Modelo Algoritmo

Herramientas

Implementación Secuencial

Herramientas

Implementación Paralela
28/03/2003 Sociedad, Ciencia, Tecnología y Matemáticas

1

Contenido de la charla
Un caso de estudio: El Problema de Mochila 0/1 Algoritmos… Ordenadores …. un poco de historia Técnicas Algorítmicas
Ramificación y Acotación Divide y Vencerás

El Problema de la Mochila
b = 100 p= 20 p = 30 b = 90 p = 20 p = 10 b=1 C = 102 b = 60 p=2 b = 15

Esqueletos Algorítmicos:
Secuenciales Paralelos
p = 40

b = 40 p = 30

b = 15 La capacidad C es 102 Los elementos N son 8 Beneficios bk= {15,100, 90, 60, 40, 15, 10, 1} Pesos pk= { 2, 20, 20, 30, 40, 30, 60, 10}

Conclusiones
b = 10 p = 60
28/03/2003 Sociedad, Ciencia, Tecnología y Matemáticas 28/03/2003

Sociedad,Ciencia, Tecnología y Matemáticas

Modelo

Modelo

Algoritmo

El Problema de la Mochila
Este problema lo podemos formular de la siguiente forma: “Se dispone de una mochila de capacidad C y de un conjunto de N objetos, siendo b[k] y p[k] el beneficio y el peso asociado al objeto k. Sin exceder la capacidad de la mochila, los objetos deben ser insertados en la mochila proporcionando el máximobeneficio”
=

Algoritmos (Al Khuwârizmî)
≤

∈{ ∀ ∈{
=

}

}

Intuitivamente un algoritmo es una sucesión finita de reglas elementales, regidas por una prescripción precisa y uniforme, que permite efectuar paso a paso, en un encadenamiento estricto y riguroso, ciertas operaciones de tipo ejecutable, con vistas a la resolución de problemas de una misma clase.
28/03/2003 Sociedad,Ciencia, Tecnología y Matemáticas

28/03/2003

Sociedad, Ciencia, Tecnología y Matemáticas

Alemania Nazi

Gran Bretaña Intercepción inglesa de los mensajes cifrados alemanes Transmisión de los textos por teletipos Escuela gubernamental de Cifra y Códigos de BLETCHLEY PARK

Alan Mathison Turing (1912-1954)
“Sobre los números calculables y su aplicación al problema de la decidibilidad” (1936)Define rigurosamente un Algoritmo Introduce los conceptos de
Máquina de Turing y Autómata Algorítmico Universal

Textos Alemanes (órdenes, instrucciones, Informaciones, etc.) no codificados

Máquinas criptográficas ENIGMA

Mensajes Alemanes Codificados EMISORAS DE RADIO

RECEPTORES DE RADIO

Recepción de Mensajes Codificados

Máquinas ENIGMA Recepción de Mensajes descodificadosCOLOSSUS

28/03/2003

Sociedad, Ciencia, Tecnología y Matemáticas

Órdenes, instrucciones, Informaciones Descifrado de mensajes Trasmitidas a los ejecutantes alemanes Sociedad, Ciencia, Tecnología y Matemáticas 28/03/2003

2

John von Neumann (1903-1957)

Máquinas de Turing
Existe una infinidad de Máquinas de Turing, cada una de las cuales define la estructura de una familia de...