Los algoritmos se pueden clasificar de muchas formas: de acuerdo con el tipo de problema que resuelven, como algoritmos geométricos, algebraicos, de gráficas, para ADN, entre otros; de acuerdo con su tolerancia a las fallas, si las toleran o no, y qué tipo de fallas toleran.
A continuación se presentan algunos de los tipos de algoritmo más importantes. Según su procedimiento de ejecución, un algoritmo puede ser:
• Secuencial: ejecuta las instrucciones una por una y en orden.
• Paralelo: ejecuta al mismo tiempo distintas partes del algoritmo.
• Distribuido: consiste en varios algoritmos que corren en distintas computadoras, los cuales se comunican y colaboran para resolver un problema.
Según las instrucciones:
• Deterministas: cada instrucción realiza una sola operación; siempre la misma.
• No deterministas: algunas instrucciones tienen libertad para elegir qué resultado dar, entre varias opciones.
• Probabilistas: incluyen las instrucciones que pueden regresar distintos resultados, pero sin libertad de elegir; deben regresar el resultado según una distribución de probabilidades.
De acuerdo con las entradas y salidas:
• Fuera de línea: recibe una entrada, ejecuta y produce una salida.
• En línea: recibe entradas una y otra vez y debe producir salidas conforme le llegan las entradas.
Por la máquina en la que corre:
• Tradicional: una computadora usual.
• Cuántica: hardware que aprovecha los principios de la física cuántica.
• Biológica: hardware basado en el cómputo del ADN.
• Otros: cómputo con regla y compás, computadoras analógicas, robots, etcétera.
Respecto a su precisión:
• Exacto: siempre devuelve una solución correcta.
• Aproximado: devuelve una solución cercana a un resultado óptimo o a un resultado correcto.
• Probabilista: devuelve una solución correcta con alta probabilidad.
• Heurístico: aparentemente funcionan bien, pero no sabemos con seguridad qué tanto o qué tan rápido.
Curiosidades
Un fractal es una forma geométrica que, a pesar de tener un algoritmo recursivo simple que la define, es demasiado irregular para ser descrita por los métodos geométricos tradicionales, y tiene la característica de que puede dividirse en partes, cada una de las cuales es a su vez similar a la forma completa. El término fue inventado por Benoît Mandelbrot en 1975.
El algoritmo más sencillo, que se abordará con detalle en este capítulo, es el secuencial, determinista, fuera de línea.
En algoritmos deterministas cada instrucción realiza una sola operación, siempre la misma. Por lo tanto, la misma entrada, siempre que ejecutamos la secuencia de instrucciones del algoritmo, producirá la misma salida. Pero no hay que dejarse engañar: inclusive en este caso un algoritmo puede tener un comportamiento bastante complicado, con ejecuciones que nunca terminan y que producen múltiples salidas a lo largo de su ejecución. De hecho, en cierto sentido pueden llegar a ser impredecibles y artísticos.
