Sesión 10_Mg Orleans Gálvez Tapia

Vista previa del material en texto

ANÁLISIS DE ALGORITMOS Y 
ESTRATEGIAS DE PROGRAMACIÓN
Docente: 
Mg. Gálvez Tapia Orleans Moisés
CIP. 171497
UNIDAD 1:
LA COMPLEJIDAD ALGORÍTMICA Y 
PRINCIPALES ESTRATEGIAS DE 
PROGRAMACIÓN
SEMANA 10: Divide y Conquista (Parte II)
¿Qué algoritmos de 
búsqueda conoce?
SABERES PREVIOS
AGENDA:
1. Algoritmo de Búsqueda Binaria en Python y Java (recursiva)
2. Algoritmo de Búsqueda Binaria en Python y Java (iterativa)
3. Algoritmo de las Torres de Hanoi en Python y Java
4. Algoritmo de ordenamiento por Selección en Java
5. Algoritmo de ordenamiento Quicksort en Java
6. Algoritmo de ordenamiento Shell en Java
7. Conclusiones
8. Referencias Bibliográficas
LOGRO DE LA SESIÓN
Al término de la clase, el estudiante implementa algoritmos de búsqueda 
binaria aplicando la técnica Divide y Conquista, demostrando dominio 
del lenguaje Python.
ALGORITMOS DIVIDE Y VENCERÁS
Un algoritmo Divide y Vencerás resuelve un problema en 3 pasos:
1. Divide el problema en un número de subproblemas que son
instancias más pequeñas del mismo problema.
2. Vence los subproblemas al resolverlos de manera recursiva. Si
son los suficientemente pequeños, resuelve los subproblemas como
casos base.
3. Combina las soluciones de los subproblemas en la solución para el
problema original.
BÚSQUEDA BINARIA
…
BÚSQUEDA BINARIA
Elemento buscado: 23
Retornar [5]
BÚSQUEDA BINARIA ITERATIVA EN JAVA
public int busquedaBinaria(){ 
int n=tamaño(), 
int inferior = 0, superior = n-1;
while(inferior <= superior){ 
int centro = (superior + inferior) / 2; 
if (elemento == vector[centro]){
return centro;
} 
else { 
if (elemento < vector[centro]){
superior = centro - 1;
} 
else {
inferior = centro + 1;
} 
} 
} 
return -1; 
}
// mientras exista 
por lo menos un 
elemento en el 
arreglo
BÚSQUEDA BINARIA RECURSIVA EN JAVA
BÚSQUEDA BINARIA ITERATIVA EN PYTHON
BÚSQUEDA BINARIA RECURSIVA EN PYTHON
EL PROBLEMA DE LAS TORRES DE HANOI 
Dice la leyenda que, al crear el mundo, Dios situó
sobre la Tierra tres varillas de diamante y sesenta
y cuatro discos de oro. Los discos son todos de
diferente tamaño e inicialmente fueron colocados
en orden decreciente de diámetros sobre la
primera de las varillas. También creó Dios un
monasterio cuyos monjes tienen la tarea de
trasladar todos los discos desde la primera varilla
a la tercera.
La única operación permitida es mover un disco
de una varilla a otra cualquiera, pero con la
condición de que no se puede situar encima de un
disco otro de diámetro mayor.
La leyenda dice también que cuando los monjes
terminen su tarea, el mundo se acabará.
264 = 1844674407 3709551616
EL PROBLEMA DE LAS TORRES DE HANOI 
Dice la leyenda que, al crear el mundo, Dios situó
sobre la Tierra tres varillas de diamante y sesenta
y cuatro discos de oro. Los discos son todos de
diferente tamaño e inicialmente fueron colocados
en orden decreciente de diámetros sobre la
primera de las varillas. También creó Dios un
monasterio cuyos monjes tienen la tarea de
trasladar todos los discos desde la primera varilla
a la tercera.
La única operación permitida es mover un disco
de una varilla a otra cualquiera, pero con la
condición de que no se puede situar encima de un
disco otro de diámetro mayor.
La leyenda dice también que cuando los monjes
terminen su tarea, el mundo se acabará.
EL PROBLEMA DE LAS TORRES DE HANOI EN PYTHON
EL PROBLEMA DE LAS TORRES DE HANOI EN PYTHON
n-1
n-1
A B C
n-1
SOLUCIÓN DEL PROBLEMA DE LAS TORRES DE HANOI
¿Cómo resolvemos el problema?
1°pasamos n-1 discos de A → B (de manera recursiva)
2°pasamos 1 disco de A → C (directamente)
3°pasamos n-1 discos de B → C (de manera recursiva)
Mg. Orleans Moisés Gálvez Tapia CIP Nº. 171497
EL PROBLEMA DE LAS TORRES DE HANOI EN JAVA
//método java de ordenación por selección
public static void seleccion(int A[]) {
int i, j, menor, pos, tmp;
for (i = 0; i < A.length - 1; i++) {
menor = A[i];
pos = i;
for (j = i + 1; j < A.length; j++){
if (A[j] < menor) {
menor = A[j];
pos = j;
}
}
if (pos != i){
tmp = A[i];
A[i] = A[pos];
A[pos] = tmp;
}
}
}
50 26 7 9 15 27
26 9 15 27
26
5015 26 27
27 26
7 50
i = 0; i < A.length - 1; i++
j = i + 1; j < A.length; j++
5026 27
50 15 279
Tomamos como menor el primero de los elementos 
que quedan por ordenar y guardamos su posición
Buscamos en el resto del array algún
elemento menor que el actual
Si hay alguno menor se intercambia
ALGORITMO DE ORDENAMIENTO POR SELECCIÓN
public void quicksort(int izq, int der) { 
int pivote=vector[izq], i=izq, j=der, aux; 
while(i<j){ 
while(vector[i]<=pivote && i<j) i++; 
while(vector[j]>pivote) j--; 
if (i<j) { 
aux= vector[i]; 
vector[i]=vector[j]; 
vector[j]=aux; 
} 
} 
vector[izq]=vector[j]; 
vector[j]=pivote; 
if(izq<j-1)
quicksort(izq,j-1); 
if(j+1 <der)
quicksort(j+1,der); 
}
ALGORITMO DE ORDENAMIENTO QUICKSORT
[0] [1] [2] [3] [4] [5]
50 26 7 9 15 27
26
269 15 277 50
i = salto; i < v.length; i++
salto = t/2; salto !=0; salto/2
5015 279
t = tamaño() = 6
Intercambio = F
Intercambio = V
7
Intercambio = V
Intercambio = F
Intercambio = V
salto = t/2 = 3
Mientras (Intercambio = V)
ALGORITMO DE ORDENAMIENTO SHELL
public void shell(){
int salto,aux; 
int t=tamaño(); 
boolean intercambio;
for(salto=t/2; salto!=0; salto=salto/2){
intercambio=true;
while(intercambio){ 
intercambio=false;
for(int i=salto; i<vector.length;i++){ 
if(vector[i-salto]>vector[i]){ 
aux=vector[i]; 
vector[i]=vector[i-salto];
vector[i-salto]=aux;
intercambio=true; 
}
} 
}
}
}
CONCLUSIONES
1. Un algoritmo Divide y Vencerás resuelve un problema siguiendo estos 3 pasos.
o Dividir: Descomponer el problema en sub-problemas.
o Vencer: Resolver los sub-problemas recursivamente.
o Combinar las soluciones de los subproblemas en la solución para el problema original.
2. Este enfoque algorítmico trabaja recursivamente y los pasos de Vencer y Combinar trabajan tan a la
par que parece un sólo paso.
REFERENCIAS BIBLIOGRÁFICAS
REFERENCIA ENLACE 
Una introducción a las matemáticas para el 
análisis y diseño de algoritmos 
https://elibro.bibliotecaupn.elogim.com/es/lc/upnort
e/titulos/35059
Manual de algorítmica: recursividad, complejidad y 
diseño de algoritmos 
https://elibro.bibliotecaupn.elogim.com/es/lc/upnort
e/titulos/56561
Introducción práctica a la programación con 
Python 
https://elibro.bibliotecaupn.elogim.com/es/lc/upnort
e/titulos/124259
Criptografía sin secretos con Python https://elibro.bibliotecaupn.elogim.com/es/lc/upnort
e/titulos/106497
ACM UVA Online http://uva.onlinejudge.org/
ACM ICPC Competition https://icpc.global/compete/preparation
https://elibro.bibliotecaupn.elogim.com/es/lc/upnorte/titulos/35059
https://elibro.bibliotecaupn.elogim.com/es/lc/upnorte/titulos/35059
https://elibro.bibliotecaupn.elogim.com/es/lc/upnorte/titulos/56561
https://elibro.bibliotecaupn.elogim.com/es/lc/upnorte/titulos/56561
https://elibro.bibliotecaupn.elogim.com/es/lc/upnorte/titulos/124259
https://elibro.bibliotecaupn.elogim.com/es/lc/upnorte/titulos/124259
https://elibro.bibliotecaupn.elogim.com/es/lc/upnorte/titulos/106497
https://elibro.bibliotecaupn.elogim.com/es/lc/upnorte/titulos/106497
http://uva.onlinejudge.org/
https://icpc.global/compete/preparation
	Diapositiva 1
	Diapositiva 2
	Diapositiva 3: UNIDAD 1: LA COMPLEJIDAD ALGORÍTMICA Y PRINCIPALES ESTRATEGIAS DE PROGRAMACIÓN
	Diapositiva 4
	Diapositiva 5
	Diapositiva 6
	Diapositiva 7
	Diapositiva 8
	Diapositiva 9
	Diapositiva 10
	Diapositiva 11
	Diapositiva 12
	Diapositiva 13
	Diapositiva 14
	Diapositiva 15
	Diapositiva 16
	Diapositiva 17
	Diapositiva 18
	Diapositiva 19
	Diapositiva 20
	Diapositiva 21
	Diapositiva 22
	Diapositiva 23
	Diapositiva 24
	Diapositiva 25