Algoritmos y grafos trabajo 1

1. Elegir una de las distintas situaciones en las que se presentan los números de Catalan y
desarrollarla. (3 puntos)
Desarrollar también una forma de obtener una fórmula cerrada a partir de la recurrencia
que los define. (2 puntos)

La situación que he elegido es la de un problema que trata de hallar el numero de combinaciones posibles que hay de agrupar una cadena de letras delongitud n con un total de n-1 pares de paréntesis de manera que queden agrupadas dentro de cada paréntesis 2 letras o un grupo de letras con un par de parentesis con otra letra o dos grupos de pares de letras.

Los posibles casos son:
Vamos a explorar los primeros casos:
Para dos letras, ab, hay sólo una forma:
(ab)
Para tres letras, abc, tenemos dos formas:
((ab)c) y (a(bc))
Si tenemoscuatros letras, abcd, se obtienen cinco formas:
((ab),(cd)), (((ab)c)d), (a(b(cd))), (a((bc)d)) y ((a(bc)d)
Obtenemos los números 1, 2 y 5. Y si continuáramos obtendríamos 14, 42...
Es interesante apuntar que a veces esta sucesión se toma de la siguiente forma:
1,1,2,5,14,42...
Escribiéndola de esta manera tenemos una forma muy interesante de calcular cada término si conocemos los anteriores:Sea k el último número de Catalan que conocemos y sea n la posición del número siguiente en esta sucesión. Entonces dicho número se calcula mediante la siguiente expresión:

Por ejemplo, si el último término que conocemos es el 14, el siguiente es el que ocupa la sexta posición. Entonces Cn=14 y n=6 y el siguiente término es:

De ahí se obtiene la siguiente tabla:
n
1
2
3
4
5
6
78
9
10
Cn
1
2
5
14
42
132
429
1.430
4.862
16.796

Fórmula cerrada:
Los números de Catalan enumeran a la familia de los arboles binarios.
Imaginemos que nuestros arboles son como los arboles genealógicos, donde
cada padre tiene exactamente 2 hijos, uno derecho y el otro izquierdo.

*Imagen obtenida del archivo catalan-1.pdf subido en el moodle.

como se puede ver en eltriángulo de Pascal:

*Imagen obtenida http://gaussianos.com/los-numeros-de-catalan/

Sea B(n) el número de árboles binarios con n padres, se puede demostrar que

con

Debemos demostrar que un árbol binario con n niños (un niño es un vértice que no es padre, es decir, no tiene descendencia) tiene exactamente n − 1 padres, y en consecuencia 2n − 1 vértices.

*Imagen obtenida delarchivo catalan-1.pdf subido en el moodle.

Para demostrar la recurrencia procedemos como sigue. Construimos un
árbol con n padres (de B(n) maneras) y seleccionamos en él al hijo menos
favorito. Los eliminamos a él y a su padre y promovemos al hermano al lugar
del padre.

Obtenemos así un árbol con n vértices, donde uno de ellos, el que corresponde
al hermano recién promovido, estámarcado.

Para que este procedimiento sea una biyección, necesitamos recordar si el
hijo menos favorito era el derecho o era el izquierdo. Tenemos dos posibilidades,
y aparece entonces un factor de dos en el lado derecho de nuestra ecuación.
Tenemos entonces que

*Imagen obtenida del archivo catalan-1.pdf subido en el moodle.

Queda demostrado B(n) = Cn . De manera que los números deCatalan
vienen dados por la fórmula cerrada:

*Imagen obtenida del archivo catalan-1.pdf subido en el moodle.
2. De entre los siguientes algoritmos, escribir uno de ellos, mostrar como funciona con un
ejemplo y estudiar en que orden está su tiempo de ejecución.

(b) Algoritmo de ordenación BottomUpSort. (5 puntos)

El algoritmo de ordenación BottomUpSort es un claro algoritmo del tipo“divide y vencerás”.

Conceptualmente, el ordenamiento con BottomUpSort funciona de la siguiente manera:
1. Si la longitud del array es 0 ó 1, entonces ya está ordenada. En otro caso:
2. Dividir el array desordenado en subarrays de tamaño de pares consecutivos; si el último quedara libre se le añadiria a la secuencia en ultimo lugar.
3. Ordenar cada subarray recursivamente aplicando el...