Ejemplo de el Analisis de algiritmos

Control de la semana N°5

Carlos Castro Molina

Administración De Servicios

Instituto IACC

11.02.2018

Instrucciones

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.

El programa AutoCAD es una combinación de dos tipos de algoritmos como los son el Probabilístico (las vegas) y Determinístico, ya que es un software de diseño gráfico asistido por computador el cual utiliza dibujos 2D y modelado 3D, donde se realizan dibujos digitales de planos de edificios e imágenes en 3D, por lo tanto la matemática y desarrollo de problemas tiene que ser exacto, como nos indica el tipo de algoritmo probabilístico (las vegas) utiliza un método de probabilidades para calcular la exactitud a la respuesta del problema, la complicación de éste es que no siempre el tiempo en entregar la solución es la optima ya que asegura la respuesta correcta entre más tiempo trabaja en la respuesta, también este software utiliza algoritmo de tipo Determinístico el cual  siempre se puede predecir el estado en todo momento durante su ejecución, ya que utiliza números y operaciones matemáticas para el cálculos de los planos, donde siempre se puede saber a ciencia cierta el resultado de estos, en todo momento durante el algoritmo o incluso antes.

1. 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.

 Gráficamente el método de bisección se observa de la siguiente manera:  

[pic 2]

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:

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

Prácticamente el teorema del valor intermedio nos pide buscar un punto X entre los puntos A y B para eso es necesario calcular la pendiente de una recta que pasa por dos puntos, si la función es continua y derivable entre 2 puntos (A,B) existe un punto X, donde la pendiente tangente es igual a la pendiente de la recta que pasa por A y por B.

Para resolver este problema es necesario crear un algoritmo con la estrategia Voraz para encontrar la mejor solución al problema ya que el punto a buscar es X y no es exacto, entonces necesita ir paso a paso buscando la mejor solución al problema e ir descartando otros posibles resultados.

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

Esta estrategia de construcción de algoritmo busca la mejor solución a un problema en momentos, para así buscar una solución general, ésta la realiza paso a paso y en cada paso busca la mejor solución pasando al siguiente paso, así evaluar y nuevamente buscar la mejor solución hasta llegar a la respuesta del problema en general. este tipo de construcción de algoritmo tiene 4 puntos fundamentales considerado computacionalmente:

1 .- Trata de resolver un problema encontrando un subconjunto de candidatos a respuesta correcta, según una serie de restricciones.

2.-  Trabaja en etapas encontrando la mejor solución que le parezca sin importar las consecuencias futuras.

3.-  Comprueba a los candidatos si son prometedores, si cumplirán con la respuesta buscada, si no los rechaza.

4.- Finalmente agregara a un candidato verificando si el conjunto es la solución.

c) ¿Qué ventajas y desventajas advierte en la aplicación de la estrategia elegida (voraz, divide y vencerás o vuelta atrás), en este caso planteado? Describa brevemente dicha estrategia.

...