Programación dinámica: Resuelve problemas de forma óptima

Question 1

¿Cuál es el principio fundamental de la programación dinámica?

Accepted Answer

El principio de optimalidad

Answer

El principio de programación recursiva

Answer

El principio de optimización

Answer

El principio de eficiencia

Question 2

¿Cómo se descomponen los problemas en la programación dinámica?

Accepted Answer

En subproblemas más pequeños y óptimos

Answer

En subproblemas de igual tamaño

Answer

En subproblemas aleatorios

Answer

No se descomponen

Question 3

¿Qué técnica es esencial en la programación dinámica para evitar la repetición de cálculos?

Accepted Answer

Memorización

Answer

Interpolación

Answer

Exclusión mutua

Answer

Copia de datos

Question 4

¿Cuál es el objetivo principal de la optimización en la programación dinámica?

Accepted Answer

Encontrar la solución óptima o una aproximación

Answer

Simplificar el código

Answer

Ahorrar tiempo de ejecución

Answer

Reducir la complejidad espacial

Question 5

¿Para qué tipo de problemas es especialmente adecuada la programación dinámica?

Accepted Answer

Problemas con subestructura óptima y subproblemas superpuestos

Answer

Problemas sin una solución óptima

Answer

Problemas con un gran número de soluciones posibles

Answer

Problemas que requieren mucho tiempo de ejecución

Question 6

¿Cuál es una ventaja clave de utilizar la programación dinámica?

Accepted Answer

Puede encontrar soluciones óptimas o aproximaciones para problemas complejos

Answer

Siempre es más eficiente que otros enfoques

Answer

No requiere ninguna optimización

Answer

Es fácil de implementar para cualquier problema

Question 7

¿En qué principio se fundamenta la programación dinámica?

Accepted Answer

Optimalidad

Answer

División

Answer

Rechazo

Answer

Memorización

Question 8

En la programación dinámica, ¿cómo se resuelven los subproblemas?

Accepted Answer

De forma óptima

Answer

De forma aleatoria

Answer

De forma aproximada

Question 9

Para calcular el camino mínimo desde la esquina superior izquierda hasta la inferior derecha en una matriz, ¿qué subproblema se resuelve primero?

Accepted Answer

El camino mínimo desde la esquina superior izquierda a la segunda fila y columna

Answer

El camino mínimo desde la esquina inferior derecha a la primera fila y columna

Answer

El camino mínimo desde la esquina superior izquierda hasta la última fila y columna

Question 10

¿Cuál es una ventaja de utilizar programación dinámica?

Accepted Answer

Eficacia en tiempo y espacio para problemas complejos

Answer

Manejo de entradas no deterministas

Answer

Simplicidad de implementación

Question 11

¿En qué consiste la memorización en la programación dinámica?

Accepted Answer

Almacenar soluciones previamente calculadas de subproblemas

Answer

Ignorar subproblemas no óptimos

Answer

Generar todos los subproblemas posibles

Question 12

¿Qué algoritmo, basado en programación dinámica, se utiliza para encontrar el camino más corto entre todos los pares de vértices en un grafo?

Accepted Answer

El algoritmo de Floyd-Warshall

Answer

El algoritmo de Prim

Answer

El algoritmo de Kruskal

Answer

El algoritmo de Dijkstra

Question 13

¿Cuál de las siguientes es una desventaja de la programación dinámica?

Accepted Answer

Puede requerir una gran cantidad de espacio y tiempo de ejecución

Answer

No es aplicable a problemas de optimización

Answer

Es excesivamente difícil de implementar

Question 14

¿Cuál de las siguientes afirmaciones describe mejor el principio de optimalidad en la programación dinámica?

Accepted Answer

La solución óptima al problema original se puede construir a partir de soluciones óptimas a sus subproblemas.

Answer

La solución se construye iterativamente, resolviendo primero los subproblemas más simples.

Answer

El problema se puede descomponer en subproblemas más pequeños que son independientes entre sí.

Question 15

¿Qué estructura de datos se utiliza comúnmente para almacenar los valores de subproblemas resueltos en la programación dinámica?

Accepted Answer

Tabla de memoización

Answer

Pila

Answer

Lista enlazada

Answer

Cola de prioridad

Question 16

El algoritmo de Floyd-Warshall es un ejemplo de programación dinámica utilizada para:

Accepted Answer

Encontrar las rutas más cortas entre todos los pares de vértices en un grafo dirigido ponderado.

Answer

Determinar si un grafo es conexo.

Answer

Ordenar un conjunto de elementos.

Question 17

La ecuación de recurrencia es una herramienta que ayuda a:

Accepted Answer

Establecer la relación entre el problema original y sus subproblemas.

Answer

Almacenar soluciones de subproblemas.

Answer

Optimizar el rendimiento del algoritmo.

Question 18

¿Cuál de las siguientes técnicas se usa para mejorar la eficiencia de los algoritmos de programación dinámica?

Accepted Answer

Memoización

Answer

Búsqueda binaria

Answer

Programación recursiva

Answer

División y conquista

Question 19

¿Cuál de los siguientes problemas NO se puede resolver usando programación dinámica?

Accepted Answer

Clasificar un conjunto de elementos usando un algoritmo de ordenamiento

Answer

Calcular la ruta más corta en un grafo ponderado

Answer

Encontrar la secuencia de edición más corta entre dos cadenas

Question 20

¿Qué técnica se usa para dividir un problema complejo en subproblemas más pequeños y manejables?

Accepted Answer

Descomposición

Answer

Encapsulación

Answer

Herencia

Answer

Polimorfismo

Question 21

Si un problema se puede dividir en subproblemas que se repiten, ¿qué técnica de diseño de algoritmos es la más adecuada para resolverlo eficientemente?

Accepted Answer

Programación dinámica

Answer

Backtracking

Answer

Fuerza bruta

Answer

Divide y vencerás

Question 22

En programación dinámica, ¿qué función tiene una tabla de subproblemas?

Accepted Answer

Almacena las soluciones a los subproblemas para evitar recalcularlos.

Answer

Muestra las relaciones entre los subproblemas en un diagrama.

Answer

Contiene una lista de todos los posibles subproblemas del problema original.

Question 23

El algoritmo de Floyd-Warshall para calcular la distancia mínima entre todos los pares de nodos en un grafo se basa en:

Accepted Answer

Programación dinámica

Answer

Búsqueda en profundidad

Answer

Algoritmos voraces

Answer

Algoritmos de ordenación

Question 24

Para encontrar la ruta más corta desde un nodo de origen a un nodo de destino en un grafo ponderado usando programación dinámica, ¿qué paso NO es necesario?

Accepted Answer

Ordenar los nodos del grafo en orden ascendente de distancia al nodo de origen.

Answer

Definir subproblemas que representen las rutas más cortas desde el nodo de origen a cada nodo intermedio.

Answer

Calcular las soluciones a los subproblemas de forma recursiva, almacenando los resultados en una tabla.

Question 25

¿Cuál es la esencia del principio de optimalidad en la programación dinámica?

Accepted Answer

Una solución óptima para un problema global se compone de soluciones óptimas para sus subproblemas.

Answer

La solución óptima para un problema se encuentra al resolver todos sus subproblemas.

Answer

La solución óptima para un problema se encuentra al resolver el subproblema más grande.

Question 26

El algoritmo de Dijkstra para encontrar el camino más corto desde un nodo de origen a todos los demás nodos en un grafo ponderado está relacionado con la programación dinámica de la siguiente manera:

Accepted Answer

El algoritmo de Dijkstra utiliza un enfoque de programación dinámica para calcular las distancias mínimas desde el nodo de origen a cada nodo.

Answer

El algoritmo de Dijkstra no está relacionado con la programación dinámica.

Question 27

¿Qué tipo de problemas se pueden resolver con la técnica de la programación dinámica?

Accepted Answer

Problemas que se pueden dividir en subproblemas superpuestos y que poseen una propiedad de optimalidad.

Answer

Problemas con soluciones únicas.

Question 28

El principio de optimalidad en programación dinámica establece que:

Accepted Answer

La solución óptima a un problema se compone de soluciones óptimas a sus subproblemas.

Answer

La solución óptima a un subproblema nunca puede ser peor que la solución óptima al problema general.

Answer

La suma de las soluciones óptimas a los subproblemas siempre da la solución óptima al problema general.

Question 29

¿Cuál de las siguientes técnicas es fundamental en la programación dinámica?

Accepted Answer

Memoización

Answer

Búsqueda binaria

Answer

Programación lineal

Answer

Recursión

Question 30

El diagrama de recurrencia para el problema de Fibonacci usando programación dinámica se representa como:

Accepted Answer

F(n) = F(n-1) + F(n-2)

Answer

F(n) = n * F(n-1)

Answer

F(n) = F(n-1) * F(n-2)

Answer

F(n) = 2 * F(n-1) + F(n-2)

Question 31

La programación dinámica es especialmente útil para resolver problemas que:

Accepted Answer

Presentan subproblemas superpuestos

Answer

Requieren un gran espacio de memoria

Answer

Tienen un conjunto finito de soluciones

Answer

Son siempre de naturaleza lineal

Question 32

En programación dinámica, ¿qué representa un estado?

Accepted Answer

Una subestructura del problema, representada por sus parámetros

Answer

Una transformación aplicada a los valores del problema

Answer

Un valor calculado y almacenado para su uso posterior

Question 33

¿Cuál de las siguientes es una ventaja de la programación dinámica?

Accepted Answer

Puede resolver problemas complejos de manera eficiente

Answer

Es fácil de implementar

Answer

Funciona bien para todos los tipos de problemas

Question 34

El problema de la edición de distancia se utiliza para:

Accepted Answer

Comparar dos cadenas y determinar la secuencia mínima de operaciones para convertir una en la otra

Answer

Encontrar el camino más corto en un grafo

Question 35

La programación dinámica se basa en el concepto de dividir un problema complejo en subproblemas más pequeños. ¿Cuál es el enfoque clave de esta técnica para resolver estos subproblemas?

Accepted Answer

Resolver los subproblemas de forma óptima y almacenar sus soluciones para evitar cálculos repetidos.

Answer

Utilizar estructuras de datos dinámicas para almacenar soluciones a problemas.

Answer

Resolver los subproblemas en orden aleatorio y combinar sus soluciones.

Question 36

Para qué tipo de problemas es especialmente eficaz la programación dinámica?

Accepted Answer

Problemas que presentan subestructura óptima y subproblemas superpuestos.

Answer

Problemas con una única solución óptima global.

Answer

Problemas de ordenación de grandes conjuntos de datos.

Answer

Problemas de búsqueda en grafos no dirigidos.

Question 37

¿Cuál es la diferencia principal entre la programación dinámica ascendente (bottom-up) y descendente (top-down)?

Accepted Answer

La programación dinámica ascendente resuelve primero los subproblemas más pequeños y luego los combina para resolver el problema original, mientras que la descendente comienza con el problema original y lo divide recursivamente en subproblemas.

Answer

La programación dinámica ascendente es más eficiente que la descendente.

Answer

La programación dinámica descendente es más fácil de entender que la ascendente.

Question 38

De los siguientes problemas, ¿cuál NO se puede resolver eficazmente utilizando la programación dinámica?

Accepted Answer

Encontrar el camino más corto entre dos nodos en un grafo no dirigido y no ponderado.

Answer

Encontrar la ruta más corta en un grafo dirigido con pesos positivos.

Answer

Encontrar la subsecuencia común más larga entre dos cadenas.

Answer

Calcular el enésimo término de la secuencia de Fibonacci.

Question 39

En el contexto de la programación dinámica, ¿qué función cumple una tabla de memoización?

Accepted Answer

Almacena las soluciones a subproblemas ya calculados para evitar volver a calcularlos en el futuro.

Answer

Una tabla que muestra la complejidad espacial del algoritmo.

Answer

Una tabla que contiene todos los datos de entrada del problema.

Question 40

Tienes que encontrar la distancia mínima para convertir la cadena "gato" en "ratón" usando solo tres operaciones: insertar, eliminar o reemplazar una letra. ¿Qué algoritmo de programación dinámica se utiliza típicamente para resolver este problema?

Accepted Answer

Distancia de edición (Edit distance)

Answer

Problema de la mochila (Knapsack problem)

Answer

Subsecuencia común más larga (Longest common subsequence)

Answer

Algoritmo de Dijkstra

Question 41

Si se utiliza un algoritmo de programación dinámica para calcular el enésimo término de la secuencia de Fibonacci, ¿cuál es la complejidad temporal típica?

Accepted Answer

O(n)

Answer

O(2^n)

Answer

O(n^2)

Answer

O(log n)

Question 42

¿Cuál es la principal ventaja de utilizar la programación dinámica en comparación con la fuerza bruta para resolver un problema?

Accepted Answer

Reduce la complejidad temporal al evitar cálculos repetidos de subproblemas.

Answer

Siempre encuentra la solución óptima global.

Answer

Es más fácil de implementar que la fuerza bruta.

Question 43

Al aplicar la programación dinámica a un problema, ¿qué paso es fundamental para comenzar el proceso de diseño?

Accepted Answer

Identificar la subestructura óptima del problema y definir la relación de recurrencia.

Answer

Determinar la complejidad espacial del algoritmo.

Answer

Escribir el código del algoritmo en un lenguaje de programación específico.

Question 44

Una posible desventaja de utilizar la programación dinámica es:

Accepted Answer

Puede requerir una cantidad significativa de memoria para almacenar las soluciones a subproblemas, especialmente para problemas con grandes espacios de estados.

Answer

Siempre es menos eficiente que la fuerza bruta.