Tarea 8 y Examen 4 de Diseño de Algoritmos
Trimestre 2012 Otoño
Entrega: 29 de noviembre de 2012 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 29 de
noviembre de 2012 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 log2 N pasos.
Problema 1 del examen: Diseñe y analize un algoritmo
para la arquitectura PRAM que calcule la posición
del máximo de N enteros A1, A2, ..., AN
usando N procesadores y que haga log2 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
con escritura común que calcule la posición
del máximo de N enteros A1, A2, ..., AN
usando N2 procesadores y que haga una cantidad constante
de pasos. En caso de empate, su algoritmo debe regresar la
posición más a la izquierda.
Problema 3 del examen:
Diseñe y analize un algoritmo para la arquitectura PRAM
con escritura común que calcule el or booleano
de N variables booleanas A1, A2, ..., AN
usando N procesadores y que haga una cantidad constante de pasos.
Problema 4 del examen:
Diseñe y analize un algoritmo para la arquitectura PRAM
con escritura común que calcule el and booleano
de N variables booleanas A1, A2, ..., AN
usando N procesadores y que haga una cantidad constante de pasos.