Clase Semana 1: Almacenamiento y transmisión de información mediante algoritmos

Camilo Meza Gaete

Created: 2022-05-26 Thu 09:24

Historia de la computación

La máquina analítica de Charles Babbage

Descrita en 1837, mediante sus componentes mecánicos debería poder servir como calculadora general (antes modeló una máquina para calcular tablas de logaritmos). Podría almacenar 1000 números de 50 dígitos cada uno, en base 10 (aproximadamente 16,2 kB).

babbage.jpg

Esta máquina se modeló a partir de los telares mecánicos y funcionaría a base de vapor. Tristemente los primeros modelos funcionales recién se produjeron 150 años después de su instrucción.

La primera programadora

Augusta Ada King, condesa de Lovelace. Se interesa por la máquina analítica de Babbage y, con su entusiasmo por las matemáticas, diseña un conjunto de instrucciones en tarjetas perforadas para determinar los números de Bernoulli.

ada.jpg

Y no solo esto, también Ada visualiza la capacidad de esta máquina programable para relacionar estos números almacenados y sus conversiones con música e incluso imágenes.

De esta manera es también la primera ingeniera en computación.

Cálculo Lambda

En la década del 30, Alonzo Church y Stephen Kleene establecen un sistema formal que permite definir el concepto de función matemática, su aplicación y la recursión.

al.png

Las funciones en cálculo lambda son anónimas, además de no poseer estado. Sólo transforman sus entradas en salidas.

\[\lambda_{x,y} \rightarrow x + y\]

Church y Kleene logran demostrar que cualquier cálculo (computación) se puede realizar con las definiciones recursivas del cálculo lambda.

Máquina de Turing

Al igual que su profesor, Alan Turing realiza un aporte a la práctica de las máquinas computacionales:

  • Una máquina teórica que puede leer y escribir en una cinta sin fin.
  • El problema de la parada.

alanTuring.png

La máquina de Turing, como se conoce a este modelo, trabajaría en una cinta desde la cual se pueden leer instrucciones, moverse, y finalmente escribir en la cinta, de acuerdo a algún código.

turingMachine.gif

El problema de la parada es algo más complejo: Si se tiene una máquina M, y se le da una instrucción I, ¿Podemos determinar si la máquina procesará I en un número finito de pasos?.

haltingMachine.jpg

Hipótesis de Church-Turing

Gracias a estos aportes, se pudo obtener dos grandes avances:

  • Una máquina que era capaz de modificarse siguiendo un conjunto de instrucciones.
  • Un lenguaje formal en el que expresar estas instrucciones.

El cálculo lambda y la máquina de Turing son equivalentes.

Modelo de Von Neumann

El equipo de físcos a cargo de Jon Von Neumann, describe una arquitectura que permitiría emular (con limitaciones físicas) una máquina de Turing.

arquitecturaVonNeumann.png

Conceptos matemáticos

Algoritmos

Habíamos propuesto que la algorítmica es dar instrucciones por medio de patrones, por ejemplo para calcular la suma de todos los enteros entre dos números:

\[\sum_{i=0}^{i=n} n = (n+1) \frac{n}{2} \]

Cálculo de una raíz cuadrada

Se podría expresar la raíz cuadrada como:

\(\sqrt{x} = y\) tal que \(y \geq 0\) y \(y^{2} = x\)

En pseudo-LISP se podría escribir lo siguiente:

(define (sqrt x)
  (the-y (and (>= y 0)
              (= (square y) x))))

Laboratorio de computación