Estrategias de construcción de algoritmos - Análisis de algoritmos

Estrategias de construcción de algoritmos

Macarena Abarca

Análisis de algoritmos

Instituto IACC

28/05/2018

Desarrollo

1. Un programa de CAD, por ejemplo AutoCAD (diseño gráfico asistido por computador) es capaz de medir con gran precisión volúmenes de figuras muy complejas o irregulares.

 ¿Qué tipo de algoritmo cree Ud. que utilizan los programas de CAD: probabilístico (Montecarlo o Las Vegas) y si es determinístico o no determinístico? Justifique su respuesta de acuerdo a las características del algoritmo señalado.  

  Respuesta: Los programas CAD como lo es AutoCAD, es de tipo probabilistico(Las Vegas) y deterministico, ya que como es un software de diseño grafico, se necesita que sea exacto en los calculos que se realizan, la desventaja que tiene este tipo es el tiempo que puede demorar en la operación ya que asegura la respuesta correcta entre más tiempo trabaja en esta. Este software utiliza el tipo de algoritmo deterministico, desde el cual se puede predecir el estado de la ejecucion en todo momento, ya que este utiliza calculos matematicos para hacer dibujos y planos exactos por lo que siempre se podra saber el resultado de estos calculos incluso antes de terminar.

2. El método de la bisección es un método numérico para encontrar el punto en que una función cruza el eje X del plano cartesiano y utiliza un teorema llamado “teorema del valor intermedio”.  El teorema del valor intermedio dice que si f(x) es continua en el intervalo [a,b] y f(a) < f(b), entonces para cada z tal que f(a) < z < f(b), existe un m que pertenece a (a,b) tal que f(m) = z.  El método de la bisección señala, en particular que, si f(a) y f(b) tienen signos opuestos, entonces un valor intermedio es precisamente z = 0 y, por lo tanto, el teorema del valor intermedio asegura que debe existir un m tal que f(m) = 0.

 De acuerdo a lo planteado, desarrolle una solución informática de acuerdo a las estrategias de construcción de algoritmos, aplicando el método de la bisección:  

a) ¿Qué estrategia algorítmica (voraz, divide y vencerás o vuelta atrás) utilizaría? Justifique su respuesta.  

Respuesta: La estrategia que yo utilizaria seria la voraz, ya que como lo que se necesita es encontrar el punto X y como no es exacto se necesita que valla paso a paso el algoritmo buscando la mejor solucion a este problema.

b)  Describa brevemente las características fundamentales de la estrategia algorítmica escogida.

Respuesta: La estrategia que elegi que es voraz, tiene las siquientes características: en cada paso del algoritmo se evalúa la mejor solución, se pasa al siguiente paso y se vuelve a evaluar hasta solucionar todo el problema. Trata de resolver un problema encontrando un subconjunto de candidatos a respuesta correcta, según una serie de restricciones. Trabaja en etapas encontrando la mejor solución que le parezca sin importar las consecuencias futuras. Comprueba a los candidatos si son prometedores, si cumplirán con la respuesta buscada, si no los rechaza, Al final agregara a un candidato verificando si el conjunto es la solución.

...