Algoritmos de aproximación

El concepto de aproximación en un algoritmo implica ...

• Encontrar la solución optima en un tiempo no mayor a un valor aproximado de acuerdo a los parametros del problema

• La posibilidad de encontrar una solución no óptima a un problema asegurando un máximo error posible comparado con su solución óptima

• Resolver un problema mediante una reduccion polinomial donde el problema original se transforma en otro de forma aproximada para resolver el problema

• La utilizacion de randomizacion en la construcción de un algoritmo que asegure que el problema se resuelva en un tiempo aproximado o que la solución sea aproximada

Un esquema de aproximación es ...

• un tipo de algoritmo de aproximación que permite mejorar la relación de aprixmación ajustando un parametro adicional

• Una representación gráfica de la relación de recurrencia en funcion del parametro ρ(n)

• el factor que como máximo puede diferir la solucion encontrada de la solución optima utilizando un cierto algoritmo de aproximación para cualquier instancia de ese problema

• un algoritmo de tipo greedy que nos permite minimizar el error de la solución de un problema de optimización

¿Cuál de los siguientes expresiones de complejidad temporal corresponde a un esquemas de aproximación totalmente polinomial en tiempo?

• Ninguno de ellos

• Todos ellos

Al resolver un problema con un algoritmo de aproximación NO es posible encontrar una solución óptima

• Falso

• Verdadero

• Depende si el problema es de optimazación o de decisión

La complejidad de un algoritmo de aproximación busca ser menor a la del algoritmo original conocido del problema

• Verdadero

• Falso

Una relación de aproximación ρ(n) corresponde ...

• al parametro ρ cuya modificación para un mismo tamaño de entrada n de un problema nos permite regular el maximo factor de error posible en la solución

• al factor que como máximo puede diferir la solucion encontrada de la solución optima utilizando un cierto algoritmo de aproximación para cualquier instancia de ese problema

• al cociente entre el valor de una solucion optima de un problema de optimizacion y el minimo error posible cometido utilizando un algoritmo de aproximación

• A la funcion ρ en funcion de n que nos indica a medida que aumenta el tamaño del problema en cuanto disminuye el error cometido de la solución

Un algoritmo de aproximación es del tipo

• Greedy

• División y conquista

• Programación dinámica

• Mejora incremental

• No tienen un tipo determinado

Cualquier algoritmo greedy que no  retorne una solución óptima corresponde a un algoritmo de aproximación para el problema

• Verdadero

• Falso

Cualquier problema que puede resolverse mediante fuerza bruta tambien puede resolverse mediante un algoritmo de aproximación

• Verdadero

• Falso

La algoritmos randomizados corresponden a un subconjunto de los problemas de aproximación

• Verdadero

• Falso