## 1.1 EL ROL DE LOS ALGORITMOS EN LA COMPUTACIÓN

El término Algoritmo proviene del matemático árabe Al'Khwarizmi, que escribió un tratado sobre los números. Este texto se perdió, pero su versión latina, Algoritmi de Numero Indorum, sí se conoce.

El trabajo de Al'Khwarizmi permitió preservar y difundir el conocimiento de los griegos (con la notable excepción del trabajo de Diofanto) e indios, pilares de nuestra civilización. Rescató de los griegos la rigurosidad y de los indios la simplicidad (en vez de una larga demostración, usar un diagrama junto a la palabra Mira). Sus libros son intuitivos y prácticos, y su principal contribución fue simplificar las matemáticas a un nivel entendible por no expertos. En particular muestran las ventajas de usar el sistema decimal indio, un atrevimiento para su época, dado lo tradicional de la cultura árabe.

La exposición clara de cómo calcular de una manera sistemática a través de algoritmos diseñados para ser usados con algún tipo de dispositivo mecánico similar a un ábaco, más que con lápiz y papel, muestra la intuición y el poder de abstracción de Al'Khwarizmi. Hasta se preocupaba de reducir el número de operaciones necesarias en cada cálculo. Por esta razón, aunque no haya sido él el inventor del primer algoritmo, merece que este concepto esté asociado a su nombre.

Los babilonios que habitaron en la antigua Mesopotamia, empleaban unas pequeñas bolas hechas de semillas o pequeñas piedras, a manera de"cuentas" y que eran agrupadas en carriles de caña. Más aún, en 1.800 A.C. un matemático babilónico inventó los algoritmos que le permitieron resolver problemas de cálculo numérico. En 1850 A.C., un algoritmo de multiplicación similar al de expansión binaria es usado por los egipcios.

La teoría de las ciencias de la computación trata cualquier objeto computacional para el cual se puede crear un buen modelo. La investigación en modelos formales de computación se inició en los 30's y 40's por Turing, Post, Kleene, Church y otros. En los 50's y 60's los lenguajes de programación, compiladores y sistemas operativos estaban en desarrollo, por lo tanto, se convirtieron tanto en el sujeto como la base para la mayoría del trabajo teórico.

El poder de las computadoras en este período estaba limitado por procesadores lentos y por pequeñas cantidades de memoria. Así, se desarrollaron teorías (modelos, algoritmos y análisis) para hacer un uso eficiente de ellas. Esto dió origen al desarrollo del área que ahora se conoce como "Algoritmos y Estructuras de Datos". Al mismo tiempo se hicieron estudios para comprender la complejidad inherente en la solución de algunos problemas. Esto dió origen a lo que se conoce como la jerarquía de problemas computacionales y al área de "Complejidad Computacional".

Definición de Algoritmo

El concepto intuitivo de algoritmo, lo tenemos prácticamente todos: Un algoritmo es una serie finita de pasos para resolver un problema.
Hay que hacer énfasis en dos aspectos para que un algoritmo exista:

1. El número de pasos debe ser finito. De esta manera el algoritmo debe terminar en un tiempo finito con la solución del problema,
2. El algoritmo debe ser capaz de determinar la solución del problema.
De este modo, podemos definir algoritmo como un "conjunto de reglas operacionales inherentes a un cómputo". Se trata de un método sistemático, susceptible de ser realizado mecánicamente, para resolver un problema dado.

Siempre que se desee resolver un problema hay que plantearse qué algoritmo utilizar. La respuesta a esta cuestión puede depender de numerosos factores, a saber, el tamaño del problema, el modo en que está planteado y el tipo y la potencia del equipo disponible para su resolución.

Características de un algoritmo

1. Entrada: definir lo que necesita el algoritmo.
2. Salida: definir lo que produce.
3. No ambiguo: explícito, siempre sabe qué comando ejecutar.
4. Finito: El algoritmo termina en un número finito de pasos.
5. Correcto: Hace lo que se supone que debe hacer. La solución es correcta.
6. Efectividad: Cada instrucción se completa en tiempo finito. Cada instrucción debe ser lo suficientemente básica como para que en principio pueda ser ejecutada por cualquier persona usando papel y lápiz.

Así podemos, decir que un algoritmo es un conjunto finito de instrucciones precisas para resolver un problema. Un algoritmo es un método o proceso seguido para resolver un problema. Si el problema es visto como una función, entonces el algoritmo toma una entrada y la transforma en la salida. Un problema es una función o asociación de entradas con salidas. Un problema puede tener muchos algoritmos.

Por tanto, un algoritmo es un procedimiento para resolver un problema cuyos pasos son concretos y no ambiguos. El algoritmo debe ser correcto, de longitud finita y debe terminar para todas las entradas. Un programa es una instanciación de un algoritmo en un lenguaje de programación.

###