El advenimiento del algoritmo
Alan TURING (1912-1954)






N. 1912 Londres
1931-34 King´s College de
Cambirdge
1936-38 Princeton Ph.D. Lógica,
Álgebra, Teoría de Números
1936 Fundador de las Ciencias de
Computación con sus Máquinas de
Turing
1939-45 Bletchley Park: descifrar
claves alemanas de la máquina
ENIGMA
1939-40 Diseña BOMBE máquina
para descifrar ENIGMA
El advenimiento del algoritmo
Alan TURING (1912-1954)


Pionero en computación: Colabora en
proyectos Colossus, ENIAC, ACE y
MARK I.
Visionario de Inteligencia Artificial




Turing Test: máquina que pueda “chatear”
como humano
http://cogsci.ucsd.edu/~asaygin/tt/ttest.html
1952 acusado de homosexual
1954 se suicidó.
El advenimiento del algoritmo

Algoritmo: Un procedimiento, explicado paso a paso
para resolver un problema o alcanzar un fin específico.
Conjunto de instrucciones del procedimiento.




Calculabilidad: Algo es “calculable” si se puede hacer
en un número finito de pasos siguiendo un algoritmo
con un número finito de instrucciones.


Algoritmos de la aritmética árabe
Algoritmos del cálculo
Algoritmos de una demostración formal
Gödel lo define matemáticamente con sus funciones
recursivas
Decidibilidad: Una afirmación es “decidible” si su
Verdad o Falsedad es calculable.
La Máquina de Turing


Máquina formal (no material) define algoritmo
Algo es calculable si y solo si existe una Máquina de
Turing que lo calcule (Tesis Church-Turing)


Cada máquina consta de:





Cualquier cosa que se pueda hacer efectivamente se puede hacer
con una máquina de Turing.
Cinta lineal dividida en casillas, potencialmente infinita en los dos
sentidos. Casillas en blanco excepto en un número finito con datos.
Mecanismo de Control: autómata que puede asumir diversos
estados.
Cabezal (lee y escribe): Lee símbolo de la casilla, lo borra, escribe
símbolo, y se desplaza una casilla a derecha o izquierda.
Programa: Lista finita de instrucciones.
Usualmente, cada máquina hace una tarea
Programa suma palotes
No.
Instruc
1
2
Estado
Inicial
A
A
Símbolo
leído
0
1
Nuevo
Estado
B
A
Nuevo
Símbolo
0
1
Sentido de
Avance
3
B
0
S
0
PARE
4
B
1
C
0
IZQUIERDA
5
6
C
C
0
1
A
C
1
0
DERECHA
DERECHA
DERECHA
DERECHA
Interpretación primera instrucción: Si el estado del mecanismo de
control es A y el símbolo que lee el cabezal en la casilla de la cinta es 0, el
mecanismo de control pasa al estado B, se borra el símbolo de la cinta para
escribir el símbolo 1 y el cabezal pasa a la siguiente casilla a la derecha
El advenimiento del algoritmo
Resultados de Turing
 Existe una Máquina Universal que simula cualquier
Máquina de Turing al leer su programa en los datos de la
cinta. Modelo del computador actual
 Hay números reales que no son calculables
 Problema de la Parada: No existe ningún algoritmo general
que pueda decidir siempre si otro programa se va a detener
o no al procesar unos datos.
 Entscheidungsproblem (propuesto por Hilbert;
inicialmente por Leibniz): Solución: No existe ningún
algoritmo general que pueda decidir siempre si una
afirmación del cálculo de predicados de primer orden es
Verdadera o Falsa.
El advenimiento del algoritmo

Algoritmo: Un procedimiento, explicado paso a paso
para resolver un problema o alcanzar un fin específico,
especialmente en un computador.





Algoritmos de la aritmética árabe
Algoritmos del cálculo
Algoritmos de una demostración formal
Programa de computador
Codificación:





Símbolos de la aritmética y el álgebra
Símbolos de la lógica
Símbolos de la programación
Encriptación en números (Gödel, binario)
Encripatción de programas en números binarios (von
Neuman)
El advenimiento del algoritmo


John von Neuman (Budapest 1903Washington 1957)
De familia Judía






Mente Universal: Lógica, Conjuntos,Teoría de
juegos, Mecánica Cuántica, Fundador de Ciencias
de Computación
Estudia química en Universidad de Berlín y
Politécnico de Zurich
Doctorado U. Budapest 1926 (Teoría de
Conjuntos)
Enseña en varias universidades alemanas
1933 Emigra a Princeton
Instituto de Estudios Avanzados, Princeton
hasta su muerte 1957
I.E.A. Princeton,fundado 1930
Aparición de los Computadores






Primera generación (1945-1955): Tubos y
conexiones
Segunda generación (1955-1965): Transistores
y sistemas de procesamiento por lotes
Tercera generación (1965-1980): Circuitos
Integrados y Multiprogramación
Cuarta generación: (1980-1990):
Computadoras personales
Quinta generación: Redes, procesamiento en
paralelo
Nanotecnología
El advenimiento del algoritmo

El computador


Alan Turing (autómatas, limitaciones, int. artificial)
John von Neumann (arquitectura del computador)




Lenguajes de computación

Fortran 1954 (John Backus 1924-) en IBM.





A von Neumann le pareció pérdida de tiempo.
Teoría de lenguajes naturales: Chomsky
Análisis y perfeccionamiento de algoritmos


U. operativa – U. control – Memoria – Input/output
El programa se puede ingresar como datos
Teoría de Autómatas
Número de operaciones: tiempo polinomial vs no polinomial
Correctitud de programas
ADN
El Cerebro – simulación de “redes neuronales”
El advenimiento del algoritmo

ADN
El advenimiento del algoritmo

ADN
El advenimiento del algoritmo

ADN
El advenimiento del algoritmo

ADN
Uso del computador en matemáticas

Grafos


Coloración de grafos – Problema de 4 colores
Problema del agente viajero



Número de operaciones (complejidad de algoritmos)



N ciudades  N! posibilidades
N=100 - N!=9.33*10157
Torres de Hanoi: 18*1021 (desde la creación hasta dentro de 500 mil millones de
año, con un movimiento por segundo)
1er problema del 3° milenio
Álgebra lineal – Optimización

George Dantzig-Simplex 1947
Uso del computador en matemáticas


Estadística
Ecuaciones diferenciales
Qué es una ecuación diferencial
 Ecuaciones Navier-Stokes

Presión, velocidad y (temperatura) en función del tiempo
 Fuselaje de un avión (1980), casco de submarino
 Fenómenos metereológicos
 No se ha demostrado existencia y unicidad en dim 3
 Otro problema del milenio


Otros problemas: deformación de una represa
Uso del computador en
matemáticas
Siglo XX: La Pérdida de la Certeza

En Matemáticas


En Ciencia de la Computación


Gödel 1931
Turing 1936
En Física
Relatividad
 Teoría cuántica
 Caos

Siglo XX: Fractales
Fractal de Mandelbrot
Siglo XX: Fractales
Fractal de Mandelbrot - detalle
Siglo XX: Fractales
Conjunto de Julia: c=0
Siglo XX: Fractales
Conjunto de Julia: c=0.3+0.04i
Siglo XX: Fractales
Siglo XX: Fractales
Conjunto de Julia: c=0.38+0.35i
Siglo XX: Fractales
Descargar

GRECIA ANTIGUA