Algoritmos: Orígenes de la palabra Al-Khwarizmi, astrónomo y matemático persa, escribió en 825 un tratado en árabe sobre el Cálculo con Cifras Indúes, que se tradujo al latín en el siglo XII como Algoritmos con números indios. La raíz es la misma que la de la palabra Álgebra.
Algoritmos: Definición y tipos Conjunto de instrucciones (en un lenguaje entendido por “la computadora”, una máquina o persona) que especifica las operaciones para procesar una información de entrada arbitraria, y producir una información de salida deseada. Información: Datos (números, cadenas de caracteres) Tipos de algoritmos: Procedimientos para realizar tareas, recetas de cálculo, …
Diversidad de tipos de datos Los tipos de datos que se utilizan en los distintos mecanismos computacionales son equivalentes: cadenas de caracteres, números en diferentes representaciones, … (excepción: el Lambda-Cálculo) La equivalencia anterior no es válida si nos interesa la eficiencia algorítmica. Otros tipos de datos no se pueden (o no se saben) tratar computacionalmente: estado instantáneo de un ser vivo, …
Tipos de datos Los programas son datos y definen funciones Normalmente usaremos cadenas de caracteres A menudo nos restringiremos a cálculos sobre cadenas que son programas Así pues, a menudo los datos serán programas y definirán funciones P(P1, …, Pn): aplicación de la función de P
Algoritmos: Orígenes del concepto Algoritmos concretos: se conocen desde antes de nuestra era Método de Euclides para calcular el máximo común divisor de dos números Método de Eratóstenes para obtener la lista de los números primos El concepto de algoritmo data del primer tercio del siglo XX.
Mecanismos computacionales Lenguajes de programación Máquinas de Turing (Turing) y variantes Gramáticas (Chomsky) Funciones recursivas (Gödel, Herbrandt) Lambda-cálculo (Church) Sistemas canónicos de reescritura (Post) Computación cuántica, …
Mecanismos computacionales, II Algunos de los mecanismos anteriores (lenguajes de programación, máquinas de Turing indeterministas, funciones recursivas, lambda cálculo) se utilizan para definir funciones. Otros (máquinas de Turing indeterministas, gramáticas, reglas de reescritura) se utilizan para reconocer la pertenencia a conjuntos de datos (normalmente cadenas de caracteres).
Mecanismos computacionales: Funciones Casi todos los mecanismos anteriores permiten definir funciones. Pueden ser funciones sobre cadenas de caracteres, sobre números o sobre funciones A veces al calcular el valor de la imagen de un dato (cadena, número o función) mediante una función no se obtiene ningún valor porque el cálculo nunca termina Las funciones definidas a partir de mecanismos computacionales son funciones parciales sobre un dominio universal (?*, ?, ?)
Mecanismos computacionales: Funciones, II Distintos programas pueden definir la misma función. Por ejemplo, hay infinitos programas que nunca paran, y todos ellos definen la función de dominio vacío. No todas las funciones en el sentido matemático se pueden definir a partir de un mecanismo computacional. Lo veremos más adelante.
Mecanismos computacionales: Funciones, III Ejemplo: Dada una máquina de Turing M con alfabeto ?, definimos la función an, si M para sobre w f(w) = ? en caso contrario donde n es el número de pasos que da la máquina antes de pararse a partir de w. A priori no está claro cómo definir f mediante un mecanismo computacional.
Mecanismos computacionales: Funciones, IV El ejemplo anterior tiene trampa: todo depende de cuál sea la máquina M. Por ejemplo, si M calcula a|w| directamen-te, f se calcula mediante la misma M. Si M se mete siempre en un bucle infinito, f se puede calcular mediante la máquina que borra el contenido de la cinta. Hay alguna máquina M para la que f no se puede calcular mediante otra máquina?
Mecanismos computacionales: Funciones, V Otro ejemplo: Hasta 1995 no se sabía cómo calcular la función f(n), que calcula el “primer” valor no trivial de x, y y z tal que xn+yn=zn a menos que no exista, en cuyo caso le hace corresponder x(n)=0, y(n)=0, z(n)=0. Tras la demostración del teorema de Fermat por Wiles, se sabe que f(2)=(3,4,5) y f(n)=(0,0,0) si n?2.
Mecanismos computacionales: Funciones, VI Un mecanismo computacional es más potente que otro cuando permite calcular más funciones. Teorema: Las máquinas de Turing, los lenguajes de programación, las funciones recursivas y el cálculo lambda tienen la misma potencia computacional.
Tesis de Church No hay ningún mecanismo computacional más potente que los anteriores. No es una afirmación demostrable, pues no hay una definición rigurosa y absoluta de mecanismo computacional.
Lenguajes de programación Qué os puedo decir que no sepáis ya? Pueden entrar en bucles interminables. Es imprevisible cuándo lo hacen. Incluso es imposible distinguir cuándo están dentro de un bucle interminable y cuándo están ejecutando un algoritmo complejo. En teoría permiten definir todas las funciones calculables (o recursivas).
Lenguajes de programación, II Lenguajes minimales: Variables Tipos de datos básicos (números, cadenas) Operaciones y condiciones básicas (incremento, anteposición, igualdad, …) Instrucciones (asignación, condicional) Etiquetas y redireccionamiento. Posibilidad adicional: Definición de funciones y recursividad.
| Página siguiente |