Page 54 - INTRODUCCIÓN AL ANÁLISIS DE ALGORITMOS

INTRODUCCIÓN AL ANÁLISIS DE ALGORITMOS

Sección ii

Paradigmas de solución de problemas

INtroduccIóN

Un problema se define como un asunto o una cuestión que requiere solución a nivel social. Se trata
de alguna situación en concreto que, en el momento en que se logra resolver, aporta beneficios a la
sociedad. Esa solución se puede apoyar en las siguientes estrategias:

• Criterio de error y acierto. Esta se puede apoyar en la heurística como proce-
dimiento práctico o informal para resolver problemas (existen otras definiciones
para la misma palabra). Además, permite resolver problemas viendo cómo otros
lo hacen.

• Matemáticamente. Consiste en buscar una determinada entidad matemática
de entre un conjunto de entidades del mismo tipo para satisfacer las llamadas
condiciones del problema.

• Una solución algorítmica a un problema abstracto. Consiste de un algoritmo
que por cada instancia del problema calcula al menos una solución correspon-
diente —en caso de haberla— o expide un certificado de que no existe solución
alguna al algoritmo dado (el algoritmo se basa en una solución matemática o una
solución heurística)

Ejemplo de un tipo de problema que no se puede resolver por medio de un algoritmo, aunque sí
n
n
n
tuvo solución matemática, es el último teorema de Fermat, el cual indica que x + y ≠ z para n > 2.
Fue conjeturado por Pierre de Fermat en 1637 y demostrado hasta 1995 por el matemático Andrew
Wiles. En otras palabras, existirán problemas que tienen una solución matemática pura, aunque sin
lograr presentar un algoritmo.
48