Menu Close

I1M2017: Resolución de problemas y el método de Polya

En la primera parte de la clase de hoy de Informática de 1º del Grado en Matemáticas se ha explicado el método de Polya de resolución de problemas.

La explicación se ha basado en la resolución del problema de cálculo eficiente del conjunto de divisores (que es la primera parte del problema propuesto ayer en Exercitium.

En primer lugar se consideró la solución elemental

divisores :: Integer -> [Integer]
divisores x =
  [y | y <- [1..x]
     , x `mod` y == 0]

Se comprueba que con dicha definición se resuelve los tres primeros ejemplos del enunciado del problema, pero no se resuelve el cuarto ejemplo. Por ello se plantea cómo mejorar la solución. Analizando el problema se ve que la clave está en considerar la factorización prima (que se calcula eficientemente con la función primeFactors de la librería Data.Numbers.Primes.

Trabajando con con ejemplo concreto (el cálculo de los divisores de 24) se observa las transformaciones que hay que hacer a la lista de los divisores primos de 24 para calcularlo.

Además, para una de esas transformaciones vemos que se puede usar otros de los problemas resueltos anteriormente en Exercitium: Producto cartesiano de una familia de conjuntos.

Una vez se tiene un plan para resolver el problema, se confirma haciendo los cálculos en una sesión de GHCi.

Ya sólo queda escribir la definición y comprobar que ha aumentado la eficiencia respecto de la primera solución y es capaz de calcular el cuarto ejemplo del enunciado del problema.

A continuación se comentó el método de Pólya para resolver problemas y se recomendó la lectura del libro de Polya Cómo plantear y resolver problemas.

I1M2017, Sin categoría