Definición de algoritmo

Un algoritmo es un conjunto detallado y lógico de pasos para alcanzar un objetivo o resolver un problema. Por ejemplo, el instructivo para armar un modelo de avión a escala; cualquier persona, si atiende de forma estricta la secuencia de los pasos, llegará al mismo resultado.

Otro ejemplo es donde puedes notar la forma como se obvian pasos pidiendo a otra persona que describa el proceso para preparar agua de limón. Seguro te diría que toma una jarra con agua, le pone jugo de limón, azúcar y listo. Para una computadora lo anterior no tendría sentido, ya que carece de unidades exactas y pasos detallados. Por lo tanto, los pasos deben tener mayor nivel de precisión, en esta secuencia:

•Inicio del proceso.
•Tomar una jarra de dos litros de capacidad.
•Llenar la jarra a 4/5 partes con agua natural.
•Tomar cuatro limones.
•Cortar los limones por la mitad.
•Exprimir los limones dejando caer el jugo sobre el agua en la jarra.
•Tomar el recipiente del azúcar.
•Agregar cuatro cucharadas soperas en la jarra con el agua.
•Revolver el agua con el jugo y el azúcar por dos minutos.
•Fin del proceso.

En conclusión, cuando se elabora un algoritmo se tomará en cuenta que la computadora es como un niño pequeño al cual se le está enseñando a realizar algo por primera vez, y es necesario concretar lo más posible cada paso que debe dar.

Propiedades de los algoritmos

Para que un algoritmo realmente lo sea cumplirá con las características o propiedades que se describen a continuación. Pulsa en cada concepto para desplegar la información correspondiente.

Finito

Dentro de la secuencia de pasos para realizar la tarea, debe tener una situación o condición que lo detenga; de lo contrario, se pueden dar ciclos infinitos que impidan llegar a un término.

Preciso

Un algoritmo no debe dar lugar a criterios, porque se presta a que exista ambigüedad; por lo tanto, debe ser concreto e indicar el orden de realización de cada paso.

Obtener el mismo resultado

En cualquier circunstancia, si se atienden de forma estricta los pasos del algoritmo, siempre se debe llegar a un mismo resultado.

Un ejemplo de lo anterior sería el siguiente: qué sucedería si a dos personas en distintos lugares se les ordenara preparar un pastel. Supón que saben cómo hacerlo, y siguiendo las indicaciones de la receta llegan a un paso en el que se indica que se agregue azúcar al gusto. Entonces, cada persona incorporaría azúcar de acuerdo a sus preferencias y el resultado no sería el mismo: los dos pasteles resultarían diferentes en sus características.

Esto concluye que si carecen de cualquiera de estas particularidades o propiedades, los pasos en cuestión no son un algoritmo.

Autómatas

Un autómata es un modelo computacional que consiste en un conjunto de estados bien definidos, un estado inicial, un alfabeto de entrada y una función de transición.

Este concepto es equivalente a otros, como autómata finito o máquina de estados finitos. En un autómata, un estado es la representación de su condición en un instante dado. El autómata comienza en el estado inicial con un conjunto de símbolos; su paso de un estado a otro se efectúa a través de la función de transición, la cual, partiendo del estado actual y un conjunto de símbolos de entrada, lo lleva al nuevo estado correspondiente.

Un ejemplo de autómata en la vida cotidiana es un elevador, ya que es capaz de memorizar las diferentes llamadas de cada piso y optimizar sus ascensos y descensos.

De tal forma que los autómatas son una aplicación de los algoritmos basados en una condición de una situación dada, que llevarán a cabo acciones que ya se encuentran programadas.

Lenguajes formales

Una forma de representar las gramáticas es la Backus-Naur (BNF), usada para describir la sintaxis de un lenguaje dado, así como su notación.

La función de una gramática es definir y enumerar las palabras y frases válidas de un lenguaje. Pulsa en cada concepto para desplegar la información correspondiente.

Alfabeto

Un alfabeto es el conjunto de todos los símbolos válidos o posibles para una aplicación. En el campo de los autómatas está formado por todos los caracteres que utiliza para definir sus entradas, salidas y estados.

En algunos casos, el alfabeto puede ser infinito o tan simple como el alfabeto binario, donde sólo se aplican los símbolos 1 y 0 para representar cualquier expresión de entrada, salida y estado.

Frase

Una frase es la asociación de un conjunto de símbolos definidos en un alfabeto (cadena), cuya propiedad es tener sentido, significado y lógica.

Las frases parten del establecimiento de un vocabulario que dispone las palabras válidas del lenguaje sobre la base del alfabeto definido. Una frase válida es aquella que cumple con las reglas de la gramática establecida.

Cadena vacía

Se dice que una cadena es vacía cuando la longitud del conjunto de caracteres que utiliza es igual a cero; es decir, es una cadena sin caracteres asociados.

Este tipo de cadenas no siempre implica el no cambio de estado en un autómata, ya que en la función de transición puede existir una definición de cambio de estado asociada a la entrada de una cadena vacía.

Lenguaje

Un lenguaje es un conjunto de cadenas que obedecen a un alfabeto fijado, y entendido como un conjunto de entradas puede o no ser resuelto por un algoritmo.

Gramáticas formales

Una gramática es una colección estructurada de palabras y frases ligadas por reglas que definen el conjunto de cadenas de caracteres que representan los comandos completos que pueden ser reconocidos por un motor de discurso.

La forma general definida por BNF es denominada regla de producción y se representa del siguiente modo:

<regla> = sentencias y frases.

Las partes de la forma general BNF se definen como sigue:

•El “lado izquierdo” o regla es el identificador único de las reglas definidas para el lenguaje. Puede ser cualquier palabra, con la condición de estar encerrada entre los símbolos <>.
•Este elemento es obligatorio en la forma BNF.
•El “operador de asignación” = es un elemento obligatorio.
•El “lado derecho”, o sentencias y frases, define todas las posibilidades válidas en la gramática definida.
•El “delimitador de fin de instrucción” (punto) es un elemento obligatorio.

Un ejemplo real aplicado a una frase simple de uso común, como “Me puede mostrar su licencia”, con la opción de anteponer el título señorita, señor o señora, se puede estructurar de la manera siguiente en una gramática BNF:

<peticion> = <comando> | <titulo> <comando>.
<titulo> = Señor | Señora | Señorita.
<comando> = Me puede mostrar su licencia = sentencias y frases.

Máquina de Turing

El concepto de algoritmo como un conjunto de pasos lógicos y secuenciales para solucionar un problema fue implementado en 1936 por Alan Turing, matemático inglés, en la máquina de Turing. Ésta se integra mediante tres elementos: cinta, cabeza de lectura-escritura y programa. La cinta tiene la propiedad de ser infinita (no acotada por sus extremos) y estar dividida en segmentos del mismo tamaño, los cuales almacenan cualquier símbolo o pueden estar vacíos; asimismo, puede interpretarse como el dispositivo de almacenamiento.

La cabeza de lectura-escritura es el dispositivo que lee y escribe en la cinta. Actúa en un segmento y ejecuta sólo una operación a la vez. También tiene un número finito de estados que cambian de acuerdo a la entrada y las instrucciones definidas en el programa que lo controla.

El último elemento, el programa, es un conjunto de instrucciones que controlan los movimientos de la cabeza de lectura-escritura, indicándole hacia dónde debe moverse y si debe escribir o leer en la celda donde se encuentre.

Actualmente, la máquina de Turing es una de las principales abstracciones utilizadas en la teoría moderna de la computación, ya que auxilia en la definición de lo que una computadora puede o no hacer.

La máquina de Turing es el antecedente más remoto de un autómata, y al igual que éste se define con varias herramientas: diagrama de estado, tabla de estado y función. Hay problemas que pueden resolverse mediante una máquina de Turing y otros no. Los primeros se llaman computables, y los segundos no computables o indecidibles. De ellos derivan, respectivamente, los procesos computables y los no computables. Pulsa en cada concepto para desplegar la información correspondiente.

Proceso computable
Proceso no computable

Proceso computable

Puede implementarse en un algoritmo o máquina de Turing, definirse en un lenguaje decidible e implementarse como el programa de la máquina de Turing.

Proceso no computable

No puede implementarse con una máquina de Turing por no tener solución para todas sus posibles entradas. Se especifica en un lenguaje indecidible imposible de ser interpretado por una máquina de Turing.

En este tema se presentaron conceptos y principios básicos de los algoritmos, sus características y terminología, para aplicarlos en la resolución de problemas (razón de ser de los algoritmos). Con el apoyo de ejemplos se generó una mejor comprensión de los puntos tratados, ya que los algoritmos pueden ser muy sencillos o muy complejos. Además, se abordó el concepto de los autómatas, una aplicación de los algoritmos, y en particular se definió y estudió la máquina de Turing, un ejemplo de los autómatas finitos deterministas que realizan sólo una actividad en una situación dada.

Introducción