Tarea 8 y Examen 4 de Diseño de Algoritmos
Trimestre 2010 Otoño
Entrega: 8 de diciembre de 2010 a las 13:00.
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 8 de diciembre de 2010 a las
13:00.
Tarea 8: 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.