Ejemplos de algoritmos

Un algoritmo es una secuencia finita y ordenada de pasos que permite resolver un problema o realizar una tarea. Seguir una receta de cocina, dividir con lápiz y papel o buscar un nombre en una lista son algoritmos. En este artículo se explica qué es un algoritmo, cuáles son sus características y se desarrollan ejemplos clásicos, desde los cotidianos hasta los de las matemáticas y la informática, con pseudocódigo y pasos explícitos.

¿Qué es un algoritmo?

Un algoritmo es un conjunto finito de instrucciones precisas que, a partir de unos datos de entrada, produce un resultado en un número limitado de pasos. No depende de un lenguaje de programación concreto: es el método de resolución, y el programa es solo una de las maneras de escribirlo para que lo ejecute un ordenador.

La palabra procede del nombre del matemático persa Al-Juarismi (siglo IX), cuyo nombre se latinizó como Algoritmi en las traducciones medievales de sus tratados de aritmética con el sistema de numeración indio. Algunos de los algoritmos más antiguos que se conservan, como el de Euclides, son anteriores en más de mil años.

Características de un algoritmo

• Finito: termina después de un número limitado de pasos.
• Preciso o bien definido: cada paso se indica sin ambigüedad.
• Con entrada: parte de cero o más datos iniciales.
• Con salida: produce al menos un resultado relacionado con la entrada.
• Efectivo: cada operación es lo bastante sencilla como para ejecutarse de forma exacta.

Los algoritmos se representan con diagramas de flujo o con pseudocódigo, una descripción en lenguaje casi natural que usa estructuras de control: la secuencia, la condición (si… entonces…) y la repetición (mientras… hacer…).

Ejemplos de algoritmos cotidianos

• Preparar una tortilla de patatas: pelar, cortar, freír, batir los huevos, mezclar, cuajar, dar la vuelta. Cada paso tiene un orden y un final.
• Cambiar una rueda pinchada: aflojar tuercas, elevar el coche con el gato, retirar la rueda, colocar la de repuesto, apretar y bajar.
• Dividir por escrito: el método de la caja repite los pasos «tomar cifras, dividir, multiplicar, restar, bajar la siguiente cifra» hasta agotar las cifras.

Ejemplos de algoritmos matemáticos

1. Algoritmo de Euclides (máximo común divisor)

El algoritmo de Euclides calcula el máximo común divisor de dos números enteros positivos. Se apoya en una propiedad demostrada como teorema: mcd(a, b) = mcd(b, a mod b), donde «a mod b» es el resto de dividir a entre b.

función mcd(a, b)
    mientras b ≠ 0 hacer
        r ← resto de a entre b
        a ← b
        b ← r
    devolver a

Ejemplo con 48 y 18: 48 = 2·18 + 12; 18 = 1·12 + 6; 12 = 2·6 + 0. El último resto no nulo es 6, luego mcd(48, 18) = 6.

2. Criba de Eratóstenes (números primos)

La criba de Eratóstenes encuentra todos los números primos hasta un valor n. Pasos:

1. Escribir todos los números de 2 a n.
2. Tomar el primer número sin tachar, p, que es primo.
3. Tachar todos sus múltiplos mayores que p.
4. Repetir con el siguiente número sin tachar hasta que p² supere n.
5. Los números que no han sido tachados son los primos.

3. Resolución de la ecuación de segundo grado

Para resolver ax² + bx + c = 0 (con a ≠ 0) se calcula el discriminante y se aplica la fórmula:

Si Δ > 0 hay dos soluciones reales, si Δ = 0 hay una doble y si Δ < 0 no hay soluciones reales. Es un algoritmo porque siempre sigue los mismos pasos con distintos coeficientes.

Ejemplos de algoritmos en informática

4. Búsqueda binaria

La búsqueda binaria localiza un elemento en una lista ordenada dividiendo en dos el intervalo de búsqueda en cada paso. Es mucho más rápida que recorrer la lista entera: para n elementos necesita del orden de log₂ n comparaciones, frente a las n de la búsqueda secuencial.

función buscar(lista, objetivo)
    inicio ← 1
    fin ← longitud(lista)
    mientras inicio ≤ fin hacer
        medio ← parte entera de (inicio + fin) / 2
        si lista[medio] = objetivo entonces devolver medio
        si lista[medio] < objetivo entonces inicio ← medio + 1
        si no fin ← medio − 1
    devolver «no encontrado»

5. Ordenación por burbuja

El método de la burbuja recorre la lista comparando pares de elementos contiguos y los intercambia si están en el orden incorrecto. Tras cada pasada, el mayor de los elementos restantes queda en su posición. Es sencillo pero lento, con un coste del orden de n² comparaciones.

repetir n − 1 veces
    para i desde 1 hasta n − 1 hacer
        si lista[i] > lista[i + 1] entonces intercambiar(lista[i], lista[i + 1])

6. Otros algoritmos célebres

Diseñar un algoritmo exige descomponer un problema, buscar patrones y razonar con rigor, habilidades que se desarrollan con el pensamiento matemático.

Ejercicios resueltos

Preguntas frecuentes

Referencias

• Knuth, D. E.: The Art of Computer Programming, vol. 1: «Fundamental Algorithms». Addison-Wesley.
• Cormen, T. H.; Leiserson, C. E.; Rivest, R. L.; Stein, C.: Introduction to Algorithms. MIT Press.
• Euclides: Elementos, Libro VII (proposiciones 1 y 2, algoritmo para el máximo común divisor).