Tipos de Algoritmos

Algoritmos Voraces
Algoritmos Voraces
1. ¿Cómo funciona?
  1. 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.
2. Características
  1. Su algoritmo voraz procede por pasos.
  2. Utiliza la función de selección.
  3. Debe existir una función, la función objetivo, que es la que hay que minimizar o maximizar.
3. ¿Para qué sirve?
  1. Sirve para determinar la función de selección, definir la función factible y definir qué caracteriza a una solución del problema.
4. Ventajas/Desventajas
  1. Es bastante fácil de llegar a un algoritmo voraz para un problema.
  2. Analizando el tiempo de ejecución de los algoritmos voraces generalmente será mucho más fácil que el de otras técnicas.
  3. Su principal desventaja es que tendremos que trabajar mucho más para entender los problemas de los algoritmos voraces.
5. Ejemplo
  1. 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
Divide y Vencerás
1. ¿Cómo funciona?
  1. Este algoritmo funciona separando un problema en subproblemas que se parecen al problema original
2. ¿Para qué sirve?
  1. Su uso o mayor objetivo es descomponer un problema para poder resolver su problema original.
3. Ventajas/Desventajas
  1. Resolución de problemas complejos.
  2. Eficiencia del algoritmo.
  3. La principal desventaja de este método es su lentitud en la repetición del proceso recursivo.
4. Ejemplo
  1. 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.
Programación Dinámica
1. ¿Cómo funciona?
  1. Se utiliza cuando se tienen problemas que se pueden dividir en subproblemas similares, de modo que sus resultados puedan ser reutilizados.
2. Características
  1. 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
  2. Solapamiento entre subproblemas: Al plantear la solución recursiva del problema, un mismo problema se resuelve más de una vez.
  3. 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.
3. ¿Para qué sirve?
  1. Caracterizar la estructura de una solución óptima.
  2. Definir de forma recursiva la solución óptima.
  3. Calcular la solución óptima de forma ascendente.
  4. Construir la solución óptima a partir de los datos
4. Ventajas/Desventajas
  1. 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.
  2. La principal desventaja es, que necesita mucha memoria para almacenar el resultado calculado de cada subproblema
5. Ejemplo
  1. 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).
Algoritmos Probabilísticos
1. ¿Cómo funciona?
  1. Están basados en el resultado devuelto en decisiones aleatorias
2. Características
  1. Puede equivocarse siempre que esto ocurra con una probabilidad pequeña para cada dato de entrada.
  2. El análisis de la eficiencia de un algoritmo determinista es en ocasiones, difícil.
  3. 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.
3. Tipos
  1. Probabilistas: Algoritmos que no garantizan la corrección de la solución.
  2. Numéricos: Dan una solución aproximada .
  3. Monte Carlo: Dan la respuesta exacta con una alta probabilidad
4. Ventajas/Desventajas
  1. Se pueden presentar distintas soluciones.
  2. Presentan mayor eficiencia en tiempo y memoria.
  3. La principal desventaja es que este algoritmo puede equivocarse
5. Ejemplo
  1. 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
Búsquedas Exhaustivas
1. ¿Cómo funciona?
  1. 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.
2. Características
  1. Estos algoritmos raramente exploran todas las posibles combinaciones de elementos, sino que expanden las combinaciones más prometedoras
  2. 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
3. ¿Para qué sirve?
  1. Se recomiendan cuando se requiere de manera prioritaria una implementación sencilla de búsqueda, antes que una búsqueda rápida.
4. Ventajas/Desventajas
  1. Se utilizan en problemas para los que no existen un algoritmo eficiente que los resuelva.
  2. 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.
5. Ejemplo
  1. 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?
Damaris Jiménez B73987, Danny Castillo Solano B71803,Wendy Martínez Madrigal B64149,Lissette Contreras Mora B82282

Nächster

Tipos de Algoritmos

Beschreibung

Zusammenfassung der Ressource

ähnlicher Inhalt

	Erstellt von Damaris Jiménez vor etwa 4 Jahre