10) ¿Qué es lo que establece la definición de O-mayúscula en términos estrictamente prácticos?
a. Define una función que, en términos aproximados, provee de valores para los tiempos de ejecución para tamaños de problemas específicos.
b. Define una función que sirve para predecir tiempos de ejecución para problemas de gran tamaño.
c. Define una función que caracteriza el comportamiento de la función de tiempo ante el crecimiento del tamaño del problema, acotándola superiormente.
d. Que para cierto tamaño del problema (n0) y desde allí en adelante, la función de tiempo queda acotada superiormente por la función de orden f(n) multiplicada por una constante (c0).
11) ¿Cuál sería una definición de programación dinámica?
a. Consiste en una técnica de diseño de algoritmos centrada básicamente en subdividir el problema a resolver y utilizar recurrencia para solucionar cada subproblema.
b. Consiste en una técnica de diseño de algoritmos centrada básicamente en resolver un problema mayor de forma acumulativa, en la que la aplicación sucesiva de toma de decisiones óptimas sobre subproblemas de este, tienden a generar la solución buscada.
c. Consiste en una técnica de diseño de algoritmos centrada básicamente en minimizar o eliminar la reiteración de la solución a subproblemas contenidos en otros subproblemas generados al subdividir un problema mayor, que es el que realmente se desea resolver, en partes.
12) ¿Cuál sería una definición de algoritmos ávidos?
a. Consiste en una técnica de diseño de algoritmos en la que un problema de mayor envergadura es resuelto por partes, donde cada una de estas es resuelta a la vez tomando alguna decisión que no contempla el global del problema, sino más bien alguna característica que genera una solución que solo depende localmente de la parte que se resuelve en cada momento.
b. Consiste en una técnica de diseño de algoritmos en la que se aplica una solución iterativa que contempla todo el conjunto de alternativas o variantes de orden o estructura de la entrada a fin de seleccionar la combinación que resuelva un problema de mayor envergadura.
c. Consiste en una técnica de diseño de algoritmos en la que se aplica un algoritmo recursivo, en la que cada recursión contempla o toma una parte o fracción de un problema de mayor envergadura y, al combinarlas, se soluciona dicho problema finalmente.
13) ¿Qué aspecto es fundamental para que se pueda aplicar programación dinámica en la solución de un problema?
a. Que se pueda subdividir el problema en partes de tal forma que en cada una de estas se pueda resolver buscando una solución local con la expectativa, no siempre cierta, de que dicha solución local aporte a la solución óptima del problema.
b. Que se pueda subdividir el problema en partes de tal forma que se pueda identificar y reutilizar soluciones de un subconjunto de estas en la solución de las restantes partes.
c. No hay aspecto alguno que sea fundamental, pues esta técnica puede utilizarse con seguridad en todo tipo de problemas.
14) ¿Qué ventaja pretende conseguir un algoritmo de programación dinámica frente a un enfoque más directo?
a. Al disminuir o eliminar el recálculo, necesariamente se disminuye el orden de complejidad del algoritmo versus un enfoque directo.
b. Al disminuir el tamaño de la entrada al problema principal, necesariamente se disminuye el orden de complejidad del algoritmo versus un enfoque directo.
c. Al simplificar el tipo y alcance de las decisiones, se puede avanzar rápidamente hacia una solución, lo que redunda en una disminución del orden de complejidad del algoritmo versus un enfoque directo.
15) ¿Qué aspecto es fundamental para que se pueda aplicar un algoritmo ávido en la solución de un problema?
a. Que se pueda subdividir el problema en partes de tal forma que en cada una de estas se pueda resolver buscando una solución local que aporte a la solución óptima del problema.
b. Que se pueda subdividir el problema en partes de tal forma que se pueda identificar y reutilizar soluciones de un subconjunto de estas en la solución de las restantes partes.
d. No hay aspecto alguno que sea fundamental, pues esta técnica puede utilizarse con seguridad en todo tipo de problemas.
16) ¿Para qué tipo de problemas genéricos es recomendable buscar una alternativa dinámica o ávida?
a. Problemas de cualquier índole, dado que ambos esquemas de diseño son aplicables siempre.
b. Problemas en los que una combinación del conjunto de valores de entrada es la que optimiza la solución.
c. Solo para problemas que se resuelven de manera directa utilizando un algoritmo recursivo.
17) Para un algoritmo de programación dinámica, ¿es de alguna importancia el orden en que se van generando las soluciones de cada una de las partes en que se subdivide el problema a resolver?
a. Es irrelevante, solo se debe generar tantas soluciones como se encuentren y evitar las repetidas.
b. Es importante, pues es imprescindible generar en primer lugar las soluciones que se sabe se repetirán en las restantes partes del problema a resolver.
c. Es irrelevante, pues en programación dinámica la cuestión a minimizar o simplificar son las decisiones que nos llevan de forma acumulada a resolver el problema principal.
18) En el problema de la selección de actividades, visto en clases, ¿el criterio que permite conformar un algoritmo ávido consiste en?
a. Al ordenar las actividades con tiempo de término creciente, se garantiza dejar siempre las actividades que dejan tiempos libres, posteriores a su término, de mayor longitud primero, lo que permite simplificar la decisión que optimiza el resultado global a una comparación de actividades compatibles.
b. El generar todas las combinaciones posibles de actividades compatibles permite finalmente elegir la combinación que optimiza el resultado global.
c. No es correcto decir que tal problema se soluciona con un algoritmo ávido, pues su solución se realiza mediante programación dinámica.
19) En el problema de la mochila fraccional, visto en clases, ¿el criterio que permite conformar un algoritmo ávido consiste en?
a. Generar el mayor conjunto de alternativas posible para distintas combinaciones de entrada que llenen la mochila, a fin de iterar sobre cada una de las combinaciones y elegir aquella que maximiza el valor de la solución.
b. Dado que el objetivo es maximizar el valor de la solución, se espera que al seleccionar en orden descendente aquellas especies que poseen un valor por unidad descendente hasta completar la capacidad de la mochila, se produzca la solución buscada.
c. No es correcto decir que tal problema se soluciona con un algoritmo ávido, pues su solución se realiza mediante programación dinámica.
20) Para el problema de la multiplicación encadenada de matrices, visto en clases, ¿el criterio que permite conformar un algoritmo ávido consiste en?
a. Generar las distintas alternativas de aparejamiento de matrices o grupos de matrices a fin de computar para cada una de estas el valor concreto de la cantidad de productos involucrados y, del total de combinaciones posibles, seleccionar aquella alternativa que minimice dichos productos.
b. El notar que algunas o muchas combinaciones de aparejamiento o agrupación forman parte de la solución de otras agrupaciones de mayor cuantía, al descubrir tal situación lo que debe hacerse es almacenar dichas soluciones y reutilizarlas posteriormente.
c. No es correcto decir que tal problema se soluciona con un algoritmo ávido, pues su solución se realiza mediante programación dinámica.
