Tipos de Algoritmos

Tipos de Algoritmos

1. Algoritmos Voraces

2. Algoritmos Voraces

   • ¿Cómo funciona?
     • Este algoritmo funciona al resolver un determinado problema de manera óptima, además funciona siguiendo una serie de procedimientos o características hasta llegar a la solución máxima o mínima.
   • Características
     • Su algoritmo voraz procede por pasos.
     • Utiliza la función de selección.
     • Debe existir una función, la función objetivo, que es la que hay que minimizar o maximizar.
   • ¿Para qué sirve?
     • Sirve para determinar la función de selección, definir la función factible y definir qué caracteriza a una solución del problema.
   • Ventajas/Desventajas
     • Es bastante fácil de llegar a un algoritmo voraz para un problema.
     • Analizando el tiempo de ejecución de los algoritmos voraces generalmente será mucho más fácil que el de otras técnicas.
     • Su principal desventaja es que tendremos que trabajar mucho más para entender los problemas de los algoritmos voraces.
   • Ejemplo
     • Se trata de devolverle a Juan una cantidad de pesetas con el menor número posible de monedas. – Se parte de: u un conjunto de tipos de monedas válidas, de las que se supone que hay cantidad suficiente para realizar el desglose

3. Divide y Vencerás

   • ¿Cómo funciona?
     • Este algoritmo funciona separando un problema en subproblemas que se parecen al problema original
   • ¿Para qué sirve?
     • Su uso o mayor objetivo es descomponer un problema para poder resolver su problema original.
   • Ventajas/Desventajas
     • Resolución de problemas complejos.
     • Eficiencia del algoritmo.
     • La principal desventaja de este método es su lentitud en la repetición del proceso recursivo.
   • Ejemplo
     • Este algoritmo «DivideyVenceras» va reduciendo en mitades el vector para conseguir el mayor elemento de cada mitad y así sucesivamente hasta llegar al vector completo. Finalmente, se compara que máximo de cada parte es mayor de los dos y éste sería el mayor elemento del vector.

4. Programación Dinámica

   • ¿Cómo funciona?
     • Se utiliza cuando se tienen problemas que se pueden dividir en subproblemas similares, de modo que sus resultados puedan ser reutilizados.
   • Características
     • Subproblemas optímales: La solución óptima a un problema puede ser definida en función de soluciones óptimas a óptimas a subproblemas de tamaño menor
     • Solapamiento entre subproblemas: Al plantear la solución recursiva del problema, un mismo problema se resuelve más de una vez.
     • Enfoque ascendente ( Enfoque ascendente (bottom-up): Primero se calculan las soluciones óptimas para problemas de tamaño pequeño. Luego, utilizando dichas soluciones, encuentra soluciones a problemas de mayor tamaño.
   • ¿Para qué sirve?
     • Caracterizar la estructura de una solución óptima.
     • Definir de forma recursiva la solución óptima.
     • Calcular la solución óptima de forma ascendente.
     • Construir la solución óptima a partir de los datos
   • Ventajas/Desventajas
     • Una de las principales ventajas de usar programación dinámica es que acelera el procesamiento, ya que se usan referencias que fueron previamente calculadas.
     • La principal desventaja es, que necesita mucha memoria para almacenar el resultado calculado de cada subproblema
   • Ejemplo
     • Pasos mínimos para llegar a 1: Para cualquier número entero positivo “e” se puede realizar cualquiera de los tres pasos: siguientes. – Restar 1 del número. (e=e-1). – Si es divisible por 2, se divide entre 2 (si e%2==0, entonces e= e/2). – Si es divisible por 3, se divide entre 3 (si e%3==0, entonces e= e/3).

5. Algoritmos Probabilísticos

   • ¿Cómo funciona?
     • Están basados en el resultado devuelto en decisiones aleatorias
   • Características
     • Puede equivocarse siempre que esto ocurra con una probabilidad pequeña para cada dato de entrada.
     • El análisis de la eficiencia de un algoritmo determinista es en ocasiones, difícil.
     • Repitiendo la ejecución un número suficiente de veces para el mismo dato, puede aumentarse tanto como se quiera el grado de confianza en obtener la solución correcta.
   • Tipos
     • Probabilistas: Algoritmos que no garantizan la corrección de la solución.
     • Numéricos: Dan una solución aproximada .
     • Monte Carlo: Dan la respuesta exacta con una alta probabilidad
   • Ventajas/Desventajas
     • Se pueden presentar distintas soluciones.
     • Presentan mayor eficiencia en tiempo y memoria.
     • La principal desventaja es que este algoritmo puede equivocarse
   • Ejemplo
     • Hacer un método que halle el área de un cuadrado. 1. Inicio 2. Lea l 3. Haga a=l*l 4. Imprima a 5. Fin

6. Búsquedas Exhaustivas

   • ¿Cómo funciona?
     • Primero, genera una lista de todas las soluciones potenciales del problema en una forma sistemática. Luego evalúa las soluciones potenciales una a una, descalificando las no factibles y manteniendo un registro de la mejor encontrada hasta el momento. Y por último, cuando la búsqueda finalice, regresa a la mejor solución encontrada.
   • Características
     • Estos algoritmos raramente exploran todas las posibles combinaciones de elementos, sino que expanden las combinaciones más prometedoras
     • La técnica de búsqueda más sencilla, conocida como backtracking o vuelta atrás, opera de manera recursiva, explorando en profundidad el árbol virtual de combinaciones de elementos
   • ¿Para qué sirve?
     • Se recomiendan cuando se requiere de manera prioritaria una implementación sencilla de búsqueda, antes que una búsqueda rápida.
   • Ventajas/Desventajas
     • Se utilizan en problemas para los que no existen un algoritmo eficiente que los resuelva.
     • Su principal desventaja es, su coste de ejecución es proporcional al número de soluciones candidatas, el cual es exponencialmente proporcional al tamaño del problema así que se sigue considerando ineficiente.
   • Ejemplo
     • El Problema del vendedor Viajero: Dada una lista de ciudades y las distancias entre cada par de ellas, ¿cuál es la ruta más corta posible que visita cada ciudad exactamente una vez y al finalizar regresa a la ciudad origen?

7. Damaris Jiménez B73987, Danny Castillo Solano B71803,Wendy Martínez Madrigal B64149,Lissette Contreras Mora B82282