¿Qué característica principal define a los algoritmos voraces?
En cada etapa eligen la mejor decisión posible sin considerar sus consecuencias futuras.
¿Qué técnica utiliza la vuelta atrás para explorar soluciones?
Construye un árbol de expansión y retrocede cuando detecta ramas que no llevan a soluciones válidas.
¿Cuál es el principio de optimalidad en programación dinámica?
Toda subsecuencia de una solución óptima también es óptima.
¿Qué tipo de grafos utiliza el algoritmo de Prim?
Grafos conexos, ponderados y no dirigidos.
¿Cómo se representa una solución al problema de las ocho reinas?
Como un vector donde cada posición indica la columna y el valor indica la fila de la reina.
¿El algoritmo de Kruskal puede formar ciclos?
No, descarta aristas que formen ciclos.
¿La técnica “Divide y vencerás” asegura siempre la mejor solución?
No, depende del diseño del algoritmo y el equilibrio de las divisiones.
¿En qué tipo de problemas no funciona el principio de optimalidad?
En problemas como el viajante, donde caminos parciales óptimos no garantizan la mejor solución global.
¿Es eficiente la técnica voraz para todos los problemas?
No, solo para problemas donde la solución parcial conduce a la mejor solución final.
¿La programación dinámica requiere memoria adicional?
Sí, para almacenar cálculos intermedios en tablas.
En programación dinámica, el solapamiento de subproblemas genera ____.
ineficiencia.
El algoritmo de Prim selecciona el arco de menor coste que conecta vértices seleccionados y ____.
no seleccionados.
En la técnica de vuelta atrás, las restricciones determinan si una rama es ____.
prometedora.
El algoritmo voraz utiliza una función de ____ para elegir la mejor opción en cada etapa.
selección.
En “Divide y vencerás”, las soluciones de los subproblemas deben ser ____.
combinables.
¿Qué estrategia utiliza la técnica de programación dinámica?
A) Descartar soluciones no prometedoras.
B) Guardar cálculos intermedios para evitar repeticiones.
C) Resolver problemas directamente mediante fuerza bruta.
B) Guardar cálculos intermedios para evitar repeticiones.
¿Qué técnica combina eficientemente soluciones parciales?
A) Algoritmos voraces.
B) Vuelta atrás.
C) Divide y vencerás.
C) Divide y vencerás.
¿Cuál es la complejidad del algoritmo de Prim?
A) O(n²).
B) O(n log n).
C) O(n³).
A) O(n²).
¿Cuál es una limitación de los algoritmos voraces?
A) Requieren almacenamiento adicional.
B) No siempre encuentran la solución óptima global.
C) Solo funcionan en grafos dirigidos.
B) No siempre encuentran la solución óptima global.
¿Qué problema ejemplifica la técnica de vuelta atrás?
A) Cambio de monedas.
B) Ocho reinas.
C) Torres de Hanói.
B) Ocho reinas.
Describe el algoritmo de Kruskal para grafos.
Ordena las aristas por peso, seleccionando aquellas que no formen ciclos para construir un árbol de recubrimiento mínimo.
¿Cómo se utiliza la recursividad en “Divide y vencerás”?
Descompone el problema en subproblemas más pequeños, los resuelve recursivamente y combina las soluciones parciales.
¿Qué elementos definen un problema para algoritmos voraces?
Un conjunto de candidatos, una función de selección, una función objetivo y restricciones para descartar opciones no válidas.
Explica cómo la programación dinámica evita redundancias.
Utiliza tablas para almacenar resultados intermedios, evitando recalcular soluciones de subproblemas solapados.
