Download pdf - laboratorio 4

Transcript
  • ALGORITMOS ,11 DE MARZO 2014 1

    Informe de Laboratorio # 4Analisis Promedio

    Fernando GualotunaFacultad de Ingeniera en Sistemas

    Escuela Politecnica [email protected]

    Abstract En la siguiente trabajo se implementa un codigo en lenguaje C para determinar el tiempo que se demorauna rutina ordenacion de numeros generados randomicamente 0-500 en el peor de los casos el numero x estara en unrango de 0-501 ;Programa determina si el elemento x se encuentra o No en el Arreglo.Realizar una grafica T vs N con su respecto analisis.

    Index Terms

    F

    1 OBJETIVO

    ANalizar de forma experimental un casode comportamiento promedio.

    2 ESPECIFICACION DEL PROBLEMASe L el arreglo que contiene n datos de Entrada.Encontrar la posicion de un dato x en el arregloRetorna O si x no esta en el arreglo.

    3 METODOCorrer varias veces el programa de un algo-ritmo de busqueda exhaustiva de numeros deuna lista de 500 numeros elegidos al azar yluego probar buscando un valor de x de entre501 posibles valores introduciendo un codigopara cronometrar tiempos.Trazar las curvas de valor promedio; y prome-dio acumulado de 1 a 500 corridas graficandopuntos de 100 en 100.

    4 OPERACION BASICAComparacion de x con el contenido de unaposicion en L.

    Analisis del peor caso W(n) = n. Analisis decomportamiento promedio:

    P(n) =n

    i=1

    p(Ii)t(Ii) (1)

    En el caso que tengan todos la misma proba-bilidad:

    P(n) =n

    i=1

    (1

    n)i (2)

    Suponiendo que x esa en la lista:

    P(n) =1

    n

    ni=1

    =1

    n

    n(n+ 1)

    2=

    n+ 1

    2(3)

    Si se considera que x No esa en la lista: In+1representa x no esta en L.Sea que la probabilidad que esa en la listap(In+1) = 1 q

    P(n) =n

    i=1

    p(Ii)t(Ii) =n

    i=1

    (q

    n)i + (1 q)n (4)

    la probabilidad que esa en L + la probabilidadque no esa en la listaP(n) = q

    n

    ni=1 +(1 q)n = qnn (

    n+12) + (1 q)n =

    q n+12

    + (1 q)n

  • ALGORITMOS ,11 DE MARZO 2014 2

    4.1 Tabla de valores

    4.2 Grafica t vs n

    4.3 Grafica t vs n

    4.4 Grafica tiempo acumulado vs numeroejecuciones

    4.5 ConclusionEl comportamiento del analisis promedio dela curva tiende a ser periodica, en unos casosel tiempo de ejecucion eran igual a 0. por talrazon fueron descartados para utilizarlos en elpromedio.

    La Grafica tiempo acumulado representa unarecta, se incremeta el valor en un valor con-stante k que se incrementa con el numero deveces que se corre el programa. El procesode correr el programa 100 veces problamentese estabiliza cuya grafica se muestra, aunquedebido a que el rango es de 0 a 500; la probabil-idad que encuentre un numero es 500

    501= 0.9988

    es decir el 99.88 %; siendo el 0.22 % que estenumero no se encuentre.

    5 CODIGO FUENTEEl codigo se encuentra en los Anexos rand1.cLos datos completos en Datos.xlsx

    REFERENCES[1] Msc Hallo Francisco Algoritmos Analisis Promedio;

    Teoria de Algoritmos Caso Promedio , Docente de laEscuela Politecnica Nacional