Scribd Logo
Cargar

¡Te damos la bienvenida a Scribd!

  • 32 vistas

    Taller I

    Cargado por

    MARCELA MAZO CASTRO
    Este documento presenta las instrucciones para un taller de análisis y diseño de algoritmos. Contiene 5 puntos que analizan la complejidad de varios algoritmos, incluyendo funciones, ordenamientos y búsquedas. Los estudiantes deben trabajar en grupos de hasta 4 personas para resolver los puntos y entregar un archivo con las soluciones antes del 2 de mayo.

    Copyright:

    © All Rights Reserved
    Descargue como PDF, TXT o lea en línea desde Scribd

    Taller I

    Cargado por

    MARCELA MAZO CASTRO
    32 vistas4 páginas
    Este documento presenta las instrucciones para un taller de análisis y diseño de algoritmos. Contiene 5 puntos que analizan la complejidad de varios algoritmos, incluyendo funciones, ordenamientos y búsquedas. Los estudiantes deben trabajar en grupos de hasta 4 personas para resolver los puntos y entregar un archivo con las soluciones antes del 2 de mayo.

    Título original

    Taller_I

    Derechos de autor

    © © All Rights Reserved

    Formatos disponibles

    PDF, TXT o lea en línea desde Scribd

    ¿Le pareció útil este documento?

    ¿Este contenido es inapropiado?

    Este documento presenta las instrucciones para un taller de análisis y diseño de algoritmos. Contiene 5 puntos que analizan la complejidad de varios algoritmos, incluyendo funciones, ordenamientos y búsquedas. Los estudiantes deben trabajar en grupos de hasta 4 personas para resolver los puntos y entregar un archivo con las soluciones antes del 2 de mayo.

    Copyright:

    © All Rights Reserved
    Descargue como PDF, TXT o lea en línea desde Scribd
    Descargar como pdf o txt
    32 vistas4 páginas

    Taller I

    Cargado por

    MARCELA MAZO CASTRO
    Este documento presenta las instrucciones para un taller de análisis y diseño de algoritmos. Contiene 5 puntos que analizan la complejidad de varios algoritmos, incluyendo funciones, ordenamientos y búsquedas. Los estudiantes deben trabajar en grupos de hasta 4 personas para resolver los puntos y entregar un archivo con las soluciones antes del 2 de mayo.

    Copyright:

    © All Rights Reserved
    Descargue como PDF, TXT o lea en línea desde Scribd
    Descargar como pdf o txt
    Está en la página 1de 4

    Taller I

    Análisis y Diseño de Algoritmos I


    Profesor: Jesús Alexander Aranda Bueno /
    2023-I

    Punto 1. En cada literal se encontrará́ un algoritmo escrito en pseudo-código. Para


    cada algoritmo, debe expresar su orden de complejidad, indicando la recurrencia y/o
    sumatorias que reflejen el T(n) (no requiere explicación adicional.
    Hágalo en términos de Θ( ). La operación básica en los siguientes algoritmos son las
    líneas print(“Hola Mundo”):

    a) funcion1(n)

    for(i = 2; i <= 4; i = i * i)
    print("Hola Mundo")

    for(i = 1; i <= n; i = i * 4 )
    print("Hola Mundo")

    b) funcion2(n)
    for(i = 1; i <= n; i = i * 2)
    for(j = 1; j <= n; j = j+j)
    print("Hola Mundo")

    c) funcion3(n)
    if(n == 1)
    print("Hola Mundo")
    else
    print("Hola Mundo")
    funcion3(n/2)
    funcion3(n/2)
    d) funcion4(n)
    if(n == 1)
    print("Hola Mundo")
    else
    print("Hola Mundo")
    for(j = 1; j <= 3; j = j + 1)
    funcion4(n/3)

    Punto 2. Dado el siguiente algoritmo:

    a) ¿Cuál es el número máximo(mínimo) de veces que se podría ejecutar la asignación


    de la línea 11? Justifique su respuesta y muestre un ejemplo donde esto ocurriría.

    b) ¿Cuál es el número máximo de veces que se podría ejecutar la asignación de la línea 16 ? Justifique
    su respuesta y muestre un ejemplo donde esto ocurriría.

    c) ¿El valor que retornar el programa a qué corresponde según el arreglo de entrada? Justifique
    claramente su respuesta.
    Punto 3. Dado el siguiente algoritmo:

    1. FuncionMisterio(a, b)
    2. if b == 0
    3. return 1
    4. if b == 1
    5. return a
    6. if even(b)
    7. c = FuncionMisterio(a, piso(b/2))
    8. return c*c
    9. else
    10. c = FuncionMisterio(a, piso(b/2))
    11. return c*c*a

    Asuma que tanto a como b son números enteros positivos. Asuma que existe una función
    even que recibe un número y devuelve true si es par, false si es impar, y lo hace en O(1)).

    a. Indique qué relación existe entre la salida y los parámetros de entrada del algoritmo.
    b. ¿Cuál es el mínimo número de veces que se ejecuta la línea 7? ¿En qué caso ocurre?

    c. ¿Cuál es el máximo número de veces que se ejecuta la línea 7? ¿En qué caso
    ocurre?
    d. ¿Cuál es la complejidad del algoritmo?

    Punto 4. Dado el siguiente algoritmo:

    1. Sort(a[1..n])
    2. for(i = 1; i <= n-1; i = i+1)
    3. min = i
    4. for(j = i+1; j <= n; j = j+1)
    5. if A[j] < A[min]
    6. min = j
    7. intercambiar(A[min], A[i])

    a. Identifique una línea básica adecuada y determine su complejidad. Determine si


    existe un peor y mejor caso.

    b. Determine si este algoritmo es estable asumiendo que puede haber elementos


    repetidos en el arreglo de entrada.

    Punto 5. Modifique el algoritmo visto en clase para determinar un orden estadístico de tal
    forma que se organicen en grupos de tamaño 9 (en lugar de tamaño 5). Realice el
    respectivo análisis de algoritmo y determine cuál sería su respectivo orden de complejidad.
    Aclaraciones sobre el taller
    El taller se puede desarrollar en grupos de máximo 4 estudiantes;
    Las entregas consisten en un archivo con las soluciones del taller. El nombre del archivo
    debe ser escrito de la siguiente forma: TallerIApellido1Apellido2Apellido3Apellido4.zip.

    El archivo correspondiente al documento solución del taller necesita ser entregado por
    medio del campus virtual a más tardar el 2 de mayo de 2023. El documento
    correspondiente al taller debe indicar el nombre de cada uno de los estudiantes que
    desarrollaron el taller. Todas las soluciones del taller necesitan su respectiva explicación,
    excepto el punto 1 que solo requiere la expresión de T(n) y la complejidad respectiva.

    También podría gustarte