¿Como se aplica el concepto de eficiencia a los algoritmos?

Se dice q un algoritmo es eficiente si produce los resultados sperados utilizando el menor tº 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éc 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 especifica q se ve influenciada por q factores?
Lo anterior y adicionalmente: Arquitectura subyacente, velocidad de procesadores, cantidad de memoria principal y secundaria, el lenguaje utilizado.
¿Por q es relevante dedicar tº al análisis de algoritmos?
Por q nos entrega una visión anticipada del comportamiento del uso de los recursos del sist. En función de un caso grl de un gran volumen de datos de entrada.
Para 2 algoritmos, ordenamiento y búsqueda respectivamente con las siguientes funciones de tº: Toe*(n2+20) y Toe+(500*n+20) ¿Cuál es la mas eficiente?

No es correcto hacer comparaciones de eficiencia para problemas distintos

A q situación particular corresponde la utilizada en el análisis de peor caso?
La q se produce cuando el conjunto de datos de entrada, independiente de su nº, se estructuran u organizan de tal forma que el algoritmo bajo análisis realiza el mayor nº de operaciones elementales.
Para la función de tº t(n)=500*n+20 y su correspondiente O-mayúscula O(n2) ¿cuáles son las constantes q satisfacen la definición de esta?

N0=501 C0=1

Para la función de tº t(n)= 500*n*n(n1/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(n2)+O(n3/2)+O(ln2(n)) ¿cuál es la O-mayúscula?
O(n2)

¿qué es lo q establece la definición de O-mayúscula en términos estrictamente prácticos?
Define una función q caracteriza el comportamiento de la función de tº ante el crecimiento del tamaño del problema acotándola superiormente.
¿Cuál seria 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, q es el q realmente se desea resolver, en partes.
¿Cuál seria una definición de algoritmos ávidos?
Consiste en una técnica de diseño de algoritmos en la q un problema de mayor envergadura es resuelto por partes dond cada una de estas, es resuelta a la vez tomando alguna decisión q no contempla el global del problema sino mas bien alguna carácterística q genera una solución q solo depende localmente de la parte q 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 q 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 mas directo?
Al disminuir o eliminar el recalculo necesariamente se disminuye el orden de complejidad del algoritmo v/s 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 q en c/u de estas se pueda resolver buscando una solución local aporte a la solución optima del problema.
¿Para que tipo de problemas genéricos es recomendable buscar una alternativa dinámica o ávida ?

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

Para un algoritmo de prog dinámica ¿Es de alguna importancia el orden en q se van generando las soluciones de c/u de las partes en q se subdivide el problema a resolver?
Es importante, pues es imprescindible generar en primer lugar las soluciones q 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 q permite conformar un algoritmo ávido consiste en?
Al ordenar las actividades con tº de termino creciente, se garantiza dejar siempre las actividades q dejan tiempo libres, posteriores a su termino, de mayor longitud primero, lo q permite simplificar la decisión q optimiza el resultado global a una comparación de actividades compatibles.
En el problema de la mochila fraccional, visto en clases ¿El criterio q permite conformar un algoritmo ávido consiste en?
Dado q el objetivo es maximizar el valor de la solución, se espera q al seleccionar en orden decendente aquellas especies q poseen un valor por unidad descedente 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 q permite conformar un algoritmo ávido consiste en?
No es correcto decir q tal problema se soluciona con un algoritmo ávido, pues su solución se realiza mediante prog dinámica.

Etiquetas: Algoritmos, algoritmos ávidos, Big O, complejidad, eficiencia, greedy, O-mayúscula, Programación Dinámica