Generalidades

El programador de computadoras es ante que nada una persona que resuelve problemas, por lo que para llegar a ser un programador eficaz se necesita aprender a resolver problemas de un modo riguroso y sistemático. A la metodología necesaria para resolver problemas mediante programas se denomina Metodología de la Programación. El eje central de esta metodología es el concepto, ya tratado, de algoritmo.

Un algoritmo es un método para resolver un problema. Aunque la popularización del término ha llegado con el advenimiento de la era informática, algoritmo proviene de Mohammed al-Khowarizmi, matemático persa que vivió durante el siglo IX y alcanzo gran reputación por el enunciado de las reglas para sumar, restar, multiplicar y dividir números decimales; la traducción al latín del apellido de la palabra algorismus derivo posteriormente en algoritmo. Euclides, el gran matemático griego (del siglo IV antes de Cristo) que invento un método para encontrar el máximo común divisor de dos números, se considera con Al-Khowarizmi el otro gran padre de la algoritmia (ciencia que trata de los algoritmos).

El profesor Niklaus Wirth, inventor de Pascal, Modula-2 y Oberon, titulo uno de sus mas famosos libros, Algoritmos + Estructuras de Datos = Programas, significándonos que solo se puede llegar a realizar un buen programa con el diseño de un algoritmo y una correcta estructura de datos. Esta ecuación será de una de las hipótesis fundamentales consideradas en esta obra.
La resolución de un problema exige el diseño de un algoritmo que resuelva el problema propuesto.

Los pasos para la resolución de un problema son:

Diseño de algoritmo, que describe la secuencia ordenada de pasos que conducen a la solución de un problema dado. (Análisis del problema y desarrollo del algoritmo).

Expresar el algoritmo como un programa de lenguaje de programación adecuado. (Fase de codificación.)

Ejecución y validación del programa por la computadora.

Para llegar a la realización de un programa es necesario el diseño previo de algoritmo, de modo que sin algoritmo no puede existir un programa.
Los algoritmos son independientes tanto del lenguaje de programación en que se expresan como de la computadora que lo ejecuta. En cada problema el algoritmo se puede expresar en un lenguaje diferente de programación y ejecutarse en una computadora distinta; sin embargo, el algoritmo será siempre el mismo. Así, por ejemplo, en una analogía con la vida diaria, una receta de un plato de cocina se puede expresar en español, ingles o francés, pero cualquiera que sea el lenguaje, los pasos para la elaboración del plato se realizaran sin importar el idioma del cocinero.

En la ciencia de la computación y en la programación, los algoritmos son más importantes que los lenguajes de programación o las computadoras. Un lenguaje de programación es tan solo un medio para expresar un algoritmo y una computadora es solo un procesador para ejecutarlo. Tanto el lenguaje de programación como la computadora son los medios para obtener un fin: conseguir que el algoritmo se ejecute y se efectúe el proceso correspondiente.
Dada la importancia del algoritmo en la ciencia de la computación, un aspecto muy importante será el diseño de algoritmos. El diseño de la mayoría de los algoritmos requiere creatividad y conocimientos profundos de la técnica de la programación. En esencia, la solución de un problema se puede expresar mediante un algoritmo.

La definición de un algoritmo debe definir tres partes: Entrada, Proceso y Salida. En el algoritmo de receta de cocina citado anteriormente se tendrá:

Entrada: ingrediente y utensilios empleados.

Proceso: elaboración de la receta en la cocina.

Salida: terminación del plato (por ejemplo, cordero).

Ejemplo de Algoritmo:

Un cliente ejecuta un pedido a una fábrica. Esta examina en su banco de datos la ficha del cliente; si el cliente es solvente entonces la empresa acepta el pedido; en caso contrario rechazara el pedido. Redactar el algoritmo correspondiente.

Los pasos del algoritmo son:

inicio

leer el pedido

examinar la ficha del cliente

si el cliente es solvente aceptar pedido; en caso contrario, rechazar pedido

fin

Diseño del Algoritmo:

En la etapa de análisis del proceso de programación se determina que hace el programa. En la etapa de diseño se determina como hace el programa la tarea solicitada. Los métodos mas eficaces para el proceso de diseño se basan en el conocido por Divide y Vencerás, es decir, la resolución de un problema complejo se realiza dividiendo el problema en sub problemas y a continuación dividir estos sub problemas en otros de nivel mas bajo, hasta que pueda ser implementada una solución en la computadora. Este método se conoce técnicamente como diseño descendente (Top Down) o modular. El proceso de romper el problema en cada etapa y expresar cada paso en forma más detallada se denomina refinamiento sucesivo.

Cada sub programa es resuelto mediante un modulo (sub programa) que tiene un solo punto de entrada y un solo punto de salida.
Cualquier programa bien diseñado consta de un programa principal (el modulo de nivel mas alto) que llama a sub programas (módulos de nivel mas bajo) que a su vez pueden llamar a otros sub programas. Los programas estructurados de esta forma se dice que tienen un diseño modular y el método de romper el programa en módulos más pequeño se llama Programación Modular. Los módulos pueden ser planeados, codificados, comprobados y depurados independientemente (incluso por diferentes programadores) y a continuación combinarlos entre si. El proceso implica la ejecución de los siguientes pasos hasta que el programa se termina:

• Programar módulo.
• Comprobar el módulo.
• Si es necesario, depurar el modulo.
• Combinar el modulo con los módulos anteriores.

El proceso que convierte los resultados del análisis del problema en un diseño modular con refinamiento sucesivo que permitan una posterior traducción al lenguaje se denomina diseño de algoritmo.

El diseño del algoritmo es independiente del lenguaje de programación en el que se vaya a codificar posteriormente.

5. Técnica de diseño de algoritmos

Diseño de Algoritmos: 

Hasta ahora se han realizado algunos comentarios respecto a la necesidad de diseñar algoritmos correctos y eficientes utilizando los elementos de un lenguaje de programación .Es necesario en este momento mencionar algo sobre como hacerlo. El acto de diseñar un algoritmo puede considerarse como una tarea que difícilmente podrá ser del todo automatizada.

Todo problema algorítmico es un reto para su diseñador, algunos resultan inmediatos de resolver, otros son bastante complejos. La investigación en esta área ha permitido descubrir un conjunto de métodos o esquemas de diseño hacia los cuales puede orientarse la realización de muchos algoritmos.
No obstante, y a pesar de que resulta mas adecuado en bastantes casos utilizar alguno de estos esquemas que realizar un diseño desde cero, idear un algoritmo continua siendo una labor bastante creativa donde los conocimientos y la experiencia del propio diseñador tiene un papel fundamental.

El diseño de un algoritmo que resuelva un problema es, en general, una tarea difícil. Una forma de facilitar esta labor consiste en recurrir a técnicas conocidas de diseño de algoritmos, se decir, a esquemas muy generales que pueden adaptarse a un problema particular al detallar las partes generales del esquema.

Muchos problemas pueden resolverse buscando una solución fácil y directa pero, a la vez bastante ineficiente. Este método, llamado de fuerza bruta, puede ser muy directo, pero con un poco de análisis puede encontrarse algoritmos más eficientes. El esquema mas sencillo quizás sea el llamado divide y vencerás, basado en la descomposición de un problema en subproblemas.

Otros esquemas requieren un análisis minucioso del problema de forma que la solución se vaya construyendo en etapas. Si puede preverse que decisión conviene en cada etapa para producir cierto tipo de mejor resultado, tenemos una solución voraz, si la decisión en una etapa, solo puede tomarse tras considerar varias soluciones de otras etapas mas simples, la solución es dinámica. Aun así, hay problemas cuya solución no puede hallarse sino mediante un proceso de búsqueda, a pesar de lo complejas que son las operaciones de búsqueda, su uso adecuado mediante el esquema de búsqueda con retroceso (o backtracking) permite ganar gran eficiencia respecto a soluciones de fuerza bruta.

Por ultimo, conviene conocer otros métodos de diseño de algoritmos que también resultan de utilidad práctica. Nos estamos refiriendo a métodos basados en la mejora de la eficiencia (por ejemplo, el uso de parámetros de acumulación al resolver problemas utilizando divide y vencerás, y el empleo de tablas como estructura auxiliar para la resolución eficiente de problemas donde se aplica programación dinámica), y a métodos basados en transformaciones del dominio para encontrar una solución mas fácilmente a un problema en un dominio transformado, siendo dicha solución finalmente adaptada al dominio original.

Consideraciones generales:

Si el hábil programador dispone de un recetario de algoritmos de donde poder seleccionar el más adecuado para cada problema, su tarea se simplifica.
Supongamos que disponemos de una especificación precisa, completa y consistente del problema a resolver y queremos obtener un algoritmo en el que, dados uno datos de entrada valido, se produzca cierto resultado. Si no nos importa la eficiencia del algoritmo, podríamos utilizar un algoritmo general llamado algoritmo del museo británico. Se programa un computador de manera que parta de un conjunto de axioma matemáticos y los que use para reducir aleatoriamente teoremas validos.

Aprender los principios básicos del diseño de algoritmos podemos preguntarnos por un método aceptable. El mas entendido, y quizás el mejor, es organizar el diseño sobre un esquema de algoritmo o una técnica de diseño que haya demostrado su utilidad para otros problemas. Este método de trabajo es practicable, puesto que existe un número reducido de esquema y técnicas de diseño.

El conocimiento de técnicas de diseño es solo un primer paso para el diseñador, que debe completarse con otros conocimientos y, sobre todo, con la experiencia.

A menudo los algoritmos requieren una organización bastante compleja de los datos, y es por tanto necesario un estudio previo de las estructuras de datos fundamentales. Dichas estructuras pueden implementarse de diferentes maneras, y es más, existen algoritmos para implementar dichas estructuras. El uso de estructuras de datos adecuadas pueden hacer trivial el diseño de un algoritmo, o un algoritmo muy complejo puede usar estructuras de datos muy simples.

Uno de los algoritmos más antiguos conocidos es el algoritmo de Euclides. El término algoritmo proviene del matemático Muhammad ibn Musa al-Khwarizmi, que vivió aproximadamente entre los años 780 y 850 d.C. en la actual nación Iraní. El describió la realización de operaciones elementales en el sistema de numeración decimal. De al-Khwarizmi se obtuvo la derivación algoritmo.

- Clasificación de algoritmos

  * Algoritmo determinista: en cada paso del algoritmo se determina de forma única el siguiente paso.

  * Algoritmo no determinista: deben decidir en cada paso de la ejecución entre varias alternativas y agotarlas todas antes de encontrar la solución.

Todo algoritmo tiene una serie de características, entre otras que requiere una serie de recursos, algo que es fundamental considerar a la hora de implementarlos en una máquina.

Estos recursos son principalmente:

 · El tiempo: período transcurrido entre el inicio y la finalización del algoritmo.

· La memoria: la cantidad (la medida varía según la máquina) que necesita el algoritmo para su ejecución.

Obviamente, la capacidad y el diseño de la máquina pueden afectar al diseño del algoritmo.

En general, la mayoría de los problemas tienen un parámetro de entrada que es el número de datos que hay que tratar, esto es, N. La cantidad de recursos del algoritmo es tratada como una función de N. De esta manera puede establecerse un tiempo de ejecución del algoritmo que suele ser proporcional a una de las siguientes funciones:

• 1 : Tiempo de ejecución constante. Significa que la mayoría de las instrucciones se ejecutan una vez o muy pocas.

• logN : Tiempo de ejecución logarítmico. Se puede considerar como una gran constante. La base del logaritmo (en informática la más común es la base 2) cambia la constante, pero no demasiado. El programa es más lento cuanto más crezca N, pero es inapreciable, pues logN no se duplica hasta que N llegue a N2.

• N : Tiempo de ejecución lineal. Un caso en el que N valga 40, tardará el doble que otro en que N valga 20. Un ejemplo sería un algoritmo que lee N números enteros y devuelve la media aritmética.

• N·logN : El tiempo de ejecución es N·logN. Es común encontrarlo en algoritmos como Quick Sort y otros del estilo divide y vencerás. Si N se duplica, el tiempo de ejecución es ligeramente mayor del doble.

• N2 : Tiempo de ejecución cuadrático. Suele ser habitual cuando se tratan pares de elementos de datos, como por ejemplo un bucle anidado doble. Si N se duplica, el tiempo de ejecución aumenta cuatro veces. El peor caso de entrada del algoritmo Quick Sort se ejecuta en este tiempo.