Tarea 10 y Examen 4b de Diseño de Algoritmos
Trimestre 2012 Primavera
Entrega: 18 de julio de 2012
Cada uno de los siguientes problemas vale un máximo de 10
puntos. Su calificación dependerá de que el diseño
y análisis del algoritmo estén bien y de qué tan
rápido sea. No use más de una página para
contestar cada problema. Entregue su tarea y examen engrapados en mi
oficina (H-264) a más tardar el 18 de julio de 2012 a las
11:30.
Tarea 10: Diseñe y analize un algoritmo
para la arquitectura PRAM que calcule la suma de N enteros A1,
A2, ..., AN usando N procesadores y que haga
menos de N pasos.
Problema 1 del examen: Diseñe y analize un algoritmo para
la arquitectura PRAM que calcule la posición del mínimo
de N enteros A1, A2, ..., AN usando N
procesadores y que haga menos de N pasos. En caso de empate, su
algoritmo debe regresar la posición más a la izquierda.
Problema 2 del examen:
Diseñe y analize un algoritmo para la arquitectura PRAM que
calcule el producto de dos matrices de N por N usando N procesadores y
que haga menos de N3 pasos.
Problema 3 del examen:
Diseñe y analize un algoritmo para la
arquitectura PRAM que calcule el producto de dos matrices de N por N
usando N2 procesadores y que haga menos de N2
pasos.
Problema 4 del examen:
Diseñe y analize un algoritmo para la
arquitectura PRAM que calcule el producto de dos matrices de N por N
usando N3 procesadores y que haga menos de N pasos.