14/12/2019 Examen final - Semana 8: RA/SEGUNDO BLOQUE-ANALISIS Y VERIFICACION DE ALGORITMOS-[GRUPO1]
Examen final - Semana 8
Fecha de entrega 17 de dic en 23:55 Puntos 120 Preguntas 10
Disponible 14 de dic en 0:00 - 17 de dic en 23:55 4 días Límite de tiempo 90 minutos
Intentos permitidos 2
Instrucciones
https://poli.instructure.com/courses/10545/quizzes/38674 1/11
14/12/2019 Examen final - Semana 8: RA/SEGUNDO BLOQUE-ANALISIS Y VERIFICACION DE ALGORITMOS-[GRUPO1]
Historial de intentos
Intento Hora Puntaje
MANTENER Intento 2 30 minutos 114 de 120
MÁS RECIENTE Intento 2 30 minutos 114 de 120
Intento 1 41 minutos 73.33 de 120
Puntaje para este intento: 114 de 120
Entregado el 14 de dic en 16:41
Este intento tuvo una duración de 30 minutos.
Pregunta 1 12 / 12 pts
Es cierto afirmar que la programación dinámica busca:
¡Correcto!
Atacar los problemas de más sencillos a más complejos.
¡Correcto!
Transformar soluciones recursivas en iterativas
¡Correcto!
Reducir la complejidad en tiempo de una solución recursiva.
Utilizar algoritmos Avaros (Greedy) para obtener una solución cercana a
la óptima
Transformar soluciones iterativas en recursivas
Atacar los problemas de más complejos a más sencillos
Pregunta 2 12 / 12 pts
Observe el grafo a continuación:
https://poli.instructure.com/courses/10545/quizzes/38674 2/11
14/12/2019 Examen final - Semana 8: RA/SEGUNDO BLOQUE-ANALISIS Y VERIFICACION DE ALGORITMOS-[GRUPO1]
La ruta de menor costo del nodo A al nodo I es:
¡Correcto!
A-D-E-I
A-D-E-G-I
No existe una ruta del nodo A al nodo I.
A-B-H-I
A-C-D-E-I
Pregunta 3 12 / 12 pts
public static void bubbleSort(int[] a){
boolean swapped;
do{
https://poli.instructure.com/courses/10545/quizzes/38674 3/11
14/12/2019 Examen final - Semana 8: RA/SEGUNDO BLOQUE-ANALISIS Y VERIFICACION DE ALGORITMOS-[GRUPO1]
swapped = false;
for (int i = 1; i < a.length; i++) {
if (a[i-1] > a[i]){
int temp = a[i-1];
a[i-1] = a[i];
a[i] = temp;
swapped = true;
}while(swapped);
La complejidad en caso promedio (cualquier permutación de a es
igualmente probable) del anterior algoritmo es:
ϴ(n^3)
ϴ(n^log(n))
ϴ(n)
ϴ(2^n)
¡Correcto!
ϴ(n^2)
Pregunta 4 12 / 12 pts
Los algoritmos de Dijkstra y Prim son ejemplos de algoritmos:
Ineficientes
https://poli.instructure.com/courses/10545/quizzes/38674 4/11
14/12/2019 Examen final - Semana 8: RA/SEGUNDO BLOQUE-ANALISIS Y VERIFICACION DE ALGORITMOS-[GRUPO1]
Dividir y Vencer
de Programación Dinámica
¡Correcto!
Voraces
De Ordenamiento
Pregunta 5 12 / 12 pts
Observe el grafo a continuación:
Ejecute el algoritmo de Dijkstra sobre el grafo, partiendo del nodo A y
complete las distancias mínimas a cada nodo.
¡Correcto! A 0
¡Correcto! B 14
¡Correcto! C 12
https://poli.instructure.com/courses/10545/quizzes/38674 5/11
14/12/2019 Examen final - Semana 8: RA/SEGUNDO BLOQUE-ANALISIS Y VERIFICACION DE ALGORITMOS-[GRUPO1]
¡Correcto! D 5
¡Correcto! E 9
¡Correcto! F 10
¡Correcto! G
18
¡Correcto! H 25
¡Correcto! I 23
Pregunta 6 6 / 12 pts
La programación dinámica es una técnica bastante amplia para atacar
problemas, que usualmente implican maximización.
¿Cuáles de las siguientes afirmaciones acerca de la programación
dinámica son verdaderas?
Respondido
Al igual que en dividir y vencer, se parte un problema grande en
problemas pequeños.
espuesta correcta
Es usual necesitar memoria adicional para almacenar las soluciones.
¡Correcto!
Se atacan problemas partiendo de los más sencillos a los más complejos
https://poli.instructure.com/courses/10545/quizzes/38674 6/11
14/12/2019 Examen final - Semana 8: RA/SEGUNDO BLOQUE-ANALISIS Y VERIFICACION DE ALGORITMOS-[GRUPO1]
¡Correcto!
Usualmente parte de una definición recursiva
Es una solución polinomial a problemas NP-completos
¡Correcto!
Su implementación es usualmente iterativa
Su implementación es usualmente recursiva.
Se llama dinámica porque necesita grupos dinámicos de programación
Pregunta 7 12 / 12 pts
Problema de la mochila.
Juanita está regresando de viaje desde Miami, y ha comprado un montón
de artículos (chucherías) que quiere vender cuando llegue a Colombia. Sin
embargo al confirmar su tiquete le advierten que puede llevar un máximo
peso W sin pagar sobreequipaje. ¿Cuáles artículos debe llevar?
Usted va a ayudar a Juanita con un algoritmo de programación dinámica, y
para esto guarda el peso de los artículos en un arreglo P[0..n-1] y sus
respectivas ganancias en un arreglo G[0..n-1].
Además define la siguiente función recursiva mG:
mG(w, i): la máxima ganancia que Juanita puede llevar sin pasarse del
límite de peso w, usando los artículos 0, 1, ... i
Tenga en cuenta que Juanita sólo tiene uno de cada artículo.
¿Cuáles de las afirmaciones a continuación son verdaderas? (Seleccione
todas las respuestas válidas).
mG(0 , w) = 0, para w en [1,W]
La función cumple la relación de recurrencia:
mG( w, i) = max( P[i] + mG( w - G[i], i-1), mG( w, i -1 ) )
para i en [1, n-1], w en [1,W]
https://poli.instructure.com/courses/10545/quizzes/38674 7/11
14/12/2019 Examen final - Semana 8: RA/SEGUNDO BLOQUE-ANALISIS Y VERIFICACION DE ALGORITMOS-[GRUPO1]
¡Correcto!
mG(i, 0) = 0, para: i en [0,n-1]
¡Correcto! La función cumple la relación de recurrencia:
mG(w, i) = max( G[i] + mG( w - P[i], i-1), mG( w, i -1 ) )
para i en [1, n-1], w en [1,W]
La función cumple la relación de recurrencia
mG( w, i) = max( mG( w - P[i], i-1), mG( w, i -1 ) )
para i en [1,n-1], w en [1,W]
¡Correcto!
La solución S es: S = mG(W, n-1)
Pregunta 8 12 / 12 pts
public static void bubbleSort(int[] a){
boolean swapped;
do{
swapped = false;
for (int i = 1; i < a.length; i++) {
if (a[i-1] > a[i]){
int temp = a[i-1];
a[i-1] = a[i];
a[i] = temp;
swapped = true;
}while(swapped);
https://poli.instructure.com/courses/10545/quizzes/38674 8/11
14/12/2019 Examen final - Semana 8: RA/SEGUNDO BLOQUE-ANALISIS Y VERIFICACION DE ALGORITMOS-[GRUPO1]
La complejidad en mejor caso del anterior algoritmo es:
ϴ(n^2)
ϴ(n^log(n))
¡Correcto!
ϴ(n)
ϴ(n^3)
ϴ(2^n)
Pregunta 9 12 / 12 pts
Para cada uno de los siguientes algoritmos, seleccione el problema en
Teoría de Grafos que soluciona:
¡Correcto! Kruskal Árbol de Expansión Min
¡Correcto! Prim Árbol de Expansión Min
¡Correcto! Dijkstra Ruta más corta
¡Correcto! A* Ruta más corta
¡Correcto! Floyd-Warshal Ruta más corta
¡Correcto! Ford-Fulkerson Flujo máximo
https://poli.instructure.com/courses/10545/quizzes/38674 9/11
14/12/2019 Examen final - Semana 8: RA/SEGUNDO BLOQUE-ANALISIS Y VERIFICACION DE ALGORITMOS-[GRUPO1]
¡Correcto! Bellman-Ford Ruta más corta
Otras opciones de coincidencia incorrecta:
Camino Hamiltoniano
Cubrimiento de Vértices
Camino Euleriano
k-Colorabilidad
Pregunta 10 12 / 12 pts
Observe el grafo a continuación:
Indique si es verdadera o falsa la siguiente afirmación:
"Existen dos rutas óptimas (de menor costo) diferentes del nodo A al nodo
H."
¡Correcto!
True
False
Puntaje del examen: 114 de 120
https://poli.instructure.com/courses/10545/quizzes/38674 10/11
14/12/2019 Examen final - Semana 8: RA/SEGUNDO BLOQUE-ANALISIS Y VERIFICACION DE ALGORITMOS-[GRUPO1]
https://poli.instructure.com/courses/10545/quizzes/38674 11/11
