Sesión 06_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 06: Algoritmos voraces
¿Qué es un algoritmo 
voraz?
SABERES PREVIOS
AGENDA:
1. Algoritmo voraz (2 ejemplos)
2. Problema del cambio de moneda (2 ejemplos)
3. Prueba de escritorio del algoritmo voraz 
4. Elementos del algoritmo voraz
5. Pasos del algoritmo voraz
6. Esquema genérico de los algoritmos voraces
7. Implementación en Python del Algoritmo del cambio de moneda.
8. Implementación en Java del Algoritmo del cambio de moneda.
9. Referencias Bibliográficas
LOGRO DE LA SESIÓN
Al término de la clase, el estudiante implementa algoritmos 
voraces en Python y C#, mostrando dominio técnico del 
lenguaje y una lógica coherente.
ALGORITMOS VORACES (greedy)
A B
9
1
3
1
2
1
0
Un algoritmo voraz encuentra una solución globalmente óptima a un problema a base de
hacer elecciones localmente óptimas. Es decir, el algoritmo siempre hace lo que “parece”
mejor en cada momento.
ALGORITMOS VORACES
A B
9
1
3
1
2
1
1
ALGORITMOS VORACES
A B
9
1
3
1
2
1
3
ALGORITMOS VORACES
A B
9
1
3
1
2
1
4
ALGORITMOS VORACES
A B
9
1
3
1
20
1
0
ALGORITMOS VORACES
A B
9
1
3
1
20
1
1
El algoritmo no sabe los siguientes valores 
(por eso no le interesan)
ALGORITMOS VORACES
A B
9
1
3
1
20
1
21
ALGORITMOS VORACES
A B
9
1
3
1
20
1
22
PROBLEMA DEL CAMBIO DE MONEDA
o Se trata de devolver una cantidad de dinero con el menor número posible de monedas.
o Se parte de un conjunto de tipos de monedas válidas de las que se supone que hay
cantidad suficiente para realizar el desglose, y de un importe a devolver.
PROBLEMA DEL CAMBIO DE MONEDA
Ejemplo 1: Queremos devolver un monto de 20$, usando monedas
de 5$ o 10$.
Entrada: Monto=20$, monedas[ ]={5,10}
Salida: 2 monedas de 10$
Opción1:
4 monedas de $5 cada una, ∴Total de monedas=4
Opción2:
2 monedas de $5 y 1 moneda de $10, ∴Total de monedas=3
Opción3:
2 monedas de $10, ∴Total de monedas=2
$20 $5 $10
Monto monedas disponibles
$5 $5
$5 $5
Opción 1
$5 $5
$10
Opción 2
$10 $10
Opción 3
PROBLEMA DEL CAMBIO DE MONEDA
Ejemplo 2: Queremos devolver un monto de 45$, usando monedas
de 9$, 10$, 20$, 5$.
Entrada: Monto=45$, monedas[ ]={9,10,20,5}
Salida: 2 monedas de $20 y 1 moneda de $5
Opción1:
5 monedas de $9 cada una, ∴Total de monedas=5
Opción2:
4 monedas de $10 y 1 moneda de $5, ∴Total de monedas=5
Opción3:
2 monedas de $20 y 1 moneda de $5, ∴Total de monedas=3
Opción4:
9 monedas de $5 cada una, ∴Total de monedas=9
$45 $9 $10
Monto monedas disponibles
$20 $5
$9 $9
$9 $9
Opción 1
$9
$10 $10
$10 $10
Opción 2
$5
$20 $20
Opción 3
$5
$5 $5
$5 $5
$5 $5
$5 $5
$5
Opción 4
ALGORITMOS VORAZ - CAMBIO DE MONEDA
3 monedas de 2 3x2
1 moneda de 1 1x1
1 moneda de 0.2 1x0.2
1 moneda de 0.1 1x0.1
2 monedas de 0.02 2x0.02
Total = 7.34
La solución encontrada es: 
Algoritmo
voraz
ALGORITMOS VORAZ - CAMBIO DE MONEDA
3 monedas de 2 3x2
1 moneda de 1 1x1
1 moneda de 0.2 1x0.2
1 moneda de 0.1 1x0.1
2 monedas de 0.02 2x0.02
Total = 7.34
La solución encontrada es: Se desea elaborar un programa con la siguiente salida:
ALGORITMOS VORAZ - CAMBIO DE MONEDA (PRUEBA DE ESCRITORIO)
ALGORITMOS VORAZ - CAMBIO DE MONEDA (PRUEBA DE ESCRITORIO)
ALGORITMOS VORAZ - CAMBIO DE MONEDA (PRUEBA DE ESCRITORIO)
ALGORITMOS VORAZ - CAMBIO DE MONEDA (PRUEBA DE ESCRITORIO)
ALGORITMOS VORAZ - CAMBIO DE MONEDA (PRUEBA DE ESCRITORIO)
ALGORITMOS VORAZ - CAMBIO DE MONEDA (PRUEBA DE ESCRITORIO)
ELEMENTOS DEL ALGORITMO VORAZ - CAMBIO DE MONEDA
Conjunto de candidatos
Cada una de las monedas de los diferentes tipos que se pueden usar
para realizar el desglose del importe dado.
Solución
Conjunto de monedas devuelto tras el desglose y cuyo valor total es
igual al importe a desglosar.
Completable
La suma de los valores de las monedas escogidas en un momento
dado no supera el importe a desglosar.
Función selección
Elegir la moneda de mayor valor de entre las candidatas.
PASOS DEL ALGORITMO VORAZ - CAMBIO DE MONEDA
Inicialmente el conjunto de candidatos escogidos es vacío.
En nuestro ejemplo, el arreglo cambio [ ] donde se va a almacenar la
cantidad de monedas de cada tipo (necesarias para devolver el
monto), empieza con CERO en cada posición.
PASOS DEL ALGORITMO VORAZ - CAMBIO DE MONEDA
En cada paso, se intenta añadir al conjunto de los escogidos “el
mejor” de los no escogidos (sin pensar en el futuro), utilizando
una función de selección basada en algún criterio de optimización.
En nuestro caso siempre vamos a elegir la moneda más alta,
porque el arreglo de monedas está ordenado de mayor a menor.
PASOS DEL ALGORITMO VORAZ - CAMBIO DE MONEDA
Tras cada paso, hay que ver si añadiendo un nuevo candidato se
puede llegar a una solución (solución completable).
o Si el conjunto no es completable, se rechaza el último candidato
elegido y no se vuelve a considerar en el futuro;
o Si es completable, se incorpora al conjunto de escogidos y
permanece siempre en él.
PASOS DEL ALGORITMO VORAZ - CAMBIO DE MONEDA
El algoritmo termina cuando se obtiene una solución.
ESQUEMA GENÉRICO DE UN ALGORITMO VORAZ
ALGORITMOS VORAZ - CAMBIO DE MONEDA EN PYTHON
ALGORITMOS VORAZ - CAMBIO DE MONEDA EN JAVA
CONCLUSIONES
i. Los algoritmos voraces se emplean para resolver problemas de optimización.
ii. Existe una entrada de tamaño n que son los candidatos a formar parte de la solución.
iii. Existe un subconjunto de esos n candidatos que satisface ciertas restricciones: se llama
solución factible.
iv. Hay que obtener la solución factible que maximice o minimice una cierta función
objetivo: se llama solución óptima.
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 19
	Diapositiva 20
	Diapositiva 21
	Diapositiva 22
	Diapositiva 23
	Diapositiva 24
	Diapositiva 25
	Diapositiva 26
	Diapositiva 27
	Diapositiva 28
	Diapositiva 29
	Diapositiva 30
	Diapositiva 31
	Diapositiva 32
	Diapositiva 33
	Diapositiva 34
	Diapositiva 36
	Diapositiva 37
	Diapositiva 38