Usuario:Jaromeroa/Taller

Los apartados que voy a ir desarrollando en pareja junto a Jorge Pando Jimeno(JorgePJ13) durante el curso son:

- Del tema de Fundamentos: La sucesión Fibonacci

- Del tema de Números y sobre números: El algoritmo del backjumping

- Del tema de Contando: El movimiento Browniano

- Del tema de Visualizando relaciones: grafos, árboles y redes: El equilibrio de Nash

Sucesión de Fibonacci

Introducción.

La sucesión de Fibonacci en matemáticas es la siguiente: 0,1,1,2,3,5,8,13,21,34,55,89,144... Esta comienza con los números 0 y 1 y cada término de la sucesión es la suma de los dos anteriores términos. A cada término de la sucesión se les llama números de Fibonacci. Dicha sucesión fue dispuesta por Leonardo de Pisa, más conocido como Fionacci, en el siglo XIII. Es muy utilizada en los ámbitos de la Informática, Biología...

Definición recursiva.

Los términos de la sucesión quedan definidos por la ecuación: Fn=Fn-1 + Fn-2 Partiendo de los valores 0(F0) y 1(F1). Esta manera de definir, de hecho considerada algorítmica, es usual en Matemática discreta.

Es importante definir F0 = 0 , para que se pueda cumplir la importante propiedad de que:

Fn divide a Fm+n, para cualquier m,n>=1.

Propiedades de la sucesión.

• El máxiimo común divisor de dos números de Fibonacci es otro número de Fibonacci.
• La suma de diez números de Fibonacci consecutivos siempre es 11 veces superior al séptimo número de la serie.
• El último dígito de cada número se repite periódicamente cada 60 números.

La sucesión de Fibonacci en la naturaleza.

La secuencia de Fibonacci se encuentra en múltiples configuraciones biológicas, donde aparecen números consecutivos de la sucesión, como en la distribución de las ramas de los árboles, la distribución de las hojas en un tallo, los frutos de la piña tropical, las flores de la alcachofa, en las piñas de las coníferas, o en el "árbol genealógico" de las abejas melíferas. Sin embargo, también se han hecho muchas invocaciones infundadas a la aparición de los números de Fibonacci aprovechando su relación con el número áureo en la literatura popular.

El árbol genealógico de las abejas.

Los machos de una colmena de abejas tienen un árbol genealógico que cumple con esta sucesión. El hecho es que un zángano (1), el macho de la abeja, no tiene padre, pero sí que tiene una madre (1, 1), dos abuelos, que son los padres de la reina (1, 1, 2), tres bisabuelos, ya que el padre de la reina no tiene padre (1, 1, 2, 3), cinco tatarabuelos (1, 1, 2, 3, 5), ocho trastatarabuelos (1, 1, 2, 3, 5, 8) y así sucesivamente, cumpliendo con la sucesión de Fibonacci.

Divisibilidad.

• Sean n y m enteros positivos. Si el número n es divisible por m entonces el término n-ésimo de Fibonacci es divisible por el término m-ésimo de la misma sucesión. En efecto 4 divide a 12, por tanto el término de orden cuatro, el 3 divide a 144, término de orden 12 en la cita sucesión.
• Cualquiera que sea el entero m, entre los m^{2}-1 primeros números de Fibonacci habrá al menos uno divisible por m. A modo de ejemplo para m = 4, entre los primeros quince números están 8 y 144, números de Fibonacci, divisibles por 4.
• Si k es un número compuesto diferente de 4, entonces el número k-ésimo de Fibonacci es compuesto. Para el caso 10, compuesto distinto de 4, el décimo número de Fibonacci 55, es compuesto.
• Los números consecutivos de Fibonacci son primos entre sí.

El Algoritmo del Backjumping

Introduccion.

Dentro de los algoritmos del backtracking, el backjumping es una técnica que reduce el espacio de búsqueda, y en consecuencia de esto, aumenta la eficacia de esta. El backjumping tiene la capacidad de remontar más niveles que el backtracking, ya que éste siempre es capaz de remontar un nivel en el diagrama de árbol cuando todos los valores han sido demostrados para una variable $x_{1},\ldots ,x_{n}$

Backjumping en nodos de hoja.

El backjumping es posible cuando todos los valores de una variable han sido probadas sin meterse en niveles inferiores.

En constraint satisfaction (satisfacción de restricciones), una evaluación parcial es compatible si y sólo si satisface todos las restricciones que implican las variables asignadas. Si no ocurriera esto, serían inconsistentes. Puede darse el caso de que una solución parcial compatible no pueda ser extendida a una solución completa compatible porque algunas variables no asignadas no pueden ser asignadas sin violar otras restrinciones.

El leaf dead end (callejón sin salida) es la condición en la cual los valores de una variable $x_{k+1}$ dada son inconsistentes con la solución parcial actual $x_{1},\ldots ,x_{k}=a_{1},\ldots ,a_{k}$. Esto pasa siempre cuando la variable $x_{k+1}$ es una hoja del diagrama de árbol.

El algoritmo del backjumping por Gaschnig trabaja de manera diferente en situaciones tipo leaf dead end, ya que hace un salto hacia atrás. Un salto seguro puede ser encontrado con una simple evaluación.

Backjumping en nodos internos.

El algoritmo que hemos visto anteriormente sólo es capaz de saltar hacia atrás cuando los valores de una variable pueden que no sean consistentes con la solución parcial actual sin bifurcaciones más lejanas. Esto quiere decir que permite hacer un backjump sólo en nodos del diagrama de árbol.

Un nodo interno del árbol de búsqueda representa una asignación de una variable que es compatible con la anterior. En el caso en el que ninguna solución extiende esta asignación, el algoritmo anterior siempre retrocede: ningún salto hacia atrás se realiza en este caso.

En los nodos internos, el backjumping no puede realizarse en los nodos de las hojas. De hecho, si algunas evaluaciones de $x_{k+1}$ requieren una bifurcación, es porque son compatibles con la asignación actual. Como resultado, no obtiene resultado buscar un prefijo que es inconsistente con estos valores de la última variable.

En tales casos, lo que resultó una evaluación $x_{k+1}=a_{k+1}$ para no ser parte de una solución con la evaluación parcial actual $x_{1},\ldots ,x_{k}$ es la búsqueda recursiva.

Este tipo de regreso es debido a un número de callejones sin salida, puntos en los que el algoritmo ha demostrado una solución parcialmente inconsistente. Teniendo el objetivo de hacer un salto hacia atrás más lejano, el algoritmo tiene que tener en cuenta que la imposibilidad de encontrar las soluciones se debe a estos callejones sin salida.

Dentro de este tipo de Backjumping, encontramos lo siguiente:

Simplificaciones.

Encontrar un salto seguro puede ser simple por dos consideraciones.

-La primera es que el algoritmo necesita un salto seguro, pero también funciona sin que sea el salto seguro más alto posible.

-La segunda simplificación es que los nodos en el subnivel de $x_{l}$ que han sido evitados por un salto hacia atrás pueden ser ignorados mientras se busca un salto hacia atrás para $x_{l}$. Todos los nodos evitados por un backjump desde un nodo $x_{m}$ hasta otro nodo $x_{l}$ son irrelevantes al subnivel asociado en $x_{m}$.

De esta manera, si un algoritmo desciende desde un nodo $x_{l}$ hasta $x_{m}$ hacia una trayectoria pero salta hacia atrás en el camino de origen, entonces podria haber ido directamente desde $x_{l}$ a $x_{m}$ instead. De hecho, el backjump indica que los nodos entre $x_{l}$ y $x_{m}$ son irrelevantes al subnivel asociado en $x_{m}$.

Este hecho puede ser explotado coleccionando, en cada nodo, un conjunto de variables previamente asignadas cuya evaluación es suficiente para probar que no existe una solución en el subnivel con raíz en el nodo. Este conjunto es construido durante la ejecución del algoritmo. Cuando vuelve atras de un nodo, de este conjunto es eliminada la variable del nodo y recolectada en el conjunto de destino del backjumping. Puesto que nunca se retrocede desde los nodos ignorados, sus conjuntos son ignoradas de forma automática.

Backjumping basado en gráficos.

Una de las razones mas fundamentales de que el backjumping esté basado en gráficos es que un salto seguro puede ser hallado comprobando cuáles de las variables $x_{m}$ están en restrición con las variables $x_{k+1},x_{k+2},...$ que están instanciadas en nodos de hoja. Para cada nodo de hoja y cada variable $x_{i}$ de índice $i>k$ que esté instanciado allí, los índices menores o iguales a $k$ k cuyas variables están en restrición con $x_{i}$ pueden hallar los saltos seguros. En concreto, cuando todos los valores para $x_{k+1}$ han sido comprobados, este conjunto contiene los índices de las variables cuyas evaluaciones prueban que ninguna solución puede ser encontrada visitando el subnivel asociado en $x_{k+1}$. Como resultado, este algoritmo podria saltar hacia atrás al índice más alto del conjunto.

Un hecho de que los nodos saltados por backjumping puedan ser ignorados cuando se considere un salto hacia atrás más lejano puede ser dado por el algoritmo siguiente. Cuándo se retira de un nodo de hoja, el conjunto de variables con las que tiene una restrición está creado y "devuelto" a su padre, o nivel superior en caso de backjumping. En cada uno de los nodos internos, un conjunto de variables está mantenido. Cada vez que un conjunto de variables ha sido recibido por uno de sus descendiente, sus variables se añaden al conjunto mantenido. Cuando el backjumping va más allá del nodo, la variable del nodo se saca de este conjunto, y el conjunto es enviado al nodo de destino del backjumping. Estos algoritmos funcionan porque el conjunto mantenido en un nodo recoge todas las variables pertinentes para probar en las hojas que son descendiente de estos nodos.

Backjumping basado en el conflicto.

Un algoritmo de backjumping aún más refinado está basado(en no solo comprobar la presencia común de dos variables en la misma restrición) en si la restrición causa una incongruencia. En particular, este algoritmo recoge una de las restriciones violadas en cada hoja. En cada nodo, el índice más alto de un variable que está en una de las restriciones recogidas en las hojas es un salto seguro.

Mientras la restrición violada escogida en cada hoja no afecte al salto resultante, la elección de las limitaciones de los índices más altos posibles aumenta la altura del salto. Debido a esto, el backjumping basado en conflicto ordena restriciones de tal manera que las restriciones de las variables de índices más bajos se prefieran sobre las restricciones sobre las variables de índice más altos.

Formalmente, una restrición $C$ prevalece sobre otra $D$ si el índice más alto de una variable en $C$ pero no en $D$ es más bajo que el índice más alto de una variable en $D$ pero no en $C$. En otras palabras, excluyendo variables comunes, las restriciones más bajas tienen preferencia.

En práctica, este algoritmo se simplifica recogiendo todos los índices en un conjunto. En particular, el algoritmo recoge en cada nodo todos los conjuntos que vienen de sus descendientes que no ha sido saltados por backjumping.