Fundamentos de algoritmos

TEMA 1. FUNDAMENTOS DE ALGORITMOS
Objetivo particular
Al culminar el aprendizaje del tema, reconocerá la definición de un algoritmo y sus
características, los conceptos generales de los autómatas y más específicamente
la de los autómatas finitos deterministas.
Temario detallado
1.1 Definición de algoritmo
1.2 Autómatas y lenguajes formales
1.3 Máquina de Turing
Introducción
La palabraalgoritmo viene de Al-Khowarizmi sobrenombre del célebre matemático
Mohamed Ben Musa. Hoy en día, el algoritmo es una forma ordenada de describir
los pasos para resolver problemas. Es una forma abstracta de reducir un problema
a un conjunto de pasos que le den solución.
Hay algoritmos muy sencillos y de gran creatividad, aunque también están los que
conllevan un alto grado de complejidad.
Unaaplicación de los algoritmos lo tenemos en los autómatas, los cuales, basados
en una condición de una situación dada, llevarán a cabo algunas acciones que ya
se encuentran programadas en el autómata.
Será de gran utilidad, involucrarse en su funcionamiento y terminología para
entender que bajo el contexto de autómatas los conceptos de alfabeto, frase,
cadena vacía, lenguaje, gramática,etcétera, cobran particular relevancia.
Se definirá y estudiará en particular a la Máquina de Turing, que es un ejemplo de
los autómatas finitos deterministas que realizan solo una actividad en una
situación dada.
Es importante que el alumno, analice con detalle los ejemplos desarrollados en
esta unidad sobre el diseño y funcionamiento de una Máquina de Turing.
El estudio de los algoritmos y losautómatas es básico y medular para que el
alumno ejercite un pensamiento lógico y abstracto sobre la forma de abordar los
problemas de su área de desempeño que es la Informática.
1.1. Definición de algoritmo1
Un algoritmo es un conjunto detallado y lógico de pasos, para alcanzar un objetivo
o resolver un problema.
Como ejemplo tenemos el instructivo para armar un modelo de un avión a escala,si una persona sigue en forma estricta los pasos indicados en el instructivo, al final
obtendrá como resultado el avión a escala, lo mismo obtendría otra persona que
se dedicara a armar el mismo modelo.
Los pasos deben ser lo suficientemente detallados para que el procesador lo
entienda, en el caso de nuestro ejemplo, el procesador es el cerebro de la persona
que está armando el modelo, peroel ser humano tiende a obviar muchas cosas y
es muy factible que el humano haga en forma automática algunos de los pasos del
instructivo, sin detenerse a pensar mucho en cómo llevarlos a cabo, pero para una
computadora resultaría imposible realizar la tarea, ya que la máquina requiere de
instrucciones muy detallados para poder ejecutarlas.
1 Véase mi Tutorial para la asignatura Análisis,diseño e implantación de algoritmos, Fondo editorial
FCA, México, 2003.
Ejemplificando lo anterior, considérese que a una persona se le pide intercambiar
los números 24 y 9, el sujeto, con cierta lógica, responderá inmediatamente “9 y
24” Ahora veamos cómo lo haría el procesador de una computadora: se tendría
que indicar de qué tipo son los datos que se van a utilizar, para este caso númerosenteros; darle nombre a tres variables, digamos num1, num2 y aux, asignarle a la
variable num1 el número 24, asignarle a num2 el 9 y posteriormente indicarle que
a la variable aux se le asigne el valor contenido en la variable num1, a num1 se le
asigne el valor contenido en la variable num2 y a esta última, se le asigne el valor
de la variable aux para posteriormente imprimir los valores de lasvariables num1 y
num2 que exhibirán los números 9 y 24; como observaste, se requieren muchos
más pasos para indicarle a una computadora que realice la misma tarea que un
ser humano, y muchas tareas todavía la computadora no las puede realizar.
Pasemos ahora a describir las características de un algoritmo, las cuáles son las
siguientes:
 Finito. El algoritmo debe de tener, dentro de la...