View
223
Download
0
Embed Size (px)
Citation preview
1
Fundamentos Informática II
Funciones Generatrices
Universidad Técnica Federico Santa MaríaDepartamento de Informática
2
Funciones Generatrices : Motivación Definición y Ejemplos Técnicas de Cálculo Metodología Ejemplos Ecuaciones Lineales Enteras Particiones de Enteros Función Generatriz Exponencial (Ejemplo) Operador de Suma (Ejemplo)
3
Repartición de Naranjas:(Ecuaciones Lineales Enteras)
De cuántas formas posibles se pueden
repartir 12 naranjas de manera que
Gabriel (G) reciba al menos 4 y María
(M) y Francisco (F) reciban al menos 2.
Motivación 1:Funciones Generatrices :
4
Buscamos la cantidad total de soluciones de la ecuación:
x1 + x2 + x3 = 12
4 ≤ x1 ≤ 8
2 ≤ x2 ≤ 6
2 ≤ x3 ≤ 6
Funciones Generatrices :
(Ecuaciones Lineales Enteras)Motivación: Repartición de Naranjas
Donde: xk : cantidad de
naranjas dela persona k
5
Motivación: Repartición de Naranjas
Funciones Generatrices :
G
M
F
4 4 4 4 4 5 5 5 5 6 6 6 7 7 8
2 3 4 5 6 2 3 4 5 2 3 4 3 2 2
6 5 4 3 2 5 4 3 2 4 3 2 2 3 2
Cantidad Total de Formas de Repartir: 15
(Ecuaciones Lineales Enteras)
6
Idea: (Euler & DeMoivre) Contar Formas de Repartir como Producto de Polinomios !
(x4+x5+x6+x7+x8)(x2+x3+x4+x5+x6) (x2+x3+x4+x5+x6) =
= ∑ αkxk
= ∑ αkxk + 15 x12 ≈ x8 ∑ xk
Funciones Generatrices :Motivación: Repartición de Naranjas
k=8
20
20
k=8k≠15
Cantidad Total de Formas de Repartir
(Ecuaciones Lineales Enteras)
k ≥ 0
Dem !
7
De cuantas maneras podemos
seleccionar r objetos de n con
repeticiones ???
Cantidad total de soluciones enteras de
la ecuación: (solución más adelante …)
x1 + x2 + x3 + ··· + xn-1 + xn = r
Motivación 2: Sist. Ecs. Enteras
Funciones Generatrices :
8
(x4+x5+x6+x7+x8)(x2+x3+x4+x5+x6) (x2+x3+x4+x5+x6)
Por convolucion: En Matlab o Scilab:
conv([1 1 1 1 1 0 0 0 0], [1 1 1 1 1 0 0 ])
conv(ans, [1 1 1 1 1 0 0 ])
ans(20-12+1)
Formas de solucion:Funciones Generatrices :
9
(x4+x5+x6+x7+x8)(x2+x3+x4+x5+x6) (x2+x3+x4+x5+x6)
Por fuerza bruta:
Formas de solucion:Funciones Generatrices :
contador=0;for x1=4:8, for x2=2:6, for x3=2:6, if (x1+x2+x3)==12 contador=contador+1; end end endend
10
(x4+x5+x6+x7+x8)(x2+x3+x4+x5+x6) (x2+x3+x4+x5+x6)
Midiendo tiempos de ejecución En Matlab:
tic toc
Formas de solucion:Funciones Generatrices :
11
(x4+x5+x6+x7+x8)(x2+x3+x4+x5+x6) (x2+x3+x4+x5+x6)
Midiendo tiempos de ejecución En C:
La forma de calcular el tiempo de CPU que toma una función es muy simple:
tomamos el valor del reloj antes de realizar la llamada (t_ini),
llamamos a la rutina en cuestión, y
tomamos nuevamente el valor del reloj (t_fin).
La diferencia entre t_fin - t_ini nos da el total de tiempo que tomó: 1) hacer la llamada a la rutina, 2) que esta haga su trabajo, 3) que devuelva el resultado.
Formas de solucion:Funciones Generatrices :
12
(x4+x5+x6+x7+x8)(x2+x3+x4+x5+x6) (x2+x3+x4+x5+x6)
Midiendo tiempos de ejecucion en C Para tomar el tiempo podemos usar la rutina clock(), que devuelve el
tiempo aproximado de CPU que transcurrió desde que nuestro programa
fue iniciado, dicho tiempo representado en un valor de tipo clock_t: un valor
entero que indica una cantidad de "tics" de reloj.
La precisión que tenemos con dicha rutina es de CLOCKS_PER_SEC (tics
de reloj por segundo), lo que significa que por cada segundo que pasa, la
función clock() nos devolverá CLOCKS_PER_SEC unidades más que el
valor anterior. En MinGW, CLOCKS_PER_SEC es igual a 1000, pero es
mejor no fiarse de esto, ya que en otras plataformas dicho valor varía.
Inclusive, según POSIX, la constante CLOCKS_PER_SEC debería ser
1000000.
Formas de solución:Funciones Generatrices :
13
(x4+x5+x6+x7+x8)(x2+x3+x4+x5+x6) (x2+x3+x4+x5+x6)
Formas de solución:Funciones Generatrices :
#include <stdio.h>#include <time.h>
int main(int argc, char *argv[]){ clock_t t_ini, t_fin; double secs;
t_ini = clock(); /* ...hacer algo... */ t_fin = clock();
secs = (double)(t_fin - t_ini) / CLOCKS_PER_SEC; printf("%.16g milisegundos\n", secs * 1000.0); return 0;}
14
Dada una secuencia de números reales a0, a1, ... ,an ,... la función definida por:
G(x) = ∑ akxk
Se denomina Función Generatriz asociada a la secuencia a0, a1 ,... ,an ,...
Definición y Ejemplos:
Funciones Generatrices :
∞
k = 0
15
Si aK = 1 para todo k є N
G1(x) = ∑ xk = (1 – x )-1
Si aK = para k = 0,…,n
Ejemplos y Técnicas de Cálculo:
Funciones Generatrices :
∞
k = 0
(1 + x ) n= ∑n
nk
xk =
nk
G2(x)
k = 0
16
Si aK = 1 para k = 0,…,n
G3(x) = ∑ xk = (1 – xn+1 )/(1 – x )
Como:
G1'(x) = ∑ (k+1)xk = (1 – x )-2
Entonces aK = (k+1) para k = 0,1,2,…
Técnicas de Cálculo:Funciones Generatrices :
k = 0
k = 0
n
∞
17
Como:
G4(x) = xG1'(x) = ∑ kxk = x /(1 – x )2
Entonces aK = k para k = 0,1,2,…
Como:
G5(x) = xG4'(x) = ∑ k2xk = x(x+1)/(1 – x )3
Entonces aK = k2 para k = 0,1,2,…
Técnicas de Cálculo:Funciones Generatrices :
k = 0
∞
∞
k = 0
18
Por Desarrollo de Maclaurin:
G6(x) = ∑(-1)k xk = (1+x )-n
Entonces 1/(1+x )n es la función generatriz de la secuencia:
aK = (-1)k = (-1)kC(n+k-1,k) k = 0,1,2,…
Técnicas de Cálculo:Funciones Generatrices :
k = 0
∞n+k-1
k
n+k-1k
19
Demostrar que: (Ejercicio)
G7(x) = ∑ xk = (1-x )-n
Entonces 1/(1-x )n es la función generatriz de la secuencia:
aK = = C(n+k-1,k) para k = 0,1,2,…
Técnicas de Cálculo:Funciones Generatrices :
k = 0
∞n+k-1
k
n+k-1k
20
Teorema: El número de selecciones, con repetición, de tamaño 1 r n de una colección de n objetos indistingibles y el número de soluciones enteras de la ecuación :
x1 + x2 + x3 + ... + xn = r
es C(n+r-1,r)
Combinaciones con Repetición yEcuaciones Lineales Enteras
Funciones Generatrices :
21
Demostración:
La función generatriz del problema es:
G(x) = (1+x+x2+x3+ ... )n = (1-x)-n
Buscamos el p-ésimo coeficiente
que es C(n+r-1,r) (recordar G7)
Funciones Generatrices :Combinaciones con Repetición yEcuaciones Lineales Enteras
22
a) Se modela el problema de enumeración como un producto de polinomios.
b) Se opera el producto de polinomios obtenido mediante las Técnicas de Cálculo vistas.
c) Se obtiene una combinación de funciones generatrices conocidas
d) Se obtiene el coeficiente del polinomio de la función generatriz que se busca
Metodología:Funciones Generatrices :
23
a) Obtener la función generatriz de la secuencia: 0, 2, 6, 12, 20, …
b) Resolver la ecuación lineal entera:x1 + x2 = 13
2 ≤ x1 ≤ 10
3 ≤ x2 ≤ 11c) Obtener el coeficiente de x5 en (1-2x)-7
d) Obtener el coeficiente de x8 en:
G(x) = [(x-3)(x-2)2]-1
Ejemplos:Funciones Generatrices :
24
Sea la función natural que entrega la cantidad total de formas de obtener n como una suma de naturales.
Buscamos obtener p(n) en función de n
Entonces:
p(n) = ∏1/(1-xk)
p(n=0) = 1
Particiones de Enteros
Funciones Generatrices :
k=0
n
25
Dada una secuencia de números reales a0, a1, ... ,an ,... la función definida por:
GE (x) = ∑ akxk / k!
Se denomina Función Generatriz Exponencial asociada a la secuencia a0, a1 ,... ,an ,...
Función Generatriz Exponencial:
Funciones Generatrices :
∞
k = 0
26
Un barco lleva 48 banderas, 12 de cada uno de los colores: rojo, blanco azul y negro. Doce (12) banderas, una señal, están puesta en un mástil para comunicación visual con otros barcos.
a) Cuántas señales tienen un número impar de banderas azules y un número par de banderas negras ?
b) Cuántas señales tienen al menos 3 banderas blancas o no tienen banderas blancas ?
F. G. Exponencial: EjemploFunciones Generatrices :
27
Dada una secuencia de números reales a0, a1, ... ,an ,... consideremos la función:
G(x) = ∑ akxk
Luego: G(x)/(1-x) = ∑ akxk ∑ xk
= ∑ ∑ akxk
Operador de Suma:Funciones Generatrices :
∞
k = 0
k = 0 k = 0
∞ ∞
n = 0 k = 0
∞ n
28
Encuentre una fórmula en función de n para expresar la secuencia:
an = ∑ i2
Encuentre la función generatriz de la
secuencia:
an = ∑ (1/i!)
Operador de Suma: Ejemplos
Funciones Generatrices :
i = 0
n
i = 0
n