Algoritmo i

1. Introducción

Estas notas son una Introducción a la Resolución Sistemática de Problemas mediante Algoritmos. El objetivo de las notas es presentar una metodología que permita obtener soluciones algorítmicas correctas de un problema dado.

La Programación de computadoras comenzó como un arte, y aún hoy en día mucha gente aprende a programar sólo mirando a otros proceder (ej. Unprofesor, un amigo, etc.), y mediante el hábito, sin conocimiento de los principios que hay detrás de esta actividad. En los últimos años, sin embargo, la investigación en el área ha arrojado teoría suficiente para que estemos en capacidad de comenzar a enseñar estos principios en los cursos básicos de enseñanza de la programación.

La metodología que proponemos toca la raíz de los problemasactuales en programación y provee principios básicos para superarlos. Uno de estos problemas es que los programadores han tenido poco conocimiento de lo que significa que un programa sea correcto y de cómo probar que un programa es correcto. Cuando decimos “probar” no queremos decir necesariamente que tengamos que usar un formalismo o las matemáticas, lo que queremos expresar es “encontrar unargumento que convenza al lector de la veracidad de algo”. Desafortunadamente, los programadores no son muy adeptos a esto, basta observar la cantidad de tiempo que se gasta en “debugging” (proceso de depuración de programas para eliminar entre otros errores, los errores de lógica), y esto ¿por qué? Porque el método de programación normalmente usado ha sido “desarrollo por casos de prueba”, es decir, elprograma es desarrollado sobre la base de algunos ejemplos de lo que el programa debe hacer. A medida que se encuentran más casos de prueba, estos son ejecutados y el programa es modificado para que tome en cuenta los nuevos casos de prueba. El proceso continúa con modificaciones del programa a cada paso, hasta que se piensa que ya han sido considerados suficientes casos de prueba.

Granparte del problema se ha debido a que no hemos poseído herramientas adecuadas. El razonamiento sobre cómo programar se ha basado en cómo los programas son ejecutados, y los argumentos sobre la corrección (diremos de ahora en adelante “correctitud”, pues el término corrección se entiende como si quisiéramos corregir un programa y lo que queremos es probar que un programa es correcto) de un programa sehan basado en sólo determinar casos de prueba que son probados corriendo el programa o simulados a mano. La intuición y el sentido común han sido simplemente insuficientes. Por otro lado, no siempre ha estado claro lo que significa que un programa sea “correcto”, en parte porque la especificación de programas ha sido también un tema muy impreciso.

El principio básico de estas notas será eldesarrollo simultáneo de un programa con la demostración de la correctitud. Es muy difícil probar la correctitud de un programa ya hecho, por lo que es más conveniente usar las ideas de prueba de correctitud a medida que se desarrolla el programa. Por otra parte, si sabemos que un programa es correcto, no tendrá sentido hacer muchas pruebas al programa con casos de prueba, sólo se harán lasnecesarias para corroborar que no cometimos un error, como humanos que somos, por ejemplo, en la transcripción del programa; además, así también reduciremos la cantidad de tiempo dedicada a la tediosa tarea del “debugging”. Para ello trataremos el tema de especificación de programas (o problemas) y el concepto de prueba formal de programas a partir del significado formal (la semántica) de losconstructores básicos (es decir, las instrucciones del lenguaje de programación) que utilizaremos para hacer los programas.

Conscientes de que estas notas van dirigidas a un primer curso sobre enseñanza de la programación, el enfoque que llevaremos a cabo trata de balancear el uso de la intuición y el sentido común, con técnicas más formales de desarrollo de programas.

1. Problemas,...