Combinatoria : nuevas tendencias e interacciones

Algoritmos aleatorios Teor´ıa de nudos : ADN Combinatoria : nuevas tendencias e interacciones J. Ram´ırez Alfons´ın Universit´ e Montpellier 2, Fran

3 downloads 165 Views 2MB Size

Story Transcript

Algoritmos aleatorios

Teor´ıa de nudos : ADN

Combinatoria : nuevas tendencias e interacciones J. Ram´ırez Alfons´ın Universit´ e Montpellier 2, Francia

ITAM, M´exico, D.F. 24 de Enero de 2013

J. Ram´ırez Alfons´ın Combinatoria : nuevas tendencias e interacciones

UM2

Algoritmos aleatorios

Teor´ıa de nudos : ADN

1 Algoritmos aleatorios

2 Teor´ıa de nudos : ADN

J. Ram´ırez Alfons´ın Combinatoria : nuevas tendencias e interacciones

UM2

Algoritmos aleatorios

Teor´ıa de nudos : ADN

Algoritmos aleatorios

J. Ram´ırez Alfons´ın Combinatoria : nuevas tendencias e interacciones

UM2

Algoritmos aleatorios

Teor´ıa de nudos : ADN

M´ etodo de Buffon d d d d

2d

d d

J. Ram´ırez Alfons´ın Combinatoria : nuevas tendencias e interacciones

UM2

Algoritmos aleatorios

Teor´ıa de nudos : ADN

M´ etodo de Buffon d d d d

2d

d d

Prob(la aguja toca una de las lineas) = π1 ·

J. Ram´ırez Alfons´ın Combinatoria : nuevas tendencias e interacciones

UM2

Algoritmos aleatorios

Teor´ıa de nudos : ADN

M´ etodo de Buffon d d d d

2d

d d

Prob(la aguja toca una de las lineas) = π1 · Repitiendo este experimento y reteniendo el n´ umero de casos cuando la aguja toca una linea, podemos obtener una aproximaci´on de π. J. Ram´ırez Alfons´ın Combinatoria : nuevas tendencias e interacciones

UM2

Algoritmos aleatorios

Teor´ıa de nudos : ADN

Probleme de matrimonios F = {f1 , . . . , fn } un conjunto de n mujeres. G = {g1 , . . . , gn } un conjunto de n hombres. Cada mujer fi hace una lista de hombres preferidos (del conjunto G ) con los que le gustar´ıa casarse.

J. Ram´ırez Alfons´ın Combinatoria : nuevas tendencias e interacciones

UM2

Algoritmos aleatorios

Teor´ıa de nudos : ADN

Probleme de matrimonios F = {f1 , . . . , fn } un conjunto de n mujeres. G = {g1 , . . . , gn } un conjunto de n hombres. Cada mujer fi hace una lista de hombres preferidos (del conjunto G ) con los que le gustar´ıa casarse. Pregunta : ¿Es posible cada mujer se case con un de los hombres que ella prefiera ?

J. Ram´ırez Alfons´ın Combinatoria : nuevas tendencias e interacciones

UM2

Algoritmos aleatorios

Teor´ıa de nudos : ADN

Sea A la matriz cuadrada de orden n cuyas entradas (i, j) es une variable formal uij si y solamente si el hombre gj esta en la lista de la mujer fi , y 0 si no.

J. Ram´ırez Alfons´ın Combinatoria : nuevas tendencias e interacciones

UM2

Algoritmos aleatorios

Teor´ıa de nudos : ADN

Sea A la matriz cuadrada de orden n cuyas entradas (i, j) es une variable formal uij si y solamente si el hombre gj esta en la lista de la mujer fi , y 0 si no. Proposici´on Existe un conjunto de tales matrimonios si y solamente si el determinante de la matriz A no es id´enticamente cero.

J. Ram´ırez Alfons´ın Combinatoria : nuevas tendencias e interacciones

UM2

Algoritmos aleatorios

Teor´ıa de nudos : ADN

Ejemplo : f1 = {g1 , g2 }, f2 = {g2 , g3 }, f3 = {g1 , g2 , g3 }.

J. Ram´ırez Alfons´ın Combinatoria : nuevas tendencias e interacciones

UM2

Algoritmos aleatorios

Teor´ıa de nudos : ADN

Ejemplo : f1 = {g1 , g2 }, f2 = {g2 , g3 }, f3 = {g1 , g2 , g3 }.   u11 u12 0 u22 u23  = u11 u22 u33 + u12 u23 u31 − u11 u23 u32 det(A) =  0 u31 u32 u3,3

J. Ram´ırez Alfons´ın Combinatoria : nuevas tendencias e interacciones

UM2

Algoritmos aleatorios

Teor´ıa de nudos : ADN

Ejemplo : f1 = {g1 , g2 }, f2 = {g2 , g3 }, f3 = {g1 , g2 , g3 }.   u11 u12 0 u22 u23  = u11 u22 u33 + u12 u23 u31 − u11 u23 u32 det(A) =  0 u31 u32 u3,3

f1

g1

f1

g1

f1

g1

f1

g1

f2

g2

f2

g2

f2

g2

f2

g2

f3

g3

f3

g3

f3

g3

f3

g3

J. Ram´ırez Alfons´ın Combinatoria : nuevas tendencias e interacciones

UM2

Algoritmos aleatorios

• Calcular un determinante • Calcular un determinante

J. Ram´ırez Alfons´ın Combinatoria : nuevas tendencias e interacciones

Teor´ıa de nudos : ADN

 

simb´ olico  es dif´ıcil. num´erico  es f´acil.

UM2

Algoritmos aleatorios

• Calcular un determinante • Calcular un determinante

Teor´ıa de nudos : ADN

 

simb´ olico  es dif´ıcil. num´erico  es f´acil.

Estudio num´erico  Dar valores aleatorios a los indeterminantes y calcular el valor num´erico.



J. Ram´ırez Alfons´ın Combinatoria : nuevas tendencias e interacciones

UM2

Algoritmos aleatorios

• Calcular un determinante • Calcular un determinante

Teor´ıa de nudos : ADN

 

simb´ olico  es dif´ıcil. num´erico  es f´acil.

Estudio num´erico  Dar valores aleatorios a los indeterminantes y calcular el valor num´erico.



Si el valor no es cero podemos afirmar que el valor simb´ olico no es cero.

J. Ram´ırez Alfons´ın Combinatoria : nuevas tendencias e interacciones

UM2

Algoritmos aleatorios

• Calcular un determinante • Calcular un determinante

Teor´ıa de nudos : ADN

 

simb´ olico  es dif´ıcil. num´erico  es f´acil.

Estudio num´erico  Dar valores aleatorios a los indeterminantes y calcular el valor num´erico.



Si el valor no es cero podemos afirmar que el valor simb´ olico no es cero. Si el valor es cero no podemos concluir que el valor simb´ olico sea cero.

J. Ram´ırez Alfons´ın Combinatoria : nuevas tendencias e interacciones

UM2

Algoritmos aleatorios

Teor´ıa de nudos : ADN

Lema Sea P(X1 , X2 , . . . , Xm ) une polinomio diferente a cero en m variables, cada una de grado ≤ d, y sea M > 0 un entero. Entonces, el n´ umero de m-pletas (a1 , a2 , . . . , am ) ∈ {0, 1, . . . , M − 1}m tales que P(a1 , a2 , . . . , am ) = 0 es a lo mas igual a mdM m−1 .

J. Ram´ırez Alfons´ın Combinatoria : nuevas tendencias e interacciones

UM2

Algoritmos aleatorios

Teor´ıa de nudos : ADN

Lema Sea P(X1 , X2 , . . . , Xm ) une polinomio diferente a cero en m variables, cada una de grado ≤ d, y sea M > 0 un entero. Entonces, el n´ umero de m-pletas (a1 , a2 , . . . , am ) ∈ {0, 1, . . . , M − 1}m tales que P(a1 , a2 , . . . , am ) = 0 es a lo mas igual a mdM m−1 . Algoritmo matrimonio (1) selccionar al azar m enteros (a1 , a2 , . . . , am ) ∈ {0, 1, . . . , 2m − 1} (2) calcular det(A(a1 , a2 , . . . , am )) (3) si det(A(a1 , a2 , . . . , am )) 6= 0 entonces responder  existe un conjunto de tales matrimonios  si no responder  no existe probablemente un conjunto de tales matrimonios  J. Ram´ırez Alfons´ın Combinatoria : nuevas tendencias e interacciones

UM2

Algoritmos aleatorios

Teor´ıa de nudos : ADN

Observaci´on : El algoritmo matrimonio nos da una respuesta segura en el caso de la existencia y solamente una respuesta  probable  en el otro caso.

J. Ram´ırez Alfons´ın Combinatoria : nuevas tendencias e interacciones

UM2

Algoritmos aleatorios

Teor´ıa de nudos : ADN

Observaci´on : El algoritmo matrimonio nos da una respuesta segura en el caso de la existencia y solamente una respuesta  probable  en el otro caso. Pregunta : ¿Cu´al es la probabilidad P que de una respuesta n´egativa falsa ?

J. Ram´ırez Alfons´ın Combinatoria : nuevas tendencias e interacciones

UM2

Algoritmos aleatorios

Teor´ıa de nudos : ADN

Observaci´on : El algoritmo matrimonio nos da una respuesta segura en el caso de la existencia y solamente una respuesta  probable  en el otro caso. Pregunta : ¿Cu´al es la probabilidad P que de una respuesta n´egativa falsa ? P

≤ =

n´ umero maximum de m-pletas que anulan el det(A), que se suponen diferente de cero n´ umero total de m-pletas mdM m−1 Mm

J. Ram´ırez Alfons´ın Combinatoria : nuevas tendencias e interacciones

UM2

Algoritmos aleatorios

Teor´ıa de nudos : ADN

Observaci´on : El algoritmo matrimonio nos da una respuesta segura en el caso de la existencia y solamente una respuesta  probable  en el otro caso. Pregunta : ¿Cu´al es la probabilidad P que de una respuesta n´egativa falsa ? P

≤ =

n´ umero maximum de m-pletas que anulan el det(A), que se suponen diferente de cero n´ umero total de m-pletas mdM m−1 Mm

Como d = 1 y M = 2m, obtenemos que P≤

J. Ram´ırez Alfons´ın Combinatoria : nuevas tendencias e interacciones

1 2

UM2

Algoritmos aleatorios

Teor´ıa de nudos : ADN

Pregunta : ¿Cu´al es el inter´es pr´actico ?

J. Ram´ırez Alfons´ın Combinatoria : nuevas tendencias e interacciones

UM2

Algoritmos aleatorios

Teor´ıa de nudos : ADN

Pregunta : ¿Cu´al es el inter´es pr´actico ? Repitiendo un k veces este procedimiento, la probabilidad de obtener une respuesta negativa falsa, tomando en cuenta todas las respuestas obtenidas, es de ≤ 21k ·

J. Ram´ırez Alfons´ın Combinatoria : nuevas tendencias e interacciones

UM2

Algoritmos aleatorios

Teor´ıa de nudos : ADN

Pregunta : ¿Cu´al es el inter´es pr´actico ? Repitiendo un k veces este procedimiento, la probabilidad de obtener une respuesta negativa falsa, tomando en cuenta todas las respuestas obtenidas, es de ≤ 21k · Puede ser calculado que la probabilidad que una computadora sea destruida por un meteorito durante cada microsegundo de sus 1 c´alculos es al menos igual a 2100 (bajo la hip´ otesis de un impacto de un meteorito por milenio que destruye al menos 100 m2 de la superficie terrestre)  

J. Ram´ırez Alfons´ın Combinatoria : nuevas tendencias e interacciones

UM2

Algoritmos aleatorios

Teor´ıa de nudos : ADN

Nudos

J. Ram´ırez Alfons´ın Combinatoria : nuevas tendencias e interacciones

UM2

Algoritmos aleatorios

Teor´ıa de nudos : ADN

ADN

J. Ram´ırez Alfons´ın Combinatoria : nuevas tendencias e interacciones

UM2

Algoritmos aleatorios

Teor´ıa de nudos : ADN

ADN y la teor´ıa de nudos

• La mol´ecula de ADN d´ uplex consiste en dos cadenas helicoidales constituidas de az´ ucar y f´ osforo, adem´as, adherida a cada mol´ecula de az´ ucar est´a una de los cuatros nucleotidos base : Adenina, Citosina, Guanina y Timina

J. Ram´ırez Alfons´ın Combinatoria : nuevas tendencias e interacciones

UM2

Algoritmos aleatorios

Teor´ıa de nudos : ADN

ADN y la teor´ıa de nudos

• La mol´ecula de ADN d´ uplex consiste en dos cadenas helicoidales constituidas de az´ ucar y f´ osforo, adem´as, adherida a cada mol´ecula de az´ ucar est´a una de los cuatros nucleotidos base : Adenina, Citosina, Guanina y Timina • Podemos pensar el ADN como dos cuerdas entrelazadas que, a su vez, pueden estar enlazados con otros mol´eculas de ADN.

J. Ram´ırez Alfons´ın Combinatoria : nuevas tendencias e interacciones

UM2

Algoritmos aleatorios

Teor´ıa de nudos : ADN

ADN y la teor´ıa de nudos

• La mol´ecula de ADN d´ uplex consiste en dos cadenas helicoidales constituidas de az´ ucar y f´ osforo, adem´as, adherida a cada mol´ecula de az´ ucar est´a una de los cuatros nucleotidos base : Adenina, Citosina, Guanina y Timina • Podemos pensar el ADN como dos cuerdas entrelazadas que, a su vez, pueden estar enlazados con otros mol´eculas de ADN. • El ADN es muy ENROLLADO dentro de la c´elula, es equivalente a poner dentro de un bal´ on de f´ utbol unos 200 Km de hilo para pescar.

J. Ram´ırez Alfons´ın Combinatoria : nuevas tendencias e interacciones

UM2

Algoritmos aleatorios

Teor´ıa de nudos : ADN

• La teor´ıa de nudos aparece de forma natural en el an´alisis estructural en el ADN. Por ejemplo, la detecci´ on de cambios provocados por una enzima en el ADN

J. Ram´ırez Alfons´ın Combinatoria : nuevas tendencias e interacciones

UM2

Algoritmos aleatorios

Teor´ıa de nudos : ADN

• La teor´ıa de nudos aparece de forma natural en el an´alisis estructural en el ADN. Por ejemplo, la detecci´ on de cambios provocados por una enzima en el ADN

J. Ram´ırez Alfons´ın Combinatoria : nuevas tendencias e interacciones

UM2

Algoritmos aleatorios

Teor´ıa de nudos : ADN

Movimientos de Reidemeister I

I

!1

II

II

!1

III

III

J. Ram´ırez Alfons´ın Combinatoria : nuevas tendencias e interacciones

!1

UM2

Algoritmos aleatorios

Teor´ıa de nudos : ADN

III

II

II

I

J. Ram´ırez Alfons´ın Combinatoria : nuevas tendencias e interacciones

II

II

UM2

Algoritmos aleatorios

Teor´ıa de nudos : ADN

III

I

II

I

J. Ram´ırez Alfons´ın Combinatoria : nuevas tendencias e interacciones

UM2

Algoritmos aleatorios

Teor´ıa de nudos : ADN

III

I

II

I

II I I

J. Ram´ırez Alfons´ın Combinatoria : nuevas tendencias e interacciones

UM2

Algoritmos aleatorios

Teor´ıa de nudos : ADN

Detectar nudos triviales Dado un nudo K ¿existe une buen m´etodo para decidir si K es trivial o no ?

J. Ram´ırez Alfons´ın Combinatoria : nuevas tendencias e interacciones

UM2

Algoritmos aleatorios

Teor´ıa de nudos : ADN

El tr´ebol ¿Es el tr´ebol un nudo no trivial ?

J. Ram´ırez Alfons´ın Combinatoria : nuevas tendencias e interacciones

UM2

Algoritmos aleatorios

Teor´ıa de nudos : ADN

Teorema (Papakyriakopoulos 1957) Un nudo es trivial si y solamente si el grupo fundamental de su complemento es abeliano.

J. Ram´ırez Alfons´ın Combinatoria : nuevas tendencias e interacciones

UM2

Algoritmos aleatorios

Teor´ıa de nudos : ADN

Teorema (Papakyriakopoulos 1957) Un nudo es trivial si y solamente si el grupo fundamental de su complemento es abeliano. Teorema El grupo fundamental del complemento del tr´ebol no es abeliano.

J. Ram´ırez Alfons´ın Combinatoria : nuevas tendencias e interacciones

UM2

Algoritmos aleatorios

Teor´ıa de nudos : ADN

Teorema (Papakyriakopoulos 1957) Un nudo es trivial si y solamente si el grupo fundamental de su complemento es abeliano. Teorema El grupo fundamental del complemento del tr´ebol no es abeliano. Teorema (Hass, Lagarias 2001) Todo diagrama de un nudo trivial con n cruces puede ser transformado a un diagrama sin cruces en a 11 lo mas 2n·10 movimientos de Reidemeister.

J. Ram´ırez Alfons´ın Combinatoria : nuevas tendencias e interacciones

UM2

Algoritmos aleatorios

Teor´ıa de nudos : ADN

Coloreando nudos Un nudo K es coloreable si cada arco puede ser coloreable con 3 colores (digamos, rojo, azul, verde) de tal forma que 1) al menos 2 colores son utilizados 2) en cualquier cruce aparecen 1 o 3 colores.

J. Ram´ırez Alfons´ın Combinatoria : nuevas tendencias e interacciones

UM2

Algoritmos aleatorios

Teor´ıa de nudos : ADN

Coloreando nudos Un nudo K es coloreable si cada arco puede ser coloreable con 3 colores (digamos, rojo, azul, verde) de tal forma que 1) al menos 2 colores son utilizados 2) en cualquier cruce aparecen 1 o 3 colores.

J. Ram´ırez Alfons´ın Combinatoria : nuevas tendencias e interacciones

UM2

Algoritmos aleatorios

Teor´ıa de nudos : ADN

Teorema Si un diagrama de un nudo K es coloreable entonces todo diagrama de K es coloreable.

J. Ram´ırez Alfons´ın Combinatoria : nuevas tendencias e interacciones

UM2

Algoritmos aleatorios

Teor´ıa de nudos : ADN

Teorema Si un diagrama de un nudo K es coloreable entonces todo diagrama de K es coloreable. Demostraci´on Los movimientos de Reidemeister conservan la propriedad de coloraci´ on.

J. Ram´ırez Alfons´ın Combinatoria : nuevas tendencias e interacciones

UM2

Algoritmos aleatorios

Teor´ıa de nudos : ADN

Teorema Si un diagrama de un nudo K es coloreable entonces todo diagrama de K es coloreable. Demostraci´on Los movimientos de Reidemeister conservan la propriedad de coloraci´ on. Corolario Un nudo trivial no es coloreable.

J. Ram´ırez Alfons´ın Combinatoria : nuevas tendencias e interacciones

UM2

Algoritmos aleatorios

Teor´ıa de nudos : ADN

Teorema Si un diagrama de un nudo K es coloreable entonces todo diagrama de K es coloreable. Demostraci´on Los movimientos de Reidemeister conservan la propriedad de coloraci´ on. Corolario Un nudo trivial no es coloreable. Corolario El tr´ebol no es trivial.

J. Ram´ırez Alfons´ın Combinatoria : nuevas tendencias e interacciones

UM2

Algoritmos aleatorios

Teor´ıa de nudos : ADN

Teorema Si un diagrama de un nudo K es coloreable entonces todo diagrama de K es coloreable. Demostraci´on Los movimientos de Reidemeister conservan la propriedad de coloraci´ on. Corolario Un nudo trivial no es coloreable. Corolario El tr´ebol no es trivial. Corolario Si un enlace es separable entonces es coloreable.

J. Ram´ırez Alfons´ın Combinatoria : nuevas tendencias e interacciones

UM2

Get in touch

Social

© Copyright 2013 - 2024 MYDOKUMENT.COM - All rights reserved.