ALGORITMIA

¿Cuál es el objetivo de la etapa de análisis en el Diseño y Análisis de un Algoritmo?: Determinar el lenguaje y herramientas disponibles para su desarrollo. Estimar los recursos que consumirá el algoritmo una vez implementado. Estimar la potencia y características del equipo informático necesarios para el correcto funcionamiento del algoritmo.

¿Qué esquema algorítmico utiliza el algoritmo de ordenación Quicksort?. Divide y venceras. Programacion dinamica. backtracking.

Ante un problema que presenta una solución recursiva siempre podemos aplicar: Divide y venceras. programacion dinamica. ambas son correctas.

En cual de los siguientes casos no se puede aplicar el esquema Divide y Vencerás: se puede en ambos casos. subproblemas con tamaños muy diferentes. problema que no cumple principio de optimalidad.

Dado el algoritmo de búsqueda binaria, supongamos que, en vez de dividir la lista de elementos en dos mitades del mismo tamaño, la dividamos en dos partes de tamaños 1/3 y 2/3. El coste de este algoritmo: Es el mismo que el original. Es mayor que el del original. Es menor que el del original.

Si n es el número de elementos del vector, el coste del algoritmo Mergesort es: O( n^2 ) y Ω( n log(n) ). Θ( n log(n) ). Θ( n^2 ).

Un problema se puede resolver por Divide y Vencerás siempre que: Cumpla el principio de optimalidad. Cumpla el teorema de reducción. Ninguna de las anteriores.

Para implementar esta funcion podemos emplear. divide y venceras. programacion dinamica. cualquiera de las anteriores.

¿Qué implementación de entre las siguientes supone el menor coste?. divide y venceras. programacion dinamica. ambas tienen mismo coste asintotico.

El problema de la mochila, ¿Puede solucionarse de forma óptima empleando la estrategia de divide y vencerás?. solo para el caso de la mochila con fraccionamiento. solo para el caso de la mochila sin fraccionamiento. se puede aplicar para ambos casos.

La complejidad temporal en el mejor de los casos... ... es el tiempo que tarda el algoritmo en resolver la talla más pequeña que se le puede presentar. las demas opciones son verdaderas. ... es una función de la talla que tiene que estar definida para todos los posibles valores de ésta.

Sobre la complejidad temporal de la siguiente función: Ninguna de las otras dos alternativas es cierta. Las complejidades en los casos mejor y peor son distintas. El mejor de los casos se da cuando n≤1 y en tal caso la complejidad es constante.

¿Qué cota se deduce de la siguiente relación de recurrencia?. f(n)∈Θ(n^2). f(n)∈Θ(n). f(n)∈Θ(nlogn).

De las siguientes expresiones, o bien dos son verdaderas y una es falsa o bien al contrario: dos son falsas y una es verdadera. Marca la que en este sentido es distinta a las otras dos. 2n^3−10n^2+1∈O(n^3). n+n√n∈Ω(n). n+n√n∈Θ(n).

Si f1(n)∈O(g1(n)) y f2(n)∈O(g2(n)) entonces... Las otras dos alternativas son ciertas. 1(n)+f2(n)∈O(max(g1(n),g2(n))). f1(n)+f2(n)∈O(g1(n)+g2(n)).

La versión de Quicksort que utiliza como pivote la mediana del vector... ... no presenta caso mejor y peor distintos para instancias del mismo tamaño. ... es más eficiente si el vector ya está ordenado. ... es la versión con mejor complejidad en el mejor de los casos.

El siguiente fragmento del algoritmo de ordenación Quicksort reorganiza los elementos del vector para obtener una subsecuencia de elementos menores que el pivote y otra de mayores. Su complejidad temporal, con respecto al tamaño del vector v, que está delimitado por los valores pi y pf, es... ... lineal en cualquier caso. ... cuadrática en el peor de los casos. ... lineal en el caso peor y constante en el caso mejor.

Dada la siguiente relación de recurrencia, ¿Qué cota es verdadera?. f(n)∈Ω(2^n). f(n)∈Θ(n^2). f(n)∈Θ(2^n).

¿Cual es la solución a la siguiente relación de recurrencia?. f(n)∈Θ(logn). f(n)∈Θ(n/3). Ninguna de las otras dos es cierta.

Indica cuál es la complejidad, en función de n, del fragmento siguiente: O(log^2(n)). O(nlog(n)). O(n^2).

Indica cuál es la complejidad de la función siguiente: (los posibles resultados se expresan en función del tamaño del problema). O(n). O(n*log(n)). O(n^2).

¿Cuál de las formulaciones expresa mejor el coste temporal de la siguiente función?. Ce(n)=∑n/2 i=1(1+log2(i)). Ce(n)=∑n/2 i=1(log2(n/2)). Ce(n)=(∑n/2 i=1(1+log2(i)))/2.

La siguiente relación de recurrencia expresa la complejidad de un algoritmo recursivo, donde g(n) es una función polinómica: Di cuál de las siguientes afirmaciones es falsa: Si g(n)∈O(1) la relación de recurrencia representa la complejidad temporal del algoritmo de búsqueda dicotómica. Si g(n)∈O(n^2) la relación de recurrencia representa la complejidad temporal del algoritmo de ordenación por inserción binaria. Si g(n)∈O(n) la relación de recurrencia representa la complejidad temporal en el mejor caso del algoritmo de búsqueda del k-ésimo elemento más pequeño de un vector (estudiado en clase).

Los algoritmos de ordenación Quicksort y Mergesort tienen en común ... ... que ordenan el vector sin usar espacio adicional. ... que se ejecutan en tiempo O(n). ... que aplican la estrategia de divide y vencerás.

Si f∈Θ(g1) y f∈Θ(g2) entonces. Las otras dos opciones son ambas ciertas. f^2∈Θ(g1⋅g2). f∈Θ(max(g1,g2)).

Con respecto al parámetro n, ¿Cuál es la complejidad temporal de la siguiente función?. Θ(n^4). Θ(n^3). Θ(n^3log(n)).

Sea el vector v[8]={8,6,4,5,4,3,2,2}. Indica cuál de las siguientes opciones es cierta. (se asume la notación del lenguaje C/C++ en la que el primer elemento del vector está en la posición 0, es decir, en v[0]). El vector v no es un montículo máximo porque el elemento v[2]=4 debe ser ``hundido'' (desplazado hacia la derecha). El vector v no es un montículo máximo porque el elemento v[3]=5 debe ser ``flotado'' (desplazado hacia la izquierda). El vector v es un montículo máximo.

Con respecto a la complejidad espacial de los algoritmos de ordenación Quicksort, Heapsort y Mergesort y sin considerar el espacio que pueda ocupar las posibles pilas de recursión: Mergesort tiene complejidad espacial lineal con el tamaño del vector a ordenar, la de los otros dos es constante. Las complejidad espacial de todos ellos es lineal con el tamaño del vector a ordenar. Mergesort y Heapsort tienen complejidad espacial lineal con el tamaño del vector a ordenar, la de Quicksort es constante.

Se pretende ordenar un vector cuyos n elementos están organizados formando un montículo (Heap). Sin tener en cuenta el tiempo empleado para este preproceso. ¿Con qué coste temporal asintótico se podría realizar la ordenación?. O(nlogn). Ninguna de las otras dos opciones es la correcta. O(n).

En función del parámetro n, ¿Cuál es la complejidad temporal asintótica de la siguiente función?. Θ(2^n). Las otras dos opciones son ambas falsas. Θ(n^2).

La complejidad temporal en el mejor de los casos de un algoritmo recursivo... ... es la complejidad temporal de las instancias que están en el caso base. ninguna de las otras dos opciones es verdadera. ... coincide con el valor del caso base de la ecuación de recurrencia que expresa la complejidad temporal del algoritmo.

Con respecto al parámetro n, ¿Cuál es la complejidad temporal de la siguiente función?. Θ(n^3logn). Θ(n^2logn). Θ(n^3).

Los algoritmos de ordenación Quicksort y Mergesort... ... tienen el mismo coste temporal asintótico en el caso peor. ... tienen el mismo coste temporal asintótico en el caso mejor. ... tienen el mismo coste temporal asintótico tanto en el caso peor como en el caso mejor.

¿Qué algoritmo es asintóticamente más rápido, el Quicksort o el Mergesort?. el Mergesort es siempre más rápido o igual (salvo una constante) que el Quicksort. Los dos son igual de rápidos ya que el coste temporal asintótico de ambos es O(nlog(n)). como su nombre indica, el Quicksort.

Si f∈Ω(g1) y f∈Ω(g2) entonces. f∉Ω(min(g1,g2)). f∈Ω(g1+g2). f∈Ω(g1⋅g2).

La siguiente relación de recurrencia expresa la complejidad de un algoritmo recursivo, donde g(n) es una función polinómica: Si g(n)∈O(n) la relación de recurrencia representa la complejidad temporal del algoritmo de ordenación Mergesort. Si g(n)∈O(n^2) la relación de recurrencia representa la complejidad temporal del algoritmo de ordenación mediante inserción binaria. Si g(n)∈O(1) la relación de recurrencia representa la complejidad temporal del algoritmo de búsqueda dicotómica.

. g(n)=n. g(n)=nlogn. g(n)=n^2.

¿Cuál de las siguientes relaciones de recurrencia expresa mejor el número de llamadas recursivas que hace el algoritmo Mergesort?. T( n ) = n + T(n/2) para n > 1 y T( n ) = 1 para n < 2. T( n ) = 1 + 2T(n/2) para n > 1 y T( n ) = 1 para n < 2. T( n ) = n + 2T(n/2) para n > 1 y T( n ) = 1 para n < 2.

¿Cuál es la relación de recurrencia que representa la complejidad en el peor caso del algoritmo de búsqueda del k-ésimo elemento más pequeño de un vector?. A. B. C.

De las siguientes expresiones, o bien dos son verdaderas y una es falsa, o bien dos son falsas y una es verdadera. Marca la que (en este sentido) es distinta a las otras dos. Θ(log^2(n))=Θ(log^3(n)). Θ(log(n^2))=Θ(log(n^3)). Θ(log2(n))=Θ(log3(n)).

Se pretende obtener la complejidad temporal en el caso más desfavorable de la siguiente función. int exa (vector < int > & v){ int i, sum = 0, n = v.size(); if (n > 0){ int j = n; while (sum < 100 and j != 0 ){ j = j / 2; sum = 0; for (i = j; i < n; i++) sum += v[i]; } return j; } else return -1; }. A. B. C.

Di cuál de estos resultados de coste temporal asintótico es falsa: La búsqueda binaria en un vector ordenado requiere en el peor caso un tiempo en O(logn). La ordenación de un vector usando el algoritmo Quicksort requiere en el peor caso un tiempo en Ω(n^2). La ordenación de un vector usando el algoritmo Mergesort requiere en el peor caso un tiempo en Ω(n^2).

Tenemos un vector ordenado de tamaño no y un vector desordenado de tamaño nd y queremos obtener un vector ordenado con todos los elementos. ¿Qué será más rápido?. Insertar los elementos del vector desordenado (uno a uno) en el vector ordenado. Ordenar el desordenado y luego mezclar las listas. Depende de si no>nd o no.

Se pretende ordenar un vector cuyos n elementos están organizados formando un montículo (Heap). Sin tener en cuenta el tiempo empleado para este preproceso, ¿Con qué coste temporal asintótico se podría realizar la ordenación?. O(n). O(nlogn). Ninguna de las otras dos opciones es la correcta.

Se quieren ordenar n números distintos comprendidos entre 1 y m. Para ello se usa un array de m booleanos que se inicializan primero a false. A continuación se recorren los n números cambiando los valores del elemento del vector de booleanos correspondiente a su número a true. Por último se recorre el vector de booleanos escribiendo los índices de los elementos del vector de booleanos que son true. ¿Es este algoritmo más rápido (asintóticamente) que el Mergesort?. Sí, ya que el Mergesort es O(nlogn) y este es O(n). Sólo si nlogn>k⋅m (donde k es una constante que depende de la implementación). No, ya que este algoritmo ha de recorrer varias veces el vector de booleanos.

Los algoritmos de ordenación Quicksort y Mergesort tienen en común ... ... que aplican la estrategia de divide y vencerás. ... que ordenan el vector sin usar espacio adicional. ... que se ejecutan en tiempo O(n).