test de muerte

Sea f(n) = 3n * 4. Dos de las tres afirmaciones siguientes prueban que f(n) ∈ O(n). ¿Cuál es la que no?. Para todo n > 4 se cumple que 3n + 4 < 4n. Para todo n > 4/(c-3), con c > 3, se cumple que 3n + 4 < cn. Para todo n < 4/(c-3), con c > 3, se cumple que 3n + 4 < cn.

Para resolver la versión simplificada del problema del encaminamiento óptimo, se ha diseñado la función met(m, n), que obtiene el mínimo tráfico de la red entre el servidor 0 y el n - 1 colocando, en el sitio más adecuado, m puertas de enlace. Para acelerarla, aplicamos la técnica de memoización. ¿Qué estructura del almacén será la más adecuada?. una tabla (dos índices). una vector (un índice). una constante (ningún índice).

¿Cuál es la complejidad temporal en el caso mejor del algoritmo que, dado un vector, nos dice cual de sus elementos quedaría en la posición k si lo ordenaramos por orden descendente de valor?. O(log n). O(n). O(n log n).

Tengo que sumar una larga lista de n cantidades diferentes y se me ha ocurrido que una manera de ganar tiempo es la siguiente estrategia recursiva: parto la lista en dos sublistas iguales, calculo su suma por separado usando la misma técnica y luego sumo las dos cantidades. Cuando al partir una lista me quedo con una cantidad solo, la suma es esa cantidad, y si me quedan cero cantidades, la suma es cero. ¿Gano tiempo, es decir, hago menos sumas?. No, en este caso el coste temporal es Θ(n log n). Sí, ya que en este caso el coste temporal se reduce a Θ(log n). No, ya que la complejidad temporal del metodo propuesto es la misma que la de ´ sumar una a una las cantidades.

Se pretende resolver el problema del encaminamiento óptimo (versión general) mediante ramificación y poda y para ello se hace uso de una cota que consiste en asumir que, independientemente de las puertas ya colocadas, los restantes nodos aún no tratados no van a ser puerta de enlace. ¿Que podemos decir de esta cota?. Que no es cota, ni optimista ni pesimista. Que es una cota optimista. Que es una cota pesimista.

Uno de estos tres algoritmos de ordenación no opera directamente sobre el vector, y necesita almacenamiento adicional para los elementos del mismo. ¿Cual es?. Mergesort. Heapsort. Quicksort.

Si lim n->∞ (f (n)/n^2) = 3 ¿cual de estas tres afirmaciones es cierta?. f(n) ∈ Ω (n^3). f(n) ∈ Θ (n^3). Las otras dos opciones son ambas falsas.

Indica cuál de los siguientes conjuntos es el conjunto O(f): a. b. c.

Se pretende resolver el problema del encaminamiento óptimo (versión general) mediante vuelta atrás. La solución se expresa mediante un vector x de n valores booleanos en el cual xi indica si se coloca una puerta en el i-ésimo servidor. Dado un nodo del árbol de búsqueda que se ha completado hasta la posición k del vector, ¿cual de los siguientes fragmentos de código obtiene una cota optimista correcta y, además, resulta ser la más rápida, en su cálculo, de entre las posibles alternativas válidas? (fíjate únicamente en el recorrido de los bucles, el resto es idéntico en las tres opciones. Descarta posibles opciones que no calculan una cota optimista correcta). a. b. c.

El elemento n-ésimo de la serie tribonacci, T(n), se define como sigue: T(n) = T(n - 3) + T(n - 2) + T(n - 1) para n >= 3; T(0) = 0; T(1) = 1 y T(2) = 1. ¿Cual de estas afirmaciones es falsa?. Una implementación ingenua de la función T(n), la cual llamaría a T(n-1), T(n - 2) y T(n - 3) tendría una complejidad prohibitiva por la repetición de cálculos que se produciría. Es posible una implementacion de programación dinámica iterativa con complejidad Θ(n). El problema no tiene una solución de programación dinámica iterativa pero se puede resolver añadiendo memoización al calculo recursivo ingenuo en el que el c alculo de T(n) comporta realizar las llamadas a T(n - 1), T(n - 2) y T(n - 3).

De la misma manera que en el problema original que se ha trabajado en las sesiones de practicas. No su puede pues, con la modificación planteada, no se cumple la propiedad de subestructura óptima. Como la distancia esta elevada al cuadrado, esta función no se puede calcular recursivamente.

Sobre el teorema de reducción: Que se cumpla es condicion necesaria para poder aplicar divide y vencer ´ as. Las otras dos opciones son ambas falsas. Que se cumpla es condicion necesaria para poder aplicar programaci ´ on din ´ amica.

De las siguientes situaciones, o bien dos son posibles y una no lo es, o bien al contrario, solo una es posible y las otras dos no lo son. Marca la que, en este sentido, es diferente a las demas. a. b. c.

¿Puede ocurrir que la solución recursiva de estilo “divide y vencerás” pero con memoización de un problema resuelva menos subproblemas que la mejor solución iterativa posible de programación dinámica?. No, nunca. Sí, porque la mejor solución iterativa posible de programación dinámica puede resolver subproblemas que no sean necesarios al resolver subproblemas posteriores. Sí, porque no existe garantía de que la mejor solución iterativa posible no resuelva problemas repetidos, mientras que la tecnica de memoización lo garantiza directamente mediante el uso de un almacén.

En la estrategia de ramificación y poda se usa una cola de prioridad para decidir en qué orden se expanden los nodos. Imaginemos un problema de optimización. ¿Puede ser que el valor por el cual se ordenan los nodos sea una cota pesimista del nodo?. Sí. No, porque para podar necesitamos una cota optimista. No, porque una cota pesimista es típicamente el valor que se encuentra en una de las hojas que cuelga del nodo.

Sobre la propiedad de subestructura óptima de un problema de optimización (por selección discreta): Es condición necesaria para poder aplicar divide y vencerás. Es condición necesaria para poder aplicar programación dinámica. Las otras dos opciones son ambas ciertas.

En cuanto a la complejidad temporal de la siguiente función, ¿cuál de las siguientes formulaciones expresa mejor su complejidad en el peor de los casos?. a. b. Las otras dos opciones son ambas falsas.

No. Debe resolverse usando una técnica de búsqueda y enumeración (vuelta atrás, ramificación y poda) ya que el problema no tiene subestructura óptima. Sí. El problema goza de subestructura óptima: podemos resolver el problema asumiendo que conocemos la solución para las m primeras ciudades y para p-1 puertos, determinar la posición óptima para que el puerto p sirva a las n - m ciudades restantes, y buscar el valor óptimo de m. No, pero el problema tiene una solución voraz exacta que consiste en empezar por asignar puerto a todos los núcleos de población e ir quitando uno a uno los puertos de manera que el tráfico que resulte de quitarlos aumente lo mínimo posible.

¿Cuál de las siguientes formulaciones expresa mejor la complejidad temporal, en función del parámetro n, de la siguiente función? (asumimos que n es potencia exacta de 2). a. b. c.

¿Cuál es el coste temporal de crear un montículo a partir de un vector no ordenado?. Θ(n). Θ(n log n). Ω(n log n) y O(n^2).

a. b. c.

a. b. c.

a. b. c.

a. b. c.

El algoritmo no devuelve en general la solución óptima del problema. El algoritmo no es voraz. El algoritmo siempre devuelve la solución óptima del problema.

a. b. c.

El algoritmo no devuelve en general la solución óptima del problema. El algoritmo no es voraz. El algoritmo siempre devuelve la solución óptima del problema.

a. b. c.

a. b. c.

Dado el problema del encaminamiento óptimo (versión simplificada), la siguiente función pretende encontrar la mejor ubicación de las puertas de enlace haciendo uso del almacén M. ¿Es correcta? Nota: la función pair<int, double>ogw(...) devuelve, respectivamente, la mejor ubicación de una puerta de enlace entre dos nodos; y el tráfico asociado a esa ubicación de la puerta de enlace). Sí, aunque solo resolvera ejemplos sencillos. No, ya que no resuelve todos los subproblemas necesarios. No, puesto que no sera posible extraer la mejor ubicación de las puertas a partir del almacén M.

Lleva la mochila llena hasta arriba y como mucho ha usado la sierra radial para cortar un queso. Los primeros quesos que ha cargado son, enteros, los quesos mas caros de toda la quesería. Lleva la mochila llena hasta arriba y ha usado la sierra radial mas de una vez para llevarse porciones bien calculadas de los quesos más caros.

Dado el problema del encaminamiento optimo (versión general), el valor que se obtiene con el método voraz es ... ... una cota superior para el valor óptimo, pero que nunca coincide con este. ... una cota inferior para el valor óptimo. ... una cota superior para el valor óptimo que a veces coincide con este.

a. b. c.

a. b. c.

a. b. c.

a. b. c.

a. b. c.

a. b. c.

a. b. c.

Teniendo en cuenta que ogw(k, n) obtiene el tráfico estimado si se coloca una sola puerta de enlace entre los nodos k y n - 1, ¿cuál de las siguientes recurrencias es la más apropiada para resolver la versión simplificada del problema del encaminamiento óptimo mediante divide y vencerás?. a. b. c.