Scribd Logo
Cargar

¡Te damos la bienvenida a Scribd!

  • 34 vistas

    Examen Quiz 2 - Semana 7 AV

    Cargado por

    edwin bernal
    Este documento presenta un examen de 9 preguntas sobre diferentes temas de algoritmos y estructuras de datos como el problema del morral, algoritmos de multiplicación de matrices, programación dinámica y subsecuencias comunes más largas. El examen evalúa la comprensión de conceptos fundamentales de estas áreas así como la habilidad para identificar afirmaciones correctas sobre la complejidad de diferentes algoritmos.

    Copyright:

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

    Examen Quiz 2 - Semana 7 AV

    Cargado por

    edwin bernal
    34 vistas6 páginas
    Este documento presenta un examen de 9 preguntas sobre diferentes temas de algoritmos y estructuras de datos como el problema del morral, algoritmos de multiplicación de matrices, programación dinámica y subsecuencias comunes más largas. El examen evalúa la comprensión de conceptos fundamentales de estas áreas así como la habilidad para identificar afirmaciones correctas sobre la complejidad de diferentes algoritmos.

    Título original

    Examen quiz 2 - Semana 7 AV

    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 de 9 preguntas sobre diferentes temas de algoritmos y estructuras de datos como el problema del morral, algoritmos de multiplicación de matrices, programación dinámica y subsecuencias comunes más largas. El examen evalúa la comprensión de conceptos fundamentales de estas áreas así como la habilidad para identificar afirmaciones correctas sobre la complejidad de diferentes algoritmos.

    Copyright:

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

    Examen Quiz 2 - Semana 7 AV

    Cargado por

    edwin bernal
    Este documento presenta un examen de 9 preguntas sobre diferentes temas de algoritmos y estructuras de datos como el problema del morral, algoritmos de multiplicación de matrices, programación dinámica y subsecuencias comunes más largas. El examen evalúa la comprensión de conceptos fundamentales de estas áreas así como la habilidad para identificar afirmaciones correctas sobre la complejidad de diferentes algoritmos.

    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 6

    Examen: Quiz 2 - Semana 7 https://poli.instructure.

    com/courses/13149/quizzes/46724/take

    Comenzado: 30 de jun en 22:55

    Pregunta 1 10 pts

    Processing math: 0%

    1 de 6 30/06/2020, 11:25 p. m.
    Examen: Quiz 2 - Semana 7 https://poli.instructure.com/courses/13149/quizzes/46724/take

    En el problema del morral, se describe que corresponde a la máxima utilidad que


    se puede conseguir llevando algunos objetos en un morral de capacidad .

    Entonces, si es correcto afirmar que:

    No es conveniente llevar el objeto

    Es necesario aumentar la capacidad del morral.

    La utilidad máxima aumento, llevando un objeto adicional.

    Pregunta 2 10 pts

    Si la complejidad de un algoritmo construido con la técnica de Dividir y Conquistar


    está determinado por la ecuación:

    donde es el tamaño del problema. Entonces, es correcto afirmar:

    n/a es el costo de resolver cada uno de los a subproblemas de tamaño b.

    n/b es el tamaño de cada uno de los subproblemas, f(n) es el costo de dividir el problema
    en los aaa subproblemas y mezclar los resultados.

    a es la cantidad de subproblemas y n/b es la cantidad de iteraciones necesarias para


    resolver cada subproblema.

    n/b Es el tamaño de cada uno de los subproblemas f(n) es el costo de dividir el problema
    de a subproblemas y mezclar los resultados

    Processing math: 0%

    2 de 6 30/06/2020, 11:25 p. m.
    Examen: Quiz 2 - Semana 7 https://poli.instructure.com/courses/13149/quizzes/46724/take

    Pregunta 3 10 pts

    Con relación al problema de cambio de monedas, se indica que determina la


    cantidad de maneras que existen para entregar un cambio usando monedas de
    denominaciones .

    Entonces, es correcto afirmar:

    Si entonces

    representa que se ha dado todo el cambio.

    Si entonces

    Si entonces

    Pregunta 4 10 pts

    En el algoritmo de Strassen, las matrices y iniciales son divididas cada una en 4


    matrices. Estas 4 matrices tienen un número de filas y columnas igual a:

    Pregunta 5 10 pts

    La subsecuencia común más larga entre las palabras: "PROBLEMA" y


    "AVIONETA" es:

    EA

    ROEA

    ONETA
    Processing math: 0%

    3 de 6 30/06/2020, 11:25 p. m.
    Examen: Quiz 2 - Semana 7 https://poli.instructure.com/courses/13149/quizzes/46724/take

    OEA

    Pregunta 6 10 pts

    La programación dinámica es una técnica que permite:

    Convertir la complejidad de un algoritmo a lineal.

    Describir algoritmos que varián de manera dinámica.

    Subdividir el problema en problemas más pequeños.

    Reducir el tiempo en algunos algoritmos recursivos.

    Pregunta 7 10 pts

    De los algoritmos para multiplicar matrices presentados en las lecturas del módulo,
    el más eficiente es:

    Algoritmo Binario.

    Algoritmo de Strassen

    Algoritmo de Coppersmith-Winograd

    Algoritmo de la escuela.

    Pregunta 8 10 pts

    Dado el algoritmo:

    fun pow(a: ,n: ) ret r : :


    Processing math: 0%

    4 de 6 30/06/2020, 11:25 p. m.
    Examen: Quiz 2 - Semana 7 https://poli.instructure.com/courses/13149/quizzes/46724/take

    var b: ;
    {Pre Q: n 0 a 0}
    if n=0 -> r:=1
    [] n≠0 and n mod 3 = 0
    b:=pow(a,k);
    r:=b*b*b;

    [] n mod 3=1-> k:=(n-1)/3;


    b:=pow(a,k);

    r:=a*b*b*b

    [] n mod 3=2-> k:=(n-2)/3;


    b:=pow(a,k);
    r:=a*a*b*b*b

    fi;
    {Pos R: r=a^n }

    ret r;

    endfun

    Es correcto afirmar:

    La complejidad el algoritmo es 0(n3)0(n^{3})

    El algoritmo no corresponde al método de divide y vencerás.

    La complejidad el algoritmo es 0(log(n))0(log(n))0(\log(n))

    La complejidad del algoritmo está dada por la relación T(n)=2T(n/3)+1T(n)=2T(n/3)+1

    Pregunta 9 10 pts

    La función objetivo que formaliza el problema de la subsecuencia mas larga es:

    Processing math: 0%

    5 de 6 30/06/2020, 11:25 p. m.
    Examen: Quiz 2 - Semana 7 https://poli.instructure.com/courses/13149/quizzes/46724/take

    f(i,j) : la cadena de la subsecuencia común más larga entre las cadenas


    s[i,...,n] y t[j,...,m]

    f(i,j) : la longitud de la subsecuencia común más larga entre las cadenas


    s[1,...,i] y t[1,...,j]

    f(i,j) : la longitud de la subsecuencia común más larga entre las cadenas


    s[i,...,n] y t[j,...,m]

    f(i,j) : la cadena de la subsecuencia común más larga entre las cadenas


    s[1,...,i] y t[1,...,j]

    Examen guardado en 23:25

    Processing math: 0%

    6 de 6 30/06/2020, 11:25 p. m.

    También podría gustarte