complejidad, estructuras, diseño y técnicas · análisis de algoritmos complejidad, estructuras,...
TRANSCRIPT
![Page 1: Complejidad, estructuras, diseño y técnicas · Análisis de Algoritmos Complejidad, estructuras, diseño y técnicas Dra. Elisa Schaeffer elisa.schaeffer@gmail.com PISIS / FIME](https://reader030.vdocumento.com/reader030/viewer/2022040318/5e3392261ad9322047225c62/html5/thumbnails/1.jpg)
Análisis de Algoritmos
Complejidad, estructuras, diseño ytécnicas
Dra. Elisa Schaeffer
PISIS / FIME / UANL
Analisis de algoritmos– p. 1
![Page 2: Complejidad, estructuras, diseño y técnicas · Análisis de Algoritmos Complejidad, estructuras, diseño y técnicas Dra. Elisa Schaeffer elisa.schaeffer@gmail.com PISIS / FIME](https://reader030.vdocumento.com/reader030/viewer/2022040318/5e3392261ad9322047225c62/html5/thumbnails/2.jpg)
Temario
Definiciones matemáticas y computacionales
Analisis de algoritmos– p. 2
![Page 3: Complejidad, estructuras, diseño y técnicas · Análisis de Algoritmos Complejidad, estructuras, diseño y técnicas Dra. Elisa Schaeffer elisa.schaeffer@gmail.com PISIS / FIME](https://reader030.vdocumento.com/reader030/viewer/2022040318/5e3392261ad9322047225c62/html5/thumbnails/3.jpg)
Temario
Definiciones matemáticas y computacionales
Problemas y algoritmos
Analisis de algoritmos– p. 2
![Page 4: Complejidad, estructuras, diseño y técnicas · Análisis de Algoritmos Complejidad, estructuras, diseño y técnicas Dra. Elisa Schaeffer elisa.schaeffer@gmail.com PISIS / FIME](https://reader030.vdocumento.com/reader030/viewer/2022040318/5e3392261ad9322047225c62/html5/thumbnails/4.jpg)
Temario
Definiciones matemáticas y computacionales
Problemas y algoritmos
Modelos de computación
Analisis de algoritmos– p. 2
![Page 5: Complejidad, estructuras, diseño y técnicas · Análisis de Algoritmos Complejidad, estructuras, diseño y técnicas Dra. Elisa Schaeffer elisa.schaeffer@gmail.com PISIS / FIME](https://reader030.vdocumento.com/reader030/viewer/2022040318/5e3392261ad9322047225c62/html5/thumbnails/5.jpg)
Temario
Definiciones matemáticas y computacionales
Problemas y algoritmos
Modelos de computación
Complejidad computacional de problemas
Analisis de algoritmos– p. 2
![Page 6: Complejidad, estructuras, diseño y técnicas · Análisis de Algoritmos Complejidad, estructuras, diseño y técnicas Dra. Elisa Schaeffer elisa.schaeffer@gmail.com PISIS / FIME](https://reader030.vdocumento.com/reader030/viewer/2022040318/5e3392261ad9322047225c62/html5/thumbnails/6.jpg)
Temario
Definiciones matemáticas y computacionales
Problemas y algoritmos
Modelos de computación
Complejidad computacional de problemas
Clases de complejidad
Analisis de algoritmos– p. 2
![Page 7: Complejidad, estructuras, diseño y técnicas · Análisis de Algoritmos Complejidad, estructuras, diseño y técnicas Dra. Elisa Schaeffer elisa.schaeffer@gmail.com PISIS / FIME](https://reader030.vdocumento.com/reader030/viewer/2022040318/5e3392261ad9322047225c62/html5/thumbnails/7.jpg)
Temario
Definiciones matemáticas y computacionales
Problemas y algoritmos
Modelos de computación
Complejidad computacional de problemas
Clases de complejidad
Estructuras de datos
Analisis de algoritmos– p. 2
![Page 8: Complejidad, estructuras, diseño y técnicas · Análisis de Algoritmos Complejidad, estructuras, diseño y técnicas Dra. Elisa Schaeffer elisa.schaeffer@gmail.com PISIS / FIME](https://reader030.vdocumento.com/reader030/viewer/2022040318/5e3392261ad9322047225c62/html5/thumbnails/8.jpg)
Temario
Análisis de algoritmos
Analisis de algoritmos– p. 3
![Page 9: Complejidad, estructuras, diseño y técnicas · Análisis de Algoritmos Complejidad, estructuras, diseño y técnicas Dra. Elisa Schaeffer elisa.schaeffer@gmail.com PISIS / FIME](https://reader030.vdocumento.com/reader030/viewer/2022040318/5e3392261ad9322047225c62/html5/thumbnails/9.jpg)
Temario
Análisis de algoritmos
Técnicas de diseño de algoritmos
Analisis de algoritmos– p. 3
![Page 10: Complejidad, estructuras, diseño y técnicas · Análisis de Algoritmos Complejidad, estructuras, diseño y técnicas Dra. Elisa Schaeffer elisa.schaeffer@gmail.com PISIS / FIME](https://reader030.vdocumento.com/reader030/viewer/2022040318/5e3392261ad9322047225c62/html5/thumbnails/10.jpg)
Temario
Análisis de algoritmos
Técnicas de diseño de algoritmos
Optimización combinatorial
Analisis de algoritmos– p. 3
![Page 11: Complejidad, estructuras, diseño y técnicas · Análisis de Algoritmos Complejidad, estructuras, diseño y técnicas Dra. Elisa Schaeffer elisa.schaeffer@gmail.com PISIS / FIME](https://reader030.vdocumento.com/reader030/viewer/2022040318/5e3392261ad9322047225c62/html5/thumbnails/11.jpg)
Temario
Análisis de algoritmos
Técnicas de diseño de algoritmos
Optimización combinatorial
Algoritmos de aproximación
Analisis de algoritmos– p. 3
![Page 12: Complejidad, estructuras, diseño y técnicas · Análisis de Algoritmos Complejidad, estructuras, diseño y técnicas Dra. Elisa Schaeffer elisa.schaeffer@gmail.com PISIS / FIME](https://reader030.vdocumento.com/reader030/viewer/2022040318/5e3392261ad9322047225c62/html5/thumbnails/12.jpg)
Temario
Análisis de algoritmos
Técnicas de diseño de algoritmos
Optimización combinatorial
Algoritmos de aproximación
Algoritmos aleatorizados
Analisis de algoritmos– p. 3
![Page 13: Complejidad, estructuras, diseño y técnicas · Análisis de Algoritmos Complejidad, estructuras, diseño y técnicas Dra. Elisa Schaeffer elisa.schaeffer@gmail.com PISIS / FIME](https://reader030.vdocumento.com/reader030/viewer/2022040318/5e3392261ad9322047225c62/html5/thumbnails/13.jpg)
Temario
Análisis de algoritmos
Técnicas de diseño de algoritmos
Optimización combinatorial
Algoritmos de aproximación
Algoritmos aleatorizados
Transiciones de fase
Analisis de algoritmos– p. 3
![Page 14: Complejidad, estructuras, diseño y técnicas · Análisis de Algoritmos Complejidad, estructuras, diseño y técnicas Dra. Elisa Schaeffer elisa.schaeffer@gmail.com PISIS / FIME](https://reader030.vdocumento.com/reader030/viewer/2022040318/5e3392261ad9322047225c62/html5/thumbnails/14.jpg)
Organización
No habrá examen. Eso no implica que no hay que estudiar.
Calificación:
Tareas semanales 30 %+ Proyecto individual 70 %
Calificación final 100 %
Analisis de algoritmos– p. 4
![Page 15: Complejidad, estructuras, diseño y técnicas · Análisis de Algoritmos Complejidad, estructuras, diseño y técnicas Dra. Elisa Schaeffer elisa.schaeffer@gmail.com PISIS / FIME](https://reader030.vdocumento.com/reader030/viewer/2022040318/5e3392261ad9322047225c62/html5/thumbnails/15.jpg)
Material de estudio
Los materiales del curso en PDF (en desarrollo) en
http://yalma.fime.uanl.mx/~elisa
y por ahora por problemas de con el servidor también en
http://www.tcs.tkk.fi/~satu/aa.pdf
La biblioteca tiene algunos libros útiles; ver bibliografía.
Analisis de algoritmos– p. 5
![Page 16: Complejidad, estructuras, diseño y técnicas · Análisis de Algoritmos Complejidad, estructuras, diseño y técnicas Dra. Elisa Schaeffer elisa.schaeffer@gmail.com PISIS / FIME](https://reader030.vdocumento.com/reader030/viewer/2022040318/5e3392261ad9322047225c62/html5/thumbnails/16.jpg)
Tareas semanales
No son obligatorias, pero hay que tomar en cuenta que sintarea ninguna, la calificación final máxima es 70.
Iniciamos las tareas juntos en clase y también revisamosjuntos los resultados.
No van a ser nada imposible ni laboroso.
No creo que es posible aprender esto solamente porescuchar en clase o leer un libro de una manerasuperficial.
Analisis de algoritmos– p. 6
![Page 17: Complejidad, estructuras, diseño y técnicas · Análisis de Algoritmos Complejidad, estructuras, diseño y técnicas Dra. Elisa Schaeffer elisa.schaeffer@gmail.com PISIS / FIME](https://reader030.vdocumento.com/reader030/viewer/2022040318/5e3392261ad9322047225c62/html5/thumbnails/17.jpg)
Proyecto individual
Cada alumno elige su propio problema y elige o desarrollaalgoritmos para el problema.
Durante el semestre, cada uno escribe un reporte enformato de un artículo cientifico sobre la complejidadcomputacional del problema y la complejidad asintótica delos algoritmos.
Las presentaciones finales (sí, hay que dar una plática) serecomienda programar en el seminario de PISIS, perotambién será posible dar la presentación a parte.
Analisis de algoritmos– p. 7
![Page 18: Complejidad, estructuras, diseño y técnicas · Análisis de Algoritmos Complejidad, estructuras, diseño y técnicas Dra. Elisa Schaeffer elisa.schaeffer@gmail.com PISIS / FIME](https://reader030.vdocumento.com/reader030/viewer/2022040318/5e3392261ad9322047225c62/html5/thumbnails/18.jpg)
Conjuntos y permutaciones
A = {a, b, c} , |A|
Analisis de algoritmos– p. 8
![Page 19: Complejidad, estructuras, diseño y técnicas · Análisis de Algoritmos Complejidad, estructuras, diseño y técnicas Dra. Elisa Schaeffer elisa.schaeffer@gmail.com PISIS / FIME](https://reader030.vdocumento.com/reader030/viewer/2022040318/5e3392261ad9322047225c62/html5/thumbnails/19.jpg)
Conjuntos y permutaciones
A = {a, b, c} , |A|
a ∈ A, a /∈ A
Analisis de algoritmos– p. 8
![Page 20: Complejidad, estructuras, diseño y técnicas · Análisis de Algoritmos Complejidad, estructuras, diseño y técnicas Dra. Elisa Schaeffer elisa.schaeffer@gmail.com PISIS / FIME](https://reader030.vdocumento.com/reader030/viewer/2022040318/5e3392261ad9322047225c62/html5/thumbnails/20.jpg)
Conjuntos y permutaciones
A = {a, b, c} , |A|
a ∈ A, a /∈ A
Z,R, ∅
Analisis de algoritmos– p. 8
![Page 21: Complejidad, estructuras, diseño y técnicas · Análisis de Algoritmos Complejidad, estructuras, diseño y técnicas Dra. Elisa Schaeffer elisa.schaeffer@gmail.com PISIS / FIME](https://reader030.vdocumento.com/reader030/viewer/2022040318/5e3392261ad9322047225c62/html5/thumbnails/21.jpg)
Conjuntos y permutaciones
A = {a, b, c} , |A|
a ∈ A, a /∈ A
Z,R, ∅
A ∪ B,A ∩ B
Analisis de algoritmos– p. 8
![Page 22: Complejidad, estructuras, diseño y técnicas · Análisis de Algoritmos Complejidad, estructuras, diseño y técnicas Dra. Elisa Schaeffer elisa.schaeffer@gmail.com PISIS / FIME](https://reader030.vdocumento.com/reader030/viewer/2022040318/5e3392261ad9322047225c62/html5/thumbnails/22.jpg)
Conjuntos y permutaciones
A = {a, b, c} , |A|
a ∈ A, a /∈ A
Z,R, ∅
A ∪ B,A ∩ B
|A ∪B| ≥ max {|A| , |B|}
Analisis de algoritmos– p. 8
![Page 23: Complejidad, estructuras, diseño y técnicas · Análisis de Algoritmos Complejidad, estructuras, diseño y técnicas Dra. Elisa Schaeffer elisa.schaeffer@gmail.com PISIS / FIME](https://reader030.vdocumento.com/reader030/viewer/2022040318/5e3392261ad9322047225c62/html5/thumbnails/23.jpg)
Conjuntos y permutaciones
A = {a, b, c} , |A|
a ∈ A, a /∈ A
Z,R, ∅
A ∪ B,A ∩ B
|A ∪B| ≥ max {|A| , |B|}
|A ∩B| ≤ mın {|A| , |B|}
Analisis de algoritmos– p. 8
![Page 24: Complejidad, estructuras, diseño y técnicas · Análisis de Algoritmos Complejidad, estructuras, diseño y técnicas Dra. Elisa Schaeffer elisa.schaeffer@gmail.com PISIS / FIME](https://reader030.vdocumento.com/reader030/viewer/2022040318/5e3392261ad9322047225c62/html5/thumbnails/24.jpg)
Conjuntos y permutaciones
A = {a, b, c} , |A|
a ∈ A, a /∈ A
Z,R, ∅
A ∪ B,A ∩ B
|A ∪B| ≥ max {|A| , |B|}
|A ∩B| ≤ mın {|A| , |B|}
A = {a | a /∈ A}
Analisis de algoritmos– p. 8
![Page 25: Complejidad, estructuras, diseño y técnicas · Análisis de Algoritmos Complejidad, estructuras, diseño y técnicas Dra. Elisa Schaeffer elisa.schaeffer@gmail.com PISIS / FIME](https://reader030.vdocumento.com/reader030/viewer/2022040318/5e3392261ad9322047225c62/html5/thumbnails/25.jpg)
Conjuntos y permutaciones
A = {a, b, c} , |A|
a ∈ A, a /∈ A
Z,R, ∅
A ∪ B,A ∩ B
|A ∪B| ≥ max {|A| , |B|}
|A ∩B| ≤ mın {|A| , |B|}
A = {a | a /∈ A}
A \ B = {a | a ∈ A, a /∈ B}
Analisis de algoritmos– p. 8
![Page 26: Complejidad, estructuras, diseño y técnicas · Análisis de Algoritmos Complejidad, estructuras, diseño y técnicas Dra. Elisa Schaeffer elisa.schaeffer@gmail.com PISIS / FIME](https://reader030.vdocumento.com/reader030/viewer/2022040318/5e3392261ad9322047225c62/html5/thumbnails/26.jpg)
Subconjuntos
B ⊆ A,C * A
Analisis de algoritmos– p. 9
![Page 27: Complejidad, estructuras, diseño y técnicas · Análisis de Algoritmos Complejidad, estructuras, diseño y técnicas Dra. Elisa Schaeffer elisa.schaeffer@gmail.com PISIS / FIME](https://reader030.vdocumento.com/reader030/viewer/2022040318/5e3392261ad9322047225c62/html5/thumbnails/27.jpg)
Subconjuntos
B ⊆ A,C * A
B ⊂ A ⇒ |B| < |A|
Analisis de algoritmos– p. 9
![Page 28: Complejidad, estructuras, diseño y técnicas · Análisis de Algoritmos Complejidad, estructuras, diseño y técnicas Dra. Elisa Schaeffer elisa.schaeffer@gmail.com PISIS / FIME](https://reader030.vdocumento.com/reader030/viewer/2022040318/5e3392261ad9322047225c62/html5/thumbnails/28.jpg)
Subconjuntos
B ⊆ A,C * A
B ⊂ A ⇒ |B| < |A|∣
∣2A∣
∣ = 2|A|
Analisis de algoritmos– p. 9
![Page 29: Complejidad, estructuras, diseño y técnicas · Análisis de Algoritmos Complejidad, estructuras, diseño y técnicas Dra. Elisa Schaeffer elisa.schaeffer@gmail.com PISIS / FIME](https://reader030.vdocumento.com/reader030/viewer/2022040318/5e3392261ad9322047225c62/html5/thumbnails/29.jpg)
Subconjuntos
B ⊆ A,C * A
B ⊂ A ⇒ |B| < |A|∣
∣2A∣
∣ = 2|A|
(
n
k
)
=n!
k!(n− k)!
Analisis de algoritmos– p. 9
![Page 30: Complejidad, estructuras, diseño y técnicas · Análisis de Algoritmos Complejidad, estructuras, diseño y técnicas Dra. Elisa Schaeffer elisa.schaeffer@gmail.com PISIS / FIME](https://reader030.vdocumento.com/reader030/viewer/2022040318/5e3392261ad9322047225c62/html5/thumbnails/30.jpg)
Subconjuntos
B ⊆ A,C * A
B ⊂ A ⇒ |B| < |A|∣
∣2A∣
∣ = 2|A|
(
n
k
)
=n!
k!(n− k)!
(a, b), (a, b], [a, b), [a, b]
Analisis de algoritmos– p. 9
![Page 31: Complejidad, estructuras, diseño y técnicas · Análisis de Algoritmos Complejidad, estructuras, diseño y técnicas Dra. Elisa Schaeffer elisa.schaeffer@gmail.com PISIS / FIME](https://reader030.vdocumento.com/reader030/viewer/2022040318/5e3392261ad9322047225c62/html5/thumbnails/31.jpg)
Subconjuntos
B ⊆ A,C * A
B ⊂ A ⇒ |B| < |A|∣
∣2A∣
∣ = 2|A|
(
n
k
)
=n!
k!(n− k)!
(a, b), (a, b], [a, b), [a, b]
A tiene |A|! permutaciones
Analisis de algoritmos– p. 9
![Page 32: Complejidad, estructuras, diseño y técnicas · Análisis de Algoritmos Complejidad, estructuras, diseño y técnicas Dra. Elisa Schaeffer elisa.schaeffer@gmail.com PISIS / FIME](https://reader030.vdocumento.com/reader030/viewer/2022040318/5e3392261ad9322047225c62/html5/thumbnails/32.jpg)
Subconjuntos
B ⊆ A,C * A
B ⊂ A ⇒ |B| < |A|∣
∣2A∣
∣ = 2|A|
(
n
k
)
=n!
k!(n− k)!
(a, b), (a, b], [a, b), [a, b]
A tiene |A|! permutaciones
k-subconjuntos ordenados de A: k! ·(
n
k
)
=n!
(n− k)!
Analisis de algoritmos– p. 9
![Page 33: Complejidad, estructuras, diseño y técnicas · Análisis de Algoritmos Complejidad, estructuras, diseño y técnicas Dra. Elisa Schaeffer elisa.schaeffer@gmail.com PISIS / FIME](https://reader030.vdocumento.com/reader030/viewer/2022040318/5e3392261ad9322047225c62/html5/thumbnails/33.jpg)
Relaciones
A× B = {(a, b) | a ∈ A, b ∈ B}
Analisis de algoritmos– p. 10
![Page 34: Complejidad, estructuras, diseño y técnicas · Análisis de Algoritmos Complejidad, estructuras, diseño y técnicas Dra. Elisa Schaeffer elisa.schaeffer@gmail.com PISIS / FIME](https://reader030.vdocumento.com/reader030/viewer/2022040318/5e3392261ad9322047225c62/html5/thumbnails/34.jpg)
Relaciones
A× B = {(a, b) | a ∈ A, b ∈ B}
R ⊆ A× B
Analisis de algoritmos– p. 10
![Page 35: Complejidad, estructuras, diseño y técnicas · Análisis de Algoritmos Complejidad, estructuras, diseño y técnicas Dra. Elisa Schaeffer elisa.schaeffer@gmail.com PISIS / FIME](https://reader030.vdocumento.com/reader030/viewer/2022040318/5e3392261ad9322047225c62/html5/thumbnails/35.jpg)
Relaciones
A× B = {(a, b) | a ∈ A, b ∈ B}
R ⊆ A× B
(a, b) ∈ R o alternativamente aRb
Analisis de algoritmos– p. 10
![Page 36: Complejidad, estructuras, diseño y técnicas · Análisis de Algoritmos Complejidad, estructuras, diseño y técnicas Dra. Elisa Schaeffer elisa.schaeffer@gmail.com PISIS / FIME](https://reader030.vdocumento.com/reader030/viewer/2022040318/5e3392261ad9322047225c62/html5/thumbnails/36.jpg)
Relaciones
A× B = {(a, b) | a ∈ A, b ∈ B}
R ⊆ A× B
(a, b) ∈ R o alternativamente aRb
Matriz: aij ={
1, si (ai, bj) ∈ R,
0, si (ai, bj) /∈ R
Analisis de algoritmos– p. 10
![Page 37: Complejidad, estructuras, diseño y técnicas · Análisis de Algoritmos Complejidad, estructuras, diseño y técnicas Dra. Elisa Schaeffer elisa.schaeffer@gmail.com PISIS / FIME](https://reader030.vdocumento.com/reader030/viewer/2022040318/5e3392261ad9322047225c62/html5/thumbnails/37.jpg)
Relaciones
A× B = {(a, b) | a ∈ A, b ∈ B}
R ⊆ A× B
(a, b) ∈ R o alternativamente aRb
Matriz: aij ={
1, si (ai, bj) ∈ R,
0, si (ai, bj) /∈ R
Transitiva: ∀a, b, c ∈ A tales que aRb y bRc, aRc
Analisis de algoritmos– p. 10
![Page 38: Complejidad, estructuras, diseño y técnicas · Análisis de Algoritmos Complejidad, estructuras, diseño y técnicas Dra. Elisa Schaeffer elisa.schaeffer@gmail.com PISIS / FIME](https://reader030.vdocumento.com/reader030/viewer/2022040318/5e3392261ad9322047225c62/html5/thumbnails/38.jpg)
Relaciones
A× B = {(a, b) | a ∈ A, b ∈ B}
R ⊆ A× B
(a, b) ∈ R o alternativamente aRb
Matriz: aij ={
1, si (ai, bj) ∈ R,
0, si (ai, bj) /∈ R
Transitiva: ∀a, b, c ∈ A tales que aRb y bRc, aRc
Reflexiva: ∀a ∈ A, aRa
Analisis de algoritmos– p. 10
![Page 39: Complejidad, estructuras, diseño y técnicas · Análisis de Algoritmos Complejidad, estructuras, diseño y técnicas Dra. Elisa Schaeffer elisa.schaeffer@gmail.com PISIS / FIME](https://reader030.vdocumento.com/reader030/viewer/2022040318/5e3392261ad9322047225c62/html5/thumbnails/39.jpg)
Relaciones
A× B = {(a, b) | a ∈ A, b ∈ B}
R ⊆ A× B
(a, b) ∈ R o alternativamente aRb
Matriz: aij ={
1, si (ai, bj) ∈ R,
0, si (ai, bj) /∈ R
Transitiva: ∀a, b, c ∈ A tales que aRb y bRc, aRc
Reflexiva: ∀a ∈ A, aRa
Simétrica: (ai, aj) ∈ R ⇔ (aj , ai) ∈ R
Analisis de algoritmos– p. 10
![Page 40: Complejidad, estructuras, diseño y técnicas · Análisis de Algoritmos Complejidad, estructuras, diseño y técnicas Dra. Elisa Schaeffer elisa.schaeffer@gmail.com PISIS / FIME](https://reader030.vdocumento.com/reader030/viewer/2022040318/5e3392261ad9322047225c62/html5/thumbnails/40.jpg)
Relaciones
A× B = {(a, b) | a ∈ A, b ∈ B}
R ⊆ A× B
(a, b) ∈ R o alternativamente aRb
Matriz: aij ={
1, si (ai, bj) ∈ R,
0, si (ai, bj) /∈ R
Transitiva: ∀a, b, c ∈ A tales que aRb y bRc, aRc
Reflexiva: ∀a ∈ A, aRa
Simétrica: (ai, aj) ∈ R ⇔ (aj , ai) ∈ R
Cláusuras
Analisis de algoritmos– p. 10
![Page 41: Complejidad, estructuras, diseño y técnicas · Análisis de Algoritmos Complejidad, estructuras, diseño y técnicas Dra. Elisa Schaeffer elisa.schaeffer@gmail.com PISIS / FIME](https://reader030.vdocumento.com/reader030/viewer/2022040318/5e3392261ad9322047225c62/html5/thumbnails/41.jpg)
Mapeos
g : A → B, g(a) = b para significar que (a, b) ∈ Rg
Analisis de algoritmos– p. 11
![Page 42: Complejidad, estructuras, diseño y técnicas · Análisis de Algoritmos Complejidad, estructuras, diseño y técnicas Dra. Elisa Schaeffer elisa.schaeffer@gmail.com PISIS / FIME](https://reader030.vdocumento.com/reader030/viewer/2022040318/5e3392261ad9322047225c62/html5/thumbnails/42.jpg)
Mapeos
g : A → B, g(a) = b para significar que (a, b) ∈ Rg
A es el dominio y B es el rango
Analisis de algoritmos– p. 11
![Page 43: Complejidad, estructuras, diseño y técnicas · Análisis de Algoritmos Complejidad, estructuras, diseño y técnicas Dra. Elisa Schaeffer elisa.schaeffer@gmail.com PISIS / FIME](https://reader030.vdocumento.com/reader030/viewer/2022040318/5e3392261ad9322047225c62/html5/thumbnails/43.jpg)
Mapeos
g : A → B, g(a) = b para significar que (a, b) ∈ Rg
A es el dominio y B es el rango
Los bi ∈ B para las cuales aplica (a, bi) ∈ Rg son laimagen a en B
Analisis de algoritmos– p. 11
![Page 44: Complejidad, estructuras, diseño y técnicas · Análisis de Algoritmos Complejidad, estructuras, diseño y técnicas Dra. Elisa Schaeffer elisa.schaeffer@gmail.com PISIS / FIME](https://reader030.vdocumento.com/reader030/viewer/2022040318/5e3392261ad9322047225c62/html5/thumbnails/44.jpg)
Mapeos
g : A → B, g(a) = b para significar que (a, b) ∈ Rg
A es el dominio y B es el rango
Los bi ∈ B para las cuales aplica (a, bi) ∈ Rg son laimagen a en B
Los elementos de A que corresponden a un b ∈ B asíque (a, b) ∈ Rg son la imagen inversa de b, g−1(b)
Analisis de algoritmos– p. 11
![Page 45: Complejidad, estructuras, diseño y técnicas · Análisis de Algoritmos Complejidad, estructuras, diseño y técnicas Dra. Elisa Schaeffer elisa.schaeffer@gmail.com PISIS / FIME](https://reader030.vdocumento.com/reader030/viewer/2022040318/5e3392261ad9322047225c62/html5/thumbnails/45.jpg)
Mapeos
g : A → B, g(a) = b para significar que (a, b) ∈ Rg
A es el dominio y B es el rango
Los bi ∈ B para las cuales aplica (a, bi) ∈ Rg son laimagen a en B
Los elementos de A que corresponden a un b ∈ B asíque (a, b) ∈ Rg son la imagen inversa de b, g−1(b)
Epiyectivo: ∀b ∈ B∃a ∈ A tal que g(a) = b
Analisis de algoritmos– p. 11
![Page 46: Complejidad, estructuras, diseño y técnicas · Análisis de Algoritmos Complejidad, estructuras, diseño y técnicas Dra. Elisa Schaeffer elisa.schaeffer@gmail.com PISIS / FIME](https://reader030.vdocumento.com/reader030/viewer/2022040318/5e3392261ad9322047225c62/html5/thumbnails/46.jpg)
Mapeos
g : A → B, g(a) = b para significar que (a, b) ∈ Rg
A es el dominio y B es el rango
Los bi ∈ B para las cuales aplica (a, bi) ∈ Rg son laimagen a en B
Los elementos de A que corresponden a un b ∈ B asíque (a, b) ∈ Rg son la imagen inversa de b, g−1(b)
Epiyectivo: ∀b ∈ B∃a ∈ A tal que g(a) = b
Inyectivo: ∀a1, a2 ∈ A tales que a1 = a2 ⇒ g(a1) = g(a2)
Analisis de algoritmos– p. 11
![Page 47: Complejidad, estructuras, diseño y técnicas · Análisis de Algoritmos Complejidad, estructuras, diseño y técnicas Dra. Elisa Schaeffer elisa.schaeffer@gmail.com PISIS / FIME](https://reader030.vdocumento.com/reader030/viewer/2022040318/5e3392261ad9322047225c62/html5/thumbnails/47.jpg)
Mapeos
g : A → B, g(a) = b para significar que (a, b) ∈ Rg
A es el dominio y B es el rango
Los bi ∈ B para las cuales aplica (a, bi) ∈ Rg son laimagen a en B
Los elementos de A que corresponden a un b ∈ B asíque (a, b) ∈ Rg son la imagen inversa de b, g−1(b)
Epiyectivo: ∀b ∈ B∃a ∈ A tal que g(a) = b
Inyectivo: ∀a1, a2 ∈ A tales que a1 = a2 ⇒ g(a1) = g(a2)
Biyectivo: inyectivo y epiyectivo
Analisis de algoritmos– p. 11
![Page 48: Complejidad, estructuras, diseño y técnicas · Análisis de Algoritmos Complejidad, estructuras, diseño y técnicas Dra. Elisa Schaeffer elisa.schaeffer@gmail.com PISIS / FIME](https://reader030.vdocumento.com/reader030/viewer/2022040318/5e3392261ad9322047225c62/html5/thumbnails/48.jpg)
Funciones
Una función f : A → B es un mapeo que asigna acada elemento de A un único elemento de B
Analisis de algoritmos– p. 12
![Page 49: Complejidad, estructuras, diseño y técnicas · Análisis de Algoritmos Complejidad, estructuras, diseño y técnicas Dra. Elisa Schaeffer elisa.schaeffer@gmail.com PISIS / FIME](https://reader030.vdocumento.com/reader030/viewer/2022040318/5e3392261ad9322047225c62/html5/thumbnails/49.jpg)
Funciones
Una función f : A → B es un mapeo que asigna acada elemento de A un único elemento de B
|x| =
{
x, si x ≥ 0
−x, si x < 0.
Analisis de algoritmos– p. 12
![Page 50: Complejidad, estructuras, diseño y técnicas · Análisis de Algoritmos Complejidad, estructuras, diseño y técnicas Dra. Elisa Schaeffer elisa.schaeffer@gmail.com PISIS / FIME](https://reader030.vdocumento.com/reader030/viewer/2022040318/5e3392261ad9322047225c62/html5/thumbnails/50.jpg)
Funciones
Una función f : A → B es un mapeo que asigna acada elemento de A un único elemento de B
|x| =
{
x, si x ≥ 0
−x, si x < 0.
exp(x) = ex =∞∑
i=0
xi
i!= 1 + x+
x2
2!+
x3
3!+ . . .
Analisis de algoritmos– p. 12
![Page 51: Complejidad, estructuras, diseño y técnicas · Análisis de Algoritmos Complejidad, estructuras, diseño y técnicas Dra. Elisa Schaeffer elisa.schaeffer@gmail.com PISIS / FIME](https://reader030.vdocumento.com/reader030/viewer/2022040318/5e3392261ad9322047225c62/html5/thumbnails/51.jpg)
Funciones
Una función f : A → B es un mapeo que asigna acada elemento de A un único elemento de B
|x| =
{
x, si x ≥ 0
−x, si x < 0.
exp(x) = ex =∞∑
i=0
xi
i!= 1 + x+
x2
2!+
x3
3!+ . . .
e ≈ 2, 718281828 es el constante de Napier
Analisis de algoritmos– p. 12
![Page 52: Complejidad, estructuras, diseño y técnicas · Análisis de Algoritmos Complejidad, estructuras, diseño y técnicas Dra. Elisa Schaeffer elisa.schaeffer@gmail.com PISIS / FIME](https://reader030.vdocumento.com/reader030/viewer/2022040318/5e3392261ad9322047225c62/html5/thumbnails/52.jpg)
Funciones
Una función f : A → B es un mapeo que asigna acada elemento de A un único elemento de B
|x| =
{
x, si x ≥ 0
−x, si x < 0.
exp(x) = ex =∞∑
i=0
xi
i!= 1 + x+
x2
2!+
x3
3!+ . . .
e ≈ 2, 718281828 es el constante de Napier
ex = lımn→∞
(
1 +x
n
)n
Analisis de algoritmos– p. 12
![Page 53: Complejidad, estructuras, diseño y técnicas · Análisis de Algoritmos Complejidad, estructuras, diseño y técnicas Dra. Elisa Schaeffer elisa.schaeffer@gmail.com PISIS / FIME](https://reader030.vdocumento.com/reader030/viewer/2022040318/5e3392261ad9322047225c62/html5/thumbnails/53.jpg)
Funciones
Una función f : A → B es un mapeo que asigna acada elemento de A un único elemento de B
|x| =
{
x, si x ≥ 0
−x, si x < 0.
exp(x) = ex =∞∑
i=0
xi
i!= 1 + x+
x2
2!+
x3
3!+ . . .
e ≈ 2, 718281828 es el constante de Napier
ex = lımn→∞
(
1 +x
n
)n
D(ex) = ex
Analisis de algoritmos– p. 12
![Page 54: Complejidad, estructuras, diseño y técnicas · Análisis de Algoritmos Complejidad, estructuras, diseño y técnicas Dra. Elisa Schaeffer elisa.schaeffer@gmail.com PISIS / FIME](https://reader030.vdocumento.com/reader030/viewer/2022040318/5e3392261ad9322047225c62/html5/thumbnails/54.jpg)
Funciones
Una función f : A → B es un mapeo que asigna acada elemento de A un único elemento de B
|x| =
{
x, si x ≥ 0
−x, si x < 0.
exp(x) = ex =∞∑
i=0
xi
i!= 1 + x+
x2
2!+
x3
3!+ . . .
e ≈ 2, 718281828 es el constante de Napier
ex = lımn→∞
(
1 +x
n
)n
D(ex) = ex
Analisis de algoritmos– p. 12
![Page 55: Complejidad, estructuras, diseño y técnicas · Análisis de Algoritmos Complejidad, estructuras, diseño y técnicas Dra. Elisa Schaeffer elisa.schaeffer@gmail.com PISIS / FIME](https://reader030.vdocumento.com/reader030/viewer/2022040318/5e3392261ad9322047225c62/html5/thumbnails/55.jpg)
Función exponencial
0
200
400
600
800
1000
0 2 4 6 8 10
Escala lineal
1
10
100
1000
10000
0 2 4 6 8 10
Escala logarítmica
Analisis de algoritmos– p. 13
![Page 56: Complejidad, estructuras, diseño y técnicas · Análisis de Algoritmos Complejidad, estructuras, diseño y técnicas Dra. Elisa Schaeffer elisa.schaeffer@gmail.com PISIS / FIME](https://reader030.vdocumento.com/reader030/viewer/2022040318/5e3392261ad9322047225c62/html5/thumbnails/56.jpg)
Exponentes
b0 = 1
Analisis de algoritmos– p. 14
![Page 57: Complejidad, estructuras, diseño y técnicas · Análisis de Algoritmos Complejidad, estructuras, diseño y técnicas Dra. Elisa Schaeffer elisa.schaeffer@gmail.com PISIS / FIME](https://reader030.vdocumento.com/reader030/viewer/2022040318/5e3392261ad9322047225c62/html5/thumbnails/57.jpg)
Exponentes
b0 = 1
b1 = b
Analisis de algoritmos– p. 14
![Page 58: Complejidad, estructuras, diseño y técnicas · Análisis de Algoritmos Complejidad, estructuras, diseño y técnicas Dra. Elisa Schaeffer elisa.schaeffer@gmail.com PISIS / FIME](https://reader030.vdocumento.com/reader030/viewer/2022040318/5e3392261ad9322047225c62/html5/thumbnails/58.jpg)
Exponentes
b0 = 1
b1 = b
ba+c = babc
Analisis de algoritmos– p. 14
![Page 59: Complejidad, estructuras, diseño y técnicas · Análisis de Algoritmos Complejidad, estructuras, diseño y técnicas Dra. Elisa Schaeffer elisa.schaeffer@gmail.com PISIS / FIME](https://reader030.vdocumento.com/reader030/viewer/2022040318/5e3392261ad9322047225c62/html5/thumbnails/59.jpg)
Exponentes
b0 = 1
b1 = b
ba+c = babc
bac = (ba)c
Analisis de algoritmos– p. 14
![Page 60: Complejidad, estructuras, diseño y técnicas · Análisis de Algoritmos Complejidad, estructuras, diseño y técnicas Dra. Elisa Schaeffer elisa.schaeffer@gmail.com PISIS / FIME](https://reader030.vdocumento.com/reader030/viewer/2022040318/5e3392261ad9322047225c62/html5/thumbnails/60.jpg)
Exponentes
b0 = 1
b1 = b
ba+c = babc
bac = (ba)c
b−a =(
1b
)a= 1
ba
Analisis de algoritmos– p. 14
![Page 61: Complejidad, estructuras, diseño y técnicas · Análisis de Algoritmos Complejidad, estructuras, diseño y técnicas Dra. Elisa Schaeffer elisa.schaeffer@gmail.com PISIS / FIME](https://reader030.vdocumento.com/reader030/viewer/2022040318/5e3392261ad9322047225c62/html5/thumbnails/61.jpg)
Logaritmos
blogb x = x donde x > 0
Analisis de algoritmos– p. 15
![Page 62: Complejidad, estructuras, diseño y técnicas · Análisis de Algoritmos Complejidad, estructuras, diseño y técnicas Dra. Elisa Schaeffer elisa.schaeffer@gmail.com PISIS / FIME](https://reader030.vdocumento.com/reader030/viewer/2022040318/5e3392261ad9322047225c62/html5/thumbnails/62.jpg)
Logaritmos
blogb x = x donde x > 0
Si logb x = y, by = x
Analisis de algoritmos– p. 15
![Page 63: Complejidad, estructuras, diseño y técnicas · Análisis de Algoritmos Complejidad, estructuras, diseño y técnicas Dra. Elisa Schaeffer elisa.schaeffer@gmail.com PISIS / FIME](https://reader030.vdocumento.com/reader030/viewer/2022040318/5e3392261ad9322047225c62/html5/thumbnails/63.jpg)
Logaritmos
blogb x = x donde x > 0
Si logb x = y, by = x
Se define que logb 1 = 0
Analisis de algoritmos– p. 15
![Page 64: Complejidad, estructuras, diseño y técnicas · Análisis de Algoritmos Complejidad, estructuras, diseño y técnicas Dra. Elisa Schaeffer elisa.schaeffer@gmail.com PISIS / FIME](https://reader030.vdocumento.com/reader030/viewer/2022040318/5e3392261ad9322047225c62/html5/thumbnails/64.jpg)
Logaritmos
blogb x = x donde x > 0
Si logb x = y, by = x
Se define que logb 1 = 0
Cambios de base: logb′(x) =logb(x)
logb(b′)
.
Analisis de algoritmos– p. 15
![Page 65: Complejidad, estructuras, diseño y técnicas · Análisis de Algoritmos Complejidad, estructuras, diseño y técnicas Dra. Elisa Schaeffer elisa.schaeffer@gmail.com PISIS / FIME](https://reader030.vdocumento.com/reader030/viewer/2022040318/5e3392261ad9322047225c62/html5/thumbnails/65.jpg)
Logaritmos
blogb x = x donde x > 0
Si logb x = y, by = x
Se define que logb 1 = 0
Cambios de base: logb′(x) =logb(x)
logb(b′)
.
Es inyectiva: logb x = logb y =⇒ x = y
Analisis de algoritmos– p. 15
![Page 66: Complejidad, estructuras, diseño y técnicas · Análisis de Algoritmos Complejidad, estructuras, diseño y técnicas Dra. Elisa Schaeffer elisa.schaeffer@gmail.com PISIS / FIME](https://reader030.vdocumento.com/reader030/viewer/2022040318/5e3392261ad9322047225c62/html5/thumbnails/66.jpg)
Logaritmos
blogb x = x donde x > 0
Si logb x = y, by = x
Se define que logb 1 = 0
Cambios de base: logb′(x) =logb(x)
logb(b′)
.
Es inyectiva: logb x = logb y =⇒ x = y
Es creciente: x > y =⇒ logb x > logb y
Analisis de algoritmos– p. 15
![Page 67: Complejidad, estructuras, diseño y técnicas · Análisis de Algoritmos Complejidad, estructuras, diseño y técnicas Dra. Elisa Schaeffer elisa.schaeffer@gmail.com PISIS / FIME](https://reader030.vdocumento.com/reader030/viewer/2022040318/5e3392261ad9322047225c62/html5/thumbnails/67.jpg)
Logaritmos
1
2
3
4
5
6
7
8
9
10
0 200 400 600 800 1000
b = 2b = e
b = 10
Analisis de algoritmos– p. 16
![Page 68: Complejidad, estructuras, diseño y técnicas · Análisis de Algoritmos Complejidad, estructuras, diseño y técnicas Dra. Elisa Schaeffer elisa.schaeffer@gmail.com PISIS / FIME](https://reader030.vdocumento.com/reader030/viewer/2022040318/5e3392261ad9322047225c62/html5/thumbnails/68.jpg)
Logaritmos
Multiplicación: logb(x · y) = logb x+ logb y
Analisis de algoritmos– p. 17
![Page 69: Complejidad, estructuras, diseño y técnicas · Análisis de Algoritmos Complejidad, estructuras, diseño y técnicas Dra. Elisa Schaeffer elisa.schaeffer@gmail.com PISIS / FIME](https://reader030.vdocumento.com/reader030/viewer/2022040318/5e3392261ad9322047225c62/html5/thumbnails/69.jpg)
Logaritmos
Multiplicación: logb(x · y) = logb x+ logb y
División: logb(
xy
)
= logb x− logb y
Analisis de algoritmos– p. 17
![Page 70: Complejidad, estructuras, diseño y técnicas · Análisis de Algoritmos Complejidad, estructuras, diseño y técnicas Dra. Elisa Schaeffer elisa.schaeffer@gmail.com PISIS / FIME](https://reader030.vdocumento.com/reader030/viewer/2022040318/5e3392261ad9322047225c62/html5/thumbnails/70.jpg)
Logaritmos
Multiplicación: logb(x · y) = logb x+ logb y
División: logb(
xy
)
= logb x− logb y
Potencia: logb xc = c logb x
Analisis de algoritmos– p. 17
![Page 71: Complejidad, estructuras, diseño y técnicas · Análisis de Algoritmos Complejidad, estructuras, diseño y técnicas Dra. Elisa Schaeffer elisa.schaeffer@gmail.com PISIS / FIME](https://reader030.vdocumento.com/reader030/viewer/2022040318/5e3392261ad9322047225c62/html5/thumbnails/71.jpg)
Logaritmos
Multiplicación: logb(x · y) = logb x+ logb y
División: logb(
xy
)
= logb x− logb y
Potencia: logb xc = c logb x
En el exponente: xlogb y = ylogb x
Analisis de algoritmos– p. 17
![Page 72: Complejidad, estructuras, diseño y técnicas · Análisis de Algoritmos Complejidad, estructuras, diseño y técnicas Dra. Elisa Schaeffer elisa.schaeffer@gmail.com PISIS / FIME](https://reader030.vdocumento.com/reader030/viewer/2022040318/5e3392261ad9322047225c62/html5/thumbnails/72.jpg)
Logaritmos
Multiplicación: logb(x · y) = logb x+ logb y
División: logb(
xy
)
= logb x− logb y
Potencia: logb xc = c logb x
En el exponente: xlogb y = ylogb x
Factorial: logb(n!) =n
∑
i=1
logb i
Analisis de algoritmos– p. 17
![Page 73: Complejidad, estructuras, diseño y técnicas · Análisis de Algoritmos Complejidad, estructuras, diseño y técnicas Dra. Elisa Schaeffer elisa.schaeffer@gmail.com PISIS / FIME](https://reader030.vdocumento.com/reader030/viewer/2022040318/5e3392261ad9322047225c62/html5/thumbnails/73.jpg)
Sucesiones
Suma: S = x1 + x2 + x3 + . . .+ xn =n
∑
i=1
xi
Analisis de algoritmos– p. 18
![Page 74: Complejidad, estructuras, diseño y técnicas · Análisis de Algoritmos Complejidad, estructuras, diseño y técnicas Dra. Elisa Schaeffer elisa.schaeffer@gmail.com PISIS / FIME](https://reader030.vdocumento.com/reader030/viewer/2022040318/5e3392261ad9322047225c62/html5/thumbnails/74.jpg)
Sucesiones
Suma: S = x1 + x2 + x3 + . . .+ xn =n
∑
i=1
xi
Parcial: Sk =k
∑
i=1
xi
Analisis de algoritmos– p. 18
![Page 75: Complejidad, estructuras, diseño y técnicas · Análisis de Algoritmos Complejidad, estructuras, diseño y técnicas Dra. Elisa Schaeffer elisa.schaeffer@gmail.com PISIS / FIME](https://reader030.vdocumento.com/reader030/viewer/2022040318/5e3392261ad9322047225c62/html5/thumbnails/75.jpg)
Sucesiones
Suma: S = x1 + x2 + x3 + . . .+ xn =n
∑
i=1
xi
Parcial: Sk =k
∑
i=1
xi
Producto: P = x1 · x2 · x3 · . . . · xn =n∏
i=1
xi
Analisis de algoritmos– p. 18
![Page 76: Complejidad, estructuras, diseño y técnicas · Análisis de Algoritmos Complejidad, estructuras, diseño y técnicas Dra. Elisa Schaeffer elisa.schaeffer@gmail.com PISIS / FIME](https://reader030.vdocumento.com/reader030/viewer/2022040318/5e3392261ad9322047225c62/html5/thumbnails/76.jpg)
Serie aritmética
xi+1 − xi = d, donde d es constante
Sn =
n−1∑
i=0
(x1 + i · d) =n(x1 + xn)
2
Analisis de algoritmos– p. 19
![Page 77: Complejidad, estructuras, diseño y técnicas · Análisis de Algoritmos Complejidad, estructuras, diseño y técnicas Dra. Elisa Schaeffer elisa.schaeffer@gmail.com PISIS / FIME](https://reader030.vdocumento.com/reader030/viewer/2022040318/5e3392261ad9322047225c62/html5/thumbnails/77.jpg)
Serie geométrica
xi+1 = xi · d
S =∞∑
i=0
dixi =x1
1− d
Sn =n
∑
i=0
dixi =x1(1− dn+1)
1− d
Analisis de algoritmos– p. 20
![Page 78: Complejidad, estructuras, diseño y técnicas · Análisis de Algoritmos Complejidad, estructuras, diseño y técnicas Dra. Elisa Schaeffer elisa.schaeffer@gmail.com PISIS / FIME](https://reader030.vdocumento.com/reader030/viewer/2022040318/5e3392261ad9322047225c62/html5/thumbnails/78.jpg)
Tarea en clase
Justificar las siguientes aproximaciones:
(
1− 1
x
)k≈ e−
k
x 1− x ≤ e−xxx
x!< ex
para |x| ≤ 1 : ex(1− x2) ≤ 1 + x ≤ ex
para k ≪ x : 1− kx≈ e−
k
x .
Analisis de algoritmos– p. 21