Sesión 9

Vista previa del material en texto

UPN, PASIÓN POR
TRANSFORMAR VIDAS
SESIÓN 9: Divide y vencerás
Ing. Mitchell Blancas
ANALISIS DE ALGORITMOS Y ESTRATEGIAS DE PROGRAMACION
LOGRO DE LA SESIÓN
Al término de la sesión el estudiante aplica divide y vencerás en la solución de problemas propuestos y los representa a través de algoritmos.
¡Pregunta!
¿Aplicas la técnica divide y vencerás en el día a día?
Divide y Vencerás (DyV)
Esquema general
Inicio
Si el problema es pequeño 
 Resolverlo
Sino
 cant = Descomponer en subproblemas
 Para ( i = 0; i < cant; i = i+1 ) Hacer
 Resolver_Suproblema(i)
 Fin_Para 
 Combinar los resultados
Fin_Si 
Fin
Cuando la cantidad de subproblemas es la unidad se llama simplificación o reducción.
Análisis de la complejidad de funciones DyV
Ciertamente el análisis de la complejidad de funciones recursivas es más complejo, debiendo utilizar las llamadas funciones de recurrencia, las cuales deben ser resueltas.
Sin embargo, las funciones DyV se pueden resolver fácilmente aplicando el llamado Teorema Maestro.
Teorema Maestro
 Θ(1), si n<=no
T(n) 
 aT(n/b) + Θ(nk), si n > no
Donde:
a>=1
b>1
k>=0
no>=0
Si el tamaño del problema es pequeño (n<=no), entonces se puede resolver en tiempo constante.
Si el tamaño del problema es grande (n>no), entonces dividimos el problema en a subproblemas de tamaño n/b.
El valor de a es el número de veces en que se llaman recursivamente, y n/b es el tamaño de la entrada en cada llamada.
El término Θ(nk), especifica la cantidad de tiempo requerido para realizar la descomposición, así como el tiempo requerido para combinarlas.
Θ(nk) si a<bk
Θ(nk log n ) si a=bk 
Θ(nlog ba) si a>bk
Potencia entera de un número
Escriba un programa para elevar un número a una potencia entera, esto es:
Xn
# include <iostream.h>
int potencia(int, int);
int main() {
 int b, e;
 cout<<"Base: "; cin>>b;
 cout<<“Exponente: "; cin>>e;
 cout<<potencia(b, e)<<endl;
}
int potencia (int b, int e) {
 if (e==0) return 1;
 if (e==1) return b;
 if (e==2) return b*b;
 int p=potencia(b, e/2);
 if (e % 2 == 0)	
 return p*p;
 else
 return p*p*b;
}
¿usa “divide y vencerás” la siguiente función?
int pot2(int b, int e) {
 if (e==0) return 1;
 if (e==1) return b;
 return b*pot2(b,e-1);
}
Cálculo de la complejidad
La función potencia( ), divide el problema en un subproblema de la mitad del tamaño (T(n/2) ), y en el peor de los casos la condicional efectuará 2 multiplicaciones (esto ocurre cuando e es impar).
 1, si n=1
T(n) 
 T(n/2) + 2, si n>1
Cálculo de la complejidad
La función potencia( ), divide el problema en un subproblema de la mitad del tamaño (T(n/2) ), y en el peor de los casos la condicional efectuará 2 multiplicaciones (esto ocurre cuando e es impar).
 1, si n=1
T(n) 
 T(n/2) + 2, si n>1
 Θ(1), si n<=no
T(n) 
 aT(n/b) + Θ(nk), si n > no
Comparando con
Cálculo de la complejidad
La función potencia( ), divide el problema en un subproblema de la mitad del tamaño (T(n/2) ), y en el peor de los casos la condicional efectuará 2 multiplicaciones (esto ocurre cuando e es impar).
 1, si n=1
T(n) 
 T(n/2) + 2, si n>1
Por el teorema maestro
Θ(nk) si a>bk
Θ(nk log n ) si a=bk 
Θ(nlog ba) si a<bk
 Θ(1), si n<=no
T(n) 
 aT(n/b) + Θ(nk), si n > no
Comparando con
Tenemos:
a=1
b=2
k=0 (ya que 2 es constante)
De donde la complejidad de potencia( ) es Θ(log n) 
Subsecuencia de suma máxima
El problema de la subsecuencia de suma máxima consiste en encontrar una secuencia cuya suma sea máxima dentro de un vector original.
	-1	6	-2	5	-1	4	3	-4	3	1
La suma máxima se consigue desde los subíndices 1 al 6 y es 15
Haga clic para modificar el estilo de texto del patrón
Segundo nivel
Tercer nivel
Cuarto nivel
Quinto nivel
Solución mediante divide y vencerás
Esto significa que hemos dividido el problema original en 3 subproblemas más pequeños.
Dividimos el arreglo en dos partes.
La subsecuencia máxima puede estar en la primera mitad
(lo resolvemos por recursión)
La subsecuencia máxima puede estar en la segunda mitad
(lo resolvemos por recursión)
La subsecuencia máxima puede empezar en la primera mitad y terminar en la segunda
(lo resolvemos calculando la subsecuencia máxima de la primera mitad pero que termine en el ultimo elemento de esa mitad y…
… calculando la subsecuencia máxima de la segunda mitad pero que empiece en el primer elemento de esa mitad…
…las dos se unen para construir la subsecuencia de suma máxima).
										
										
										
										
										
1
2
3
# include <iostream.h>
int sumaMax(int [], int, int);
int main()
{
 int a[]={-1, 6, -2, 5, -1, 4, 3, -4, 3, 1};
 cout<<"la suma es:" << sumaMax(a, 0, 9)<<endl;
}
int sumaMax(int a[ ], int izq, int der) {	
 if ( izq==der )
 return a[izq]>0? a[izq]:0;
 int centro=(izq+der)/2;
 // maxima suma de la 1ra mitad
 int maxSumIzq = sumaMax(a, izq, centro); 
 // maxima suma de la 2da mitad
 int maxSumDer = sumaMax(a, centro+1, der); 
 // maxima suma que empieza en una mitad y termina en la otra
 int sumIzqBorde = 0;
 int maxSumIzqBorde= 0;
 for(int i=centro; i>=izq; i--) {
 sumIzqBorde += a[i];
 if ( sumIzqBorde > maxSumIzqBorde )
 maxSumIzqBorde = sumIzqBorde;
 }
Código
 int sumDerBorde = 0;
 int maxSumDerBorde = 0;
 for ( int j=centro+1; j<=der; j++ )
 {
 sumDerBorde += a[j];
 if ( sumDerBorde > maxSumDerBorde )
 maxSumDerBorde = sumDerBorde;
 }
 // calcula la mayor suma entre maxSumIzq, 
 // maxSumDer y la maxima suma que empieza
 // en una mitad y termina en otra
 int max =maxSumIzq;
 if( maxSumDer > max)
 max=maxSumDer;
if( maxSumIzqBorde + maxSumDerBorde > max)
 max= maxSumIzqBorde+ maxSumDerBorde;
 return max;
}
# include <iostream.h>
int sumaMax(int [], int, int);
int main()
{
 int a[]={-1, 6, -2, 5, -1, 4, 3, -4, 3, 1};
 cout<<"la suma es:" << sumaMax(a, 0, 9)<<endl;
}
int sumaMax(int a[ ], int izq, int der) {	
 if ( izq==der )
 return a[izq]>0? a[izq]:0;
 int centro=(izq+der)/2;
 // maxima suma de la 1ra mitad
 int maxSumIzq = sumaMax(a, izq, centro); 
 // maxima suma de la 2da mitad
 int maxSumDer = sumaMax(a, centro+1, der); 
 // maxima suma que empieza en una mitad y termina en la otra
 int sumIzqBorde = 0;
 int maxSumIzqBorde= 0;
 for(int i=centro; i>=izq; i--) {
 sumIzqBorde += a[i];
 if ( sumIzqBorde > maxSumIzqBorde )
 maxSumIzqBorde = sumIzqBorde;
 }
Código
 int sumDerBorde = 0;
 int maxSumDerBorde = 0;
 for ( int j=centro+1; j<=der; j++ )
 {
 sumDerBorde += a[j];
 if ( sumDerBorde > maxSumDerBorde )
 maxSumDerBorde = sumDerBorde;
 }
 // calcula la mayor suma entre maxSumIzq, 
 // maxSumDer y la maxima suma que empieza
 // en una mitad y termina en otra
 int max =maxSumIzq;
 if( maxSumDer > max)
 max=maxSumDer;
if( maxSumIzqBorde + maxSumDerBorde > max)
 max= maxSumIzqBorde+ maxSumDerBorde;
 return max;
}
If(a[izq]>0)
 return a[izq];
Else
return 0;
# include <iostream.h>
int sumaMax(int [], int, int);
int main()
{
 int a[]={-1, 6, -2, 5, -1, 4, 3, -4, 3, 1};
 cout<<"la suma es:" << sumaMax(a, 0, 9)<<endl;
}
int sumaMax(int a[ ], int izq, int der) {	
 if ( izq==der )
 return a[izq]>0? a[izq]:0;
 int centro=(izq+der)/2;
 // maxima suma de la 1ra mitad
 int maxSumIzq = sumaMax(a, izq, centro); 
 // maxima suma de la 2da mitad
 int maxSumDer = sumaMax(a, centro+1, der); 
 // maxima suma que empieza en una mitad y termina en la otra
 int sumIzqBorde = 0;
 int maxSumIzqBorde= 0;
 for(int i=centro; i>=izq; i--) {
 sumIzqBorde += a[i];
 if ( sumIzqBorde> maxSumIzqBorde )
 maxSumIzqBorde = sumIzqBorde;
 }
Código
 int sumDerBorde = 0;
 int maxSumDerBorde = 0;
 for ( int j=centro+1; j<=der; j++ )
 {
 sumDerBorde += a[j];
 if ( sumDerBorde > maxSumDerBorde )
 maxSumDerBorde = sumDerBorde;
 }
 // calcula la mayor suma entre maxSumIzq, 
 // maxSumDer y la maxima suma que empieza
 // en una mitad y termina en otra
 int max =maxSumIzq;
 if( maxSumDer > max)
 max=maxSumDer;
if( maxSumIzqBorde + maxSumDerBorde > max)
 max= maxSumIzqBorde+ maxSumDerBorde;
 return max;
}
Modifique el programa para mostrar los subíndices 1 al 6
Cálculo de la complejidad
La función sumaMax( ), se hace 2 llamadas recursivas de la mitad de tamaño, y dos bucles que depende de n. Por lo que su recurrencia seria:
 Θ(1), si n=1
T(n) 
 2.T(n/2) + Θ(n), si n>1
Por el teorema maestro
Θ(nk) si a<bk
Θ(nk log n ) si a=bk 
Θ(nlog ba) si a>bk
 Θ(1), si n<=no
T(n) 
 aT(n/b) + Θ(nk), si n > no
Comparando con
Tenemos:
a=2
b=2
k=1
De donde la complejidad de sumaMax( ) es Θ(nlog n) 
Calendario de un campeonato
Se tiene que programar los encuentros de un campeonato que tiene n participantes con la condición de que cada participante se enfrente a cada uno de los otros solo una vez. 
Para simplificar el problema suponga que n es una potencia de 2.
		1	2	3	4	5	6	7
	1	2	3	4	5	6	7	8
	2	1	4	3	6	7	8	5
	3	4	1	2	7	8	5	6
	4	3	2	1	8	5	6	7
	5	6	7	8	1	4	3	2
	6	5	8	7	2	1	4	3
	7	8	5	6	3	2	1	4
	8	7	6	5	4	3	2	1
Haga clic para modificar el estilo de texto del patrón
Segundo nivel
Tercer nivel
Cuarto nivel
Quinto nivel
# include <iostream.h>
# include <iomanip.h>
# define COL 64 
void torneo(int n, int tabla[][COL]);
void main(void)
{
 int n, tabla[COL][COL];
 cout<<"Nro de participantes (potencia de 2):";
 cin>>n;
 torneo(n, tabla);
 for(int i=0; i<n; i++)
 {
 for(int j=0; j<n-1; j++)
	cout<<setw(3)<<tabla[i][j];
 cout<<endl;
 }
}
Código
void torneo(int n, int tabla[][COL])
{ int i, j;
 if(n==2) 
 { tabla[0][0]=2;
 tabla[1][0]=1;
 }
 else
 { // llena el cuadrante superior izquierdo
 torneo(n/2, tabla);
 // llena el cuadrante inferior izquierdo
 for (i=n/2; i<n; i++)
 for(j=0; j<n/2-1; j++)
 tabla[i][j]=tabla[i-n/2][j] + n/2;
 // llena el cuadrante superior derecho
 for(i=0; i<n/2; i++)
 for(j=n/2-1; j<n-1; j++)
	if(i+j<n-1)
 tabla[i][j]= i + j + 2;
	else
	 tabla[i][j]= i + j - n/2 + 2;
 // llena el cuadrante inferior derecho
 for(i=n/2; i<n; i++)
 for(j=n/2-1; j<n-1; j++)
	if(i>j)
	 tabla[i][j] = i - j;
	else
	 tabla[i][j] = i + n/2 - j;
 }
}
Cálculo de la complejidad
La función torneo( ), divide el problema en un problema de la mitad de tamaño y 3 partes más para completar la matriz. 
Como ocurre una llamada recursiva, y como cada una de las 3 partes tiene una complejidad cuadrática, tendremos:
 2, si n=2
T(n) 
 1.T(n/2) + 3n2, si n>=2
Por el teorema maestro
Θ(nk) si a<bk 
Θ(nk log n ) si a=bk
Θ(nlog ba) si a>bk
 Θ(1), si n<=no
T(n) 
 aT(n/b) + Θ(nk), si n > no
Comparando con
Tenemos:
a=1
b=2
k=2
De donde la complejidad de torneo( ) es Θ(n2) 
Haga clic para modificar el estilo de texto del patrón
Segundo nivel
Tercer nivel
Cuarto nivel
Quinto nivel
BackTracking
¡Gracias por su atención!