Diseño de Algoritmos

En DyV si a=br entonces el orden es. V. F.

En la multiplicación de enteros grandes la mejora consiste en reducir las multiplicaciones de 5 a 3. V. F.

Con respecto a la técnica Divide y Vencerás: a. No debe existir solapamiento entre los subproblemas generados. b. Siempre se divide el problema principal en subproblemas de igual tamaño. c. El número de subproblemas y su tamaño no afecta a la eficiencia final del algoritmo.

El valor del umbral n0 vendrá dado de forma gráfica como: a. El punto de corte entre las gráficas de las funciones que representan el algoritmo clásico y el algoritmo DYV. b. El mínimo absoluto de la gráfica de la función que representa el algoritmo DYV. c. El mínimo absoluto de la gráfica de la función que representa el algoritmo clásico.

Si implementamos un algoritmo para multiplicar enteros grandes utilizando la técnica Divide y Vencerás y obtenemos la siguiente recurrencia: a. La multiplicación mediante el algoritmo clásico será más eficiente. b. La multiplicación mediante el algoritmo divide y vencerás será más eficiente. c. Con ambas técnicas se obtiene el mismo orden de eficiencia.

La búsqueda del mayor y menor elemento de un vector mediante la técnica de Divide y Vencerás tomando como valores de umbral n0=1 y n0=2 será: a. De un orden de eficiencia menor con n0=1. b. De un orden de eficiencia menor con n0=2. c. Tendrán la misma eficiencia con ambos umbrales.

Un problema ha sido resuelto con DYV. Si la ecuación de tiempos viene expresada por esta función. Entonces el orden exacto de complejidad del algoritmo es: a. b. c. d.

En la técnica de DyV: Los tamaños de los subproblemas han de ser de similar magnitud. Las funciones de descomposición y combinación han de ser polinomiales. El cáculo de umbral se realiza a posteriori.

Si en la división de un problema en subproblemas los tamaños están en la proporción de 1:n probablemente estaremos más cerca de poder usar Programación Dinámica que Divide y Vencerás. V. F.

El uso de Divide y Vencerás solamente proporciona algoritmos recursivos como solución de los subproblemas. V. F.

Las funciones de descomposición y combinación usadas en la técnica Divide y Vencerás han de ser eficaces. V. F.

El número de subproblemas en los que se descompone el problema original al aplicar la técnica Divide y Vencerás debe ser lo más grande posible para que estos sean lo más simples posible. V. F.

Podemos decir que el algoritmo recursivo diseñado para calcular el factorial de un número utiliza al 100% la técnica de diseño de algoritmos de Divide y Vencerás. V. F.

El umbral vendrá dado de forma gráfica como el punto de corte entre la función que representa el algoritmo clásico y la función del algoritmo DYV en la gráfica tamaño(n)- tiempos(t). V. F.

Al descomponer un problema utilizando DYV, cuantos más subproblemas obtengamos, mejor será la eficiencia final del algoritmo diseñado, ya que se reduce el tamaño de estos. V. F.

Un algoritmo DYV debe evitar seguir avanzando recursivamente cuando el tamaño de los casos ya no lo justifique. V. F.

En el problema de la búsqueda del máximo y del minimo elemento de un vector, la eficiencia del algoritmo resultante es igual tanto si se escogen como umbral los valores 1 o 2. V. F.

No existe ganancia en cuanto orden de complejidad si al implementar un algoritmo, utilizando la técnica DYV se obtiene la siguiente recurrencia: V. F.

La exponenciación discreta se puede considerar una operación elemental con números enteros grandes. V. F.

Un problema ha sido resuelto con DYV. Si la ecuación de tiempos viene expresada por la función siguiente, entonces el orden exacto de complejidad del algoritmo es cuadrático: T(n)={3n^2 si n≤n0 } {3T(n/2)+n^2 si n>n0 }. V. F.

En el problema de encontrar el k-ésimo elemento de un vector usando DyV se utiliza una estrategia parecida a la del algoritmo del mergesort. V. F.

El número de subproblemas en los que se descompone el problema original al aplicar la técnica Divide y Vencerás debe ser lo más grande posible para conseguir así que estos sean más simples. V. F.

Un algoritmo Divide y Vencerás debe avanzar recursivamente hasta obtener subproblemas de tamaño uno (caso base) que se solucionan aplicando el algoritmo clásico. V. F.

El valor del umbral vendrá dado de forma gráfica como el mínimo absoluto de la función del algoritmo clásico en la gráfica tamaño(n)–tiempos(t). V. F.

En el problema exponenciación discreta usando DyV se utiliza 1 como umbral. V. F.

Un problema ha sido resuelto con DYV. Si la ecuación de tiempos viene expresada por esta función. Entonces el orden exacto de complejidad del algoritmo es: T(n)={3n^2 si n≤n0 } {3T(n/2)+n^2 si n>n0 }. Θ(n^2). Θ(n^2 log2 n). Θ(n^log2 3). Ninguna de las anteriores.

Para un vector V[1..n] de elementos que se pueden ordenar, se desean hallar los m elementos más pequeños. ¿Cuál de las siguientes alternativas sería más eficiente?. Ordenar primeroV y después coger los m primeros elementos. Ir seleccionado en primer lugar el primer elemento más pequeño, después el segundo y así sucesivamente hasta el elemento m-ésimo. La eficiencia depende de los valores de n y de m.

Supongamos que tenemos los siguientes órdenes de eficiencia: Ordenados, de menor a mayor quedarían: a. b. c.

¿Qué calcula la siguiente función recursiva?. La suma de a y b. La resta de a y b. la suma de los dígitos de a.

¿Qué ocurre si en la función Reordenar(V: vector; i,j: TPosicion; pivote:TElemento) que utiliza el Quicksort se cambia la llamada a la función Cambiar(V, inf, sup) y se sitúa al final del bucle?. Se incrementa la eificiencia del algoritmo. No pasa nada. El algoritmo es funcional igual. El algoritmo no funciona correctamente.

El caso general de la función de tiempos de la siguiente función recursiva es: FUNCION ejer_b (x: entero; n:entero) : entero; Inicio SI x = 0 ENTONCES ejer_b <- n SI_NO ejer_b <- 2 * ejer_b (x -1, n div 2) + ejer_b (x - 2, n div 2)+ n; Fin;. t(n) = t(n-1) + t(n-2) + c n>0. t(n) = 2*t(n-1) + t(n-2) + c n>0. t(n) = 2 * t(n /2) + c n>0.

la Búsqueda Binaria Recursiva: Consume más memoria que la Búsqueda Binaria Iterativa. Es un ejemplo en el que se ponen plenamente de manifiesto los fundamentos de la técnica Divide y Vencerás. Obtiene la solución antes que la Búsqueda Binaria Iterativa.

La técnica de resolución de problemas Divide y Vencerás consiste en: Dividir el problema en subproblemas y resolver cada uno de ellos. Obtener un subproblema de tamaño menor y solucionarlo recursivamente. Dividir un problema de tamaño n en dos subproblemas de tamaño n/2 y resolver cada uno de ellos de forma recursiva.

En el algoritmo de ordenación Mergesort: La mayor parte del trabajo no recursivo se invierte en combinar las soluciones parciales obtenidas. El mejor pivote que se podría utilizar es la mediana, pero no se utiliza porque motivos de eficiencia. Fue propuesto por Hoare y se basa en la técnica Divide y Vencerás.

Con respecto a los algoritmos de Ordenación basados en DyV, ¿Cuál de las siguientes afirmaciones es falsa?: El Mergesort es igual de eficiente que el Quicksort. Se diferencian en la forma en la que dividen el vector original en subvectores. Ambos utilizan la función de Mezcla para obtener el vector ordenado a partir de los subvectores ya ordenados.

El algoritmo de Búsqueda Binaria,. Realiza, en el peor de los casos, int[lg2 n] +1 comparaciones (siendo n el número de elementos del vector). Siempre encuentra el elemento a buscar antes que el algoritmo de Búsqueda Secuencial. Es menos eficiente que el algoritmo de Búsqueda Secuencial si el elemento a buscar no se encuentra en el vector.