.. -*- coding: utf-8 -*-

Ejercicios
==========

Coeficiente de endogamia
------------------------

Este es el árbol genealógico del caballo Lion's Share:


.. image:: ejercicios_media/lion_share.png
    :align: center


Queremos calcular la  *probabilidad*  de que los dos alelos de un gen dado provengan del mismo ascendiente, bajo las hipótesis normales de genética de Mendel. Esta probabilidad es igual a la suma, para cada ascendiente que está en el linaje tanto del padre como de la madre, del producto de la relación del ascendiente en cuestión con el padre y de su relación con la madre. La relación entre un ascendiente y su descendiente es :math:`\frac{1}{2^k}`, donde k es el número de generaciones que los separa, pero si el ascendiente aparece más de una vez en el linaje hay que sumar un término :math:`\frac{1}{2^k}` por cada aparición en la generación k-ésima.



 - Calcula el coeficiente de endogamia de Lion's Share (la probabilidad definida arriba)

 - ¿Qué tipo de grafo representa mejor un árbol genealógico? ¿Qué propiedades tiene?

 - (opcional) Escribe un programa que acepte un grafo del tipo anterior, y el nodo raíz, y calcule la probabilidad mencionada antes. Puedes hacerlo en otro lenguaje de programación, pero en ese caso habla con el profesor antes. Un algoritmo en pseudo\-código puede ser aceptable.


El grafo está sacado de: http://www.graphviz.org/content/lion_share


::

    sage: pares = [
    sage: ("025","027"),  ("022","027"),  ("019","024"),  ("020","024"), 
    sage: ("027","028"),  ("026","028"),  ("018","026"),  ("024","026"), 
    sage: ("011","025"),  ("023","025"),  ("008","018"),  ("017","018"), 
    sage: ("010","022"),  ("021","022"),  ("013","019"),  ("014","019"), 
    sage: ("015","023"),  ("005","023"),  ("016","020"),  ("005","020"), 
    sage: ("012","021"),  ("005","021"),  ("001","012"),  ("ZZ02","012"), 
    sage: ("003","008"),  ("002","008"),  ("001","017"),  ("007","017"), 
    sage: ("009","010"),  ("004","010"),  ("002","011"),  ("006","011"), 
    sage: ("002","013"),  ("ZZ01","013")]
    sage: ag = DiGraph()
    sage: for v1, v2 in pares:
    ...       ag.add_edge(v1,v2)
    sage: attach(DATA + 'graphviz.sage')
    sage: graphviz(ag, 'dot', False)



Recogida de basuras
------------------------

 - Encuentra el recorrido de longitud más corta que pasa una vez por cada arista, para el problema de recogida de basuras.


Malabares
------------------------

 - ¿Cuáles de entre las secuencias siguientes podrían formar parte de un truco de malabares (con las hipótesis habituales)?
    + ...333334...
    + ...333332...
    + ...13425350...
    + ...13525350...

 - Completa estas secuencias de malabares hasta engancharlas con la secuencia 3333...
    + ...515151
    + ...525145

 - (opcional) ¿Cuántos circuitos hamiltonianos tiene el grafo_malabar_con_cabeza(3,4)?

 - Escribe el grafo de malabares con dos pelotas de un color y una tercera de otro color y altura máxima 4. Si la tercera pelota es una manzana, identifica los estados en los que puedes pegarle un mordisco.

 - Pepito está aprendiendo a hacer malabares con cuchillos. Se ve capaz de lanzar y recibir los cuchillos a altura 5 pero no quiere lanzar dos  cuchillos seguidos tan alto por si se hace un lío al recogerlos. Modifica el grafo de tres objetos y altura 5 para evitar lanzar dos objetos a altura 5 seguidos.


Cadenas de Markov
------------------------

 - Al hablar de páginas web mencionamos un motivo por el que una cadena de Markov podría converger a una u otra distribución de probabilidad dependiendo del punto de partida. Muestra un grafo concreto que tenga este problema.

 - Estudia el problema de la convergencia en el circuito con dos vértices, que te mostramos abajo: ¿converge la distribución de probabilidad de los caminos aleatorios que comienzan en el vértice 0? ¿y en el vértice 1? ¿se aplica tu razonamiento a todos los circuitos de cualquier longitud (grafos con vértices 0,1,..,n tales que 0 está unido a 1, 1 a 2, ..., y n a 0)?

.

.. image:: ejercicios_media/circuito2.png
    :align: center

.

 - Encuentra otro grafo fuertemente conexo, y que no sea un circuito, pero tal que la distribución de probabilidad no converja desde algún punto de partida.

 - Busca en la literatura (o en internet, pero llegando a una fuente de confianza), las hipótesis bajo las cuales la distribución de probabilidad de una cadena de Markov converge a una misma distribución de probabilidad, independientemente del punto de partida. Razona si los grafos que vimos al estudiar el problema de evolución verifican esta propiedad.