cc3001 Métodos Matemáticos
Patricio Poblete
Otoño 2012
Patricio Poblete () cc3001 Métodos Matemáticos Otoño 2012 1 / 17
Funciones discretas
Para estudiar la eciencia de los algoritmos, generalmente usamos
funciones discretas, que miden cantidades tales tiempo de ejecución,
memoria utilizada, etc.
Estas funciones son discretas porque dependen del tamaño del
problema (n). Por ejemplo, n podría representar el número de
elementos a ordenar.
Notación: f (n) o bien fn
Patricio Poblete () cc3001 Métodos Matemáticos Otoño 2012 2 / 17
Funciones discretas
Para estudiar la eciencia de los algoritmos, generalmente usamos
funciones discretas, que miden cantidades tales tiempo de ejecución,
memoria utilizada, etc.
Estas funciones son discretas porque dependen del tamaño del
problema (n). Por ejemplo, n podría representar el número de
elementos a ordenar.
Notación: f (n) o bien fn
Patricio Poblete () cc3001 Métodos Matemáticos Otoño 2012 2 / 17
Funciones discretas
Para estudiar la eciencia de los algoritmos, generalmente usamos
funciones discretas, que miden cantidades tales tiempo de ejecución,
memoria utilizada, etc.
Estas funciones son discretas porque dependen del tamaño del
problema (n). Por ejemplo, n podría representar el número de
elementos a ordenar.
Notación: f (n) o bien fn
Patricio Poblete () cc3001 Métodos Matemáticos Otoño 2012 2 / 17
Notación O
Se dice que una función f (n) es O(g(n)) si existe una constante c > 0
y un n0 ≥ 0 tal que para todo n ≥ n0 se tiene que f (n) ≤ cg(n).
Se dice que una función f (n) es Ω(g(n)) si existe una constante c > 0
y un n0 ≥ 0 tal que para todo n ≥ n0 se tiene que f (n) ≥ cg(n).
Se dice que una función f (n) es Θ(g(n)) si f (n) = O(g(n) y
f (n) = Ω(g(n)).
Patricio Poblete () cc3001 Métodos Matemáticos Otoño 2012 3 / 17
Notación O
Se dice que una función f (n) es O(g(n)) si existe una constante c > 0
y un n0 ≥ 0 tal que para todo n ≥ n0 se tiene que f (n) ≤ cg(n).
Se dice que una función f (n) es Ω(g(n)) si existe una constante c > 0
y un n0 ≥ 0 tal que para todo n ≥ n0 se tiene que f (n) ≥ cg(n).
Se dice que una función f (n) es Θ(g(n)) si f (n) = O(g(n) y
f (n) = Ω(g(n)).
Patricio Poblete () cc3001 Métodos Matemáticos Otoño 2012 3 / 17
Notación O
Se dice que una función f (n) es O(g(n)) si existe una constante c > 0
y un n0 ≥ 0 tal que para todo n ≥ n0 se tiene que f (n) ≤ cg(n).
Se dice que una función f (n) es Ω(g(n)) si existe una constante c > 0
y un n0 ≥ 0 tal que para todo n ≥ n0 se tiene que f (n) ≥ cg(n).
Se dice que una función f (n) es Θ(g(n)) si f (n) = O(g(n) y
f (n) = Ω(g(n)).
Patricio Poblete () cc3001 Métodos Matemáticos Otoño 2012 3 / 17
Ejemplos
3n = O(n)2 = O(1)2 = O(n)3n + 2 = O(n)
3 = Ω(1)3n = Ω(n)3n = Ω(1)3n + 2 = Ω(n)
3n + 2 = Θ(n)
Patricio Poblete () cc3001 Métodos Matemáticos Otoño 2012 4 / 17
Ejemplos
3n = O(n)2 = O(1)2 = O(n)3n + 2 = O(n)
3 = Ω(1)3n = Ω(n)3n = Ω(1)3n + 2 = Ω(n)
3n + 2 = Θ(n)
Patricio Poblete () cc3001 Métodos Matemáticos Otoño 2012 4 / 17
Ejemplos
3n = O(n)2 = O(1)2 = O(n)3n + 2 = O(n)
3 = Ω(1)3n = Ω(n)3n = Ω(1)3n + 2 = Ω(n)
3n + 2 = Θ(n)
Patricio Poblete () cc3001 Métodos Matemáticos Otoño 2012 4 / 17
Ecuaciones de Recurrencia
Son ecuaciones en que el valor de la función para un n dado se obtiene
en función de valores anteriores.
Esto permite calcular el valor de la función para cualquier n, a partir
de condiciones de borde (o condiciones iniciales)
Ejemplo: Torres de Hanoi
an = 2an−1 + 1
a0 = 0
Ejemplo: Fibonacci
fn = fn−1 + fn−2
f0 = 0
f1 = 1
Patricio Poblete () cc3001 Métodos Matemáticos Otoño 2012 5 / 17
Ecuaciones de Recurrencia
Son ecuaciones en que el valor de la función para un n dado se obtiene
en función de valores anteriores.
Esto permite calcular el valor de la función para cualquier n, a partir
de condiciones de borde (o condiciones iniciales)
Ejemplo: Torres de Hanoi
an = 2an−1 + 1
a0 = 0
Ejemplo: Fibonacci
fn = fn−1 + fn−2
f0 = 0
f1 = 1
Patricio Poblete () cc3001 Métodos Matemáticos Otoño 2012 5 / 17
Ecuaciones de Recurrencia
Son ecuaciones en que el valor de la función para un n dado se obtiene
en función de valores anteriores.
Esto permite calcular el valor de la función para cualquier n, a partir
de condiciones de borde (o condiciones iniciales)
Ejemplo: Torres de Hanoi
an = 2an−1 + 1
a0 = 0
Ejemplo: Fibonacci
fn = fn−1 + fn−2
f0 = 0
f1 = 1
Patricio Poblete () cc3001 Métodos Matemáticos Otoño 2012 5 / 17
Ecuaciones de Recurrencia
Son ecuaciones en que el valor de la función para un n dado se obtiene
en función de valores anteriores.
Esto permite calcular el valor de la función para cualquier n, a partir
de condiciones de borde (o condiciones iniciales)
Ejemplo: Torres de Hanoi
an = 2an−1 + 1
a0 = 0
Ejemplo: Fibonacci
fn = fn−1 + fn−2
f0 = 0
f1 = 1
Patricio Poblete () cc3001 Métodos Matemáticos Otoño 2012 5 / 17
Ecuaciones de Primer Orden
Consideremos una ecuación de la forma
an = ban−1 + cn
donde b es una constante y cn es una función conocida.
Como precalentamiento, consideremos el caso b = 1:
an = an−1 + cn
Esto se puede poner en la forma
an − an−1 = cn
Sumando a ambos lados, queda una suma telescópica:
an = a0 +∑
1≤k≤n
ck
Patricio Poblete () cc3001 Métodos Matemáticos Otoño 2012 6 / 17
Ecuaciones de Primer Orden
Consideremos una ecuación de la forma
an = ban−1 + cn
donde b es una constante y cn es una función conocida.
Como precalentamiento, consideremos el caso b = 1:
an = an−1 + cn
Esto se puede poner en la forma
an − an−1 = cn
Sumando a ambos lados, queda una suma telescópica:
an = a0 +∑
1≤k≤n
ck
Patricio Poblete () cc3001 Métodos Matemáticos Otoño 2012 6 / 17
Ecuaciones de Primer Orden
Consideremos una ecuación de la forma
an = ban−1 + cn
donde b es una constante y cn es una función conocida.
Como precalentamiento, consideremos el caso b = 1:
an = an−1 + cn
Esto se puede poner en la forma
an − an−1 = cn
Sumando a ambos lados, queda una suma telescópica:
an = a0 +∑
1≤k≤n
ck
Patricio Poblete () cc3001 Métodos Matemáticos Otoño 2012 6 / 17
Ecuaciones de Primer Orden
Consideremos una ecuación de la forma
an = ban−1 + cn
donde b es una constante y cn es una función conocida.
Como precalentamiento, consideremos el caso b = 1:
an = an−1 + cn
Esto se puede poner en la forma
an − an−1 = cn
Sumando a ambos lados, queda una suma telescópica:
an = a0 +∑
1≤k≤n
ck
Patricio Poblete () cc3001 Métodos Matemáticos Otoño 2012 6 / 17
Ecuaciones de Primer Orden (cont.)
Para resolver el caso general:
an = ban−1 + cn
dividamos ambos lados por el factor sumante bn:
an
bn=
an−1
bn−1+
cn
bn
Si denimos An = an/bn, Cn = cn/b
n, queda una ecuación que ya sabemos
resolver:
An = An−1 + Cn
con solución
An = A0 +∑
1≤k≤n
Ck
y nalmente
an = a0bn +
∑1≤k≤n
ckbn−k
Patricio Poblete () cc3001 Métodos Matemáticos Otoño 2012 7 / 17
Ejemplo: Torres de Hanoi
El número de movimientos de discos está dado por la ecuación
an = 2an−1 + 1
a0 = 0
De acuerdo a lo anterior, la solución es
an =∑
1≤k≤n
2n−k =∑
0≤k≤n−1
2k
lo cual se simplica a
an = 2n − 1
Patricio Poblete () cc3001 Métodos Matemáticos Otoño 2012 8 / 17
Ejemplo: Torres de Hanoi
El número de movimientos de discos está dado por la ecuación
an = 2an−1 + 1
a0 = 0
De acuerdo a lo anterior, la solución es
an =∑
1≤k≤n
2n−k =∑
0≤k≤n−1
2k
lo cual se simplica a
an = 2n − 1
Patricio Poblete () cc3001 Métodos Matemáticos Otoño 2012 8 / 17
Ejercicio
Generalizar este método para resolver ecuaciones de la forma
an = bnan−1 + cn
donde bn y cn son funciones conocidas.
Patricio Poblete () cc3001 Métodos Matemáticos Otoño 2012 9 / 17
Ecuaciones lineales con coecientes constantes
Ejemplo: Fibonacci
fn = fn−1 + fn−2
f0 = 0
f1 = 1
Este tipo de ecuaciones tienen soluciones exponenciales, de la forma
fn = λn:fn = fn−1 + fn−2 ⇐⇒ λn = λn−1 + λn−2
Dividiendo ambos lados por λn−2 obtenemos la ecuación característica
λ2 − λ− 1 = 0
cuyas raíces son
φ =1 +√5
2≈ 1.618 . . . , φ =
1−√5
2≈ −0.618 . . .
Patricio Poblete () cc3001 Métodos Matemáticos Otoño 2012 10 / 17
Ecuaciones lineales con coecientes constantes
Ejemplo: Fibonacci
fn = fn−1 + fn−2
f0 = 0
f1 = 1
Este tipo de ecuaciones tienen soluciones exponenciales, de la forma
fn = λn:fn = fn−1 + fn−2 ⇐⇒ λn = λn−1 + λn−2
Dividiendo ambos lados por λn−2 obtenemos la ecuación característica
λ2 − λ− 1 = 0
cuyas raíces son
φ =1 +√5
2≈ 1.618 . . . , φ =
1−√5
2≈ −0.618 . . .
Patricio Poblete () cc3001 Métodos Matemáticos Otoño 2012 10 / 17
Ecuaciones lineales con coecientes constantes
Ejemplo: Fibonacci
fn = fn−1 + fn−2
f0 = 0
f1 = 1
Este tipo de ecuaciones tienen soluciones exponenciales, de la forma
fn = λn:fn = fn−1 + fn−2 ⇐⇒ λn = λn−1 + λn−2
Dividiendo ambos lados por λn−2 obtenemos la ecuación característica
λ2 − λ− 1 = 0
cuyas raíces son
φ =1 +√5
2≈ 1.618 . . . , φ =
1−√5
2≈ −0.618 . . .
Patricio Poblete () cc3001 Métodos Matemáticos Otoño 2012 10 / 17
Ecuaciones lineales con coecientes constantes(cont.)
La solución general se obtiene como una combinación lineal de estas
soluciones:
fn = Aφn + Bφn
La condición inicial f0 = 0 implica que B = −A, esto es,
fn = A(φn − φn)
y la condición f1 = 1 implica que
A(φ− φ) = A√5 = 1
con lo cual obtenemos nalmente la fórmula de los números de Fibonacci:
fn =1√5
(φn − φn)
Nótese que φn → 0 cuando n→∞, de modo que fn = Θ(φn).
Patricio Poblete () cc3001 Métodos Matemáticos Otoño 2012 11 / 17
Ecuaciones lineales con coecientes constantes(cont.)
La solución general se obtiene como una combinación lineal de estas
soluciones:
fn = Aφn + Bφn
La condición inicial f0 = 0 implica que B = −A, esto es,
fn = A(φn − φn)
y la condición f1 = 1 implica que
A(φ− φ) = A√5 = 1
con lo cual obtenemos nalmente la fórmula de los números de Fibonacci:
fn =1√5
(φn − φn)
Nótese que φn → 0 cuando n→∞, de modo que fn = Θ(φn).
Patricio Poblete () cc3001 Métodos Matemáticos Otoño 2012 11 / 17
Ecuaciones lineales con coecientes constantes(cont.)
La solución general se obtiene como una combinación lineal de estas
soluciones:
fn = Aφn + Bφn
La condición inicial f0 = 0 implica que B = −A, esto es,
fn = A(φn − φn)
y la condición f1 = 1 implica que
A(φ− φ) = A√5 = 1
con lo cual obtenemos nalmente la fórmula de los números de Fibonacci:
fn =1√5
(φn − φn)
Nótese que φn → 0 cuando n→∞, de modo que fn = Θ(φn).
Patricio Poblete () cc3001 Métodos Matemáticos Otoño 2012 11 / 17
Ecuaciones lineales con coecientes constantes(cont.)
La solución general se obtiene como una combinación lineal de estas
soluciones:
fn = Aφn + Bφn
La condición inicial f0 = 0 implica que B = −A, esto es,
fn = A(φn − φn)
y la condición f1 = 1 implica que
A(φ− φ) = A√5 = 1
con lo cual obtenemos nalmente la fórmula de los números de Fibonacci:
fn =1√5
(φn − φn)
Nótese que φn → 0 cuando n→∞, de modo que fn = Θ(φn).
Patricio Poblete () cc3001 Métodos Matemáticos Otoño 2012 11 / 17
Teorema Maestro
Consideremos una ecuación de la forma
T (n) = pT (n
q) + Kn
Supongamos que n es una potencia de q, digamos n = qk . Entonces
T (qk) = pT (qk−1) + Kqk
y si denimos ak = T (qk), tenemos la ecuación
ak = pak−1 + Kqk
la cual tiene solución
ak = a0pk + K
∑1≤j≤k
qjpk−j
Patricio Poblete () cc3001 Métodos Matemáticos Otoño 2012 12 / 17
Teorema Maestro
Consideremos una ecuación de la forma
T (n) = pT (n
q) + Kn
Supongamos que n es una potencia de q, digamos n = qk . Entonces
T (qk) = pT (qk−1) + Kqk
y si denimos ak = T (qk), tenemos la ecuación
ak = pak−1 + Kqk
la cual tiene solución
ak = a0pk + K
∑1≤j≤k
qjpk−j
Patricio Poblete () cc3001 Métodos Matemáticos Otoño 2012 12 / 17
Teorema Maestro
Consideremos una ecuación de la forma
T (n) = pT (n
q) + Kn
Supongamos que n es una potencia de q, digamos n = qk . Entonces
T (qk) = pT (qk−1) + Kqk
y si denimos ak = T (qk), tenemos la ecuación
ak = pak−1 + Kqk
la cual tiene solución
ak = a0pk + K
∑1≤j≤k
qjpk−j
Patricio Poblete () cc3001 Métodos Matemáticos Otoño 2012 12 / 17
Teorema Maestro (cont.)
Como k = logq n, tenemos
T (n) = T (1)plogq n + Kplogq n∑
1≤j≤logqn
(q
p)j
y observamos que
plogq n = (qlogq p)logq n = (qlogq n)logq p = nlogq p
Por lo tanto
T (n) = nlogq p(T (1) + K∑
1≤j≤logqn
(q
p)j)
Patricio Poblete () cc3001 Métodos Matemáticos Otoño 2012 13 / 17
Teorema Maestro: Caso p < q
T (n) = nlogq p(T (1) + K∑
1≤j≤logqn
(q
p)j)
En el caso p < q tenemos:
T (n) = nlogq p(T (1) + Kq
p
(qp
)logq n − 1qp− 1
)
⇒ T (n) = Θ(n)
Patricio Poblete () cc3001 Métodos Matemáticos Otoño 2012 14 / 17
Teorema Maestro: Caso p < q
T (n) = nlogq p(T (1) + K∑
1≤j≤logqn
(q
p)j)
En el caso p < q tenemos:
T (n) = nlogq p(T (1) + Kq
p
(qp
)logq n − 1qp− 1
)
⇒ T (n) = Θ(n)
Patricio Poblete () cc3001 Métodos Matemáticos Otoño 2012 14 / 17
Teorema Maestro: Caso p = q
T (n) = nlogq p(T (1) + K∑
1≤j≤logqn
(q
p)j)
En el caso p = q tenemos:
T (n) = n(T (1) + K∑
1≤j≤logqn
1)
=⇒ T (n) = Θ(n log n)
Patricio Poblete () cc3001 Métodos Matemáticos Otoño 2012 15 / 17
Teorema Maestro: Caso p = q
T (n) = nlogq p(T (1) + K∑
1≤j≤logqn
(q
p)j)
En el caso p = q tenemos:
T (n) = n(T (1) + K∑
1≤j≤logqn
1)
=⇒ T (n) = Θ(n log n)
Patricio Poblete () cc3001 Métodos Matemáticos Otoño 2012 15 / 17
Teorema Maestro: Caso p > q
T (n) = nlogq p(T (1) + K∑
1≤j≤logqn
(q
p)j)
En el caso p > q tenemos:
T (n) = nlogq p(T (1) + K∑
1≤j≤logqn
(q
p)j)
Peroq
p< 1 =⇒ T (n) ≤ nlogq n(T (1) + K
qp
1− qp
)
=⇒ T (n) = Θ(nlogq p)
Patricio Poblete () cc3001 Métodos Matemáticos Otoño 2012 16 / 17
Teorema Maestro: Caso p > q
T (n) = nlogq p(T (1) + K∑
1≤j≤logqn
(q
p)j)
En el caso p > q tenemos:
T (n) = nlogq p(T (1) + K∑
1≤j≤logqn
(q
p)j)
Peroq
p< 1 =⇒ T (n) ≤ nlogq n(T (1) + K
qp
1− qp
)
=⇒ T (n) = Θ(nlogq p)
Patricio Poblete () cc3001 Métodos Matemáticos Otoño 2012 16 / 17
Ejercicio
Estudiar la siguiente ecuación, que generaliza el Teorema Maestro:
T (n) = pT (n
q) + Knr
Patricio Poblete () cc3001 Métodos Matemáticos Otoño 2012 17 / 17