Fundamente de la informatica

Fundamentos de Inform´tica II
a
ILI-153
Horst H. von Brand
2º Semestre 2011

pgflastimage

Resumen
Este documento representa los apuntes de las clases de Fundamentos de Inform´tica II, dictadas durante
a
los segundos semestres de 2008, 2009, 2010 y 2011 en la casa central de la Universidad T´cnica Federico Santa
e
Mar´ por el autor. El contenido de este curso (como lo indica elnombre) es la culminaci´n de lo cubierto en
ıa
o
Fundamentos de Inform´tica I. Hay material adicional en estos apuntes, que no se vio en clase.
a

1.

Funciones generatrices

En lo que sigue veremos c´mo usar series de potencias (una herramienta del an´lisis, vale decir matem´ticas de
o
a
a
lo continuo) para resolver una variedad de problemas discretos. La idea de funciones generatricespermite resolver
muchos problemas de forma simple y transparente. Incluso cuando no da soluciones puede iluminar, indicando
relaciones entre problemas que a primera vista no son obvias. El aplicar herramientas anal´
ıticas (especialmente la
teor´ de funciones de variables complejas) permite deducir resultados que de otra forma ser´ muy dif´
ıa
ıan
ıciles de
obtener.
Nos centramos enaplicaciones y en aplicaciones de las t´cnicas discutidas m´s que en exponer la teor´ nuestros
e
a
ıa,
ejemplos frecuentemente llevan a resultados de inter´s independiente. Para detalles de la teor´ y aplicaciones
e
ıa
adicionales v´anse [?, ?].
e
∞
Sea una secuencia an 0 = a0 , a1 , a2 , . . . , an , . . . . La funci´n generatriz (ordinaria) de la secuencia es la serie
o
de potencias:
anxn

A(x) =
0≤n

El punto es que la serie representa en forma compacta y manejable la secuencia infinita. Como veremos, en muchos
casos resulta bastante m´s sencillo manipular la serie que trabajar directamente con la secuencia. Para el caso
a
especial de secuencias de enteros, un recurso indispensable es la enciclopedia de secuencias [?], que registra muchos
miles de secuencias, c´mo segeneran y da referencias al respecto.
o
Para un primer ejemplo, volveremos al problema de la Competencia de Ensayos de la Universidad de Miskatonic,
que llev´ a la relaci´n:
o
o
b2r+1 = b2r−1 + r + 1

b1 = 1

con lo que tenemos, como antes (arbitrariamente dando el valor cero a los que no quedan definidos por la recurrencia):
bn

∞
0

= 0, 1, 0, 3, 0, 6, 0, 10, 0, 15, . . .

Contarcon algunos valores sirve para verificar (y para “sentir” c´mo se comportan).
o
Definamos la serie:
b2r+1 xr

B ( x) =
r ≥0

Si multiplicamos nuestra recurrencia por xr y sumamos sobre r ≥ 1 queda:
b2r+1 xr =
r ≥1

b2r−1 xr +
r ≥1

(r + 1)xr
r ≥1

Expresando lo anterior en t´rminos de B (x), reconocemos:
e
b2r+1 xr =
r ≥1

b2r+1 xr − b1
r ≥0

= B (x) − 1
b2r−1 xr =
r ≥1b2r+1 xr+1
r ≥0

b2r+1 xr

=x
r ≥0

= xB (x)
En nuestra ecuaci´n aparecen t´rminos (r + 1)xr , que sugieren la derivada de xr+1 . Por el otro lado, sabemos que
o
e
para |x| < 1 vale la serie geom´trica:
e
1
=
1−x

xr
r ≥0

Derivando la serie geom´trica respecto de x t´rmino a t´rmino, lo que es v´lido dentro de su radio de convergencia,
e
e
e
a
queda:
d
dx

1
1−x=
r ≥0

1
=
(1 − x)2

dr
x
dx
rxr−1

r ≥1

(r + 1)xr

=
r ≥0

Tambi´n:
e
(r + 1)xr =
r ≥1

(r + 1)xr − 1
r ≥0

Uniendo las anteriores queda:
B (x) − 1 = xB (x) +

1
−1
(1 − x)2

Despejando B (x):
B (x) =

1
(1 − x)3

Conociendo la funci´n B (x), de cierta forma sabemos los valores b2r+1 que interesan.
o
Para algunas aplicaciones basta llegar hasta ac´,puede extraerse bastante informaci´n sobre los coeficientes de
a
o
la funci´n. Por ejemplo, claramente la serie en este caso converge para −1 < x < 1, y por la prueba de la raz´n,
o
o
sabemos que
l´
ım

r →∞

b2r+1
=1
b2r+3

2

Pero interesa obtener una f´rmula expl´
o
ıcita (ojal´ simple) para los coeficientes, de forma de poder determinar el
a
tama˜o requerido de las...