Algunas funciones y sumatorias
G. M. Luna: \Analisis y dise~no de algoritmos"
1
~ DE ALGORITMOS ANALISIS Y DISENO Algunas funciones y sumatorias Guillermo Morales-Luna Seccion de Computacion CINVESTAV-IPN
[email protected]
Mexico, D.F., a 22 de enero de 2001. CONTENIDO Algunas funciones Sumatorias
Algunas funciones y sumatorias
G. M. Luna: \Analisis y dise~no de algoritmos"
Algunas funciones f es monotona si es creciente o decreciente. Es creciente si: 8n0 n1 : (n1 n2 ) f (n1) f (n2)): Es decreciente si: 8n0 n1 : (n1 n2 ) f (n1) f (n2)):
Pisos y techos 8x 2 IR: bxc
= el mayor entero que no supera a x, dxe = el menor entero que no esta por debajo de x, x 7! bxc y x 7! dxe son \piso" y \techo".
2
Algunas funciones y sumatorias
Polinomios En una variable: p(n) =
G. M. Luna: \Analisis y dise~no de algoritmos"
3
Xm aini. i=0
m es el grado del polinomio, @p, a0 : : : am son los coecientes del polinomio. am, es el coe ciente principal. En varias variables: p(n) =
Xm aini, A IN k conjunto nito i2A
si n = (n1 : : : nk ) e i = (i1 : : : ik ), entonces
ni
k Y = nij . j =1
j
Consideraremos solo polinomios de una variable. Grado 1: lineales. Grado 2: cuadraticos. Grado 3 cubicos.
Algunas funciones y sumatorias
G. M. Luna: \Analisis y dise~no de algoritmos"
Para cualesquiera dos p1 p1: p1 (n) = O(p2 (n)) p1 (n) = (p2 (n)) p1 (n) = o(p2 (n))
nO(1) =
m0
@p1 @p2 , @p1 = @p2 , @p1 < @p2 : O(nm): clase de fun'es acotadas polinomialmente.
Potencias
y 8n 2 IN : an+1 = an a: Si n1 = ;n con n 2 IN , an1 = a1n . p Si a > 0, 8 pq 2 QI , con q > 0, a q = x donde x es tal que xq = ap. Por continuidad, queda de nido az 8z 2 IR. 8a 6= 0: a0 = 1
,
4
Algunas funciones y sumatorias
G. M. Luna: \Analisis y dise~no de algoritmos"
Reglas de las potencias:
an am = an+m (an)m = anm
8> 0 < 8a > 0 an ;! n!+1 > 1 :
1
8m,
5
si a < 1 si a = 1 si a > 1
m
n = 0 y nm = o(an). lim n!+1 an
Si a > 0 y f (n) = nO(1), f (n) = o(an ): cualquier potencia \crece mas rapido que una funcion acotada polinomialmente". 1 n Base de los logaritmos naturales: e = n!lim 1+ n , +1 aprox. e = 2:7182818284590452354 : : : Para nes de calculo X xm = 1 + x + x2 + x3 + x4 +
ex = (1) m ! 2 6 24 m0
Algunas funciones y sumatorias
G. M. Luna: \Analisis y dise~no de algoritmos"
Logaritmos Para a > 0,
logaritmo en base a de x > 0: loga x = y 2 IR con ay = x. loga (xy) = loga x + loga y loga (xy ) = y loga x ax logb x = log loga b Logaritmo natural: x 7! ln x = loge x. Para nes de calculo
ln(1 + x) =
(2)
X (;1)1+m xm = x ; x2 + x3 ; x4 + x5 ; x6 (3) m
m1
(loga n)m
2
(loga n)m
3
4
5
m n = an11 n! ;! 0, i.e. +1
6
Con n1 = loga n: n = aloga n (loga n)m = o(n). (loga n)O(1) = O((loga n)m): acotadas \polilogartmicamente". m0
6
Algunas funciones y sumatorias
G. M. Luna: \Analisis y dise~no de algoritmos"
Factoriales Recursivamente: 0! = 1 y 8n 2 IN : (n + 1)! = n! (n + 1): ; p ; p ; n n p ; n ; 1 + n y 2 n ne n n! 2 n e n! = 2 n ne 1
1 1 + 12 n
n! = o(nn ), n! = !(2n) y log(n!) = (n log n):
7
:
Sucesion de Fibonacci Recursivamente, F0 = 0
F1 = 1
,
y
8n 2 IN
: Fn+2 = Fn+1 + Fn :
Razones doradas p : 1+ = 2p5 = 1:6180339887498948482 : : : = 1;2 5 = ;0:6180339887498948482 : : :
b
Fn = p+5b y Fn = EnteroMasProximo La sucesion crece exponencialmente. 8n :
n
n
Algunas funciones y sumatorias
pn . 5
G. M. Luna: \Analisis y dise~no de algoritmos"
Funciones iteradas Sea f : IR+ ! IR creciente, con f (n) < n 8n. 8< n si m = 0, Composicion de f : f (m) : n 7! : (m;1) f (f (n)) si m > 0. Para c 2 IR 8 1:
1
Xn 1 = k + (1 ; k) i=1
ik
i=1
1
i
nk;1 + O(1).
14
Algunas funciones y sumatorias
G. M. Luna: \Analisis y dise~no de algoritmos"
Productos log (Qni=1 ai) = Pni=1 log (ai) : Acotamiento de sumas
15
Acotamiento termino a termino
A = (a1 : : : an ) 2 (IR+)n , B = (b1 : : : bn ), 8i n : ai bi :
Xn ai Xn bi. i=1
i=1 A = (ai )i1 , B = (bi )i1 ,
X ai X bi.
Pi1 bi < +1 y 8i : ai bi:
i1
i1 Si B = (bi )i1 domina a la larga a A, 9i0 8i 0 : ai bi , entonces i0 ai ai + bi . i=1 i1 ii0 +1
X
X
X
Algunas funciones y sumatorias
G. M. Luna: \Analisis y dise~no de algoritmos"
Acotamiento por razones menores que 1 Sea a
A = (ai )i1 t.q. 9r 2]0 18i : ai+1i X ai a0 1 . 8i : ai a0 ri y 1;r
r, entonces
i1
Aproximacion por integrales Sea A = (ai)i1, con ai = f (i), f integrable. Entonces,
Zn
.
m;1
f (x)dx
Xn Z n+1 f (x)dx
i=m;1
m
16