Optimización Combinatoria: Cuestionarios y Ejercicios Interactivos

Question 1

En la Optimización Combinatoria, ¿cuál de las siguientes afirmaciones es correcta?

Accepted Answer

Es un área de la optimización que se ocupa de problemas con conjuntos de soluciones discretas y finitas.

Answer

Es una rama de la optimización que emplea técnicas avanzadas de cálculo para resolver problemas de optimización continua.

Question 2

Un problema que se puede resolver en tiempo polinómico se clasifica como:

Accepted Answer

Problema P

Answer

Problema de optimización no lineal

Answer

Problema NP-completo

Answer

Problema NP-difícil

Question 3

Identifica cuál de los siguientes problemas es NP-completo:

Accepted Answer

Problema de la mochila

Answer

Optimización de funciones lineales

Answer

Asignación de recursos

Answer

Programación lineal

Question 4

Define qué es una heurística:

Accepted Answer

Un método para encontrar soluciones aproximadas para problemas difíciles en un tiempo razonable.

Answer

Una técnica que siempre conduce a la solución óptima.

Answer

Un algoritmo garantizado para encontrar una solución factible.

Question 5

La aproximación del avión de corte es una técnica empleada para:

Accepted Answer

Resolver problemas enteros lineales mixtos.

Answer

Generar soluciones iniciales para problemas de optimización no lineal.

Answer

Encontrar soluciones óptimas para problemas de grafos.

Question 6

¿Cuál de las siguientes opciones es un ejemplo de una aplicación de la Optimización Combinatoria en el mundo real?

Accepted Answer

Optimización de rutas de reparto

Answer

Predicción meteorológica

Answer

Reconocimiento de voz

Answer

Procesamiento de lenguaje natural

Question 7

En el contexto de la optimización, ¿qué es una cota inferior?

Accepted Answer

Un valor que es menor o igual que la solución óptima.

Answer

Un valor que es mayor o igual que la solución óptima.

Answer

Un valor que es siempre igual a la solución óptima.

Question 8

La relajación lagrangiana es un enfoque que:

Accepted Answer

Convierte un problema restringido en uno no restringido introduciendo variables adicionales y una función de penalización.

Answer

Proporciona una cota superior para la solución óptima.

Answer

Encuentra la solución óptima de un problema en un número finito de pasos.

Question 9

En la Optimización Combinatoria, el conjunto de soluciones posibles es:

Accepted Answer

Discreto y finito

Answer

Mixto (discreto y continuo)

Answer

Continuo e infinito

Question 10

Un problema NP-completo en Optimización Combinatoria se caracteriza por:

Accepted Answer

Su tiempo de resolución crece exponencialmente con el tamaño del problema.

Answer

Tiene un número finito de soluciones óptimas.

Answer

Siempre se puede resolver en tiempo polinómico.

Question 11

Una heurística en Optimización Combinatoria:

Accepted Answer

Busca soluciones aproximadas de forma rápida.

Answer

Siempre encuentra la solución óptima.

Answer

Es un método sistemático que garantiza la óptima.

Question 12

¿Cuál es una ventaja de los algoritmos de aproximación?

Accepted Answer

Encuentran soluciones satisfactorias en tiempos razonables.

Answer

Son fáciles de implementar pero lentos.

Answer

Siempre garantizan la solución óptima.

Question 13

Los algoritmos voraces en Optimización Combinatoria toman decisiones:

Accepted Answer

Basadas en la información actual, sin considerar las consecuencias futuras.

Answer

Basadas en la solución óptima global conocida.

Answer

Aleatoriamente, para explorar diferentes posibilidades.

Question 14

¿Cuál es la clase de complejidad del problema del conjunto de cobertura?

Accepted Answer

NP-completo

Answer

P

Answer

NP-difícil (pero no NP-completo)

Answer

NP-fácil

Question 15

¿Qué técnica se utiliza para resolver problemas de programación dinámica?

Accepted Answer

Descomposición en subproblemas

Answer

Programación lineal

Answer

Búsqueda en anchura

Answer

Aproximación aleatoria

Question 16

La función objetivo en Optimización Combinatoria representa:

Accepted Answer

La función a optimizar.

Answer

El algoritmo de resolución.

Answer

La mejor solución conocida.

Answer

Las restricciones del problema.

Question 17

¿En qué tipo de optimización se clasifica el problema de la mochila?

Accepted Answer

Optimización combinatoria

Answer

Optimización lineal

Answer

Optimización estocástica

Answer

Optimización continua

Question 18

¿Cuál de las siguientes afirmaciones define correctamente la Optimización Combinatoria?

Accepted Answer

Se centra en problemas de optimización con un conjunto discreto y finito de soluciones posibles.

Answer

Siempre encuentra soluciones óptimas para los problemas que resuelve.

Answer

Trata con problemas de optimización continuos.

Question 19

¿Qué característica define los problemas NP-completos?

Accepted Answer

La verificación de una solución candidata es computacionalmente difícil.

Answer

Se pueden resolver en tiempo polinomial.

Answer

Siempre tienen múltiples soluciones óptimas.

Question 20

Identifica una aplicación práctica de la Optimización Combinatoria:

Accepted Answer

Optimización de rutas de transporte

Answer

Cálculo gráfico

Answer

Reconocimiento de voz

Answer

Minería de datos

Question 21

¿A qué concepto se refiere la dificultad de encontrar soluciones óptimas en un tiempo razonable?

Accepted Answer

Intratabilidad

Answer

Complejidad

Answer

Coherencia

Answer

Convergencia

Question 22

Respecto a las heurísticas, ¿cuál de las siguientes afirmaciones es correcta?

Accepted Answer

Proporcionan soluciones aproximadas de manera eficiente.

Answer

Son complejas de implementar pero altamente eficientes.

Answer

Siempre encuentran soluciones óptimas.

Question 23

¿Cuál es el objetivo principal de la Optimización Combinatoria?

Accepted Answer

Encontrar soluciones óptimas o aproximadas para problemas discretos.

Answer

Resolver ecuaciones diferenciales

Answer

Probar hipótesis estadísticas

Question 24

En un problema de optimización combinatoria, el conjunto de soluciones posibles se define como:

Accepted Answer

Discreto y finito

Answer

Continuo y finito

Answer

Infinito y discreto

Answer

Infinito y continuo

Question 25

¿Qué tipo de problemas pertenecen a la clase NP-completos?

Accepted Answer

Problemas que no pueden resolverse en tiempo polinómico para todas las instancias

Answer

Problemas que se pueden resolver en tiempo lineal

Answer

Problemas que se pueden resolver en tiempo cuadrático

Question 26

En un problema de optimización combinatoria, ¿qué término describe la función que se desea optimizar?

Accepted Answer

Función objetivo

Answer

Algoritmo de resolución

Answer

Conjunto de soluciones posibles

Answer

Restricciones

Question 27

¿Cuál de los siguientes es un ejemplo de un problema de optimización combinatoria?

Accepted Answer

El problema del viajante

Answer

El cálculo del área de un círculo

Answer

La resolución de una ecuación de segundo grado

Answer

La suma de dos números enteros

Question 28

En optimización combinatoria, ¿qué es un algoritmo de aproximación?

Accepted Answer

Un algoritmo que encuentra soluciones con una garantía de estar dentro de un factor constante del óptimo

Answer

Un algoritmo que siempre encuentra la solución óptima

Question 29

¿Cuál de las siguientes afirmaciones describe una propiedad de los problemas NP-difíciles?

Accepted Answer

Son al menos tan difíciles como los problemas NP-completos

Answer

Se pueden resolver en tiempo polinómico para todas las instancias

Answer

Son más fáciles de resolver que los problemas NP-completos

Question 30

¿Qué se entiende por reducción polinómica en el contexto de la optimización combinatoria?

Accepted Answer

Una transformación que convierte un problema de optimización en otro cuyo resultado se puede utilizar para resolver el problema original

Answer

Una transformación que reduce el tiempo de resolución de un problema de optimización

Question 31

¿Cuál es el objetivo de la optimización combinatoria?

Accepted Answer

Encontrar la mejor solución posible para un problema de optimización con un conjunto finito y discreto de soluciones

Answer

Resolver ecuaciones algebraicas complejas

Question 32

En Optimización Combinatoria, el conjunto de soluciones posibles se caracteriza por ser:

Accepted Answer

Discreto y finito

Answer

Real y no negativo

Answer

Continuo e infinito

Answer

Cualquiera de los anteriores

Question 33

En el problema del viajante, ¿un nodo del grafo representa?

Accepted Answer

Una ciudad

Answer

Un camino

Answer

Una distancia

Answer

Un tiempo

Question 34

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

Accepted Answer

Resolver problemas de forma recursiva y almacenar soluciones parciales

Answer

Encontrar la solución óptima en un solo paso

Answer

Generar todas las soluciones posibles

Question 35

¿Qué algoritmo se destaca por su eficiencia en la resolución del problema de asignación?

Accepted Answer

Algoritmo húngaro

Answer

Algoritmo de Dijkstra

Answer

Algoritmo de Kruskal

Answer

Algoritmo de Floyd-Warshall

Question 36

En el problema de cobertura de conjuntos, ¿qué representa un conjunto de cobertura?

Accepted Answer

Un subconjunto que contiene al menos un elemento de cada conjunto en la colección

Answer

Un conjunto que contiene todos los elementos de la colección

Answer

Un conjunto que es disjunto a todos los demás conjuntos en la colección

Question 37

Respecto a los problemas NP-difíciles, ¿cuál de las siguientes afirmaciones es correcta?

Accepted Answer

Si existe un algoritmo polinómico para resolverlos, entonces P = NP

Answer

Son más fáciles de resolver que los problemas NP-completos

Answer

Siempre se pueden resolver en tiempo exponencial

Question 38

En el problema de partición, ¿cuál es el objetivo?

Accepted Answer

Dividir un conjunto de enteros en dos subconjuntos con suma igual

Answer

Encontrar el subconjunto más grande de un conjunto

Answer

Ordenar un conjunto de enteros

Question 39

En el contexto de la Optimización Combinatoria, ¿qué es una reducción?

Accepted Answer

Una transformación que convierte un problema en otro de dificultad conocida

Answer

Una estimación del valor óptimo de un problema

Answer

Un algoritmo garantizado para encontrar la solución óptima

Question 40

En el ámbito de la Optimización, ¿qué caracteriza a la Optimización Combinatoria?

Accepted Answer

Se enfoca en problemas donde el conjunto de soluciones posibles es discreto y finito.

Answer

Utiliza métodos iterativos para resolver problemas con funciones continuas.

Answer

Se centra en encontrar la mejor solución dentro de un conjunto infinito de opciones.

Question 41

Un problema se considera NP-difícil si:

Accepted Answer

Es al menos tan difícil de resolver como cualquier problema NP-completo.

Answer

Se trata de un problema de optimización con restricciones lineales.

Answer

Se puede resolver en tiempo polinómico con un algoritmo eficiente.

Question 42

El algoritmo voraz es una técnica heurística que:

Accepted Answer

Construye una solución paso a paso, seleccionando la mejor opción local en cada etapa.

Answer

Se aplica exclusivamente a problemas de optimización continua.

Answer

Garantiza encontrar la solución óptima en un tiempo razonable.

Question 43

¿Cuál de los siguientes problemas se clasifica como un problema de programación entera?

Accepted Answer

Asignar tareas a máquinas para minimizar el tiempo total de procesamiento, considerando que las tareas solo pueden ser asignadas a una máquina.

Answer

Resolver un sistema de ecuaciones lineales con coeficientes reales.

Answer

Encontrar la ruta más corta entre dos puntos en un mapa.

Question 44

La relajación lineal de un problema de programación entera:

Accepted Answer

Reemplaza las variables enteras por variables continuas, permitiendo una solución más fácil pero posiblemente no óptima para el problema original.

Answer

Aumenta la complejidad computacional del problema original.

Answer

Siempre garantiza encontrar la solución óptima al problema original.

Question 45

¿Cuál de las siguientes afirmaciones sobre la técnica de ramificación y poda es verdadera?

Accepted Answer

Es un método sistemático para explorar el espacio de soluciones de un problema de optimización combinatoria, descartando ramas no prometedoras.

Answer

Siempre encuentra la solución óptima en un tiempo finito para cualquier problema de optimización combinatoria.

Answer

Requiere que el problema tenga una función objetivo continua para su aplicación.

Question 46

Un metaheurístico se define como:

Accepted Answer

Un algoritmo de búsqueda que busca soluciones de alta calidad para problemas complejos, sin garantizar la optimalidad.

Answer

Un método para resolver exactamente problemas NP-completos en tiempo polinómico.

Answer

Un algoritmo determinista que siempre encuentra la solución óptima para cualquier problema.

Question 47

¿Cuál es una ventaja de utilizar la programación con restricciones (CP) para resolver problemas de optimización combinatoria?

Accepted Answer

Permite modelar problemas complejos con restricciones de forma declarativa, facilitando la formulación y la resolución.

Answer

Se aplica únicamente a problemas con funciones objetivo lineales.

Answer

Garantiza encontrar la solución óptima en tiempo polinómico para cualquier problema de CP.