aplicaciones del análisis...
Post on 29-Aug-2020
13 Views
Preview:
TRANSCRIPT
Aplicaciones del analisis combinatorio
Laura Eslava
UNAM
25 de noviembre de 2010
Laura Eslava Analisis Combinatorio
Plan de la platica
Plantear problemas
Especificacion de clases combinatorias
Traduccion a funciones generadoras
Comportamiento asintotico
Laura Eslava Analisis Combinatorio
Analisis Combinatorio
Laura Eslava Analisis Combinatorio
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
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
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
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
Clase Combinatoria
Ejemplo:
Clase: TriangulacionesTamano: Numero de triangulos.
Laura Eslava Analisis Combinatorio
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
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
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
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
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
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
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
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
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
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
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
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
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
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
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
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
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
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
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
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
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
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
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
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
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
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
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
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
GRACIAS!
Laura Eslava Analisis Combinatorio
top related