Teoría de Algoritmos

Enviado por Programa Chuletas y clasificado en Otras materias

Escrito el en español con un tamaño de 6,41 KB

 
¿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 solucion para problemas concretos en funcion 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 vision anticipada del comportamiento del uso de los recursos del sist. En funcion 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 funcion de tº t(n)=500*n+20 y su correspondiente O-mayuscula O(n2) ¿cuáles son las constantes q satisfacen la definición de esta?
N0=501 C0=1

Para la funcion de tº t(n)= 500*n*n(n1/2+1) ¿cuáles de las siguientes son sus O-mayusculas? 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-mayuscula?
O(n2)

¿qué es lo q establece la definición de O-mayuscula en terminos estrictamente practicos?
Define una funcion q caracteriza el comportamiento de la funcion 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 avidos?
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 característica q genera una solucion q solo depende localmente de la parte q se resuelve en cada momento.

¿Qué aspecto es fundamental para que se pueda aplicar programación dinamica en la solucion 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 solucion de las restantes partes.

¿Qué ventaja pretende conseguir un algoritmo de programación dinamica 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 avido en la solucion 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 solucion local aporte a la solucion optima del problema.

¿Para que tipo de problemas genericos es recomendable buscar una alternativa dinamica o avida ?
Problemas en los q una combinación del conjunto de valores de entrada es la q optimiza la solucion.

Para un algoritmo de prog dinamica ¿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 avido 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 avido consiste en?
Dado q el objetivo es maximizar el valor de la solucion, 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 solucion buscada.

Para el problema de la multiplicación encadenada de matrices, visto en clases ¿El criterio q permite conformar un algoritmo avido consiste en?
No es correcto decir q tal problema se soluciona con un algoritmo avido, pues su solucion se realiza mediante prog dinamica.

Entradas relacionadas: