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 laspropiedades 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 entradaparticular 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 problemacuya 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ónconstituyen 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 problemapara 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 oprocedimiento 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 un problema del conjunto.
o Hay criterios para determinar que tan "buena" esuna solución, distintos de ver si trabaja o no, o hasta qué punto es general la aplicabilidad del método. Estos criterios involucran aspectos tales como: eficiencia, elegancia, velocidad, etc.
03. Describa el modelo básico: Problema-Algoritmo-Solución.
04. Describa metodología básica para la solución de problemas (p. ej. George Polya).
George Polya nació en Hungría en 1887. Obtuvo sudoctorado en la Universidad de Budapest y en su disertación para obtener el grado abordó temas de probabilidad. Fué maestro en el Instituto Tecnológico Federalen Zurich, Suiza. En 1940 llegó a la Universidad de Brown en EE.UU. y pasó a la Universidad de Stanford en 1942. En sus estudios, estuvo interesado en el proceso del descubrimiento, o cómo es que se derivan los resultados matemáticos. Advirtióque para entender una teoría, se debe conocer cómo fue descubierta. Por ello, su enseñanza enfatizaba en el proceso de descubrimiento aún más que simplemente desarrollar ejercicios apropiados. Para involucrar a sus estudiantes en la solución de problemas, generalizó su método en los siguientes cuatro pasos:
1. Entender el problema. 2. Configurar un plan 3. Ejecutar el plan 4. Mirar hacia...