Algoritmo en Informática
Un algoritmo es una secuencia finita y ordenada de pasos precisos que permite resolver un problema a partir de unos datos de entrada.
Un algoritmo es una secuencia finita y ordenada de pasos precisos que, a partir de unos datos de entrada, permite resolver un problema o realizar una tarea. En informática es la idea que hay detrás de cualquier programa: antes de escribir una sola línea de código, alguien ha diseñado el procedimiento que la máquina debe seguir.
¿Qué es un algoritmo en informática?
Un algoritmo es un método de resolución de problemas descrito con tanta exactitud que puede ejecutarse sin interpretación ni intuición: cada paso es inequívoco y el resultado final se obtiene en un número limitado de operaciones. Una receta de cocina se parece a un algoritmo, pero una máquina no entiende «añadir sal al gusto»; un algoritmo informático debe especificar todo con rigor.
La palabra procede del nombre del matemático persa Muhammad ibn Musa al-Jwarizmi (siglo IX), que trabajó en la Casa de la Sabiduría de Bagdad y cuyos textos difundieron en Europa el sistema de numeración indoarábigo y las reglas de cálculo con él. De su nombre latinizado, Algoritmi, derivó el término «algoritmo». La palabra «álgebra» procede, a su vez, del título de otra de sus obras.
Un algoritmo no es lo mismo que un programa. El algoritmo es la idea, independiente de cualquier tecnología; el programa es su traducción a un lenguaje de programación concreto, como Python, C o Java, para que lo ejecute un ordenador.
Características de un algoritmo
Siguiendo la caracterización clásica del informático Donald Knuth, un algoritmo correcto reúne estas propiedades:
- Finitud: termina siempre tras un número finito de pasos.
- Precisión (definición): cada paso está definido sin ambigüedad.
- Entrada: recibe cero o más datos iniciales.
- Salida: produce al menos un resultado relacionado con la entrada.
- Efectividad: cada operación es lo bastante elemental como para poder realizarse en un tiempo finito.
Además, en la práctica se valoran otras cualidades: que sea correcto (que dé siempre la solución buscada), eficiente (que use pocos recursos) y general (que sirva para toda una familia de problemas y no solo para un caso).
Cómo se representa un algoritmo
- Lenguaje natural: descripción en frases numeradas; es sencillo pero puede resultar ambiguo.
- Pseudocódigo: mezcla de lenguaje natural y estructuras propias de la programación («si… entonces», «mientras…»), sin la sintaxis estricta de un lenguaje real.
- Diagrama de flujo: esquema gráfico con símbolos normalizados (inicio, proceso, decisión, entrada/salida) unidos por flechas.
- Código fuente: la versión ejecutable escrita en un lenguaje de programación.
Todos los algoritmos se construyen combinando tres estructuras básicas: la secuencia (un paso tras otro), la selección (elegir un camino según una condición) y la repetición o iteración (volver a ejecutar un bloque mientras se cumpla una condición). Este resultado, conocido como teorema de Böhm-Jacopini (1966), es la base de la programación estructurada.
Un ejemplo clásico: el algoritmo de Euclides
Uno de los algoritmos más antiguos que se conservan, descrito por Euclides en sus Elementos hacia el 300 a. C., calcula el máximo común divisor de dos números enteros positivos:
- Dividir el número mayor entre el menor y quedarse con el resto.
- Si el resto es 0, el divisor es el resultado y el algoritmo termina.
- Si no, sustituir el mayor por el menor y el menor por el resto, y volver al paso 1.
Para 48 y 18: 48 = 2 · 18 + 12; después 18 = 1 · 12 + 6; después 12 = 2 · 6 + 0. El resultado es 6. Cumple todas las propiedades: es finito, preciso, tiene entrada (dos números), salida (el divisor) y operaciones elementales.
Tipos de algoritmos habituales
| Tipo | Objetivo | Ejemplos |
|---|---|---|
| Búsqueda | Localizar un elemento en un conjunto de datos | Búsqueda lineal, búsqueda binaria |
| Ordenación | Colocar los datos según un criterio | Burbuja, inserción, quicksort, mergesort |
| Grafos | Recorrer redes y calcular rutas | Dijkstra, A*, búsqueda en anchura |
| Criptográficos | Proteger y verificar información | AES, RSA, SHA-256 |
| Compresión | Reducir el tamaño de los datos | Huffman, LZ77, algoritmos de JPEG y MP3 |
| Aprendizaje automático | Obtener modelos a partir de ejemplos | Regresión lineal, árboles de decisión, redes neuronales |
Eficiencia y complejidad
Dos algoritmos pueden resolver el mismo problema y, sin embargo, diferir enormemente en rapidez. Para compararlos se analiza su complejidad: cómo crece el número de operaciones (complejidad temporal) o la memoria necesaria (complejidad espacial) cuando aumenta el tamaño n de la entrada. Se expresa con la notación asintótica «O grande» (Big O).
| Notación | Nombre | Ejemplo |
|---|---|---|
| O(1) | Constante | Acceder a una posición de un array |
| O(log n) | Logarítmica | Búsqueda binaria en una lista ordenada |
| O(n) | Lineal | Búsqueda lineal |
| O(n log n) | Casi lineal | Mergesort; quicksort en el caso medio |
| O(n²) | Cuadrática | Ordenación por burbuja |
La diferencia es enorme: para buscar entre mil millones de elementos ordenados, la búsqueda lineal puede requerir hasta mil millones de comparaciones, mientras que la binaria necesita unas 30.
Aplicaciones
Los algoritmos están presentes en casi todo lo que hace un dispositivo digital: el buscador que ordena resultados, el navegador GPS que calcula la ruta más corta, el sistema que recomienda series, el cifrado de una compra online, la compresión de una foto o el reconocimiento de voz. En el campo de la inteligencia artificial, los algoritmos de aprendizaje automático ajustan sus parámetros a partir de grandes volúmenes de datos; de ahí la importancia de analizar sus sesgos y de que sus decisiones sean transparentes.
La noción formal de algoritmo está ligada a la teoría de la computación. En los años treinta, Alan Turing y Alonzo Church formalizaron qué significa «computable», y de ahí surgieron la tesis de Church-Turing y el modelo de la máquina de Turing. Del mismo autor es la prueba de Turing, que plantea cómo evaluar si una máquina exhibe un comportamiento inteligente.
Ventajas y limitaciones
- Ventajas: automatizan tareas, son reproducibles, permiten analizar de antemano su coste y se pueden reutilizar en distintos programas.
- Limitaciones: hay problemas sin algoritmo posible (como el problema de la parada) y otros cuya solución exacta resulta inviable por su coste; un algoritmo mal diseñado puede dar resultados erróneos o discriminatorios.
Preguntas frecuentes
¿Qué es un algoritmo en palabras sencillas?
Es una lista de instrucciones claras y ordenadas para resolver un problema o realizar una tarea, de modo que cualquiera, persona o máquina, pueda seguirla y llegar al mismo resultado.
¿Cuál es la diferencia entre algoritmo y programa?
El algoritmo es el método abstracto de resolución; el programa es la implementación de ese método en un lenguaje de programación concreto para que un ordenador lo ejecute.
¿De dónde viene la palabra algoritmo?
Procede del nombre del matemático persa al-Jwarizmi (siglo IX), cuyo nombre se latinizó como Algoritmi en las traducciones medievales de sus obras sobre aritmética.
¿Qué significa la notación O grande?
Describe cómo crece el tiempo o la memoria que necesita un algoritmo al aumentar el tamaño de los datos de entrada. Permite comparar algoritmos sin depender del ordenador utilizado.
¿Todos los problemas se pueden resolver con un algoritmo?
No. La teoría de la computación demuestra que existen problemas indecidibles, como el problema de la parada, para los que no puede existir un algoritmo general.
Referencias
- Knuth, D. E. (1997). The Art of Computer Programming, Vol. 1: Fundamental Algorithms. Addison-Wesley.
- Cormen, T. H., Leiserson, C. E., Rivest, R. L. y Stein, C. (2009). Introduction to Algorithms (3.ª ed.). MIT Press.
- Brassard, G. y Bratley, P. (1997). Fundamentos de algoritmia. Prentice Hall.
Cómo citar este artículo
Equipo de Conceptualia. (2023). «Algoritmo en Informática». Conceptualia. https://conceptualia.es/cultura-y-sociedad/tecnologia/algoritmo-en-informatica/
