Saltar al contenido
CULTURA DE ALGORITMO

¿Qué es un algoritmo?

Los 10 principales tipos de algoritmos que debes conocer si quieres tener un conocimiento por encima de la media sobre cómo funciona hoy Internet.

😱 ¿QUÉ ES un ALGORITMO? [ Los 10 tipos QUE DEBES CONOCER ]

Desde hace un tiempo a esta parte existía un consenso mayoritario sobre cómo se definía el concepto de algoritmo. Pero con el aumento de la capacidad de cómputo, de nuevas tecnologías de procesamiento y también de enormes avances en inteligencia artificial, el concepto de algoritmo ha ido perdiendo precisión hasta el punto de que podemos definirlo simplemente como: una secuencia de instrucciones.

Por más complejos que puedan ser o parecer lo único que importa es que haya un estado inicial (o datos de entrada) y una secuencia de pasos que produzca siempre un resultado (los datos de salida).

IR DIRECTAMENTE AL VÍDEO


Un primer acercamiento

Parece todo muy abstracto, pero realmente funciona exactamente como una receta de cocina: tenemos unos datos de entrada (los ingredientes), una secuencia de pasos (la propia receta) y unos datos de salida (el plato cocinado).

Pues eso es básicamente un algoritmo. Piensa que esa forma de resolver problemas se aplica en un número infinito de situaciones, como por ejemplo: el protocolo de emergencia de un avión, las instrucciones de un electrodoméstico o el manual de montaje de un mueble. Pero también y aunque no lo parezca, se aplica para saber dónde colocar un hospital, qué enfermedades podrías contraer en el futuro, cómo conducir un vehículo sin conductor o a clasificar contenido relevante en tu red social favorita. Y aquí es donde entran los algoritmos informáticos.

La informática nos permite programar estos algoritmos para realizar operaciones tan sencillas como el cálculo de un número par, o tan complejas como la secuenciación del genoma humano.

↑ Subir

3 formas de expresar un algoritmo

Para expresar un algoritmo normalmente se utilizan tres descripciones:

  • Descripción de alto nivel: se establece el problema, se selecciona un modelo matemático y se explica la secuencia de pasos de manera verbal.
  • Descripción formal: se usa pseudocódigo para describir la secuencia de pasos que conducen a la solución. Mezcla lenguaje natural con algunas convenciones sintácticas propias de lenguajes de programación, aunque no está regido por ningún estándar.
  • Implementación: se utiliza un lenguaje de programación específico.

Veamos un ejemplo de algoritmo con cada una de estas tres descripciones para saber si un número es par o impar. La forma más sencilla de automatizar el cálculo de la paridad de un número es dividirlo entre 2, y si el resto de la división entera es cero, el número es par, sino es impar.

Descripción de alto nivel:

Es necesario construir un algoritmo que sea capaz de leer un número y determinar si es par o impar

Leeremos un dato de entrada, lo dividiremos por 2 y si el resto de la división entera es 0 podemos concluir que el número es par, de lo contrario el número es impar.

Descripción formal:

pseudocódigo o descripción formal de un algoritmo para el cálculo de un número par o impar

Imprementación: en el lenguaje de programación C.

implementación en el lenguaje de programación C para un algoritmo que calcula si un número es par o impar

↑ Subir

Diseño de algoritmos

Para resolver este problema anterior hemos necesitado tan sólo 13 líneas de código. Piensa que cualquier algoritmo de cierta complejidad puede alcanzar una cifra de miles e incluso millones de líneas de código.

¿Te haces una idea de lo complejo que es buscar un fallo en un algoritmo con un millón de líneas de código?

Porque a veces el error es simplemente que no se formatea correctamente la salida de los datos en pantalla, pero ¿y si el error está en la propia lógica del programa, en la propia secuencia de pasos del algoritmo?

Esta es precisamente una de las profesiones más demandadas en la actualidad, tiene nombres muy llamativos y muy diversos, pero al final se trata de realizar tareas de vigilancia y/o «mantenimiento» de algoritmos.

No hemos tocado aún otra de las utilidades de los algoritmos, la automatización de tareas. Estamos hablando de crear secuencias de instrucciones que un ordenador ejecute sin pensar. O lo que es lo mismo, nosotros pensamos para que el ordenador se limite a ejecutar nuestras instrucciones. Las instrucciones que hemos creado los programadores.

El diseño de un algoritmo es la parte más importante de todo el proceso. Es una tarea inmensamente creativa y tremendamente responsable. Ten en cuenta que un algoritmo mal diseñado puede funcionar pero al mismo tiempo tener unos costes de mantenimiento inasumibles. Fallos no detectados en algoritmos pueden causar auténticas catástrofes.

↑ Subir

Los 10 grandes tipos de algoritmos

Vamos a profundizar un poco más en el mundo de los algoritmos recorriendo 10 grandes tipos de algoritmos.

1. Algoritmos deterministas

Son los más estudiados y los más familiares de todos.

Son aquellos que para unos mismos datos de entrada producirán siempre la misma salida, es decir que son completamente predictivos si se conocen sus entradas.

2. Algoritmos no deterministas

Aquí muchas personas tienden a pensar:

…si hemos quedado en que se trata de aplicar una serie de operaciones a unos datos de entrada para obtener una salida, siempre se va a obtener la misma salida, ¿no?

La respuesta es que NO es así y en muchas ocasiones es hasta deseable que NO sea así.

Piensa en un algoritmo que se encargue de barajar cartas en cualquier juego online: los datos de entrada son siempre los mismos y las operaciones a realizar con ellas también, sin embargo lo deseable es que la salida nunca se repita, la ordenación final de las cartas debe ser completamente aleatoria, sino el juego sería predecible y dejaría de ser negocio. Este es un ejemplo de algoritmo NO determinista.

3. Algoritmos voraces

Son aquellos que aplican una estrategia de búsqueda que consiste en elegir la opción óptima en cada paso, con la idea de llegar a una solución general óptima. Por ello, normalmente se aplica a los problemas de optimización.

Algunos de los algoritmos voraces más populares son los de Prim, Dijkstra o Kruskal.

Recuerda siempre que pagues en una máquina y esta te devuelva el cambio, que ahí está el Algoritmo de Kruskal calculándote el número mínimo de monedas.

4. Algoritmos paralelos

Son aquellos que pueden ser ejecutados por partes por varias unidades de procesamiento al mismo tiempo.

Por ejemplo, el cálculo de números primos es una tarea costosa computacionalmente que se puede paralelizar.

Si queremos saber todos los números primos que hay entre el 1 y el 1000, podemos ejecutar nuestro algoritmo en 4 unidades de procesamiento: la primer a del 1 al 250, la segunda del 251 al 500, la tercera del 501 al 750 y la cuarta del 751 al 1000. El tiempo de cómputo sería mucho menor que si lo ejecutáramos en una sola unidad de procesamiento.

Este tipo de algoritmos han encontrado múltiples aplicaciones en campos como la realidad virtual, la química computacional, el procesamiento de imágenes en medicina, mapas y sistemas de vigilancia, etc.

5. Algoritmos probabilísticos

Son aquellos que basan su resultado en la toma de algunas decisiones al azar, aunque en promedio obtienen buenas soluciones para cualquier conjunto de datos de entrada.

Esto puede parecer algo descabellado pero si el margen de error, aunque exista es pequeño, ayuda a resolver una ingente cantidad de problemas cuya resolución con un algoritmo determinista es inasumible en tiempo de computación.

Un buen ejemplo de esto es una de las aplicaciones del Algoritmo de Montecarlo que es decidir si un número impar es primo o no.

Si tenemos un número muy grande, del orden de cientos de cifras, y queremos saber si es primo o no, tenemos que aplicar algoritmos probabilísticos.

¿Para qué voy a querer saber si un número de 200 cifras es primo o no?


Pues porque en el cálculo de números primos muy grandes es donde reside la fortaleza de los sistemas de criptografía que usan las contraseñas WiFi, las firmas digitales, las tarjetas y webs seguras, y un largo etcétera de sistemas de seguridad que usamos a diario.

Por eso, entre otras razones, son tan importantes los números primos y los algoritmos probabilísticos.

6. Algoritmos divide y vencerás

Divide y vencerás son un tipo de algoritmos que intentan resolver un problema complejo a base de resolver muchos pequeños problemas en los que puede dividirse el problema original.

También llamados algoritmos recursivos

La recursividad entre los programadores es una de esas cosas que generan profundos odios o amores eternos. Básicamente porque la recursividad es un arte, un reto que es difícil aprender y que cuando se aplica correctamente es de una elegancia superior.

Algunos algoritmos populares de este tipo son los de ordenamiento como quicksort o Karatsuba, pero también algoritmos de análisis sintácticos, búsquedas binarias, algoritmo de las torres de hanoi, etc.

Es necesario resaltar que en muchas ocasiones lo que se obtiene es la solución más sencilla, no la mejor.

Pero bueno, veamos un caso práctico de algoritmo recursivo para calcular por ejemplo el factorial de un número.

El factorial de un número cualquiera n, expresado por el propio número acompañado por el signo de exclamación (n!), es una operación matemática de multiplicación decreciente, puesto que se calcula multiplicándose a sí mismo por todos los números que le preceden.

Si quisiéramos calcular por ejemplo el valor de 9 factorial, multiplicaríamos 9 por todos los números que le preceden. Con la precaución de tener en cuenta que 0 factorial no se considera cero, sino 1.

9! = 9 x 8 x 7 x 6 x 5 x 4 x 3 x 2 x 1 = 362.880

implementación de una función en el lenguaje de programación C que calcula el factorial de un número
Función en C que calcula el factorial de un número.

Estas viendo lo que los programadores llamamos una función, un trozo de código, un algoritmo que forma parte de otro algoritmo más grande.

Nuestro algoritmo se llama calcula_factorial y funciona de la siguiente manera.

Desde otro lugar de nuestro programa lo llamamos proporcionándole el valor que se llama número, nuestro algoritmo se ejecuta y devuelve un numero entero tras ejecutar la instrucción return. Los números que ves en el margen izquierdo son simplemente los números de línea de nuestro código para facilitaros la localización de una u otra instrucción. La ejecución de las instrucciones será secuencial.

Por ejemplo si el resultado de evaluar la condición de la línea 9 es falso, la línea 10 no se ejecutará. Si la condición de la línea 11 también se evalúa a falso, la línea 12 tampoco se ejecutará. Y la línea 14 sólo se ejecutará si las condiciones de las líneas 9 y 11 se han evaluado a falso, como en este caso.

Este es el funcionamiento de una estructura if-else.

Otra particularidad de este código es que sólo es posible ejecutar una instrucción return, puesto que está dentro de bloques cuyas condiciones de acceso son mutuamente excluyentes.

Recuerda que nuestro algoritmo termina cuando se ejecuta la instrucción return.

Si te fijas en la línea 14 volvemos a llamar a la función calcula_factorial pero esta vez no lo hacemos con el valor número sino con el valor número-1.

Esta es la forma en la que funciona la recursividad para calcular el factorial.

Lo que va a ocurrir si queremos calcular el factorial del número 4 es que se va a ejecutar la función calcula_factorial(4) y va a devolver 4*calcula_factorial(3), que va a devolver 3*calcula_factorial(2), que va a devolver 2*calcula_factorial(1) que va a devolver 1.

De esta forma hemos encadenado un 4*3*2*1.

Nuestro algoritmo terminaría devolviendo 24, que es el factorial de 4 calculado de forma recursiva con un algoritmo divide y vencerás.

7. Algoritmos metaheurísticos

Son soluciones que generalmente se aplican a problemas que no tienen un algoritmo que los resuelva de forma satisfactoria o cuando no es posible implementar una solución óptima.

En la mayoría de los casos nos movemos en problemas de optimización combinatoria, es decir, un espacio de soluciones gigantesco con un coste computacional extraordinariamente alto.

Entra en esta categoría el  famosísimo problema de las n-reinas del ajedrez.

Se trata de colocar en un tablero de ajedrez de n x n casillas, n reinas sin que ninguna de las reinas quede amenazando a otras.

Para quien no lo sepa, el movimiento de la reina es vertical, horizontal y diagonal.

Te animo a que pares aquí un minuto, e intentes resolver el problema de las 8 reinas. Ya sabes, un tablero normal de ajedrez, 8×8, y colocar 8 reinas de forma que ninguna de ellas quede amenazando a otra.

Para un problema de 8 reinas existen 12 soluciones distintas, concretamente estas:

Y este un ejemplo de algoritmo en C++ que lo resuelve.

implementación en el lenguaje de programación C++ del problema de las n reinas
Implementación en C++ del problema de las 8 reinas.

Con 17 reinas tendríamos casi 12 millones de soluciones distintas, y con 27 reinas (el más grande conocido hasta ahora) tendríamos nada más y nada menos que 29.363.495.934.315.694 soluciones distintas (2,93×1016).

Ahora creo que se entiende mejor la magnitud del problema.

Este orden de magnitudes no es ni mucho menos algo excepcional en el mundo de los algoritmos, sino más bien el día a día en campos como la medicina, el transporte o la inteligencia artificial.

Dentro de esta categoría encontraríamos entre otros: los algoritmos genéticos, las optimizaciones por enjambre de partículas o por colonia de hormigas, búsquedas tabú, estocásticos o vecindades variables.

Todos ellos muy interesantes para verlos en profundidad en otro artículo.

8. Algoritmos de programación dinámica

Pretende optimizar problemas complejos reduciendo el tiempo de ejecución, a través de la resolución de problemas más pequeños de forma óptima, que ayuden a encontrar la solución óptima de todo el problema.

Veamos el famoso problema de la mochila. Supongamos que tenemos una mochila con una capacidad de por ejemplo 5Kg que puedo llenar con diversos objetos de distinto peso y valor.

El problema que tratamos de resolver es la elección óptima de objetos para para maximizar mis ganancias sin exceder la capacidad de los 5Kg.

El enunciado es sencillo, pero su resolución es tremendamente compleja. Y va aumentando de complejidad conforme añadimos requisitos como un aumento del número de objetos y una alta varianza de pesos y valores. Tal y como ocurre en la vida real si sustituimos la mochila los objetos por almacenes y paquetes, trailers y mercancías o carteras financieras y valores bursátiles.

La resolución del problema de la mochila ha sido aplicado con éxito para un número elevado de objetos en sistemas de control de almacenes, transporte, medicina y mercados financieros.

9. Algoritmos de ramificación y poda

Esta técnica trata de soluciones que se presentan en forma de árbol, donde cada rama nos lleva a una posible solución posterior a la actual.

El algoritmo se encarga de detectar qué ramas no aportan soluciones óptimas y las “poda” dejando de recorrer esa parte del árbol para no malgastar recursos.

Selección de ramas óptimas.

Es un tipo de algoritmos que se ha utilizado popularmente para resolver sudokus, puzles, ajedrez o problemas una aplicación más práctica como el problema del viajante (que ha sido clave en el sector del transporte) o el problema de la asignación cuadrática (muy utilizados en el diseño de centros comerciales y terminales de aeropuertos).

10. Algoritmos de vuelta atrás

Es una generalización de los algoritmos anteriores, aunque en esta ocasión las soluciones no tienen por qué ser las óptimas.

Durante esta búsqueda si se encuentra una alternativa incorrecta, la búsqueda retrocede hasta el paso anterior y toma la siguiente alternativa.

Cuando se han terminado las posibilidades, se vuelve a la elección anterior y se toma la siguiente opción.

Si no hay más alternativas la búsqueda falla. De esta forma, se crea un árbol en el que cada nodo es un estado de la solución.

Solución secuencial para encontrar la salida de un laberinto.

Con esta técnica se han resuelto problemas como las salidas de un laberinto, o el del caballo del ajedrez: un antiguo problema matemático en el que colocando el caballo en una posición cualquiera del tablero, debemos encontrar una sucesión de movimientos en los que el caballo pase por todas las casillas y una sola vez.

¿Imposible? Aquí lo tienes.

Solución gráfica al desafío del caballo del ajedrez.

¿Espectacular verdad?

↑ Subir

Conclusión

Si con este pequeñísimo recorrido por el mundo de los algoritmos aún no te he convencido de la importancia que tienen, piensa que el mayor imperio empresarial de la actualidad se construyó gracias a un único algoritmo, el PAGERANK de Google.

Si te ha gustado este tema y quieres conocer un poco más sobre alguno de los conceptos que hemos tratado en este vídeo házmelo saber en los comentarios. Y si quieres ser el primero en conocer las novedades en vídeo de Cultura de Algoritmo, ya sabes, suscríbete 👇.

Vídeo

↑ Subir