SandovalPadillaReporteActividad 7 - Fernando Cesar Sandoval Padilla

Vista previa del material en texto

UNIVERSIDAD DE GUADALAJARA
Centro Universitario de Ciencias Exactas e Ingenierías
Algoritmia
Actividad 7: Algoritmos de divide y vencerás 
Alumno: Sandoval Padilla Fernando Cesar
Docente: Ibarra Chávez Salomón Eduardo
Código: 215685409
Sección: D02
	
2 de Abril de 2020
Algoritmos de divide y vencerás
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). 
:ent
void quicksort (int *array, int start, int end)
{
int pivot; if (start>end)
{
pivot = divide (array, start, end); ///Menores
quicksort (array, start, pivot – 1); ///Mayores
quicksort (array, pivot + 1, end);
}
}
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. 
Algoritmo recursivo
Hanói (dim N, palo A, palo B, palo C)
///N, origen, destino, auxiliar
Si N ==1
Imprimir: Pasar disco de A a B
Else
Hanoi (N-1, A, C, B)
Imprimir: Psar disco de A a B
Hanói(N-1, C, B, A)
Algoritmo en el caso de tres discos:
Hanói(3, 1, 2, 3) 
Hanói(1, 1, 2, 3) cambia de 1 a 2
Hanói(2, 1, 3, 2) cambia de 1 a 3 cambia de 1 a 3
Hanói(1, 2, 3, 1) cambia de 2 a 3
cambia de 1 a 2 cambia de 1 a 2 cambia de 1 a 2
Hanói(1, 3, 1, 2) cambia de 3 a 1
Hanói(2, 3, 2, 1) cambia de 3 a 2 cambia de 3 a 2
Hanói(1, 1, 2, 3) cambia de 1 a 2
3. Encuentra el orden de crecimiento para las soluciones de las siguientes recurrencias.
a) T(n)=4T(n/2)+n, T(1)=1 Asintótico en 2n3
b) T(n)=4T(n/2)+n2, T(1)=1 Asintótico en n2
c) T(n)=4T(n/2)+n3, T(1)=1 Asintótico en 3n2