Logo Studenta

Actividad07_Martinez_Nava_Jorge_Justino - Fernando Cesar Sandoval Padilla

Vista previa del material en texto

Universidad de Guadalajara 
 
Centro Universitario de Ciencias Exactas e Ingeniería 
 
Algoritmia 
 
Profesor: Salomón Eduardo Ibarra Chávez 
 
Alumno: Jorge Justino Martinez Nava 
 
Actividad 07 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
1. Implementa el algoritmo del SAR para 4 y 8 bits de 
precisión, en C/C++ o Java; de tal manera que se muestre en 
pantalla el desarrollo del SAR hasta llegar a la solución (con 
4 y 8 bits). Muestre la tasa entre la precisión y la 
complejidad O(n). 
 
 
 
El tiempo de ejecución de un algoritmo de divide y vencerás, T(n), viene 
dado por la suma de dos elementos: El tiempo que tarda en resolver los A 
subproblemas en los que se divide el original, A·T(n/B), donde n/B es el 
tamaño de cada sub-problema. El tiempo necesario para combinar las 
soluciones de los sub-problemas para hallar la solución del original; 
normalmente es O (nk) Por tanto, el tiempo total es: T(n) = A·T(n/B) + O (n 
k). La solución de esta ecuación, si A es mayor o igual que 1 y B es mayor 
que 1, es: 
 
si A>Bk 
 
T(n) = O(nlog B A) 
 
si A=Bk 
 
 T(n) = O(nk log n) 
 
si A<Bk 
 
 T(n) = O(nk) 
 
 
 
2. El algoritmo recursivo para las torres de Hanoi conviertalo a 
explícito con n=11 y posteriormente codificarlo con 
OpenMP....comparar tiempos de ejecución.

Otros materiales