aplicaciones del análisis...
TRANSCRIPT
![Page 1: Aplicaciones del análisis combinatoriolya.fciencias.unam.mx/computocientifico/archivos/combinatoria-seminario.pdfPatrones escondidos en texto Patrones Un patr on escondido p es una](https://reader035.vdocumento.com/reader035/viewer/2022062507/5fdf9599421ae349b96ba0d6/html5/thumbnails/1.jpg)
Aplicaciones del analisis combinatorio
Laura Eslava
UNAM
25 de noviembre de 2010
Laura Eslava Analisis Combinatorio
![Page 2: Aplicaciones del análisis combinatoriolya.fciencias.unam.mx/computocientifico/archivos/combinatoria-seminario.pdfPatrones escondidos en texto Patrones Un patr on escondido p es una](https://reader035.vdocumento.com/reader035/viewer/2022062507/5fdf9599421ae349b96ba0d6/html5/thumbnails/2.jpg)
Plan de la platica
Plantear problemas
Especificacion de clases combinatorias
Traduccion a funciones generadoras
Comportamiento asintotico
Laura Eslava Analisis Combinatorio
![Page 3: Aplicaciones del análisis combinatoriolya.fciencias.unam.mx/computocientifico/archivos/combinatoria-seminario.pdfPatrones escondidos en texto Patrones Un patr on escondido p es una](https://reader035.vdocumento.com/reader035/viewer/2022062507/5fdf9599421ae349b96ba0d6/html5/thumbnails/3.jpg)
Analisis Combinatorio
Laura Eslava Analisis Combinatorio
![Page 4: Aplicaciones del análisis combinatoriolya.fciencias.unam.mx/computocientifico/archivos/combinatoria-seminario.pdfPatrones escondidos en texto Patrones Un patr on escondido p es una](https://reader035.vdocumento.com/reader035/viewer/2022062507/5fdf9599421ae349b96ba0d6/html5/thumbnails/4.jpg)
Problemas
1 El numero de palabras binarias que no tienen mas de 4 cerosconsecutivos, ni 2 unos seguidos.
2 ¿Cual es la probabilidad de que el texto de Hamlet tenga unmensaje escondido?
3 ¿Cuantos mapeos de [1...n] a [1...n] no tienen puntos fijos?
4 ¿Cual es la probabilidad de que estos tengan r orbitas?
Laura Eslava Analisis Combinatorio
![Page 5: Aplicaciones del análisis combinatoriolya.fciencias.unam.mx/computocientifico/archivos/combinatoria-seminario.pdfPatrones escondidos en texto Patrones Un patr on escondido p es una](https://reader035.vdocumento.com/reader035/viewer/2022062507/5fdf9599421ae349b96ba0d6/html5/thumbnails/5.jpg)
Clase Combinatoria
Definicion
Una clase combinatoria A es un conjunto a lo mas numerable endonde se define una funcion Tamano que cumple
El tamano de todos los elementos es un entero no negativo.
El conjunto An de todos los elementos de tamano n de laclase es finito.
Ejemplo:
Laura Eslava Analisis Combinatorio
![Page 6: Aplicaciones del análisis combinatoriolya.fciencias.unam.mx/computocientifico/archivos/combinatoria-seminario.pdfPatrones escondidos en texto Patrones Un patr on escondido p es una](https://reader035.vdocumento.com/reader035/viewer/2022062507/5fdf9599421ae349b96ba0d6/html5/thumbnails/6.jpg)
Clase Combinatoria
Definicion
Una clase combinatoria A es un conjunto a lo mas numerable endonde se define una funcion Tamano que cumple
El tamano de todos los elementos es un entero no negativo.
El conjunto An de todos los elementos de tamano n de laclase es finito.
Ejemplo:
Clase:Arboles binarios planosTamano: Nodos con grado 2.
Laura Eslava Analisis Combinatorio
![Page 7: Aplicaciones del análisis combinatoriolya.fciencias.unam.mx/computocientifico/archivos/combinatoria-seminario.pdfPatrones escondidos en texto Patrones Un patr on escondido p es una](https://reader035.vdocumento.com/reader035/viewer/2022062507/5fdf9599421ae349b96ba0d6/html5/thumbnails/7.jpg)
Clase Combinatoria
Definicion
Una clase combinatoria A es un conjunto a lo mas numerable endonde se define una funcion Tamano que cumple
El tamano de todos los elementos es un entero no negativo.
El conjunto An de todos los elementos de tamano n de laclase es finito.
Ejemplo:
W ={E , a, b, aa, ab, ba, bb,
aaa, aab, aba, abb, baa, bab, bba, bbb,
aaaa, aaab, aaba, aabb, abaa, . . .}
Clase: Palabras binariasTamano: Longitud de la palabra.
Laura Eslava Analisis Combinatorio
![Page 8: Aplicaciones del análisis combinatoriolya.fciencias.unam.mx/computocientifico/archivos/combinatoria-seminario.pdfPatrones escondidos en texto Patrones Un patr on escondido p es una](https://reader035.vdocumento.com/reader035/viewer/2022062507/5fdf9599421ae349b96ba0d6/html5/thumbnails/8.jpg)
Clase Combinatoria
Ejemplo:
Clase: TriangulacionesTamano: Numero de triangulos.
Laura Eslava Analisis Combinatorio
![Page 9: Aplicaciones del análisis combinatoriolya.fciencias.unam.mx/computocientifico/archivos/combinatoria-seminario.pdfPatrones escondidos en texto Patrones Un patr on escondido p es una](https://reader035.vdocumento.com/reader035/viewer/2022062507/5fdf9599421ae349b96ba0d6/html5/thumbnails/9.jpg)
Funciones generadoras
La sucesion |An| = an, n ∈ N forma la cuenta sucesiva osucesion de conteo de la clase combinatoria.
Se codifica en una serie de potencias formales, que puede ser
FGO-Ordinaria:
A(z) =∑i≥1
anzn
FGE-Exponencial:
A(z) =∑i≥1
anzn
n!
Esta eleccion depende del modelo de la clase combinatoria.
Laura Eslava Analisis Combinatorio
![Page 10: Aplicaciones del análisis combinatoriolya.fciencias.unam.mx/computocientifico/archivos/combinatoria-seminario.pdfPatrones escondidos en texto Patrones Un patr on escondido p es una](https://reader035.vdocumento.com/reader035/viewer/2022062507/5fdf9599421ae349b96ba0d6/html5/thumbnails/10.jpg)
Diccionario de operaciones
Para especificar cualquier clase combinatoria tenemos:
Clase Neutra E : tiene un solo elemento de tamano cero,
E (z) = 1.
Clase Atomica Z: tiene un solo elemento de tamano 1,
Z (z) = z .
Utilizaremos que operaciones entre clases se traducen aoperaciones entre sus FG’s.
Operaciones: Uniones, producto, secuencias, ciclos, conjuntos.
Laura Eslava Analisis Combinatorio
![Page 11: Aplicaciones del análisis combinatoriolya.fciencias.unam.mx/computocientifico/archivos/combinatoria-seminario.pdfPatrones escondidos en texto Patrones Un patr on escondido p es una](https://reader035.vdocumento.com/reader035/viewer/2022062507/5fdf9599421ae349b96ba0d6/html5/thumbnails/11.jpg)
Diccionario de operaciones
Para especificar cualquier clase combinatoria tenemos:
Clase Neutra E : tiene un solo elemento de tamano cero,
E (z) = 1.
Clase Atomica Z: tiene un solo elemento de tamano 1,
Z (z) = z .
Utilizaremos que operaciones entre clases se traducen aoperaciones entre sus FG’s.
Operaciones: Uniones, producto, secuencias, ciclos, conjuntos.
Laura Eslava Analisis Combinatorio
![Page 12: Aplicaciones del análisis combinatoriolya.fciencias.unam.mx/computocientifico/archivos/combinatoria-seminario.pdfPatrones escondidos en texto Patrones Un patr on escondido p es una](https://reader035.vdocumento.com/reader035/viewer/2022062507/5fdf9599421ae349b96ba0d6/html5/thumbnails/12.jpg)
Operaciones basicas
Suma: Se considera que las clases son ajenas,
A =B ∪ CA(z) =B(z) + C (z)
Producto:A =B × C
A(z) =B(z) · C (z)
Secuencia: Es necesario que B0 = ∅,
A = Seq(B) =⋃k≥0Bk
A(z) =1
1− B(z)
Laura Eslava Analisis Combinatorio
![Page 13: Aplicaciones del análisis combinatoriolya.fciencias.unam.mx/computocientifico/archivos/combinatoria-seminario.pdfPatrones escondidos en texto Patrones Un patr on escondido p es una](https://reader035.vdocumento.com/reader035/viewer/2022062507/5fdf9599421ae349b96ba0d6/html5/thumbnails/13.jpg)
Operaciones basicas
Suma: Se considera que las clases son ajenas,
A =B ∪ CA(z) =B(z) + C (z)
Producto:A =B × C
A(z) =B(z) · C (z)
Secuencia: Es necesario que B0 = ∅,
A = Seq(B) =⋃k≥0Bk
A(z) =1
1− B(z)
Laura Eslava Analisis Combinatorio
![Page 14: Aplicaciones del análisis combinatoriolya.fciencias.unam.mx/computocientifico/archivos/combinatoria-seminario.pdfPatrones escondidos en texto Patrones Un patr on escondido p es una](https://reader035.vdocumento.com/reader035/viewer/2022062507/5fdf9599421ae349b96ba0d6/html5/thumbnails/14.jpg)
Operaciones basicas
Suma: Se considera que las clases son ajenas,
A =B ∪ CA(z) =B(z) + C (z)
Producto:A =B × C
A(z) =B(z) · C (z)
Secuencia: Es necesario que B0 = ∅,
A = Seq(B) =⋃k≥0Bk
A(z) =1
1− B(z)
Laura Eslava Analisis Combinatorio
![Page 15: Aplicaciones del análisis combinatoriolya.fciencias.unam.mx/computocientifico/archivos/combinatoria-seminario.pdfPatrones escondidos en texto Patrones Un patr on escondido p es una](https://reader035.vdocumento.com/reader035/viewer/2022062507/5fdf9599421ae349b96ba0d6/html5/thumbnails/15.jpg)
Lenguajes
Teniendo un alfabeto A con m letras:
Especificacion:L = Seq(A),
FGO:
L(z) =1
1−mz,
Cuenta sucesiva:Ln = mn.
Para m = 2 tenemos otra especificacion de L:
L = Seq(a)Seq(bSeq(a)),
Laura Eslava Analisis Combinatorio
![Page 16: Aplicaciones del análisis combinatoriolya.fciencias.unam.mx/computocientifico/archivos/combinatoria-seminario.pdfPatrones escondidos en texto Patrones Un patr on escondido p es una](https://reader035.vdocumento.com/reader035/viewer/2022062507/5fdf9599421ae349b96ba0d6/html5/thumbnails/16.jpg)
Lenguajes
Teniendo un alfabeto A con m letras:
Especificacion:L = Seq(A),
FGO:
L(z) =1
1−mz,
Cuenta sucesiva:Ln = mn.
Para m = 2 tenemos otra especificacion de L:
L = Seq(a)Seq(bSeq(a)),
Laura Eslava Analisis Combinatorio
![Page 17: Aplicaciones del análisis combinatoriolya.fciencias.unam.mx/computocientifico/archivos/combinatoria-seminario.pdfPatrones escondidos en texto Patrones Un patr on escondido p es una](https://reader035.vdocumento.com/reader035/viewer/2022062507/5fdf9599421ae349b96ba0d6/html5/thumbnails/17.jpg)
Lenguajes
Teniendo un alfabeto A con m letras:
Especificacion:L = Seq(A),
FGO:
L(z) =1
1−mz,
Cuenta sucesiva:Ln = mn.
Para m = 2 tenemos otra especificacion de L:
L = Seq(a)Seq(bSeq(a)),
Laura Eslava Analisis Combinatorio
![Page 18: Aplicaciones del análisis combinatoriolya.fciencias.unam.mx/computocientifico/archivos/combinatoria-seminario.pdfPatrones escondidos en texto Patrones Un patr on escondido p es una](https://reader035.vdocumento.com/reader035/viewer/2022062507/5fdf9599421ae349b96ba0d6/html5/thumbnails/18.jpg)
Lenguajes restringidos
Esta nos permite encontrar la clase de palabras en donde b aparecesolo k veces:
Especificacion:
L(k) = Seq(a)(bSeq(a))k
FGO:
L(k)(z) =zk
(1− z)k+1,
Cuenta sucesiva:
L(k)n =
(n
k
).
Laura Eslava Analisis Combinatorio
![Page 19: Aplicaciones del análisis combinatoriolya.fciencias.unam.mx/computocientifico/archivos/combinatoria-seminario.pdfPatrones escondidos en texto Patrones Un patr on escondido p es una](https://reader035.vdocumento.com/reader035/viewer/2022062507/5fdf9599421ae349b96ba0d6/html5/thumbnails/19.jpg)
Lenguajes restringidos
Esta nos permite encontrar la clase de palabras en donde b aparecesolo k veces:
Especificacion:
L(k) = Seq(a)(bSeq(a))k
FGO:
L(k)(z) =zk
(1− z)k+1,
Cuenta sucesiva:
L(k)n =
(n
k
).
Laura Eslava Analisis Combinatorio
![Page 20: Aplicaciones del análisis combinatoriolya.fciencias.unam.mx/computocientifico/archivos/combinatoria-seminario.pdfPatrones escondidos en texto Patrones Un patr on escondido p es una](https://reader035.vdocumento.com/reader035/viewer/2022062507/5fdf9599421ae349b96ba0d6/html5/thumbnails/20.jpg)
Patrones escondidos en texto
Patrones
Un patron escondido p es una sucesion de letras que aparecen enuna palabra:
p = p1p2 · · · pk ,
en el orden correcto pero no necesariamente contiguas.
El patron combinatoric en el texto de Hamlet.
La clase de palabras que contienen al patron escondido:
L = Seq(A \ p1)p1Seq(A \ p2)p2 · · ·Seq(A \ pk)pkSeq(A).
La clase que distingue cada uno de los patrones escondidos:
L = Seq(A)p1Seq(A)p2 · · ·Seq(A)pkSeq(A).
Laura Eslava Analisis Combinatorio
![Page 21: Aplicaciones del análisis combinatoriolya.fciencias.unam.mx/computocientifico/archivos/combinatoria-seminario.pdfPatrones escondidos en texto Patrones Un patr on escondido p es una](https://reader035.vdocumento.com/reader035/viewer/2022062507/5fdf9599421ae349b96ba0d6/html5/thumbnails/21.jpg)
Patrones escondidos en texto
Patrones
Un patron escondido p es una sucesion de letras que aparecen enuna palabra:
p = p1p2 · · · pk ,
en el orden correcto pero no necesariamente contiguas.
La clase de palabras que contienen al patron escondido:
L = Seq(A \ p1)p1Seq(A \ p2)p2 · · ·Seq(A \ pk)pkSeq(A).
La clase que distingue cada uno de los patrones escondidos:
L = Seq(A)p1Seq(A)p2 · · ·Seq(A)pkSeq(A).
Laura Eslava Analisis Combinatorio
![Page 22: Aplicaciones del análisis combinatoriolya.fciencias.unam.mx/computocientifico/archivos/combinatoria-seminario.pdfPatrones escondidos en texto Patrones Un patr on escondido p es una](https://reader035.vdocumento.com/reader035/viewer/2022062507/5fdf9599421ae349b96ba0d6/html5/thumbnails/22.jpg)
Patrones escondidos en texto
Patrones
Un patron escondido p es una sucesion de letras que aparecen enuna palabra:
p = p1p2 · · · pk ,
en el orden correcto pero no necesariamente contiguas.
La clase de palabras que contienen al patron escondido:
L = Seq(A \ p1)p1Seq(A \ p2)p2 · · ·Seq(A \ pk)pkSeq(A).
La clase que distingue cada uno de los patrones escondidos:
L = Seq(A)p1Seq(A)p2 · · ·Seq(A)pkSeq(A).
Laura Eslava Analisis Combinatorio
![Page 23: Aplicaciones del análisis combinatoriolya.fciencias.unam.mx/computocientifico/archivos/combinatoria-seminario.pdfPatrones escondidos en texto Patrones Un patr on escondido p es una](https://reader035.vdocumento.com/reader035/viewer/2022062507/5fdf9599421ae349b96ba0d6/html5/thumbnails/23.jpg)
Mensajes subliminales
Para saber si en Hamlet hay un mensaje subliminal para estudiarcombinatorics:
Buscamos la probabilidad de que un texto de longitudn = 120057, con alfabeto de 26 letras...
tenga en total 1,63× 1039 patrones escondidos de longitudk = 13...
Finalmente, el texto de Hamlet tiene 23 veces mas patronesde lo esperado!!!
Haciendo un analisis mas refinado de la distribucion de la letras, elerror se reduce al 5 %.
Laura Eslava Analisis Combinatorio
![Page 24: Aplicaciones del análisis combinatoriolya.fciencias.unam.mx/computocientifico/archivos/combinatoria-seminario.pdfPatrones escondidos en texto Patrones Un patr on escondido p es una](https://reader035.vdocumento.com/reader035/viewer/2022062507/5fdf9599421ae349b96ba0d6/html5/thumbnails/24.jpg)
Mensajes subliminales
Para saber si en Hamlet hay un mensaje subliminal para estudiarcombinatorics:
Buscamos la probabilidad de que un texto de longitudn = 120057, con alfabeto de 26 letras...
tenga en total 1,63× 1039 patrones escondidos de longitudk = 13...
Finalmente, el texto de Hamlet tiene 23 veces mas patronesde lo esperado!!!
Haciendo un analisis mas refinado de la distribucion de la letras, elerror se reduce al 5 %.
Laura Eslava Analisis Combinatorio
![Page 25: Aplicaciones del análisis combinatoriolya.fciencias.unam.mx/computocientifico/archivos/combinatoria-seminario.pdfPatrones escondidos en texto Patrones Un patr on escondido p es una](https://reader035.vdocumento.com/reader035/viewer/2022062507/5fdf9599421ae349b96ba0d6/html5/thumbnails/25.jpg)
Mensajes subliminales
Para saber si en Hamlet hay un mensaje subliminal para estudiarcombinatorics:
Buscamos la probabilidad de que un texto de longitudn = 120057, con alfabeto de 26 letras...
tenga en total 1,63× 1039 patrones escondidos de longitudk = 13...
Finalmente, el texto de Hamlet tiene 23 veces mas patronesde lo esperado!!!
Haciendo un analisis mas refinado de la distribucion de la letras, elerror se reduce al 5 %.
Laura Eslava Analisis Combinatorio
![Page 26: Aplicaciones del análisis combinatoriolya.fciencias.unam.mx/computocientifico/archivos/combinatoria-seminario.pdfPatrones escondidos en texto Patrones Un patr on escondido p es una](https://reader035.vdocumento.com/reader035/viewer/2022062507/5fdf9599421ae349b96ba0d6/html5/thumbnails/26.jpg)
Mensajes subliminales
Para saber si en Hamlet hay un mensaje subliminal para estudiarcombinatorics:
Buscamos la probabilidad de que un texto de longitudn = 120057, con alfabeto de 26 letras...
tenga en total 1,63× 1039 patrones escondidos de longitudk = 13...
Finalmente, el texto de Hamlet tiene 23 veces mas patronesde lo esperado!!!
Haciendo un analisis mas refinado de la distribucion de la letras, elerror se reduce al 5 %.
Laura Eslava Analisis Combinatorio
![Page 27: Aplicaciones del análisis combinatoriolya.fciencias.unam.mx/computocientifico/archivos/combinatoria-seminario.pdfPatrones escondidos en texto Patrones Un patr on escondido p es una](https://reader035.vdocumento.com/reader035/viewer/2022062507/5fdf9599421ae349b96ba0d6/html5/thumbnails/27.jpg)
Mensajes subliminales
Para saber si en Hamlet hay un mensaje subliminal para estudiarcombinatorics:
Buscamos la probabilidad de que un texto de longitudn = 120057, con alfabeto de 26 letras...
tenga en total 1,63× 1039 patrones escondidos de longitudk = 13...
Finalmente, el texto de Hamlet tiene 23 veces mas patronesde lo esperado!!!
Haciendo un analisis mas refinado de la distribucion de la letras, elerror se reduce al 5 %.
Laura Eslava Analisis Combinatorio
![Page 28: Aplicaciones del análisis combinatoriolya.fciencias.unam.mx/computocientifico/archivos/combinatoria-seminario.pdfPatrones escondidos en texto Patrones Un patr on escondido p es una](https://reader035.vdocumento.com/reader035/viewer/2022062507/5fdf9599421ae349b96ba0d6/html5/thumbnails/28.jpg)
Factores
Un factor p es una sucesion de letras que aparecen en una palabra:
p = p1p2 · · · pk ,
en el orden correcto y necesariamente contiguas.
Teorema (de Borges)
Toma cualquier conjunto finito de patrones y un texto aleatorio delongitud n.La probabilidad de que el texto contenga todos los patrones tiendeexponencialmente rapido a 1, conforme n→∞.
Laura Eslava Analisis Combinatorio
![Page 29: Aplicaciones del análisis combinatoriolya.fciencias.unam.mx/computocientifico/archivos/combinatoria-seminario.pdfPatrones escondidos en texto Patrones Un patr on escondido p es una](https://reader035.vdocumento.com/reader035/viewer/2022062507/5fdf9599421ae349b96ba0d6/html5/thumbnails/29.jpg)
La biblioteca de Babel
La biblioteca era tan grande que contenıa...
Todo: la historia minuciosa del porvenir, las autobiografıas de losarcangeles, el catalogo fiel de la Biblioteca, miles y miles decatalogos falsos, la demostracion de la falacia de esos catalogos, lademostracion de la falacia del catalogo verdadero, el evangeliognostico de Basilides, el comentario de ese evangelio, el comentariodel comentario de ese evangelio, la relacion verıdica de tu muerte,la version de cada libro a todas las lenguas, las interpolaciones decada libro en todos los libros,...
La biblioteca de Babel, (fragmento.)
Laura Eslava Analisis Combinatorio
![Page 30: Aplicaciones del análisis combinatoriolya.fciencias.unam.mx/computocientifico/archivos/combinatoria-seminario.pdfPatrones escondidos en texto Patrones Un patr on escondido p es una](https://reader035.vdocumento.com/reader035/viewer/2022062507/5fdf9599421ae349b96ba0d6/html5/thumbnails/30.jpg)
Permutaciones
Esta clase se define en el universo etiquetado
Las permutaciones estan completamente determinadas por suciclos.
P = Seq(Z) = Set(Cyc(Z))
P(z) =1
1− z
Laura Eslava Analisis Combinatorio
![Page 31: Aplicaciones del análisis combinatoriolya.fciencias.unam.mx/computocientifico/archivos/combinatoria-seminario.pdfPatrones escondidos en texto Patrones Un patr on escondido p es una](https://reader035.vdocumento.com/reader035/viewer/2022062507/5fdf9599421ae349b96ba0d6/html5/thumbnails/31.jpg)
Mapeos de [1 . . . n]→ [1 . . . n]
Dado un mapeo f , se construye una grafica donde
i → jsi y solo sif (i) = j
G es la clase dearboles no planos.
F = Set(Cyc(G)).
Un marcador µ se usa para contar nuevos parametros, como elnumero de orbitas,
F = Set(µCyc(G)).
Laura Eslava Analisis Combinatorio
![Page 32: Aplicaciones del análisis combinatoriolya.fciencias.unam.mx/computocientifico/archivos/combinatoria-seminario.pdfPatrones escondidos en texto Patrones Un patr on escondido p es una](https://reader035.vdocumento.com/reader035/viewer/2022062507/5fdf9599421ae349b96ba0d6/html5/thumbnails/32.jpg)
Mapeos de [1 . . . n]→ [1 . . . n]
Dado un mapeo f , se construye una grafica donde
i → jsi y solo sif (i) = j
G es la clase dearboles no planos.
F = Set(Cyc(G)).
Un marcador µ se usa para contar nuevos parametros, como elnumero de orbitas,
F = Set(µCyc(G)).
Laura Eslava Analisis Combinatorio
![Page 33: Aplicaciones del análisis combinatoriolya.fciencias.unam.mx/computocientifico/archivos/combinatoria-seminario.pdfPatrones escondidos en texto Patrones Un patr on escondido p es una](https://reader035.vdocumento.com/reader035/viewer/2022062507/5fdf9599421ae349b96ba0d6/html5/thumbnails/33.jpg)
Comportamiento Asintotico
La singularidaddominante z0 de unafuncion es la de menornorma.
El creciemiento asintotico de una cuenta sucesiva se expresa con
un factor exponencial An,determinado por la posicion de la singularidad dominante.
un factor subexponencial Θ(n),determinado por la naturaleza de la singularidad.
Laura Eslava Analisis Combinatorio
![Page 34: Aplicaciones del análisis combinatoriolya.fciencias.unam.mx/computocientifico/archivos/combinatoria-seminario.pdfPatrones escondidos en texto Patrones Un patr on escondido p es una](https://reader035.vdocumento.com/reader035/viewer/2022062507/5fdf9599421ae349b96ba0d6/html5/thumbnails/34.jpg)
Comportamiento Asıntotico: Triangulaciones
Especificacion Recursiva
T (z) = 1−√1−4z2 ,
Factor Exponencial(1
z0
)n
,
Factor Subexponencial
O(n3/2).
Tn ∼4n−1√π√
n3
Laura Eslava Analisis Combinatorio
![Page 35: Aplicaciones del análisis combinatoriolya.fciencias.unam.mx/computocientifico/archivos/combinatoria-seminario.pdfPatrones escondidos en texto Patrones Un patr on escondido p es una](https://reader035.vdocumento.com/reader035/viewer/2022062507/5fdf9599421ae349b96ba0d6/html5/thumbnails/35.jpg)
Conclusiones
El metodo simbolico:
Ofrece un lenguaje universal para modelar clasescombinatorias,
Distintos modelos de una clase permiten estudiar distintascaracterısticas de ella.
Las funciones generadoras:
guardan la informacion de la cuenta sucesiva y
simplifican el calculo de probabilidades en modelos discretos.
Se puede utilizar herramienta de analisis complejo,
para estudiar el comportamiento asintotico de la cuentasucesiva.
Laura Eslava Analisis Combinatorio
![Page 36: Aplicaciones del análisis combinatoriolya.fciencias.unam.mx/computocientifico/archivos/combinatoria-seminario.pdfPatrones escondidos en texto Patrones Un patr on escondido p es una](https://reader035.vdocumento.com/reader035/viewer/2022062507/5fdf9599421ae349b96ba0d6/html5/thumbnails/36.jpg)
Conclusiones
El metodo simbolico:
Ofrece un lenguaje universal para modelar clasescombinatorias,
Distintos modelos de una clase permiten estudiar distintascaracterısticas de ella.
Las funciones generadoras:
guardan la informacion de la cuenta sucesiva y
simplifican el calculo de probabilidades en modelos discretos.
Se puede utilizar herramienta de analisis complejo,
para estudiar el comportamiento asintotico de la cuentasucesiva.
Laura Eslava Analisis Combinatorio
![Page 37: Aplicaciones del análisis combinatoriolya.fciencias.unam.mx/computocientifico/archivos/combinatoria-seminario.pdfPatrones escondidos en texto Patrones Un patr on escondido p es una](https://reader035.vdocumento.com/reader035/viewer/2022062507/5fdf9599421ae349b96ba0d6/html5/thumbnails/37.jpg)
GRACIAS!
Laura Eslava Analisis Combinatorio