El papel de los algoritmos en la computación

Mucho del énfasis actual en el desarrollo de software ha sido sobre las herramientas de desarrollo.  Si bien las herramientas son importantes, no debemos descuidar el desarrollo de habilidades del programador. El conocimiento formal sobre algoritmos muchas veces puede hacer la diferencia entre un desarrollador promedio y un desarrollador de primera.

Informalmente podemos decir que un algoritmo es un procedimiento computacional bien definido que toma una serie de valores como entrada y produce un valor o una serie de valores como salida. 

Se dice que un algoritmo es correcto si para cada conjunto de valores de entrada, el algoritmo termina con la salida correcta. Cuando esto ocurre se dice que el algoritmo resuelve el problema de computo que se le ha dado.

Hay una gran cantidad problemas para los cuales se han creado algoritmos. Ejemplos de algunos algoritmos sofisticados: Análisis del genoma humano, motores de búsqueda, sistemas criptográficos para el comercio electrónico, asignación de recursos escasos en manufactura, etc.

Los problemas algorítmicos interesantes exiben dos características:

1. Tienen muchas soluciones candidatas posibles, pero muchas de ellas no resuelven el problema y puede ser complicado encontrar aquella que lo hace.

2. Tienen aplicaciones a problemas de la vida real. 

Conjuntamente con los algoritmos esta el estudio de las estructuras de datos. No hay una estructura de datos adecuada para todos los propósitos, por eso es importante entender las limitaciones y ventajas de cada una de ellas. Así mismo hay una gran cantidad de técnicas que se pueden utilizar, es importante tener familiaridad con ellas para poder usarlas al diseñar nuestros propios algoritmos.

Problemas NP-Complete

Por lo general buscamos encontrar algoritmos eficientes, sin embargo hay problemas para los cuales no existen soluciones eficientes.  Un tipo de estos problemas son los conocidos como NP-Complete. Por que son estos problemas interesantes? Pues aunque no se les ha encontrado una solución eficiente, tampoco se ha podido probar si existe o no tal solución. La propiedad mas interesante de estos problemas es que si se encuentra una solución eficiente para uno de ellos esa solución sera aplicable para todos ellos. Es importante conocer de estos problemas por que es frecuente encontrarlos en aplicaciones del mundo real. Si puedes mostrar que algún problema es NP-Complete, entonces sabes que el mejor uso de tu tiempo esta en encontrar una buena solución aunque esta no sea la mejor solución.

Ordenes de Complejidad

Es posible que dos algoritmos diseñados para resolver el mismo problema tengan diferencias dramáticas en su eficiencia. Estas diferencias pueden ser mucho mas significativas que las diferencias debido al hardware y software. Como un ejemplo, el ordenamiento por inserción(insertion sort), toma un tiempo que es aproximadamente (c1 * n * n ) en donde n es el numero de elementos y c1 es una constante independiente de n. El ordenamiento por mezcla (merge sort), toma un tiempo que aproximadamente ( c2 * n * log(n))  En donde log(n) es el logartimo base 2 de n. En el primer caso el factor es n  y en el segundo caso el factor es log(n).

Compara el crecimiento de n con el crecimiento de log(n).

Es tal la diferencia que ya no importa que c2 sea mucho mayor que c1. O sea que cuando n crece deja de importar el hardware utilizado o el compilador, el merge sort va a ser mas rápido que el insertion sort. El análisis de algoritmos es una área muy interesante que te da una mejor claridad y entendimiento sobre como lograr algoritmos eficientes. Espero que en el futuro podamos profundizar en el tema.