I1M2014: El patrón de divide y vencerás en Haskell
En la primera parte de la clase de hoy del curso de Informática de 1º del Grado en Matemáticas hemos estudiado la técnica de resolución de problemas mediante divide y vencerás.
La clase comenzó analizando los árboles de ordenación de una lista de números mediante la ordenación por mezcla y la ordenación rápida.
De este análisis se extrae el patrón de resolución de problemas mediante divide y vencerás (DyV) y sus argumentos:
- cómo reconocer si el problema es elemental,
- cómo se resuelven los problemas elementales,
- cómo se descompone un problema y
- cómo se combinan las soluciones de los subproblemas.
A continuación se implementa el patrón DyV en Haskell, usando su posibilidad de programar en orden superior para abstraer los argumentos del problema.
Finalmente, se aplica el patrón DyV para implementar los algoritmos de ordenación por mezcla y ordenación rápida.
Las transparencias usadas en la clase son las páginas 1-10 del tema 23:
Read More “I1M2014: El patrón de divide y vencerás en Haskell”