Cuestionario 27 AED

Para cada uno de los algoritmos o procesos listados en la columna de la izquierda, seleccione la expresión de orden que mejor describe su tiempo de ejecución en el peor caso. Dado un arreglo v con n componentes, ordenarlo de menor a mayor mediante el algoritmo de selección directa. O(n^2) (léase: "orden n al cuadrado"). O(n^3) (léase: "orden n al cubo"). O(1). O(log(n)). O(n).

Para cada uno de los algoritmos o procesos listados en la columna de la izquierda, seleccione la expresión de orden que mejor describe su tiempo de ejecución en el peor caso. Dadas dos matrices de orden n*n, obtener la matriz producto aplicando el método tradicional. O(n^2) (léase: "orden n al cuadrado"). O(n^3) (léase: "orden n al cubo"). O(1). O(log(n)). O(n).

Para cada uno de los algoritmos o procesos listados en la columna de la izquierda, seleccione la expresión de orden que mejor describe su tiempo de ejecución en el peor caso. Dado un arreglo v con n componentes, acceder y cambiar el valor del casillero v[k] (con 0 <= k <= n-1). O(n^2) (léase: "orden n al cuadrado"). O(n^3) (léase: "orden n al cubo"). O(1). O(log(n)). O(n).

Para cada uno de los algoritmos o procesos listados en la columna de la izquierda, seleccione la expresión de orden que mejor describe su tiempo de ejecución en el peor caso. Dado un arreglo ya ordenado v con n componentes, buscar un valor x aplicando búsqueda binaria. O(n^2) (léase: "orden n al cuadrado"). O(n^3) (léase: "orden n al cubo"). O(1). O(log(n)). O(n).

Para cada uno de los algoritmos o procesos listados en la columna de la izquierda, seleccione la expresión de orden que mejor describe su tiempo de ejecución en el peor caso. Dado un arreglo v con n componentes, buscar un valor x aplicando búsqueda secuencial. O(n^2) (léase: "orden n al cuadrado"). O(n^3) (léase: "orden n al cubo"). O(1). O(log(n)). O(n).

¿Cuántas comparaciones en el peor caso obliga a hacer una búsqueda secuencial en una lista ordenada (o en un arreglo ordenado) que contenga n valores?. Peor caso: O(1) comparaciones. Peor caso: O(log(n)) comparaciones. Peor caso: O(n) comparaciones. Peor caso: O(n^2) comparaciones.

¿Cuál es la diferencia entre el peor caso y el caso promedio en el análisis de algoritmos?. El peor caso es la configuración de datos de entrada más desfavorable para el algoritmo, mientras que el caso promedio describe una configuración de datos pensada para favorecer al algoritmo. El peor caso es la configuración de datos de entrada más favorable para el algoritmo, mientras que el caso promedio describe una configuración aleatoria de datos (no pensada ni para favorecer ni para desfavorecer al algoritmo). El peor caso es la configuración de datos de entrada más desfavorable para el algoritmo, mientras que el caso promedio describe una configuración aleatoria de datos (no pensada ni para favorecer ni para desfavorecer al algoritmo). El peor caso es la configuración de datos de entrada más favorable para el algoritmo, mientras que el caso promedio describe una configuración de datos pensada para desfavorecer al algoritmo.

¿Cuáles de los siguientes son factores de eficiencia comunes a considerar en el análisis de algoritmos? (Más de una respuesta puede ser válida... marque todas las que considere correctas). El tiempo de ejecución. El consumo de memoria. La complejidad aparente del código fuente. La calidad aparente de la interfaz de usuario.

¿Qué significa decir que un algoritmo dado tiene un tiempo de ejecución O(1)?. El tiempo de ejecución es logarítmico: a medida que aumenta el número de datos, aumenta el tiempo pero en forma muy suave. El tiempo de ejecución siempre es de un segundo, sin importar la cantidad de datos. El tiempo de ejecucíón es constante, sin importar la cantidad de datos. El tiempo de ejecución es lineal: si aumenta el número de datos, aumenta el tiempo en la misma proporción.

¿Qué significa decir que un algoritmo dado tiene un tiempo de ejecución O(n )?. El tiempo de ejecucíón es constante, sin importar la cantidad de datos. A medida que aumenta el número de datos, aumenta el tiempo pero en forma muy suave: el conjunto de datos se divide en dos. se procesa una de las mitades, se desecha la otra y se repite el proceso hasta que no pueda volver a dividirse la mitad que haya quedado. El proceso normalmente consiste en dos ciclos (uno dentro del otro) de aproximadamente n iteraciones cada uno, de forma que las operaciones críticas se aplican un número cuadrático de veces. El tiempo de ejecución es lineal: si aumenta el número de datos, aumenta el tiempo en la misma proporción.

¿Qué significa decir que un algoritmo dado tiene un tiempo de ejecución O(n)?. A medida que aumenta el número de datos, aumenta el tiempo pero en forma muy suave: el conjunto de datos se divide en dos. se procesa una de las mitades, se desecha la otra y se repite el proceso hasta que no pueda volver a dividirse la mitad que haya quedado. El tiempo de ejecucíón es constante, sin importar la cantidad de datos. El proceso normalmente consiste en dos ciclos (uno dentro del otro) de aproximadamente n iteraciones cada uno, de forma que las operaciones críticas se aplican un número cuadrático de veces. El tiempo de ejecución es lineal: si aumenta el número de datos, aumenta el tiempo en la misma proporción.

¿Qué significa decir que un algoritmo dado tiene un tiempo de ejecución O(log(n))?. El tiempo de ejecucíón es constante, sin importar la cantidad de datos. A medida que aumenta el número de datos, aumenta el tiempo pero en forma muy suave: el conjunto de datos se divide en dos. se procesa una de las mitades, se desecha la otra y se repite el proceso hasta que no pueda volver a dividirse la mitad que haya quedado. El tiempo de ejecución es lineal: si aumenta el número de datos, aumenta el tiempo en la misma proporción. El proceso normalmente consiste en dos ciclos (uno dentro del otro) de aproximadamente n iteraciones cada uno, de forma que las operaciones críticas se aplican un número cuadrático de veces.

Suponga que dispone de cuatro algoritmos diferentes para resolver el mismo problema, y que se sabe que los tiempos de ejecución (en el peor caso) son, respectivamente: O(n*log(n)), O(n^2), O(n^3) y O(n). ¿Cuál de esos tres algorimos debería elegir, suponiendo que todos hacen el mismo consumo razonable de memoria?. El algoritmo cuyo tiempo de ejecución es O(n^2). El algoritmo cuyo tiempo de ejecución es O(n^3). El algoritmo cuyo tiempo de ejecución es O(n*log(n)). El algoritmo cuyo tiempo de ejecución es O(n).

¿Con qué nombre general se conoce en la Teoria de la Complejidad a un problema para el cual sólo se conocen algoritmos cuyo tiempo de ejecución es exponencial (o sea, problemas para los que todas las soluciones conocidas son algoritmos con tiempo O(2^n)?. Problemas Intratables. Problemas Irresolubles. Problemas Inmanejables. Problemas Imperdonables.

En la columna de la izquierda se muestra el código fuente en Python de diversos procesos sencillos. Para cada uno de ellos, seleccione de la lista de la derecha la expresión en notación Big O que mejor describa el tiempo de ejecución de cada proceso para el peor caso. (Aclaración: una expresión como n^2 debe entenderse como "n al cuadrado" o n ). n = int(input('N: ')) ac = 0 for i in range(n): ac += i print(ac). O(n). O(1). O(n^3). O(n^2).

En la columna de la izquierda se muestra el código fuente en Python de diversos procesos sencillos. Para cada uno de ellos, seleccione de la lista de la derecha la expresión en notación Big O que mejor describa el tiempo de ejecución de cada proceso para el peor caso. (Aclaración: una expresión como n^2 debe entenderse como "n al cuadrado" o n ). ac = 0 for i in range(10): ac += i print(ac). O(n). O(1). O(n^3). O(n^2).

En la columna de la izquierda se muestra el código fuente en Python de diversos procesos sencillos. Para cada uno de ellos, seleccione de la lista de la derecha la expresión en notación Big O que mejor describa el tiempo de ejecución de cada proceso para el peor caso. (Aclaración: una expresión como n^2 debe entenderse como "n al cuadrado" o n ). n = int(input('N: ')) ac = 0 for i in range(n): for j in range(i+1, n): ac += i*j for i in range(n): for j in range(n): for k in range(n): ac += (i+j+k) print(ac). O(n). O(1). O(n^3). O(n^2).

En la columna de la izquierda se muestra el código fuente en Python de diversos procesos sencillos. Para cada uno de ellos, seleccione de la lista de la derecha la expresión en notación Big O que mejor describa el tiempo de ejecución de cada proceso para el peor caso. (Aclaración: una expresión como n^2 debe entenderse como "n al cuadrado" o n ). n = int(input('N: ')) ac = 0 for i in range(n): for j in range(i+1, n): ac += i*j print(ac). O(n). O(1). O(n^3). O(n^2).

Analice el siguiente esquema de una función en Python: def procesar(n, m): for i in range(n+1): for j in range(m+1): # ... acciones sencillas a realizar... # ... suponga que no hay otro ciclo aquí... # ... y que sólo aparecen operaciones de tiempo constante... ¿Cuál de las siguientes expresiones de orden describe mejor el tiempo de ejecución de esta función en el peor caso?. O(n*n). O(n*m). O(n). O(m).

Si se realiza un análisis preciso del ordenamiento por Selección Directa para un arreglo de n componentes, se llega a la conclusión que ese algoritmo hará n-1 pasadas, con n-1 comparaciones en la primera, n-2 en la segunda, y así sucesivamente reduciendo de a 1 la cantidad de comparaciones hasta hacer sólo una comparación en la última pasada. Por lo tanto, el algoritmo hará invariablemente una cantidad total de ½(n - n) comparaciones. Sabiendo esto, ¿cuáles de las siguientes expresiones son correctas para describir la cantidad de comparaciones que hará el algoritmo, usando distintos tipos de notaciones? (Más de una respuesta puede ser correcta. Marque TODAS las que considere correctas). Cantidad de comparaciones: O(n^2). Cantidad de comparaciones: o(n^2). Cantidad de comparaciones: Ω(n^2). Cantidad de comparaciones: Θ(n^2).

¿Cuál es la principal característica de todos los métodos de ordenamiento conocidos como métodos simples o directos?. Son muy fáciles de programar. Son muy veloces para cualquier tamaño del arreglo a ordenar. Tienen un tiempo de ejecución de orden cuadrático en el peor caso. Tienen un tiempo de ejecución de orden lineal en el peor caso.

¿Cuáles de las siguientes son características correctas del algoritmo Shellsort? (Más de una puede ser cierta... marque TODAS las que considere válidas). El algoritmo Shellsort consiste en una mejora del algoritmo de Inserción Directa (o Inserción Simple), consistente en armar suconjuntos ordenados con elementos a distancia h > 1 en las primeras fases, y terminar con h = 1 en la última. El algoritmo Shellsort es complejo de analizar para determinar su rendimientos en forma matemática. Se sabe que para la serie de incrementos decrecientes usada en la implementación vista en las clases de la asignatura, tiene un tiempo de ejecución para el peor caso de O(n^1.5). En el caso promedio, el algoritmo Shellsort es tan eficiente como el Heapsort o el Quicksort, con tiempo de ejecución O(n*log(n)). El algoritmo Shellsort consiste en una mejora del algoritmo de Selección Directa, consistente en buscar iterativamente el menor (o el mayor) entre los elementos que quedan en el vector, para llevarlo a su posición correcta, pero de forma que la búsqueda del menor en cada vuelta se haga en tiempo logarítmico.

¿Qué diferencia existe entre el conteo exhaustivo de operaciones críticas y el análisis asintótico del comportamiento de una función en el análisis de algoritmos?. Ninguna. Ambas se refieren a la misma técnica básica del análisis de algoritmos. El conteo exhaustivo busca determinar una expresión o fórmula que exprese de manera rigurosa la cantidad de operaciones críticas que lleva a cabo un algoritmo, mientras que el análisis asintótico busca determinar el comportamiento general de una función para valores muy grandes del tamaño del problema. El análisis asintótico busca determinar una expresión o fórmula que exprese de manera rigurosa la cantidad de operaciones críticas que lleva a cabo un algoritmo, mientras que el conteo exhaustivo busca determinar el comportamiento general de una función para valores muy grandes del tamaño del problema. El conteo exhaustivo busca determinar una expresión o fórmula que exprese de manera rigurosa la cantidad de operaciones críticas que lleva a cabo un algoritmo, mientras que el análisis asintótico busca determinar una expresión o fórmula que exprese de manera rigurosa la cantidad de operaciones no críticas que lleva a cabo un algoritmo.

¿Qué se entiende, en el contexto del Análisis de Algoritmos, por un Orden de Complejidad?. Un conjunto o familia de funciones matemáticas que se comportan asintóticamente de la misma forma. Un conjunto o familia de algoritmos que resuelven el mismo problema. Un conjunto o familia de subrutinas con similares objetivos (equivalente al concepto de módulo). Un conjunto de datos ordenados.

Si los algoritmos de ordenamiento simples tienen todos un tiempo de ejecución O(n ) en el peor caso, entonces: ¿cómo explica que las mediciones efectivas de los tiempos de ejecución de cada uno sean diferentes frente al mismo arreglo?. La notación Big O rescata el término más significativo en la expresión que calcula el rendimiento, descartando constantes y otros términos que podrían no coincidir en los tres algoritmos. Los tiempos deben coincidir. Si hay diferencias, se debe a errores en los intrumentos de medición o a un planteo incorrecto del proceso de medición. La notación Big O no se debe usar para estimar el comportamiento en el peor caso, sino sólo para el caso medio. La notación Big O no se usa para medir tiempos sino para contar comparaciones u otro elemento de interés. Es un error, entonces, decir que los tiempos tienen "orden n cuadrado".

Se tiene un algoritmo que realiza cierta cantidad de procesos sobre un conjunto de n datos y un minucioso análisis matemático ha determinado que la cantidad de procesos que el algoritmo realiza en el peor caso viene descripto por la función f(n) = 3n^3 + 5n^2 + 2n^1.5 ¿Cuál de las siguientes expresiones representa mejor el orden del algoritmo para el peor caso?. O(3n^3 + 5n^2 + 2n^1.5). O(n^1.5). O(n^3 + n^2). O(n^3).

¿Cuáles de las siguientes son correctas en cuanto a los tiempos de ejecución de los algoritmos de ordenamiento clásicos? (Más de una puede ser cierta... marque TODAS las que considere válidas). Algoritmo Quick Sort: O(n*log(n)) en el caso promedio, pero O(n^2) en el peor caso. Algoritmos directos o simples: O(n^2) en el peor caso para todos ellos. Algoritmo Heap Sort: O(n*log(n)) tanto para el caso promedio como para el peor caso. Algoritmo Shell Sort: O(n^2) en el peor caso para la serie de incrementos decrecientes vista en clase.