¿Cómo se aplica el concepto de eficiencia a los algoritmos?

Se dice que un algoritmo es eficiente si produce los resultados esperados utilizando el menor tiempo posible en concordancia con el total de datos a procesar.

¿Cuál es el objetivo del análisis de algoritmos?

Proveer de mecanismos y técnicas para evaluar, comparar y seleccionar estrategias de solución para problemas concretos en función de los recursos utilizados.

¿Un algoritmo traducido en un programa real y para un conjunto de datos de entrada reales, presenta una medida de tiempo de ejecución específica que se ve influenciada por qué factores?

Lo anterior y adicionalmente: arquitectura subyacente, velocidad de procesadores, cantidad de memoria principal y secundaria, el lenguaje utilizado.

¿Por qué es relevante dedicar tiempo al análisis de algoritmos?

Porque nos entrega una visión anticipada del comportamiento del uso de los recursos del sistema en función de un caso general de un gran volumen de datos de entrada.

Para 2 algoritmos, ordenamiento y búsqueda respectivamente con las siguientes funciones de tiempo: Toe*(n^2+20) y Toe+(500*n+20) ¿Cuál es el más eficiente?

No es correcto hacer comparaciones de eficiencia para problemas distintos.

¿A qué situación particular corresponde la utilizada en el análisis de peor caso?

La que se produce cuando el conjunto de datos de entrada, independiente de su número, se estructuran u organizan de tal forma que el algoritmo bajo análisis realiza el mayor número de operaciones elementales.

Para la función de tiempo t(n)=500*n+20 y su correspondiente O-mayúscula O(n^2) ¿cuáles son las constantes que satisfacen la definición de esta?

N0=501 C0=1

Para la función de tiempo t(n)= 500*n*n(n^(1/2)+1) ¿cuáles de las siguientes son sus O-mayúsculas? I. O(n^(3/2)) II. O(n^2) III. O(n^3)

I, II, III

Para la siguiente expresión: n*O(log(n))+O(n^2)+O(n^(3/2))+O(ln^2(n)) ¿cuál es la O-mayúscula?

O(n^2)

¿Qué es lo que establece la definición de O-mayúscula en términos estrictamente prácticos?

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.

¿Cuál sería una definición de programación dinámica?

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.

¿Cuál sería una definición de algoritmos ávidos?

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.

¿Qué aspecto es fundamental para que se pueda aplicar programación dinámica en la solución de un problema?

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.

¿Qué ventaja pretende conseguir un algoritmo de programación dinámica frente a un enfoque más directo?

Al disminuir o eliminar el recalculo necesariamente se disminuye el orden de complejidad del algoritmo versus un enfoque directo.

¿Qué aspecto es fundamental para que se pueda aplicar un algoritmo ávido en la solución de un problema?

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.

¿Para qué tipo de problemas genéricos es recomendable buscar una alternativa dinámica o ávida?

Problemas en los que una combinación del conjunto de valores de entrada es la que optimiza la solución.

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?

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.

En el problema de la selección de actividades, visto en clases, ¿el criterio que permite conformar un algoritmo ávido consiste en?

Al ordenar las actividades con tiempo de término creciente, se garantiza dejar siempre las actividades que dejan tiempo libre, 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.

En el problema de la mochila fraccionaria, visto en clases, ¿el criterio que permite conformar un algoritmo ávido consiste en?

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 o produzca la solución buscada.

Para el problema de la multiplicación encadenada de matrices, visto en clases, ¿el criterio que permite conformar un algoritmo ávido consiste en?

No es correcto decir que tal problema se soluciona con un algoritmo ávido, pues su solución se realiza mediante programación dinámica.