Tecnicas algoritmicas Flashcards
Temas de estrategias de algoritmos (14 cards)
Describir la idea general de un algoritmo de fuerza bruta. Dar un ejemplo de uno
Un algoritmo de fuerza bruta se aplica tanto en problemas de buscar si existe una solucion, o buscar la solución optima. Plantea el universo de todas soluciones posibles (sean o no válidas), y luego recorre de manera secuencial todo ese universo buscando una solución válida, o la óptima.
Un ejemplo de problema que se resuelve con algoritmo de fuerza bruta es colocar 8 reinas en un tablero de ajedrez, de manera que 2 reinas no se esten amenazando. La solucion de fuerza bruta implicaria generar todas las soluciones “posibles” (tableros con 8 reinas) y recorrer ese universo hasta encontrar uno válido
Describir la idea general de un algoritmo de backtracking y modificar el algoritmo de fuerza bruta dado en el punto anterior para convertirlo en un algoritmo de backtracking. Discutir ventajas y desventajas de este algoritmo respecto del algoritmo basado en fuerza bruta.
La idea de backtracking en su base es similar a fuerza bruta. En su construcción se puede pensar como un arbol dirigido, con su raiz es el origen del problema, cada nodo es una solucion parcial, y las hojas son soluciones posibles. El algoritmo recorre las soluciones parciales hasta que llega a una solucion posible y la verifica. En caso de no ser válida retrocede(Backtrack) hasta la ultima solucion valida que no tenga “mas acciones”(revisrar esto).
En el caso del problema de las 8 reinas. en vez de analizar todas las soluciones, partiriamos de soluciones parciales con 0 reinas, luego con 1, con 2, etc. Hasta tener 8, y ahi verificariamos su valides.
Su mayor ventaja es que en problemas donde no podes llegar a una solucion valida partiendo de una solucion parcial invalida, podes realizar podas al arbol de decisión. En este ejemplo, si tenes una solucion parcial con dos reinas amenazandose, podes considerar que todas las soluciones que parten de esa solucion van a ser invalidas, y no tenes que analizarlas.
En caso de tener un problema de optimización, se podria tambien podar una solucion parcial que analicemos que no va a dar soluciones mas optimas que una solucion valida ya encontrada.
La unica desventaja es que todo eso es una complejidad adicional a la hora de diseñar y analizar el algoritmo
Dar la complejidad computacional del algoritmo presentado en el punto anterior de fuerza bruta y backtracking y explicar en qué puntos este algoritmo podría ser útil en la práctica.
El universo de problemas seria (en total 64!/8!(64-8)! = 4.426.165.368 posiciones diferentes). Mal ejemplo voy a buscar otro
Describir informalmente la técnica de programación dinámica. Explicar el concepto de “superposición de estados” y dar las técnicas de programación dinámica “top-down” y “bottom-up”.
Ilustrar los conceptos dados en el punto anterior con un algoritmo de programación dinámica “top-down”. Explicar si es posible modificar este algoritmo para que sea un algoritmo de programación “bottom-up”. Dar la complejidad computacional del o de los algoritmos presentados.
Definir los conceptos de “problema” “instancia” y “problema de optimización” en programación dinámica.
Explicar qué es un algoritmo de programación dinámica.
Explicar qué es un algoritmo goloso relacionándolo con los elementos clave de un algoritmo de programación dinámica.
Dar un ejemplo de una aplicación en grafos que se resuelva con un algoritmo de programación dinámica. Demostrar que el algoritmo resuelve el problema propuesto y dar su complejidad computacional.
Definición de “problema” “instancia” y “problema de optimización” en Goloso.
Explicar que es un Agoritmo Goloso.
Definición de concepto de Heurística y dar un ejemplo para un problema NP-Hard/ Explicar qué es programación dinámica relacionándolo con los elementos clave de un algoritmo de programación dinámica.
Dar un ejemplo de una aplicación en grafos que se resuelva con un algoritmo Goloso
Dar un ejemplo que se resuelva de forma exacta con un algoritmo goloso. Para este algoritmo, demostrar correctitud y dar su complejidad.
