• Author / Uploaded
• JUAN JOSE CAMACHO MARTINEZ

Citation preview

10/12/2019

Quiz 2 - Semana 7: RA/SEGUNDO BLOQUE-ANALISIS Y VERIFICACION DE ALGORITMOS-[GRUPO1]

Quiz 2 - Semana 7

Fecha de entrega 10 de dic en 23:55 Límite de tiempo 90 minutos

Puntos 90

Preguntas 9

Disponible 7 de dic en 0:00 - 10 de dic en 23:55 4 días

Intentos permitidos 2

Instrucciones

Volver a realizar el examen

Historial de intentos

MÁS RECIENTE

Intento

Hora

Puntaje

Intento 1

10 minutos

90 de 90

Puntaje para este intento: 90 de 90 Entregado el 10 de dic en 19:28 Este intento tuvo una duración de 10 minutos.

10 / 10 pts

Pregunta 1

En el problema del morral, se describe que

f (i, d)

conseguir llevando algunos objetos s1 , s2 , … , si

corresponde a la máxima utilidad que se puede en un morral de capacidad d . 1/5

10/12/2019

Quiz 2 - Semana 7: RA/SEGUNDO BLOQUE-ANALISIS Y VERIFICACION DE ALGORITMOS-[GRUPO1]

Entonces, si

f (i, d) > f (i + 1, d)

es correcto afirmar que:

Es necesario aumentar la capacidad d del morral.

¡Correcto!

No es conveniente llevar el objeto s i+1 La utilidad máxima aumento, llevando un objeto adicional.

f (i + 1, d) = f (i, d − 1)

.

Pregunta 2

10 / 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. ¡Correcto!

Reducir el tiempo en algunos algoritmos recursivos.

¡Correcto!

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

Pregunta 3

10 / 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:

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 n/a es el costo de resolver cada uno de los a subproblemas de tamaño b. ¡Correcto! 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.

Pregunta 4

10 / 10 pts

2/5

10/12/2019

Quiz 2 - Semana 7: RA/SEGUNDO BLOQUE-ANALISIS Y VERIFICACION DE ALGORITMOS-[GRUPO1]

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

Algoritmo Binario. Algoritmo de la escuela. Algoritmo de Strassen ¡Correcto!

Algoritmo de Coppersmith-Winograd

10 / 10 pts

Pregunta 5

Dado el algoritmo: fun pow(a: R ,n: N ) ret r : R : var b: R ; {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 del algoritmo está dada por la relación T(n)=2T(n/3)+1T(n)=2T(n/3)+1

¡Correcto!

La complejidad el algoritmo es 0(log(n))0(log(n))0(\log(n)) El algoritmo no corresponde al método de divide y vencerás. La complejidad el algoritmo es 0(n3)0(n^{3})

Pregunta 6

10 / 10 pts

En el algoritmo de Strassen, las matrices An×n y Bn×n iniciales son divididas cada una en 4 matrices. Estas 4 matrices tienen un número de filas y columnas igual a:

3/5

10/12/2019 ¡Correcto!

Quiz 2 - Semana 7: RA/SEGUNDO BLOQUE-ANALISIS Y VERIFICACION DE ALGORITMOS-[GRUPO1] n/2

Respuestas correctas n/2 n /2 n/2 (n/2)x(n/2) n/ 2

10 / 10 pts

Pregunta 7

Con relación al problema de cambio de monedas, se indica que f (i, b)

determina la cantidad de maneras

que existen para entregar un cambio b usando monedas de denominaciones d1 , d2 , d3 , d4 , … , di

.

Entonces, es correcto afirmar:

Si d i

> b

− 1, b) > f (i, b)

representa que se ha dado todo el cambio.

f (i, 0)

¡Correcto!

entonces f (i

Si d i

> b

entonces f (i

− 1, b) = f (i, b)

Si d i

> b

entonces f (i

− 1, b) < f (i, b)

10 / 10 pts

Pregunta 8

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

ONETA ¡Correcto!

OEA ROEA EA

10 / 10 pts

Pregunta 9

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

f(i,j)

: la longitud de la subsecuencia común más larga entre las cadenas s[i,...,n]

,j)

: la cadena de la subsecuencia común más larga entre las cadenas s[1,...,i]

y t[j,...,m] y t[1,...,j]

4/5

10/12/2019

¡Correcto!

Quiz 2 - Semana 7: RA/SEGUNDO BLOQUE-ANALISIS Y VERIFICACION DE ALGORITMOS-[GRUPO1]

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]

Puntaje del examen: 90 de 90

×

5/5