Paradigmas de Diseño de Algoritmos
Los paradigmas de diseño de algoritmos son estrategias recurrentes de alto nivel —dividir y conquistar, programación dinámica, elección voraz y búsqueda exhaustiva con poda— utilizadas para construir algoritmos correctos y eficientes para problemas computacionales.
Definition
Un paradigma de diseño de algoritmos es una plantilla o estrategia general para resolver una clase de problemas, caracterizada por una forma de descomponer el problema y combinar subsoluciones, junto con las propiedades estructurales que debe tener un problema para que el paradigma sea aplicable.
Scope
Esta área cubre las técnicas de propósito general para construir algoritmos independientemente de cualquier dominio de problema único. Trata cómo la estructura de un problema (subestructura óptima, subproblemas superpuestos, la propiedad de elección voraz, descomponibilidad) sugiere una estrategia coincidente, y cómo cada paradigma se razona para su corrección y se analiza para su tiempo de ejecución. Excluye las estructuras de datos que implementan estos algoritmos (cubiertas en estructuras de datos fundamentales) y los límites teóricos de la complejidad de lo que cualquier algoritmo puede lograr (cubiertos en complejidad y análisis de algoritmos).
Sub-topics
Core questions
- ¿Qué propiedad estructural de un problema hace que un paradigma dado sea aplicable y correcto?
- ¿Cómo se convierte una descomposición recursiva en un algoritmo eficiente mediante la memoización o la tabulación?
- ¿Cuándo una elección localmente óptima (voraz) conduce a una solución globalmente óptima?
- ¿Cómo se deriva el tiempo de ejecución de un algoritmo basado en paradigmas, por ejemplo, mediante recurrencias?
- ¿Cómo podan los paradigmas de búsqueda exhaustiva el espacio de búsqueda para seguir siendo tratables en instancias típicas?
Key concepts
- dividir y conquistar
- relaciones de recurrencia
- programación dinámica
- memoización y tabulación
- elección voraz y argumentos de intercambio
- backtracking (vuelta atrás)
- ramificación y poda
- subestructura óptima
- búsqueda exhaustiva y poda
Key theories
- Subestructura óptima
- Un problema tiene subestructura óptima cuando una solución óptima puede ensamblarse a partir de soluciones óptimas a sus subproblemas; esta propiedad subyace tanto a la programación dinámica como a muchos algoritmos voraces.
- Subproblemas superpuestos y memoización
- Cuando una descomposición recursiva revisita los mismos subproblemas repetidamente, almacenar la solución de cada subproblema (memoización o tabulación ascendente) reduce la recálculo exponencial a tiempo polinómico, la base de la programación dinámica.
- Propiedad de elección voraz
- Algunos problemas admiten una solución globalmente óptima construida haciendo repetidamente la elección que parece mejor en el momento; la corrección se demuestra típicamente mediante un argumento de intercambio o mediante la teoría de matroides.
Clinical relevance
Los paradigmas de diseño son el vocabulario de trabajo del software práctico: dividir y conquistar subyace a la clasificación rápida y al procesamiento de señales, la programación dinámica impulsa la alineación de secuencias en bioinformática y las subrutinas de ruta más corta, los métodos voraces impulsan la programación y la compresión de datos (codificación de Huffman), y la ramificación y poda es central para la optimización combinatoria y la investigación de operaciones.
History
El razonamiento de dividir y conquistar es anterior a las computadoras, pero se volvió central con algoritmos rápidos como el mergesort y la multiplicación de Karatsuba en la década de 1960. Richard Bellman introdujo la programación dinámica en la década de 1950. El tratamiento sistemático de los paradigmas en libros de texto como una lente unificadora maduró a través de obras como el texto de diseño y análisis de Aho, Hopcroft y Ullman, y posteriormente CLRS y Kleinberg-Tardos.
Key figures
- Richard Bellman
- Thomas H. Cormen
- Jon Kleinberg
- Éva Tardos
- Robert Sedgewick
Related topics
Seminal works
- cormen2009
- kleinberg2006
- sedgewick2011
Frequently asked questions
- ¿Cuál es la diferencia entre la programación dinámica y los algoritmos voraces?
- Ambos explotan la subestructura óptima, pero un algoritmo voraz se compromete con una elección localmente óptima en cada paso y nunca la reconsidera, mientras que la programación dinámica considera y combina soluciones a todos los subproblemas relevantes. El algoritmo voraz es más rápido cuando se aplica, pero es correcto para menos problemas.
- ¿Cómo sé qué paradigma usar?
- Observe la estructura del problema: si es descomponible en subproblemas independientes, sugiere dividir y conquistar; si hay subproblemas superpuestos con subestructura óptima, sugiere programación dinámica; si hay una propiedad de elección voraz demostrable, sugiere un algoritmo voraz; y de lo contrario, puede ser necesaria una búsqueda sistemática con poda (backtracking o ramificación y poda).