Scribd Logo
Cargar

¡Te damos la bienvenida a Scribd!

  • 195 vistas

    Parcial Diseño de Algoritmos Univalle

    Cargado por

    ToXiC GoLDeN - Android Gaming
    Este documento presenta un examen parcial de fundamentos de análisis y diseño de algoritmos con 4 secciones y un total de 100 puntos. La primera sección trata sobre el crecimiento de funciones (15 puntos). La segunda sección aborda ecuaciones de recurrencia y sus métodos de solución (30 puntos). La tercera sección cubre estructuras de datos comunes y su complejidad (15 puntos). Finalmente, la cuarta sección examina conceptos de computación iterativa y recursiva (40 puntos).

    Copyright:

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

    Parcial Diseño de Algoritmos Univalle

    Cargado por

    ToXiC GoLDeN - Android Gaming
    195 vistas1 página
    Este documento presenta un examen parcial de fundamentos de análisis y diseño de algoritmos con 4 secciones y un total de 100 puntos. La primera sección trata sobre el crecimiento de funciones (15 puntos). La segunda sección aborda ecuaciones de recurrencia y sus métodos de solución (30 puntos). La tercera sección cubre estructuras de datos comunes y su complejidad (15 puntos). Finalmente, la cuarta sección examina conceptos de computación iterativa y recursiva (40 puntos).

    Descripción original:

    Título original

    Parcial diseño de algoritmos univalle

    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 un examen parcial de fundamentos de análisis y diseño de algoritmos con 4 secciones y un total de 100 puntos. La primera sección trata sobre el crecimiento de funciones (15 puntos). La segunda sección aborda ecuaciones de recurrencia y sus métodos de solución (30 puntos). La tercera sección cubre estructuras de datos comunes y su complejidad (15 puntos). Finalmente, la cuarta sección examina conceptos de computación iterativa y recursiva (40 puntos).

    Copyright:

    © All Rights Reserved
    Descargue como PDF, TXT o lea en línea desde Scribd
    Descargar como pdf o txt
    195 vistas1 página

    Parcial Diseño de Algoritmos Univalle

    Cargado por

    ToXiC GoLDeN - Android Gaming
    Este documento presenta un examen parcial de fundamentos de análisis y diseño de algoritmos con 4 secciones y un total de 100 puntos. La primera sección trata sobre el crecimiento de funciones (15 puntos). La segunda sección aborda ecuaciones de recurrencia y sus métodos de solución (30 puntos). La tercera sección cubre estructuras de datos comunes y su complejidad (15 puntos). Finalmente, la cuarta sección examina conceptos de computación iterativa y recursiva (40 puntos).

    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 1

    Primer examen parcial

    Fundamentos de análisis y diseño de algoritmos


    Duración: 2 horas
    *
    Carlos Andres Delgado S, Ing
    25 de Abril 2017

    Nombre: 4. Computación iterativa [40 pun-


    Código: tos]

    1. (25 puntos) Para el siguiente algoritmo iterativo:


    1. Crecimiento de funciones [15
    puntos] algoritmo2 ( int a , int n) {
    int b = n ;
    int c = 3 ;
    Indique si existen funciones f (n), g(n) y h(n), tales int r = 0 ;
    que f (n) es Θ(g(n)), g(n) es o(h(n)) y h(n) es ω(f (n)). w h i l e ( b >= 0 ) {
    Realice una demostración y muestre con un ejemplo. w h i l e ( c >=0){
    r+=a ;
    c −−;
    }
    2. Ecuaciones de recurrencia [30 r+=n ;
    puntos] c = 3;
    b−−;
    }
    1. (15 puntos) Utilizando el método de iteración, so- print ( r ) ;
    lucione la siguiente ecuación de recurrencia
    }

    T (n) = T (n − 1) + 3n, T (0) = O(1)


    a) Indique la forma de estado, estado inicial y
    2. (15 puntos) Utilizando el método de árboles, solu- estado final
    cione la siguiente ecuación de recurrencia b) Indique la transición de estados
    n c) Indique la invariante de ciclo
    T (n) = 9T ( ) + n2 + 3, T (1) = O(n)
    3
    2. (15 puntos) Para el siguiente algoritmo recursivo
    indique la ecuación de recurrencia y calcule la com-
    3. Estructuras de datos [15 puntos]
    plejidad el términos de O(n):
    1. (5 puntos) ¿Cual es la complejidad de las opera- / / n e s u n n u m e r o par , a >= 1
    algoritmo3 ( int n , int a ) {
    ciones en una pila? ¿Porque? i f ( n == 1 ) {
    return a ;
    2. (10 puntos) ¿Cual es la complejidad de las opera- }
    else {
    ciones de búscar, insertar y eliminar en una tabla int c = algoritmo4 (n , a )
    hash con hashing uniforme con n elementos y m c + algoritmo3 (n/2 , a ) + algoritmo3 (n
    /2 , a )
    llaves? }

    algoritmo4 ( int n , int a ) {


    int i = 0 ;
    int j = 0 ;
    int k = 0 ;
    w h i l e ( i <n ) {
    w h i l e ( j <n ) {
    w h i l e ( k<−n ) {
    a+=k ;
    k++;
    }
    j ++;
    }
    i ++;
    }

    * carlos.andres.delgado@correounivalle.edu.co }

    También podría gustarte