Algoritmos y estructuras de datos

Cuando escribimos un programa de cómputo, generalmente implementamos un método que ya se ha usado previamente para resolver algún problema. Este método, frecuentemente es independiente de una computadora particular para poder usarse, se puede utilizar en cualquier computadora y en cualquier lenguaje. 

Es este método, más que el propio programa de cómputo, el que debemos estudiar para saber cómo resolver el problema. El término algoritmo se usa en sistemas computacionales para describir un método para resolver problemas al implementarse como un programa de computadora. La informática se trata de algoritmos: son el objeto central de muchas, sino de la mayoría, de las áreas de este campo.

Muchos algoritmos de interés involucran métodos para organizar los datos involucrados en los cálculos. Los objetos creados de este modo son llamados estructuras de datos, y también son objetos de estudio de los sistemas computacionales. Por lo tanto, los algoritmos y las estructuras de datos van de la mano. Estoy convencido que las estructuras de datos existen tanto como productos intermedios como productos finales de los algoritmos y debemos estudiarlas para poder entender estos últimos. 

Cuando usamos una computadora para resolver un problema, típicamente nos enfrentamos a un número variado de posibles soluciones. Para problemas pequeños, no importa qué enfoque usemos, siempre y cuando resuelva el problema correctamente. Sin embargo, para problemas grandes (o aplicaciones donde necesitamos resolver un gran número de problemas pequeños), vamos a necesitar crear métodos que usen el tiempo o el espacio de la manera más eficiente posible.

La razón principal para aprender sobre diseño de algoritmos es que esta disciplina nos brinda el potencial de obtener enormes ahorros, incluso hasta el punto de permitir realizar tareas que de otra manera serían imposibles. En una aplicación donde se procesan millones de objetos, no es raro poder hacer un programa millones de veces más rápido utilizando un algoritmo bien diseñado. Por otro lado, invertir dinero o tiempo adicional para comprar e instalar una computadora nueva solo tiene el potencial de acelerar un programa por un factor de 10 o 100. El diseño cuidadoso de algoritmos es una parte extremadamente efectiva del proceso de resolver un problema grande, sin importar el área de la aplicación.

Cuando se está desarrollando un programa muy grande o complejo, es una buena inversión tratar de entender y definir el problema que se va a resolver, administrar la complejidad y descomponerlo en subtareas más tareas que puedan implementarse fácilmente. A menudo, muchos de los algoritmos necesarios después de la descomposición son triviales de implementar. Sin embargo, en la mayoría de los casos, hay unos pocos algoritmos cuya elección es crítica porque la mayor parte de los recursos del sistema se usarán para ejecutarlos. Éste es el tipo de algoritmos en los que nos concentramos en esta serie. Estudiaremos una variedad de algoritmos fundamentales que son útiles para resolver problemas enormes en una amplia variedad de áreas de aplicación.

La compartición de programas en sistemas informáticos se está generalizando. Si bien esperamos utilizar gran parte de los algoritmos que veremos en esta serie de artículos, la realidad es que solo vamos a implementar unos cuantos. Por ejemplo, las librerías Java ya contienen implementaciones de muchos algoritmos fundamentales.

Sin embargo, implementar versiones simples de algoritmos básicos nos ayuda a entenderlos mejor y, por tanto, a usar y ajustar las versiones avanzadas de librerías de forma más efectiva. Aún más importante, la oportunidad de reimplementar algoritmos básicos surge con frecuencia. La razón principal es que a menudo nos enfrentamos a entornos informáticos completamente nuevos (hardware y software) con características que las implementaciones antiguas podrían no aprovecharse al máximo. En otras palabras, a menudo implementamos algoritmos básicos adaptados a nuestro problema, en lugar de depender de rutinas del sistema, para que nuestras soluciones sean más portables y duraderas.

Otro motivo común para reimplementar algoritmos básicos es que, a pesar de los avances de Java, los mecanismos para compartir software no siempre son lo suficientemente potentes como para permitirnos adaptar convenientemente los programas de las librerías para que funcionen de manera efectiva en tareas específicas.

Los programas informáticos suelen estar sobreoptimizados. No vale la pena esforzarse por garantizar que una implementación de un algoritmo en particular sea la más eficiente posible, a menos que el algoritmo se vaya a utilizar para una tarea enorme o muchas veces. De lo contrario, una implementación cuidadosa y relativamente simple será suficiente: podemos tener cierta confianza en que funcionará y es probable que se ejecute de 5 a 10 veces más lento en el peor de los casos que la mejor versión posible, lo que significa que puede tardar unos segundos adicionales. Por el contrario, la elección adecuada del algoritmo en primer lugar puede suponer una diferencia de un factor de 100 o 1000 o más, lo que podría traducirse en minutos, horas o incluso más en tiempo de ejecución.

La idea es centrarnos en las implementaciones más simples y razonables de los mejores algoritmos. Prestaremos especial atención a la codificación cuidadosa de las partes críticas de los algoritmos y nos esforzaremos en señalar dónde el esfuerzo de optimización de bajo nivel podría ser más beneficioso.

Elegir el mejor algoritmo para una tarea específica puede ser complejo e incluso requerir análisis matemáticos sofisticados. La rama de la computación que estudia estas cuestiones se llama análisis de algoritmos. Mediante este análisis, se ha demostrado que muchos de los algoritmos que estudiaremos tienen un rendimiento excelente, mientras que otros simplemente han demostrado funcionar bien a través de la experiencia.

Nuestro objetivo principal es aprender algoritmos razonables para tareas importantes. Sin embargo, también prestaremos mucha atención al rendimiento comparativo de estos métodos. No debemos utilizar un algoritmo sin tener una idea de los recursos que podría consumir. Es importante ser conscientes del rendimiento esperado de nuestros algoritmos.