Sesión 05_Mg Orleans Gálvez Tapia(1)

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 05: Análisis de Algoritmos
¿Qué algoritmos de 
búsqueda conoce?
SABERES PREVIOS
AGENDA:
1. Notación O grande
2. Clasificación de algoritmos con la notación O grande.
3. Algoritmo de búsqueda por Fuerza Bruta
4. Prueba de escritorio del algoritmo de Fuerza Bruta
5. Implementación en Python y C# del algoritmo de Fuerza Bruta
6. Referencias Bibliográficas
LOGRO DE LA SESIÓN
Al término de la clase, el estudiante implementa el
algoritmo de búsqueda por fuerza bruta usando Python y 
C#, mostrando dominio técnico del lenguaje y una lógica 
coherente.
Indicar si la siguiente afirmación es cierta: 
Ejemplo 08: O(log2 𝑛) ⊂ O(𝑛
1/2):
Aplicamos la regla de L’hopital:
lim
𝑛→∞
𝑓(𝑛)
𝑔(𝑛)
= lim
𝑛→∞
𝑓′(𝑛)
𝑔′(𝑛)
Si 𝑓 𝑛 = log2 𝑛 ⇒ 𝑓′ 𝑛 =
1
𝑛.ln(2)
Si 𝑔 𝑛 = 𝑛1/2 ⇒ 𝑔′ 𝑛 =
1
2
𝑛−1/2
lim
𝑛→∞
𝑓′(𝑛)
𝑔′(𝑛)
= lim
𝑛→∞
1
𝑛.ln(2)
1
2
𝑛−1/2
= lim
𝑛→∞
2
𝑛1/2.ln(2)
= 
2
ln(2)
. lim
𝑛→∞
1
𝑛1/2
= 
2
ln(2)
.
1
∞1/2
= 
2
ln(2)
.
1
∞
= 
2
ln(2)
. 0 = 0
Por la propiedad de inclusión (ii), si k=0, entonces O(f) ⊂ O(g). Por lo tanto O(log2 𝑛) ⊂ O(𝑛
1/2) es cierta.
Aplicamos las siguientes propiedades:
o Si 𝑓 𝑥 = log𝑎 𝑥 ⇒ 𝑓′ 𝑥 =
1
𝑥.ln(𝑎)
o Si 𝑔 𝑥 = 𝑥𝑛 ⇒ 𝑔′ 𝑥 = 𝑛. 𝑥𝑛−1
o ∞𝑘 = ∞ (si k>0)
∞𝑘 = 0 (si k<0)
o Cualquier número dividido entre ±∞ da 
como resultado 0.
NOTACIÓN O(grande)
a) 2n
CLASIFICACIÓN DE ALGORITMOS CON LA NOTACIÓN O(grande)
Primero, determinamos el orden de complejidad entre a) y b):
Sea 𝑓 𝑛 = log2 𝑛 ⇒ 𝑓′ 𝑛 =
1
𝑛.ln(2)
Sea 𝑔 𝑛 = 2𝑛 ⇒ 𝑔′ 𝑛 = 2𝑛. ln(2)
Aplicamos la regla de L’hopital:
lim
𝑛→∞
𝑓(𝑛)
𝑔(𝑛)
= lim
𝑛→∞
𝑓′(𝑛)
𝑔′(𝑛)
= 𝑙𝑖𝑚
𝑛→∞
1
𝑛.ln(2)
2𝑛. ln(2) = 𝑙𝑖𝑚𝑛→∞
1
𝑛.2𝑛.(ln 2)2
= 
1
(ln 2)2
𝑙𝑖𝑚
𝑛→∞
1
𝑛.2𝑛
= 
1
(ln 2)2
.
1
∞.2∞
= 
1
(ln 2)2
.
1
∞.∞
=
1
(ln 2)2
.
1
∞
= 0
Ejercicio 01: Ordenar de menor a mayor: b) log2(n) c) n
8
Por la propiedad de inclusión (ii), si k=0, entonces O(f) ⊂ O(g). Por lo tanto O(log2 𝑛) ⊂ O(2
𝑛)
Propiedades:
𝑓 𝑥 = 𝑎𝑢 ⇒ 𝑓′ 𝑥 = 𝑎𝑢. ln 𝑎 . 𝑢′
𝑘∞=∞ y 𝑘−∞=0 (si k>1)
∞. ∞=∞
𝑘
∞
= 0
a) 2n
Segundo, determinamos el orden de complejidad entre b) y c):
Sea 𝑓 𝑛 = log2 𝑛 ⇒ 𝑓′ 𝑛 =
1
𝑛.ln(2)
Sea 𝑔 𝑛 = 𝑛8 ⇒ 𝑔′ 𝑛 = 8. 𝑛7
Aplicamos la regla de L’hopital:
lim
𝑛→∞
𝑓(𝑛)
𝑔(𝑛)
= lim
𝑛→∞
𝑓′(𝑛)
𝑔′(𝑛)
= 𝑙𝑖𝑚
𝑛→∞
1
𝑛.ln(2)
8.𝑛7
= 𝑙𝑖𝑚
𝑛→∞
1
8.𝑛8.ln(2)
= 
1
8.ln(2)
𝑙𝑖𝑚
𝑛→∞
1
𝑛8
=
1
8.ln(2)
.
1
∞8
=
1
8.ln(2)
.
1
∞
= 0
Por la propiedad de inclusión (ii), si k=0, entonces O(f) ⊂ O(g). Por lo tanto O(log2 𝑛) ⊂ O(𝑛
8)
Ejercicio 01: Ordenar de menor a mayor: b) log2(n) c) n
8
CLASIFICACIÓN DE ALGORITMOS CON LA NOTACIÓN O(grande)
Propiedades:
∞𝑘 = ∞ (si k>0)
∞𝑘 = 0 (si k<0)
𝑘
∞
= 0
a) 2n
Tercero, determinamos el orden de complejidad entre a) y c):
Sea 𝑓 𝑛 = 2𝑛 ⇒ 𝑓′ 𝑛 = 2𝑛. ln(2)
Sea 𝑔 𝑛 = 𝑛8 ⇒ 𝑔′ 𝑛 = 8. 𝑛7
Aplicamos la regla de L’hopital:
lim
𝑛→∞
𝑓(𝑛)
𝑔(𝑛)
= lim
𝑛→∞
𝑓′(𝑛)
𝑔′(𝑛)
= 𝑙𝑖𝑚
𝑛→∞
2𝑛. ln(2)
8.𝑛7
= 
ln(2)
8
. 𝑙𝑖𝑚
𝑛→∞
2𝑛
𝑛7
=
ln(2)
8
.
2∞
∞7
=
ln(2)
8
.
∞
∞
= ∞
Por la propiedad de exclusión(iii), si k= ±∞, entonces O(f) ⊃ O(g). Es decir, O(2𝑛) ⊃ O(𝑛8).
Por lo tanto el orden de complejidad de las tres funciones, de menor a mayor es el siguiente:
O(𝒍𝒐𝒈𝟐 𝒏) ⊂ O(𝒏
𝟖) ⊂ O(𝟐𝒏). Eso significa que el algoritmo cuyo orden de complejidad es 𝐥𝐨𝐠𝟐 𝐧 resulta ser el
más eficiente, mientras que el algoritmo cuyo orden de complejidad es 𝟐𝒏 es el menos eficiente.
Ejercicio 01: Ordenar de menor a mayor: b) log2(n) c) n
8
CLASIFICACIÓN DE ALGORITMOS CON LA NOTACIÓN O(grande)
Propiedades:
𝑓 𝑥 = 𝑎𝑢 ⇒ 𝑓′ 𝑥 = 𝑎𝑢. ln 𝑎 . 𝑢′
𝑘∞=∞ y 𝑘−∞=0 (si k>1)
∞𝑘 = ∞ (si k>0)
∞𝑘 = 0 (si k<0)
∞
∞
= ∞
Sea 𝑓 𝑛 = log2(n)
Sea 𝑔 𝑛 = 𝑛. log2(n)
Calculamos: lim
𝑛→∞
𝑓(𝑛)
𝑔(𝑛)
= k
𝑙𝑖𝑚
𝑛→∞
log2(n)
𝑛.log2(n)
= 𝑙𝑖𝑚
𝑛→∞
1
𝑛
= 
1
∞
= 0
Por la propiedad de inclusión (ii), si k=0, entonces O(f) ⊂ O(g). Por lo tanto O(log2 𝑛) ⊂ O(n. log2 𝑛)
Ejercicio 02: ¿Cuál de las siguientes funciones tiene menor complejidad?
a) log2(n) b) n.log2(n)
CLASIFICACIÓN DE ALGORITMOS CON LA NOTACIÓN O(grande)
ALGORITMOS DE FUERZA BRUTA
Fuente: https://canvas.projekti.info/ebooks/Algorithm%20Design%20and%20Applications%5BA4%5D.pdf
https://canvas.projekti.info/ebooks/Algorithm%20Design%20and%20Applications%5bA4%5d.pdf
ALGORITMOS DE FUERZA BRUTA
Algorithm Design and Applications
(Michael T. Goodrich, Roberto Tamassia Pág. 654-655)
ALGORITMOS DE FUERZA BRUTA (PRUEBA DE ESCRITORIO)
ALGORITMOS DE FUERZA BRUTA (PRUEBA DE ESCRITORIO)
ALGORITMOS DE FUERZA BRUTA (PRUEBA DE ESCRITORIO)
ALGORITMOS DE FUERZA BRUTA (PRUEBA DE ESCRITORIO)
ALGORITMOS DE FUERZA BRUTA (PRUEBA DE ESCRITORIO)
ALGORITMOS DE FUERZA BRUTA EN C#
ALGORITMOS DE FUERZA BRUTA EN PYTHON
CONCLUSIONES
i. Los algoritmos de Fuerza Bruta son capaces de encontrar la solución a cualquier problema
por complicado que sea. Su fundamento es muy simple, probar todas las posibles
combinaciones.
ii. Son sencillos de implementar, pero muy ineficientes en lo que refiere a tiempo de
computo o ejecución (algoritmos de orden exponencial en general), que perfectamente
pueden dejar «colgado» el proceso en ejecución, por más veloces que sean los
procesadores que se tenga.
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 22
	Diapositiva 23
	Diapositiva 24