## ACTIVIDAD 5 AUTOEVALUACIÓN

## Repaso de la Unidad I

Descripción

Los ejercicios que se proponen tienen la finalidad de que realices un repaso de los temas de la Unidad I.

1. Determine el orden asintótico de las soluciones de las ecuaciones de recurrencia siguientes. Puede suponer que T(1)=1, la recurrencia es para n>1 y c es alguna constante positiva.

a. T(n) =T(n/2) + c lg n.
b. T(n) = T(n/2) + cn.
c. T(n) = 2T(n/2) + cn.
d. T(n) = 2T(n/2) + cn lg n.
e. T(n) = 2T(n/2) + cn2.
2. El problema de las Torres de Hanoi se usa con frecuencia como ejemplo al enseñar recursión. Seis discos de diferente tamaño están ensartados en una varilla y ordenados por tamaño, con el más grande hasta abajo. Hay dos varillas vacías. El problema consiste en pasar todos los discos a la tercera varilla moviendo sólo uno a la vez y sin colocar un disco encima de uno más pequeño. Se puede usar la segunda varilla para movimientos intermedios.
La solución común mueve recursivamente todos los discos menos el último de la varilla inicial a la varilla intermedia, luego mueve el disco que queda en la varilla inicial a la varilla de destino, luego mueve recursivamente todos los demás discos de la varilla intermedia a la varilla de destino.

Demuestre la ecuación de recurrencia para el problema de las Torres de Hanoi y el orden de Complejidad.

3. Escriba un programa para ordenamiento por burbuja simple y burbuja mejorada. Realice un experimento para convencerse de que, en efecto, el desempeño medio de los algoritmos es O(n2).

4. Sea a un arreglo de n elementos y p, r índices del rango a ordenar:

    Merge-Sort(a,  p,  r)

    {

    if ( p < r )

    {

      q = parteEntera((p+r)/2);

      Merge-Sort(a,  p,  q);

      Merge-Sort(a,  q+1,r);

      Merge(a,  p,  q,  r);

    }

    }

5. Calcular la complejidad de la implementación recursiva del termino n de la serie de Tribonacci (0, 1, 1, 2, 4, 7, 13, 24, 44, 81, 149, 274, 504, 927, 1705, ...)

    int  Tribonacci( int  num )

    {

      if  (num==0)

      return  0;

      else  if  (num==1||num==2)

      return  1;

      else

      return  Tribonacci(num-1)+Tribonacci(num-2)+Tribonacci(num-3);

    }

Calcular la cota de complejidad del algoritmo Merge –Sort recursivo.

Valor 0%

###