Algoritmos

Investigar y describir:

01. Definiciones de problema y caso o instancia.

Un problema computacional constituye una pregunta a ser respondida, teniendo generalmente varios parámetros, o variables libres, cuyos valores no se han especificado. Un problema se describe mediante:

1. Una descripción general de todos sus parámetros (pueden ser de entrada o de salida).

2. Una sentencia que describa las propiedades que la respuesta, o la solución, debe cumplir.

Una instancia de un problema se obtiene cuando se especifican valores particulares para todos los parámetros del problema. Por ejemplo, consideremos el problema del test de primalidad. La instancia es un número (e.g. 15) y la solución es "sí" si el número es primo, y "no" en caso contrario. Visto de otra manera, la instancia es una entrada particular del problema, y la solución es la salida correspondiente para la entrada dada.

Problemas de decisión

Un problema de decisión es un tipo especial de problema computacional cuya respuesta es solamente "sí" o "no" (o, de manera más formal, "1" o "0").

Un problema de decisión pudiera verse como un lenguaje formal, donde los elementos que pertenecen al lenguaje son las instancias del problema cuya respuesta es "sí", los que no pertenecen al lenguaje son aquellas instancias cuya respuesta es "no". El objetivo es decidir, con la ayuda de un algoritmo, si una determinada entrada es un elemento del lenguaje formal considerado. Si el algoritmo devuelve como respuesta "sí", se dice que el algoritmo acepta la entrada, de lo contrario se dice que la rechaza.

Los problemas de decisión constituyen uno de los principales objetos de estudio de la teoría de la complejidad computacional, pues la NP-completitud se aplica directamente a estos tipos de problemas en vez de a problemas de optimización. Estos problemas tienen gran importancia porque casi todo problema puede transformarse en un problema de decisión.

02. Explique el proceso de solución de problemas.

Cuando se tiene un problema para el cual debemos especificar un algoritmo solución, tendremos en cuenta varios puntos:

o Si no se conoce un método para solucionar el problema en cuestión, debemos hacer un análisis del mismo para llegar a una solución, después de evaluar alternativas, exigencias y excepciones.

o Si se conoce un "buen" método de solución al problema, se debe especificar exacta y completamente el método o procedimiento de solución en un lenguaje que se pueda interpretar fácilmente.

o Los problemas pueden agruparse en conjunto de problemas que son semejantes.

o En algún sentido, en general, un método para solucionar todos los problemas de un conjunto dado, se considera superior a un método para solucionar solamente

...