¿Qué es un Algoritmo? Ejemplos de uso en Informática

¿Qué es un algoritmo?

Llamamos “algoritmo” al conjunto finito y ordenado de acciones con las que podemos resolver un determinado problema.

¿Qué es un problema?

Llamamos “problema” a una situación que se nos presenta y que, mediante la aplicación de un algoritmo, pretendemos resolver.

Los algoritmos están presentes en nuestra vida cotidiana y, aún sin saberlo, aplicamos algoritmos cada vez que se nos presenta un problema sin importar cuál sea su grado de complejidad.

Ejemplo de algoritmo en la vida cotidiana

Para ejemplificar esto imaginemos que estamos dando un paseo por la ciudad y que, al llegar a una esquina, tenemos que cruzar la calle. Intuitivamente, aplicaremos el siguiente algoritmo:

• Esperar a que la luz del semáforo peatonal esté en verde (esperarSemaforo);
• Cruzar la calle (cruzarCalle);

Este algoritmo está compuesto por las acciones: esperarSemaforo y cruzarCalle, en ese orden, y es extremadamente simple gracias a que cada una de estas engloba a otro conjunto de acciones más puntuales y específicas. Por ejemplo:

La acción esperarSemaforo implica:

• Observar la luz del semáforo (observarLuz);
• Si la luz está en “rojo” o en “verde intermitente” entonces
  • esperar un momento (esperar);
  • ir a: observarLuz;

Por otro lado, la acción cruzarCalle implica:

• Bajar la calzada (bajarCalzada);
• Avanzar un paso (avanzarPaso);
• Si la distancia hacia la otra calzada es mayor que la distancia que podemos avanzar dando un nuevo paso entonces
  • ir a: avanzarPaso;
• Subir la calzada de la vereda de enfrente (subirCalzada);

Como vemos, cada acción puede descomponerse en acciones más puntuales y específicas. Por lo tanto, cada una de las acciones del algoritmo se resuelve con su propio algoritmo o secuencia finita y ordenada de acciones.

Cuando una acción se descompone en acciones más puntuales y específicas decimos que es un “módulo”.

Podemos seguir profundizando cada acción tanto como queramos. Por ejemplo, analicemos la acción (o el módulo) bajarCalzada: esta acción se resuelve:

• levantando un pie,
• adelantándolo,
• inclinando el cuerpo hacia adelante,
• y apoyando el pie en la calle,
• luego levantando el otro pie,
• adelantándolo y
• apoyándolo en la calle

Claro que “levantar un pie” implica tensionar un conjunto de músculos, etcétera.

Análisis del enunciado de un problema

Resulta evidente que, si vamos a diseñar un algoritmo para resolver un determinado problema, tenemos que tener totalmente estudiado y analizado el contexto de dicho problema. Esto implica:

• Comprender el alcance
• Identificar los datos de entrada
• Identificar los datos de salida o resultados

El análisis anterior es fundamental para poder diseñar una estrategia de solución que será la piedra fundamental para el desarrollo del algoritmo.

Análisis del problema

Repasemos el contexto del problema de “cruzar la calle” que formulamos más arriba:

Caminando por la ciudad llegamos a una esquina y pretendemos cruzar la calle. Para poder cruzar con la mayor seguridad posible, tenemos que esperar que el semáforo habilite el paso peatonal. Hasta que esto ocurra nos encontraremos detenidos al lado del semáforo y una vez que este lo permita avanzaremos, paso a paso, hasta llegar a la vereda de enfrente.

Se considera que el semáforo habilita el paso peatonal cuando emite una luz “verde fija”. En cambio si el semáforo emite una luz “roja” o “verde intermitente” se recomienda esperar

Datos de entrada

En este contexto podemos identificar los siguientes datos de entrada:

• Nuestra posición inicial - posición en donde nos detuvimos a esperar a que el semá-foro habilite el paso peatonal. La llamaremos posInicial.
• Luz del semáforo - el color de la luz que el semáforo está emitiendo. Lo llamaremos luz.
• Distancia de avance de paso - que distancia avanzamos cada vez que damos un nuevo paso. La llamaremos distPaso.
• Posición de la vereda de enfrente. La llamaremos posFinal ya que es allí hacia donde nos dirigimos

Datos de salida

Si bien en este problema no se identifican datos de salida resulta evidente que luego de ejecutar la secuencia de acciones del algoritmo nuestra posición actual deberá ser la misma que la posición de la vereda de enfrente. Es decir, si llamamos p a nuestra posición actual resultará que su valor al inicio del algoritmo será posInicial y al final del mismo deberá ser posFinal

Memoria y operaciones aritméticas y lógicas

En la vida real, cuando observamos la luz del semáforo almacenamos este dato en algún lugar de nuestra memoria para poder evaluar si corresponde cruzar la calle o no.

Generalmente, los datos de entrada ingresan al algoritmo a través de una acción que llamamos “lectura” o “ingreso de datos” y permanecen en la memoria el tiempo durante el cual el algoritmo se está ejecutando.

Por otro lado, el hecho de evaluar si corresponde o no cruzar la calle implica realizar una operación lógica. Esto es: determinar si la proposición “el semáforo emite luz roja o verde intermitente” resulta ser verdadera o falsa.

También realizaremos una operación lógica cuando estemos cruzando la calle y tengamos que determinar si corresponde dar un nuevo paso o no.

Recordemos que llamamos p a nuestra posición actual, posFinal a la posición de la vereda de enfrente y distPaso a la distancia que avanzamos dando un nuevo paso. Por lo tanto, corresponde dar otro paso si se verifíca que posFinal > p+distPaso.

Aquí además de la operación lógica estamos realizando una operación aritmética: la suma p+distPaso.

En resumen, estos son los recursos que tenemos disponibles para diseñar y desarrollar algoritmos:

• La memoria
• La posibilidad de realizar operaciones aritméticas
• La posibilidad de realizar operaciones lógicas

Teorema de la programación estructurada

Este teorema establece que todo algoritmo puede resolverse mediante el uso de tres estructuras básicas llamadas “estructuras de control”:

• La “estructura secuencial” o “acción simple”
• La “estructura de decisión” o “acción condicional”
• La “estructura iterativa” o “acción de repetición”

Dos de estas estructuras las hemos utilizado en nuestro ejemplo de cruzar la calle. La estructura secuencial es la más sencilla y simplemente implica ejecutar una acción, luego otra y así sucesivamente.

La estructura de decisión la utilizamos para evaluar si correspondía dar un nuevo paso en función de nuestra ubicación actual y la ubicación de la vereda de enfrente.

Sin embargo, para resolver el problema hemos utilizado una estructura tabú: la estructura “ir a” o, en inglés, “go to” o “goto”.

Esta estructura quedó descartada luego de que el teorema de la programación estructurada demostrara que con una adecuada combinación de las tres estructuras de control antes mencionadas es posible resolver cualquier algoritmo sin tener que recurrir al “goto” (o estructura “ir a”).

Para ejemplificarlo vamos a replantear el desarrollo de los algoritmos anteriores y reemplazaremos la estructura “ir a” (goto) por una estructura iterativa: la estructura “repetir mientras que”

Veamos el desarrollo del módulo esperarSemaforo:

Con “ir a”	Sin “ir a” (solución correcta)
ObservarLuz; Si la luz está en “rojo” o en “verde intermitente” entonces esperar; ir a: observarLuz;	ObservarLuz; Repetir mientras que la luz esté en “rojo” o en “verde intermitente” hacer esperar; observarLuz;

Veamos ahora el desarrollo del módulo cruzarCalle:

Con “ir a”	Sin “ir a” (solución correcta)
bajarCalzada; avanzarPaso; Si la distancia hacia la otra calzada es mayor que la distancia que pode-mos avanzar dando un nuevo paso entonces ir a: avanzarPaso; subirCalzada;	bajarCalzada; avanzarPaso; Repetir mientras que la distancia hacia la otra calzada sea mayor que la distancia que podemos avanzar dando un nuevo paso hacer avanzarPaso; subirCalzada;

Como vemos, la combinación “acción condicional + goto” se puede reemplazar por una estructura de repetición.

Si bien ambos desarrollos son equivalentes la nueva versión es mejor porque evita el uso del goto, estructura que quedó en desuso porque trae grandes problemas de mantenibilidad.