Tecnologías de la Información y Comunicación (TIC)

PROGRAMACION-ALGORITMOS

La importancia de un algoritmo radica en mostrar la manera de llevar a cabo procesos y resolver mecánicamente problemas matemáticos o de otro tipo. Al igual que las funciones matemáticas, los algoritmos reciben una entrada y la transforman en una salida, comportándose como una caja negra. Sin embargo, no toda caja negra que convierta una entrada en una salida se puede considerar un algoritmo: para que un algoritmo pueda ser considerado como tal, debe ser una secuencia ordenada, finita y definida (formalización de su comportamiento) de instrucciones. De este modo se puede seguir y predecir el comportamiento del algoritmo para cualquier entrada posible (salvo algoritmos probabilistas, que tiene usualmente una salida distinta), a partir del seguimiento de esa secuencia de instrucciones, que como es ordenada y definida, no da lugar a ambigüedades y puede seguirse su traza.

El concepto de algoritmo, aunque similar y obviamente relacionado, no debe confundirse con el concepto de programa. Mientras el primero es la especificación de un conjunto de pasos (operaciones, instrucciones, órdenes,...) orientados a la resolución de un problema (método), el segundo es ese conjunto de operaciones especificadas en un determinado lenguaje de programación y para un computador concreto, susceptible de ser ejecutado (o compilado o interpretado). Un algoritmo, estrictamente hablando, no puede ejecutarse hasta que se implementa, ya sea en un lenguaje de programación, en un circuito eléctrico, en un aparato mecánico, usando papel y lápiz, o en algún otro modelo de computación.

La mayoría de los algoritmos involucran métodos de organizar los datos que intervienen en el cómputo. Estos objetos creados son llamados, de esta manera la estructura de los datos, y también son objetos centrales del estudio en la informática. De esta forma, los algoritmos y estructuras de los datos van siempre de la mano. Los algoritmos simples pueden dar lugar a una estructura de datos complicada y, recíprocamente, los algoritmos complicados pueden usar estructuras de los datos simples.

Cuando usamos una computadora para ayudarnos a resolver un problema, nos enfrentamos típicamente con varios posibles esquemas. Para los problemas pequeños, lo que apenas importa es que lo usemos, con tal de que se tenga uno que resuelva el problema correctamente. Para los problemas grandes (o aplicaciones dónde nosotros necesitamos resolver un gran número de problemas pequeños), sin embargo, nos motivamos en inventar métodos que usan tiempo eficazmente de forma rápida como sea posible.

Cuando un programa de computadora es grande o complejo, este será desarrollado con mucho esfuerzo, ya que se debe comprender y definir el problema a ser resuelto, manejando su complejidad, y descomponiéndolo en partes más pequeñas que puedan resolverse más fácilmente. A menudo, muchos de los algoritmos que se necesitan, después de la descomposición son triviales al instrumento. En la mayoría de los casos, sin embargo, existen algoritmos cuyo funcionamiento es crítico porque alguno o varios de los recursos del sistema (memoria, tiempos de uso de procesador, etc.) pueden agotarse durante su funcionamiento.

Características de los algoritmos

El científico de computación Donald Knuth ofreció una lista de cinco propiedades, que son ampliamente aceptadas como requisitos para un algoritmo:

1. Carácter finito. "Un algoritmo siempre debe terminar después de un número finito de pasos".
2. Precisión. "Cada paso de un algoritmo debe estar precisamente definido; las operaciones a llevar a cabo deben ser especificadas de manera rigurosa y no ambigua para cada caso".
3. Entrada. "Un algoritmo tiene cero o más entradas: cantidades que le son dadas antes de que el algoritmo comience, o dinámicamente mientras el algoritmo corre. Estas entradas son tomadas de conjuntos específicos de objetos".
4. Salida. "Un algoritmo tiene una o más salidas: cantidades que tienen una relación específica con las entradas".
5. Eficacia. "También se espera que un algoritmo sea eficaz, en el sentido de que todas las operaciones a realizar en un algoritmo deben ser suficientemente básicas como para que en principio puedan ser hechas de manera exacta y en un tiempo finito por un hombre usando lápiz y papel".

Knuth admite que, aunque su descripción pueda ser intuitivamente clara, carece de rigor formal, puesto que no está exactamente claro qué significa "precisamente definido", "de manera rigurosa y no ambigua", o "suficientemente básicas", y así sucesivamente.

A partir del carácter finito y de la salida se deduce que ante una misma situación inicial (o valores de entrada) un algoritmo debe proporcionar siempre el mismo resultado (o salida), con excepción de los algoritmos probabilistas.

Algoritmos y funciones

Formalmente, un algoritmo calcula a una función. Como cualquier conjunto finito es numerable, y cualquier conjunto no numerable se puede expresar en términos del conjunto de los números naturales (infinito, pero numerable, de hecho no existe otro conjunto más grande que sea también numerable), en esencia, todo algoritmo calcula a funciones definidas en los numeros naturales. En este punto, una función está parcial o totalmente definida. Una función es parcial cuando hay números naturales que no pertenecen a su dominio (es decir, hay números naturales sobre los que no está definida la función), y una función es total en caso contrario.

Si una función es parcial, el algoritmo que lo calcula solo devolverá un resultado (es decir gasta un tiempo de cálculo finito) para los valores en los que la función está definida, no devolviendo resultado (el tiempo de cálculo es infinito) para el resto de valores. Si un algoritmo que calcula a una función parcial devolviera un resultado para los valores no definidos de la función, entonces no calcularía a esa función sino a otra. Del mismo modo, un algoritmo que calcula a una función total siempre devuelve un resultado para todo valor, y que al igual que las funciones parciales, éste debe coincidir exactamente con el valor que devuelve la función a la que calcula; y reiterativamente, en caso contrario, no calcularía a esa función sino a otra. Así, todo algoritmo (secuencia de pasos finita, ordenada y definida) calcula a una función definida sobre los números naturales, sea cuál sea ésta su naturaleza.

Toda función para la cual exista un algoritmo que lo calcule se denomina función computable (parcialmente computable o totalmente computable depende del grado de definición de la función en cuestión), pero existen funciones que no pueden ser calculadas como la función de Ackermann; a este último tipo de funciones se las denomina funciones no computables.

Medios de expresión de un algoritmo

Los algoritmos pueden ser expresados de muchas maneras, incluyendo al lenguaje natural, pseudocódigo, diagramas de flujo y lenguajes de programación entre otros. Las descripciones en lenguaje natural tienden a ser ambiguas y extensas. El usar pseudocódigo y diagramas de flujo evita muchas ambigüedades del lenguaje natural. Dichas expresiones son formas más estructuradas para representar algoritmos; no obstante, se mantienen independientes de un lenguaje de programación específico.

La descripción de un algoritmo usualmente se hace en tres niveles:

1. Descripción de alto nivel. Se establece el problema, se selecciona un modelo matemático y se explica el algoritmo de manera verbal, posiblemente con ilustraciones y omitiendo detalles.
2. Descripción formal. Se usa pseudocódigo para describir la secuencia de pasos que encuentran la solución.
3. Implementación. Se muestra el algoritmo expresado en un lenguaje de programación específico o algún objeto capaz de llevar a cabo instrucciones.

También es posible incluir un teorema que demuestre que el algoritmo es correcto, un análisis de complejidad o ambos.

Diagrama de flujo. Expresa un algoritmo para calcular la raíz cuadrada de un número x

Diagrama de flujo

Los diagramas de flujo son descripciones gráficas de algoritmos; usan símbolos conectados con flechas para indicar la secuencia de instrucciones y están regidos por ISO.

Los diagramas de flujo son usados para representar algoritmos pequeños, ya que abarcan mucho espacio y su construcción es laboriosa. Por su facilidad de lectura son usados como introducción a los algoritmos, descripción de un lenguaje y descripción de procesos a personas ajenas a la computación.

Pseudocódigo.

Pseudocódigo es la descripción de un algoritmo que asemeja a un lenguaje de programación pero con algunas convenciones del lenguaje natural. Tiene varias ventajas con respecto a los diagramas de flujo, entre las que se destaca el poco espacio que se requiere para representar instrucciones complejas. El pseudocódigo no está regido por ningún estándar. pseudo viene de falso y por ende es un codigo al que aunque es entendible no se aplica al proceso que debe realizar la maquina.

La palabra algoritmo proviene del nombre del matemático llamado Muhammad ibn Musa al-Jwarizmi que vivió entre los siglos VIII y IX. Su trabajo consistió en preservar y difundir el conocimiento de la antigua Grecia y de la India. Sus libros eran de fácil comprensión, de ahí que su principal logro no fuera el de crear nuevos teoremas o corrientes de pensamiento, sino el de simplificar la matemática a punto tal que pudieran ser comprendidas y aplicadas por un mayor número de personas. Cabe destacar cómo señaló las virtudes del sistema decimal indio (en contra de los sistemas tradicionales árabes) y cómo explicó que, mediante una especificación clara y concisa de cómo calcular sistemáticamente, se podrían definir algoritmos que fueran usados en dispositivos mecánicos en vez de las manos (por ejemplo, ábacos). También estudió la manera de reducir las operaciones que formaban el cálculo. Es por esto que aún no siendo el creador del primer algoritmo, el concepto lleva aunque no su nombre, sí su pseudónimo.

Así, de la palabra algorismo, que originalmente hacía referencia a las reglas de uso de la aritmética utilizando dígitos árabes, se evolucionó a la palabra latina, derivación de al-Khwarizmi, algobarismus, que más tarde mutaría a algoritmo en el siglo XVIII. La palabra ha cambiado de forma que en su definición se incluye a todos los procedimientos finitos para resolver problemas.

Ya en el siglo XIX, se produjo el primer algoritmo escrito para un computador. La autora fue Ada Byron, en cuyos escritos se detallaban la máquina analítica en 1842. Por ello que es considerada por muchos como la primera programadora aunque, desde Charles Babbage, nadie completó su máquina, por lo que el algoritmo nunca se implementó.

La falta de rigor matemático en la definición de "procedimiento bien definido" para los algoritmos trajo algunas dificultades a los matemáticos y lógicos del siglo XIX y comienzos de XX. Este problema fue en gran parte resuelto con la descripción de la máquina de Turing, un modelo abstracto de computadora formulado por Alan Turing, y la demostración de que cualquier método anticipado por otros matemáticos que pueda encontrarse para describir "procedimientos bien definidos" puede ser emulado en una máquina de Turing (una afirmación conocida como "tesis de Church-Turing").

En la actualidad, el criterio formal para definir un algoritmo es que se trata de un proceso que puede implementarse en una máquina de Turing completamente especificada, o en alguno de los formalismos equivalentes. El interés original de Turing era el problema de la detención: decidir cuándo un algoritmo describe un procedimiento de terminación. En términos prácticos importa más la teoría de la complejidad computacional, que incluye los problemas llamados NP-completos, es decir aquellos sobre los que generalmente se presume que requerirán tiempo más que polinómico para cualquier algoritmo (determinístico). NP denota la clase de los problemas de decisión que pueden ser resueltos en tiempo polinómico por una máquina de Turing no determinística.

Tipos de algoritmos según su función

• Algoritmo de ordenamiento
• Algoritmo de búsqueda

Técnicas de diseño de algoritmos

• Algoritmos voraces (greedy): seleccionan los elementos más prometedores del conjunto de candidatos hasta encontrar una solución. En la mayoría de los casos la solución no es óptima.
• Algoritmos paralelos: permiten la división de un problema en subproblemas de forma que se puedan ejecutar de forma simultánea en varios procesadores.
• Algoritmos probabilísticos: algunos de los pasos de este tipo de algoritmos están en función de valores pseudoaleatorios
• Algoritmos determinísticos: El comportamiento del algoritmo es lineal: cada paso del algoritmo tiene únicamente un paso sucesor y otro ancesor.
• Algoritmos no determinísticos: El comportamiento del algoritmo tiene forma de árbol y a cada paso del algoritmo puede bifurcarse a cualquier número de pasos inmediatamente posteriores, además todas las ramas se ejecutan simultáneamente.
• Divide y vencerás: dividen el problema en subconjuntos disjuntos obteniendo una solución de cada uno de ellos para después unirlas, logrando así la solución al problema completo.
• Metaheurísticas: encuentran soluciones aproximadas (no óptimas) a problemas basándose en un conocimiento anterior (a veces llamado experiencia) de los mismos.
• Programación dinámica: intenta resolver problemas disminuyendo su coste computacional aumentando el coste espacial.
• Ramificación y acotación: se basa en la construcción de las soluciones al problema mediante un árbol implícito que se recorre de forma controlada encontrando las mejores soluciones.
• Vuelta Atrás (Backtracking): se construye el espacio de soluciones del problema en un árbol que se examina completamente, almacenando las soluciones menos costosas.