martes, 24 de junio de 2008

Pasos en la solución de un problema

La solución del problema exige una comprensión de la tarea, la concepción de un plan que nos lleve hacia la meta, la ejecución del mencionado plan y, por último, un análisis que nos lleve a determinar si hemos alcanzado o no la meta.


Según POLYA y otros autores, el primer paso en la resolución de problemas consiste en la comprensión de los mismos. Seguramente resulta obvio la afirmación de que es imposible resolver una tarea sin una comprensión previa de ella, pero comprender un problema no sólo significa entender las palabras, el lenguaje o los símbolos en los que está planteado sino también asumir la situación como tal problema y adquirir una disposición de búsqueda de esa solución. Generalmente, para que nos planteemos una situación como un problema debemos tomar conciencia de que estamos ante una situación nueva, o de que se ha producido un cambio respecto a alguna situación anterior, o bien de que nos enfrentamos ante una tarea para la cual sólo tenemos una explicación insuficiente. Expresado con otras palabras, comprender un problema implica darse cuenta de las dificultades y escollos que presenta una tarea y la voluntad de intentar superarlas. Para que se dé esta comprensión es, por supuesto, necesario que además de los elementos de novedad, el problema contenga aspectos ya conocidos que nos permitan guiar nuestra búsqueda de solución.

Algoritmos

Introducción
La etapa más importante de la solución de un problema con una computadora es el diseño del algoritmo.
Es importante recordar mientras diseñamos un algoritmo que una computadora sólo sigue las instrucciones y no puede actuar si no se le ha ordenado de manera explícita. Por lo tanto, el solucionador de problemas debe prever cualquier aspecto del problema en el propio algoritmo.
La palabra Algoritmo se usa en homenaje al matemático UZBEKO ALKUARITZMI quien escribió un libro en el cual por primera vez se expresaban métodos precisos para efectuar las cuatro operaciones básicas, las cuales hoy en día se siguen utilizando.

Definición
Un algoritmo es un conjunto finito de pasos que especifica una secuencia de operaciones a realizar en orden para resolver un problema específico o clases de problemas. En otras palabras, un algoritmo es un método para la solución del problema.
Un algoritmo es el medio por el que se explica cómo puede resolverse un problema, mediante aproximaciones paso a paso. Se puede formular de muchas formas, siempre y cuando se realice de modo no ambiguo.
Para describir algoritmos de computadoras se han diseñado lenguajes de programación. Cada una de las acciones de las que consta un algoritmo se llamará sentencia y éstas deben ser escritas en términos de cierto lenguaje comprensible para la máquina, que es el lenguaje de programación. El conjunto formado por la representación de datos utilizada y el algoritmo en sí, se conoce usualmente con el nombre de Programa. Un programa es la descripción del proceso en un cierto lenguaje.
Un algoritmo, consiste de dos partes esenciales: una descripción de acciones que deben ser ejecutadas y una descripción de los datos que son manipulados por esas acciones. Las acciones se describen mediante las llamadas sentencias y los datos mediante declaraciones y definiciones.

Propiedades
Un algoritmo es un procedimiento para ejecutar un trabajo y tiene cuatro propiedades principales:
· Secuencialidad: se debe especificar sin lugar a dudas la secuencia en la que se debe llevar a cabo los pasos del algoritmo. Un algoritmo debe tener una instrucción inicial única y cada instrucción debe tener un suceso único para un dato de entrada dado. En las especificaciones del algoritmo, incluyendo los programas, las instrucciones son llevadas a cabo de arriba hacia abajo (la sucesora implícita de una instrucción es una consecutiva físicamente), a menos que las instrucciones por sí mismas especifiquen otra cosa.
· Ausencia de ambigüedad: Un algoritmo debe ser definido, claro, preciso y no ambiguo. La representación de cada paso de un algoritmo debe tener una única interpretación aunque una representación para una computadora puede diferir para la de un humano.
Esta condición significa que cada vez que se presente para su ejecución un algoritmo con los mismos datos de entrada, se obtendrán los mismos resultados.
Las instrucciones de un algoritmo deben ordenar a la computadora que sólo lleve a cabo tareas que sea capaz de hacer. Una computadora no puede llevar a cabo una instrucción si tiene información insuficiente o si el resultado de la ejecución de la orden no está definido.
· Generalidad: Un algoritmo se puede utilizar para varios problemas que se relacionan entre sí. Un algoritmo se aplica a un problema o clase de problemas específicos, el rango de las entradas o dominio se tiene que definir previamente, ya que éste determina el alcance o la generalidad del algoritmo.
· Limitación: Un algoritmo es finito en tamaño y tiempo. La ejecución de un algoritmo programado debe finalizar después de que se haya llevado a cabo una cantidad finita de operaciones. De otra manera, no podremos exigir que la ejecución produzca una solución. La esencia del método del algoritmo consiste en la repetición del mismo paso o paso, probablemente con algunas modificaciones, muchas veces durante la ejecución de un programa basado en un algoritmo dado. El número de operaciones que se realizan en la ejecución de un algoritmo raramente es igual al número de pasos en la descripción del algoritmo.

La definición de un algoritmo debería describir tres partes: entrada, proceso y salida. Un algoritmo implica generalmente alguna entrada (algo que existe y es utilizado por el algoritmo); en un algoritmo de receta de cocina, la entrada está constituida por los ingredientes y los utensilios empleados. Un algoritmo produce también resultados denominados salida. La salida de la receta será la terminación del plato. Un algoritmo define la transformación de la entrada en la salida.

Dominio de un algoritmo
Si el algoritmo no es general dentro de alguna clase de problemas, entonces es de poca utilidad. Por lo tanto, un método para marcar el número telefónico 4220234 casi no tiene valor para nadie, mientras que un método para marcar cualquier número podría ser útil. Por supuesto, debe haber alguna restricción a la generalidad de un algoritmo.
La clase o el conjunto de datos y las condiciones para las cuales un algoritmo trabaja correctamente se llama dominio. Cuando se trata de resolver cualquier problema es necesario definir el dominio del algoritmo y después verificar que trabaja para todos los casos que se encuentran dentro de este dominio.

Errores en la construcción de un algoritmo

Errores de dominio: Se presentan cuando no se han especificado todas las situaciones que se pueden presentar en la práctica o se ha descuidado la apreciación de su importancia. Las pruebas más difíciles son aquellas que verifican que se ha seleccionado un dominio correcto para el algoritmo.
A medida que el problema se presenta, se tiene que clasificar y hay tres opciones:
1. Ignorarlo porque es improbable y quizás nunca ocurra.
2. Restringir el dominio del algoritmo para excluirlo.
3. Corregir el algoritmo.

Errores de lógica: son aquellos errores que se detectan después de que se ha definido en forma adecuada el dominio de un algoritmo, en la etapa de prueba o verificación. Se deben principalmente a las siguientes causas:
1. Etapas incorrectas
2. Secuencia incorrecta de etapas.

Formas de expresar un algoritmo
Un mismo algoritmo puede ser expresado de distintas formas y en distintos lenguajes:
· Lenguaje común: en el lenguaje común que hablamos y escribimos; útil para comunicar un algoritmo a otra persona o en una fase de análisis previo de un sistema computacional.
· Diagramas de flujo: es un lenguaje gráfico; útil para visualizar en forma rápida la secuencia lógica de pasos a seguir por un algoritmo y de gran ayuda para la traducción del mismo a un programa de computación.
· Tablas de decisión: expresan en forma de tablas las distintas alternativas que intervienen en un algoritmo y las operaciones elementales a realizar en cada alternativa. Muy útiles para analizar la lógica de un algoritmo en forma exhaustiva y precisa.
· Lenguajes de pseudocódigos: tipo de lenguaje compuesto por una lista de enunciados, algunos de los cuales coinciden con los que se usan en los diagramas de flujo. En la lógica del algoritmo se pueden utilizar distintos tipos de organización o estructuras de control. Se pseudo codifican las estructuras de control de la programación estructurada.
· Lenguajes de programación: es la forma obligada de expresión de un algoritmo para que pueda ser leído, ejecutado y almacenado por el computador.

Proceso de resolución de problemas

El proceso de resolver problemas mediante computadoras se describe en la figura 1. Se trata de encontrar un método por medio del cual se pueda resolver un problema. Una vez que se haga esto, la computadora se hace cargo del mismo y suministra las respuestas a la pregunta. Esta es una simplificación porque una vez que se tiene un método es necesario expresar este método en una forma en que la computadora pueda operarlo.
Esto se representa en la figura 2. Por lo tanto, la persona que desea utilizar una computadora para resolver un problema de computación, debe ejecutar tres trabajos:
· Algoritmación: dado el problema, debe ser capaz de elaborar un método de resolución o algoritmo (heurística o resolución de problemas).
· Codificación: habiendo diseñado el algoritmo, se requiere convertirlo en una forma que la computadora pueda manejar (codificación utilizando un lenguaje de programación). Se obtiene así el programa.
· Operación: por último, debe hacer que la computadora ejecute el programa para producir los resultados deseados y esto requiere un conocimiento del diseño de la máquina, de su organización y operación.

Es conveniente destacar la diferencia entre dos conceptos importantes: programación y codificación.
· Programación: es un proceso mental dividido en varias etapas que abarca desde la comprensión del problema que va a resolverse hasta entender en detalle qué método se utilizará para obtener la solución y qué lenguaje se empleará para introducirlo en la computadora.
· Codificación: es describir en términos de algún lenguaje de programación adecuado, el algoritmo. Es una etapa de la programación.
En consecuencia, la Programación incluye las etapas de algoritmación y codificación.



Problemas de Computación

Una vez que se comprende un problema, se debe decidir qué tipo de problema es. Dos tipos de problemas comunes son:
1. Los problemas que buscan respuestas: si un ejercicio implica el cálculo del número de palabras que hay en un libro o la bisección de una línea utilizando regla y compás, se trata de un trabajo en que se debe encontrar algo que se desconoce. La forma en que esto se haga no es de particular importancia, siempre y cuando se obtenga la respuesta correcta.
2. Los problemas que buscan pruebas: cuando se pide que se pruebe que hay 720 formas de colocar seis libros en un fila se está dando la respuesta. La tarea es distinta a la de encontrar una respuesta porque ya se sabe lo que se desea. Todo lo que se tiene que hacer es determinar la relación entre los datos y la respuesta.
Es importante observar que un problema en que se buscan respuestas se tiene que elaborar una solución, mientras que cuando se pide que se pruebe sólo es necesario demostrar que existe (o no existe) una solución, sin crearla.
Los problemas de computación no pueden ser problemas en que se busquen pruebas porque el propósito del trabajo de las computadoras es encontrar respuestas que no se conocen de antemano. Pero tampoco se les puede considerar como problemas en que se busquen respuestas porque es la computadora misma la que determina la respuesta, no la persona que trabaja con ella.
3. Los problemas de computación pertenecen a una tercera clase: los problemas que buscan métodos. Aquí se busca un método mediante el cual se pueda derivar una respuesta.