22972452
Description
Mind Map by Damaris Jiménez, updated more than 1 year ago
|
Created by Damaris Jiménez
almost 5 years ago
|
|
Tipos de Algoritmos
- Algoritmos Voraces
- 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.
- 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.
- Su algoritmo voraz procede por pasos.
- ¿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.
- 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.
- Es bastante fácil de llegar a un
algoritmo voraz para un
problema.
- 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
- 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
- ¿Cómo funciona?
- Divide y Vencerás
- ¿Cómo funciona?
- Este algoritmo funciona separando un
problema en subproblemas que se parecen
al problema original
- 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.
- 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.
- Resolución de problemas complejos.
- 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.
- 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.
- ¿Cómo funciona?
- 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.
- 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.
- 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
- ¿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
- Caracterizar la estructura de una solución óptima.
- 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
- 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.
- 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).
- 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).
- ¿Cómo funciona?
- Algoritmos Probabilísticos
- ¿Cómo funciona?
- Están basados en el resultado devuelto en decisiones aleatorias
- 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.
- Puede equivocarse siempre que esto ocurra con una
probabilidad pequeña para cada dato de entrada.
- 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
- Probabilistas: Algoritmos que no garantizan la corrección de la solución.
- Ventajas/Desventajas
- Se pueden presentar distintas soluciones.
- Presentan mayor eficiencia en tiempo y memoria.
- La principal desventaja es que
este algoritmo puede
equivocarse
- Se pueden presentar distintas soluciones.
- 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
- 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
- ¿Cómo funciona?
- 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.
- 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
- Estos algoritmos raramente exploran todas las posibles
combinaciones de elementos, sino que expanden las
combinaciones más prometedoras
- ¿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.
- 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.
- Se utilizan en problemas para los que no existen un
algoritmo eficiente que los resuelva.
- 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?
- 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?
- ¿Cómo funciona?
- Damaris Jiménez B73987, Danny
Castillo Solano B71803,Wendy
Martínez Madrigal B64149,Lissette
Contreras Mora B82282
Want to create your own Mind Maps for free with GoConqr? Learn more.