Los algoritmos y la computación - 4ta Parte

Analizar un algoritmo ha llegado a significar predecir los recursos que el algoritmo requiere. En ocasiones, recursos como la memoria, el ancho de banda de las comunicaciones o el hardware del computador son la principal preocupación, pero la mayoría de las veces lo que se quiere medir es el tiempo de cálculo.

Por lo general, analizando varios algoritmos candidatos para un problema, podemos identificar el más eficiente. Este análisis puede indicar más de un candidato viable, pero a menudo podemos descartar varios algoritmos inferiores en el proceso.

Antes de poder analizar un algoritmo, debemos tener un modelo de la tecnología de implementación que utilizaremos, incluyendo un modelo para los recursos de esa tecnología y sus costos.

_{Imagen de Pixabay}

En sentido estricto, deberíamos definir con precisión las instrucciones del modelo RAM y sus costos. Sin embargo, hacerlo sería tedioso y aportaría poca información sobre el diseño y el análisis de algoritmos. Sin embargo, debemos tener cuidado de no abusar del modelo RAM.

Por ejemplo,

¿qué pasaría si una RAM tuviera una instrucción que ordenara?

Entonces podríamos ordenar en una sola instrucción. Una RAM así no sería realista, ya que los computadores reales no tienen esas instrucciones. El modelo de RAM contiene instrucciones que se encuentran comúnmente en los computadores reales:

• aritmética (como sumar, restar, multiplicar, dividir, resto, piso, techo),
• movimiento de datos (cargar, almacenar, copiar) y
• control (bifurcación condicional e incondicional, llamada a subrutina y retorno).

Cada una de estas instrucciones requiere una cantidad de tiempo constante. Los tipos de datos en el modelo RAM son enteros y de punto flotante (para almacenar números reales).

Por ejemplo, cuando se trabaja con entradas de tamaño n, normalmente asumimos que los enteros están representados por c log(n) bits para alguna constante c mayor que 1, lo cual es necesario para que cada palabra pueda contener el valor de n, permitiéndonos indexar los elementos de entrada individuales, y restringimos c para que sea una constante y el tamaño de la palabra no crezca arbitrariamente.

Si el tamaño de la palabra pudiera crecer arbitrariamente, podríamos almacenar enormes cantidades de datos en una palabra y operar con todo ello en tiempo constante, lo que es claramente un escenario poco realista.

_{Imagen de Pixabay}

Los ordenadores reales contienen instrucciones que no figuran en la lista anterior, y tales instrucciones representan una zona gris en el modelo de la RAM. Por ejemplo,

¿es la exponenciación una instrucción de tiempo constante?

En el caso general, NO; se necesitan varias instrucciones para calcular x^y cuando x e y son números reales. Sin embargo, en situaciones restringidas, la exponenciación es una operación de tiempo constante.

Muchos computadores tienen una instrucción de desplazamiento a la izquierda, que en tiempo constante desplaza los bits de un entero en k posiciones a la izquierda. En la mayoría de los computadores, desplazar los bits de un entero una posición a la izquierda equivale a multiplicar por 2, por lo que desplazar los bits k posiciones a la izquierda equivale a multiplicar por 2^k. Por lo tanto, estos computadores pueden calcular 2^k en una instrucción de tiempo constante desplazando el entero 1 en k posiciones a la izquierda, siempre que siempre que k no sea mayor que el número de bits de una palabra del computador.

_{Imagen de Pixabay}

En el modelo de RAM, no se intenta modelar la jerarquía de memoria que es común en los computadores actuales. Es decir, no se modela las cachés ni la memoria virtual. Varios modelos computacionales intentan dar cuenta de los efectos de la jerarquía de memoria, que a su veces son significativos en programas reales en máquinas reales.

Analizar un algoritmo sencillo en el modelo RAM puede ser un reto. Las herramientas matemáticas necesarias pueden incluir:

• la combinatoria,
• la teoría de la probabilidad,
• la destreza algebraica y
• la capacidad de identificar los términos más significativos de una fórmula.

Como el comportamiento de un algoritmo puede ser diferente para cada entrada posible, necesitamos un medio para resumir ese comportamiento en fórmulas sencillas y fáciles de entender. Aunque normalmente se selecciona un solo modelo de máquina para analizar un algoritmo determinado, todavía existen muchas opciones a la hora de decidir cómo expresar el análisis. Se quiere una forma que sea sencilla de escribir y manipular, que muestre las características importantes de un algoritmo y que sea fácil de entender de las necesidades de recursos de un algoritmo y que suprima los detalles tediosos.

---

_{Imagen de Pixabay}

---

Si quedastes fascinado con este apasionante tema de los algoritmos y la computación, no te pierdas la próxima publicación sobre este tema, si deseas ampliar más te invito a leer las siguientes referencias:

• Alfred V. Aho, John E. Hopcroft, and Jeffrey D. Ullman. The Design and Analysis of Computer Algorithms. Addison-Wesley, 1974.
• Selim G. Akl. The Design and Analysis of Parallel Algorithms. Prentice Hall, 1989.
• Mikhail J. Atallah, editor. Algorithms and Theory of Computation Handbook. CRC Press, 1999.
• Eric Bach and Jeffrey Shallit. Algorithmic Number Theory—Volume I: Efficient Algorithms. The MIT Press, 1996.