Introducción a la computación

¿Cuál es el propósito de la disciplina? Es decir, ¿a qué se dedicará el resto de su vida la persona profesional de esta disciplina? ¿Cuál es el método para lograr ese propósito?

Los estudios universitarios no son un fin. Nadie estudia para contemplar un título colgado en una pared, ahí terminar y dedicarse a otra cosa. Los estudios son un medio. Los fines para los cuales se estudia una carrera son más trascendentales. Los hay a corto y largo plazo. Ejemplos podrían ser: para cambiar a otra carrera en la que no logré ingresar, para ganar bien, crear una empresa, ser como alguien que admiro, …​

Mercado laboral costarricense e internacional. Sector industria, gobierno, y académico. Empleamiento vs emprendedurismo.

Un problema es una situación vivencial desventajosa y las acciones para cambiarla a una situación favorable (modelo solución) no son inmediatamente obvias. Hay que averiguar o construir este modelo, lo cual genera un bloqueo mental. Se diferencia de un ejercicio que es una situación para la cual se tiene un modelo solución, el cual simplemente se aplica o “ejercita”.

Comprender el problema. Complejo cuando uno no está familiarizado(a) con el contexto.

Producto: documentos de requerimientos.

Prueba: verificación con los usuarios/clientes.

Generar casos de prueba

Arquitecto que construye un edificio sin planos. Cambian los requerimientos.

Resolver el problema con artefactos baratos. Pueden ser artefactos de invención propia, o si son definidos por un colectivo, depende del paradigma.

Producto: modelos o diseños.

Prueba: Rastrear el modelo con casos de prueba y confirmar que realiza o produce el resultado deseado.

Traducir los modelos

Concepto de control de versiones y sus beneficios.

Crear un repositorio para el curso, y cada curso de la carrera

Agregar todos los archivos de Markdown hechos hasta el momento (filosofía de la computación).

Buscar soluciones existentes primero: adopción de herramientas de software

Definición de programación

Reutilizar recursos siempre dando el crédito cuando corresponde.

No se puede instruir una máquina si uno no puede resolver un problema con los recursos que uno dispone. Sin las limitaciones de la máquina

Recursos: papel, plastilina, legos, matemática…​

Resolver algunos problemas funcionales/matemática discreta.

Procesamiento

Almacenamiento

Comunicación

Definición de paradigma de computación/programación.

Paradigmas, conceptos, y lenguajes de programación. Relación entre ellos.

Relaciones entre paradigmas

Computación/programación imperativa vs declarativa

Computación/programación funcional

Computación/programación procedimental

Computación/programación genérica

Computación/programación orientada a eventos

Computación/programación orientada a objetos

Computación/programación concurrente

Computación/programación distribuida

Computación/programación lógica

Computación/programación metaprogramación

Problemas complejos: combinación de los paradigmas

Metáfora de la caja de herramientas. Ejemplo del albañil que sólo usa martillo.

Hacerle un readme al repositorio

Tabla de contenidos

El agente que ejecuta un algoritmo (persona o máquina), llamado agente computacional, no necesita comprender el problema, ni las decisiones de diseño que llevaron a la formulación del algoritmo.

No todo problema se puede resolver algorítmicamente, incluso aunque parezcan factibles. Un ejemplo clásico el el problema de la parada, que consiste en construir un algoritmo que indique si otro algoritmo se detendrá en algún momento. Teóricamente es imposible construir este algoritmo. Este tipo de problemas se les conoce como problemas no resolubles {unsolvable problems}.

Existe otro conjunto de problemas para los cuales teóricamente se puede construir una solución algorítmica, pero su ejecución consume tantos recursos que incluso la super computadora más potente que disponga la humanidad tardaría millones de años en poderlos ejecutar. A estos problemas se les llaman problemas intratables.

Un ejemplo de un problema intratable es una solución que construya todo el espacio de movimientos (jugadas) del Ajedrez, lo cual sería el algoritmo que gane todos los juegos en que compita. Con una oportunidad promedio de 40 jugadas posibles por turno y 30 turnos para que el juego concluya, la cantidad aproximada de movimientos es un árbol de \(40^30 ~ 10^48\) jugadas. Una supercomputadora que pueda analizar mil billones de jugadas en un segundo (\(10^15\)) tardaría \(\frac{10^48}{10^15}=10^33s=3.17 \cdot 10^25 \text{años}\), es decir, aproximadamente 32 cuatrillones de años en hacer su primer movimiento.

Existe un último grupo de problemas que se conjetura pueden resolverse algorítmicamente, pero nadie ha intentado o logrado elaborar uno. Algunas actividades que son naturales para los seres humanos, pero realmente difíciles para las computadoras entran en esta categoría, como la habilidad de generar humor.

La máquina no tiene tanta libertad como los humanos. Sus capacidades son limitadas a los tres tipos de recursos. De ellos se definen ocho tipo de instrucciones:

Un valor es un elemento de un conjunto de datos. Por ejemplo, -5 es un valor del conjunto de números enteros. Una expresión es una combinación de operadores y operandos que se evalúa en un valor. Por lo tanto, las instrucciones que trabajan con un valor, puede este cambiarse por una expresión.

Las tareas/subtareas (rutinas/subrutinas) es el mecanismo funcional y procedimental de descomponer, modularizar, y abstraer grandes problemas en otros unidades más pequeñas y reutilizables desde diferentes contextos.

Las primitivas de comunicación (primer grupo de la tabla) son los archivos (una secuencia de bytes que se accede con cursores de entrada o salida) y los eventos. Los archivos ofrecen operaciones de entrada (input o read), salida (output o write), posicionamiento (seeking), apertura (open), cierre (close), y manejo de errores (eof). Los eventos pertenecen al paradigma de computación dirigida por eventos (event-driven programming). A nivel de algoritmos se podrían incorporar la primitiva de registro de eventos (when).

La memoria (almacenamiento, segundo grupo de la tabla) se organiza en cuatro primitivas: variables, indirección (direcciones de memoria o punteros), arreglos (array), y registros de memoria (record).

Entrada y salida [AC]

Variables y expresiones (cómputo) [AC]

Control de flujo/secuencia [AC]

Tareas/subrutinas/modularización [AC]

El ábaco: representa el estado del programa, la persona es la CPU. La persona ejecuta procedimientos o algoritmos para realizar las operaciones.

El incremento de la investigación científica en el renacimiento, que requería el cómputo de cálculos aritméticos más complejos y precisos, pudo ser la motivación de automatizarlos mediante máquinas [Schn19]. Hubo un considerable número de máquinas calculadoras mecánicas que se desarrollarían hasta la aparición de la calculadora electrónica hacia 1970. En lo siguiente sólo se listan algunas.

La Pascalina (Francia) Video de la máquina. Podía hacer sumas y restas. Concepto de acumulador, desborde, aritmética de precisión de punto fijo vs matemática entera.

Gottfried Leibnitz (Alemania) se interó en el trabajo de Pascal y otros. Construyó dos calculadoras capaces de multiplicar. Su innovación se debe a un dispositivo al que llamó La rueda de Leibnitz (Leibnitz’s Wheel) creado en 1673 y que se usaría en las calculadoras mecánicas hasta su extición hacia la década de los 1970.

Se diferencian de las computadoras en que las calculadoras no son programables.

En la Pascalina, cada engranaje representa un dígito en base 10. Naturalmente, la Pascalina no puede representar números de una cantidad infinita de dígitos, si no de tantos dígitos como engranajes tenga. Si una pascalina tiene w engranajes, se dice que es una Pascalina de w digitos. El concepto de Pascalina en este contexto sigue siendo válido en las computadoras modernas, pero recibe el nombre de acumulador (en inglés, accumulator) o registro de CPU (en inglés, register). Naturalmente las computadoras modernas no utilizan engranajes sino transistores, pero el concepto sigue siendo el mismo.

Suma de dos números en precisión de punto fijo. En un aritmética de precisión de punto fijo, la instrucción 6.a del algoritmo anterior, cambiaría por "encienda bombillo de desbordamiento (overflow)".

El telar de Joseph Jacquard primera máquina programable para automatizar la creación de tejidos que era una labor muy lenta y propensa a fallos. 1801. El dispositivo innovador fue el uso de tarjetas perforadas que indicaban si un hilo iba por encima o debajo del tejido. Forman un patrón. Cada tarjeta programa una fila del patrón. Varias tarjetas se conectan entre ellas y el telar las procesaba en secuencia. Primer dispositivo en usar código binario?

Impacto en la sociedad. Personas por temor a perder su puesto de trabajo, formaron agrupaciones que violentamente se opusieron a los cambios tecnológicos. Un ejemplo fueron los Luddites, liderados por Ned Ludd Nottingham en Inglaterra, quienes quemaron fábricas donde se usaban telares de Jacquard. Es el inicio de la tecnofobia [Schn19].

Charles Babbage era hijo de un bancario en Inglaterra. Estudió matemáticas y se convirtió en profesor de esta disciplina en la Universidad de Cambridge. En las dos anteriores el operador interpreta el resultado que es la posición final de los engranajes. Babbage visionó que la calculadora imprimiera el resultado para evitar errores de interpretación.

¿Por qué escribir procedimientos que sabemos hacer informalmente de esa manera tan complicada? Porque si podemos especificar formalmente un algoritmo para resolver un problema, entonces podemos automatizar su solución. Es decir, codificarlo en un lenguaje de programación, convertirlo en un programa de computadora, de tal forma que pueda ser ejecutado con las ventajas de velocidad, almacenamiento, y comunicación que esta dispone.

Hay varias convenciones para representar enteros negativos en un acumulador: signo-magnitud, notación de exceso, y complemento a dos.

El primer bit siempre indica el signo, donde 0 es positivo o neutro, y 1 es negativo. El bit de signo sólo tiene ese significado. Los restantes bits codifican la magnitud utilizando notación sin signo.

Se utiliza el método de los complementos para representar positivos y negativos en acumuladores de ancho \$w\$ dígitos en base \$b\$. En este método se define:

Una forma más rápida de calcular el negativo es obtener el complemento a la base -1 de cada dígito y luego sumarle uno, expresado \$\bar{x} = b^w - 1 - x + 1\$, de lo que se infiere que el negativo de un número es su complemento más 1:

Se utiliza el método de los complementos para representar positivos y negativos.

Sea \$\vec{n}\$ un número en una base cualquiera \$b \ge 2\$, cuyos dígitos representados un acumulador de ancho \$w\$ corrresponden al vector \$(n_{w-1}, n_{w-2}, ..., n_0)\$. Al sumar el valor posicional de esos dígitos, se obtiene su equivalente valor en base \$10\$:

En complemento a 2 el bit más significativo además de su valor posicional, representa el signo. Al convertir el vector \$\vec{n}\$ de complemento a 2 a base 10, el primer dígito pesa su valor posicional acorde a su signo, es decir:

Para convertir un número \$n\$ en base \$10\$ a cualquier otra base sin signo \$b \ge 2\$, el resultado serán los residuos de múltiples divisiones por la base hasta que el cociente se anule. Este algoritmo puede expresarse construyendo el vector resultado \$\vec{r}\$ compuesto de los dígitos:

Para convertir un número \$n\$ en base \$10\$ con signo, es decir a complemento a \$b\$, donde la base destino \$b \ge 2\$, se hacen dos pasos. Primero, se convierte el valor absoluto \$|n|\$ a la base destino cuyo resultado intermedio sería el vector \$\vec{s}\$, usando la conversión sin signo de la Ecuación (4). Luego, si \$n\$ es negativo, el resultado final sería el negativo de \$\vec{s}\$, expresado como el complemento a la base según la Ecuación (1), es decir \$-\vec{s}=\bar{s} + 1\$:

Algoritmo para convertir de decimal (reales de los humanos) a IEEE 754:

Algoritmo para convertir de punto flotante a decimal:

Tabla de mapeo entre operadores lógicos, operadores aritméticos, y compuertas lógicas. Sus tablas de verdad.

Actividad: probar las compuertas lógicas en LogiSim.

Un comparador (CMP) es una función que recibe dos números a y b de igual cantidad de bits y produce tres salidas:

Circuito que recibe dos números de igual cantidad de bits y produce otro número resultado de igual cantidad de bits. Produce además un bit de acarreo final que sirve para saber si hubo desborde (overflow) o no. Para permitir encadenar varios sumadores, recibe como entrada un acarreo que proviene de otro sumador.

Un multiplexor o selector (MUX) es un circuito lógico (función) que recibe \$2^n\$ entradas y escoge/selecciona una de ellas que será copiada en la salida. Las entradas están numeradas desde 0 hasta \$2^n - 1\$. Para saber cuál de las entradas es la que será copiada en la salida, recibe la identificación de éste como otro número de \$n\$ bits. Por lo tanto, la cantidad total de entradas del multiplexor corresponde a \$2^n + n\$.

Un demultiplexor (DEMUX) es un circuito lógico (función) que invierte la función del multiplexor. Recibe un número por entrada que será copiado a una de las \$2^n\$ salidas del circuito, las demás producirán ceros. Las salidas están numeradas desde 0 hasta \$2^n - 1\$. Para saber cuál de las salidas será la que copie la entrada, recibe la identificación de esta como otro número de \$n\$ bits. Por lo tanto, la cantidad total de entradas del demultiplexor corresponde a \$n + 1\$ mientras que las salidas a \$2^n\$.

Un decodificador (decoder, DEC) es el mismo circuito que el demultiplexor con la diferencia de que no tiene un número por entrada que será copiado en una de las salidas. Sino que las salidas son siempre de un único bit y una de ellas estará encendida (1) y las demás apagadas (0). En adelante se usará más este circuito que el demultiplexor.

Memoria es un arreglo de celdas (bytes) que almacenan datos o instrucciones. Toda celda está identificada por un entero sin signo, su dirección de memoria.

Ancho de la memoria (actualmente 8 bits). Se requieren varias celdas continuas para almacenar números más grandes de 16, 32, 64, y 128 bits.

Memoria principal vs memoria secundaria. Random Access Memory (RAM) vs Read-Only Memory (ROM).

Dirección vs valor. Prefijos en base 10 y base 2.

Registros de una memoria:

Operaciones de una memoria (algoritmos):

Arquitectura de von Neumann

Tipos de instrucciones

Actividades:

Ejercicios: