Tipos de Algoritmos

Description

Mind Map on Tipos de Algoritmos, created by Stuard Diaz Lopez on 19/05/2020.
Stuard Diaz Lopez
Mind Map by Stuard Diaz Lopez, updated more than 1 year ago
Stuard Diaz Lopez
Created by Stuard Diaz Lopez almost 4 years ago
49
0

Resource summary

Tipos de Algoritmos
  1. Algoritmo Voraz
    1. El denominado “algoritmo voraz” sigue una estrategia sencilla pero eficaz. Simplemente, se trata de elegir la opción óptima en cada paso local, con la esperanza de llegar a una solución general óptima.
      1. Caracteristicas
        1. 1- El problema a resolver debe ser optimizado[MAZ-MIN], debe existir una función que es la que hay que minimizar o maximizar
          1. 2-Dominio, son un conjunto de valores posibles para cada una de las variables de la función objetivo.
            1. 3-Pueden existir un conjunto de restricciones que imponen condiciones a los valores del dominio que pueden tomar las variables de función de la función objetivo
              1. 4-La solución para el problema debe ser dada en forma de secuencia de decisiones.
              2. Función
                1. Se emplean sobre todo para resolver problemas de optimización, como por ejemplo, encontrar la secuencia óptima para procesar un conjunto de tareas por un computador, hallar el camino mínimo de un grafo, etc.
                2. Ventajas
                  1. El tiempo de ejecución: al tomar siempre la solución más prometedora, la complejidad es lineal en el número total de decisiones.
                    1. Fáciles de implementar
                      1. Soluciones eficientes
                      2. Desventajas
                        1. No todos los problemas se pueden solucionar con este tipo de algoritmos
                          1. Dificultad para encontrar un modo de selección optimo para el problema
                          2. Ejemplos
                            1. El algoritmo de Prim es un algoritmo perteneciente a la teoría de los grafos para encontrar un árbol recubridor mínimo en un grafo conexo, no dirigido y cuyas aristas están etiquetadas. En otras palabras, el algoritmo encuentra un subconjunto de aristas que forman un árbol con todos los vértices, donde el peso total de todas las aristas en el árbol es el mínimo posible. Si el grafo no es conexo, entonces el algoritmo encontrará el árbol recubridor mínimo para uno de los componentes conexos que forman dicho grafo no conexo.
                        2. Integrantes grupo: Didier Stuard Díaz B72582, Yamsineth Vargas B88189, Laura Masis Brenes B74530, Gerald Ramírez B89056
                          1. Divide y vencerás
                            1. ¿Como funciona este tipo de algoritmo? Separa un problema en sub problemas para resolver el problema original con mayor eficacia.
                              1. ¿Qué características tiene? Se divide en 3 partes: Divide el problema en un número de sub problemas. Vence los sub problemas al resolverlos de manera recursiva. Combina las soluciones de los sub problemas para resolver el problema original.
                                1. ¿Para que sirven y en que se usan? Sirve para resolver problemas complejos y extensos, se usan en problemas de ordenamiento, o búsquedas.
                                  1. Ventajas
                                    1. • Resolución de problemas complejos
                                      1. • Eficiencia del algoritmo
                                        1. • Paralelismo (Realizar varios cálculos simultáneamente)
                                        2. Desventajas
                                          1. • Lentitud en la repetición del proceso recursivo
                                            1. • Dificultad o incluso inconveniencia de aplicar el método a situaciones en las que la solución al problema general no se deriva de la suma directa y simple de los sub problemas (parte)
                                            2. Ejemplos
                                              1. • Búsqueda Binaria • Encontrar el elemento máximo en un array. • Merge -sort(Ordenar array). • Quick -sort(Ordenar rápido un array)
                                          2. Algoritmos Probabilísticos
                                            1. ¿Cómo funciona? dan una respuesta utilizando criterios basados en la utilización de números aleatorios. La salida depende no sólo de la entrada, y esta componente aleatoria hace que el programa pueda comportarse de forma distinta en dos ejecuciones con los mismos parámetros de entrada.
                                              1. Características:
                                                1. Existen varios tipos de algoritmos probabilísticos dependiendo de su funcionamiento, pudiéndose distinguir: • Algoritmos numéricos, que proporcionan una solución aproximada del problema. • Algoritmos de Montecarlo, que pueden dar la respuesta correcta o respuesta erróneas (con probabilidad baja). • Algoritmos de Las Vegas, que nunca dan una respuesta incorrecta: o bien no encuentran la respuesta correcta e informan del fallo
                                                2. ¿En que se usa?
                                                  1. Se puede optar por la elección aleatoria si se tiene un problema cuya elección óptima es demasiado costosa frente a la decisión aleatoria.
                                                  2. Ventajas
                                                    1. • Diferentes soluciones • Aumentar la posibilidad de encontrar la solución correcta • Mayor eficiencia en tiempo y memoria
                                                    2. Desventajas
                                                      1. • Un algoritmo probabilista puede equivocarse siempre que esto ocurra con una probabilidad pequeña para cada dato de entrada. • El análisis de los algoritmos probabilistas es, a menudo, muy difícil.
                                                      2. Ejemplo
                                                        1. La aguja de Buffon Si se tira una aguja de longitud μ a un suelo hecho con tiras de madera de anchura w (w≥μ), la probabilidad de que la aguja toque más de una tira de madera es p=2μ/wπ. Aplicación: Una aplicación del teorema de Buffon es utilizarlo para predecir el valor de π. Sea μ=w/2, entonces p=1/π. Si se tira la aguja un número de veces n suficientemente grande y se cuenta el número k de veces que la aguja toca más de una tira de madera, se puede estimar el valor de p: k ~ n/p → p ~ n/k.
                                                    3. Búsqueda exhaustiva
                                                      1. Función Búsqueda exhaustiva , es una técnica trivial pero a menudo usada, que consiste en enumerar sistemáticamente todos los posibles candidatos para la solución de un problema, con el fin de chequear si dicho candidato satisface la solución al mismo.
                                                        1. Características
                                                          1. Se utiliza para resolver problemas para los que no existe un algoritmo eficiente para resolverlos. • Mediante la programación paralela se intentara reducir el tiempo de ejecución de estos algoritmos
                                                          2. ¿En que se usa?
                                                            1. Es un método utilizado cuando es más importante una implementación sencilla que una mayor rapidez. Este puede ser el caso en aplicaciones críticas donde cualquier error en el algoritmo puede acarrear serias consecuencias; también es útil como método "base" cuando se desea comparar el desempeño de otros algoritmos metaheurísticos.
                                                            2. Ventajas
                                                              1. Es un algoritmo simple  Es la más simple y busca en todo el espacio de solución.  Enumera todos los posibles candidatos para la solución.  Encuentra una solución
                                                              2. Desventajas
                                                                1. Depende de N el número de N posiciones a compararse y por ende el tiempo de ejecución  Requiere un determinado espacio
                                                                2. Ejemplo
                                                                  1. Problema del agente viajero Dada una lista de n ciudades y las distancias entre cada par de ellas, encontrar el recorrido (ruta) más corto posible que visita cada ciudad exactamente una vez y regresa a la ciudad origen.
                                                              3. Programación dinámica
                                                                1. 1- ¿Cómo funciona este tipo de Algoritmo? Divide el problema en subproblemas. Se divide en dos etapas:
                                                                  1. Etapa de Análisis:
                                                                    1. Analiza el problema desde su última etapa y calcula todas as opciones posibles y lo agrega a una tabla de resultados obtenidos, luego hace lo mismo con la etapa anterior a esa y así secuencialmente hasta llegar a la primera etapa.
                                                                    2. Etapa de decisión:
                                                                      1. Una vez guardadas las opciones empieza desde la primera etapa y decide la mejor opción, y así secuencialmente hasta llegar a la última etapa para finalmente dar una solución.
                                                                      2. 2- Características
                                                                        1. - El tiempo de ejecución puede mejorarse secuencialmente. - Divide el problema en subetapas - Es un método capaz de resolver problemas eficientemente.
                                                                        2. ¿Para qué sirve?, ¿en qué se usa?
                                                                          1. - Sirve para resolver problemas complejos caracterizados por decisiones que se deben tomar de manera secuencial. Se usa principalmente para resolver problemas de alta complejidad.
                                                                          2. - Ventajas:
                                                                            1. Eficaz para resolver problemas de gran complejidad al dividirlo y secuenciarlo. Resuelve cada subproblema de una sola vez. Los cálculos de cada etapa se organizan y se guardan de manera eficiente facilitando su consulta para posteriores análisis.
                                                                            2. Desventajas
                                                                              1. Si la red es muy grande se vuelve laborioso. No aplicable a todo tipo de problemas. Si hay un error en una tabla afecta a todo el problema.
                                                                              2. Ejemplo
                                                                                1. Un autobús necesita desplazarse de un punto A a un punto B, pero hay diferente rutas para llegar al destino, el algoritmo va a hacer un recorrido desde el punto B hasta el A, va a guardar las distancias de las rutas para finalmente analizarlas y dar como solución la ruta más corta.
                                                                            Show full summary Hide full summary

                                                                            Similar

                                                                            algoritmos
                                                                            Francisco Garcia
                                                                            Drama Works IB English
                                                                            miss.bakare
                                                                            Subh Milis le Seamus O Neill
                                                                            l.watters97
                                                                            Plant Structure and Photosynthesis
                                                                            mckenziedev
                                                                            AS Pure Core 1 Maths (AQA)
                                                                            jamesmikecampbell
                                                                            AS-Level Chemistry: Unit 1:The Atom
                                                                            Daena Targaryen
                                                                            GCSE Subjects
                                                                            KimberleyC
                                                                            Cell structure F211 OCR AS Biology
                                                                            helen.rebecca
                                                                            Mind Maps with GoConqr
                                                                            Elysa Din
                                                                            Tests for Positive Ions: Flame Test Colours
                                                                            bella.mort
                                                                            DEV I Part I
                                                                            d owen