Laboratorio 1, página 2: Problema vs. instancia de un problema

• Un problema (problem) es una descripción general de una tarea que puede (o no) ser resuelta algorítmicamente.
• La instancia de un problema (instance of a problem) es el caso de un problema, con entradas específicas.

Laboratorio 1, página 2: Tiempo lineal vs. búsqueda lineal

• Un algoritmo toma tiempo lineal (linear time) si al multiplicar el tamaño de la entrada por diez se multiplica el tiempo requerido por diez.
  
AAP-2.O.5
• Un algoritmo de búsqueda lineal (linear search) o búsqueda secuencial (sequential search) revisa en orden cada elemento de una lista, un proceso que toma tiempo lineal.

Laboratorio 1, página 3: Búsqueda binaria

Un algoritmo de búsqueda binaria (binary search) comienza en medio de una lista ordenada y elimina repetidamente la mitad de la lista hasta que se encuentra el valor deseado o se han eliminado todos los elementos.

La búsqueda lineal hace un recorrido completo de la lista. La búsqueda binaria ahorra tiempo al hacer un recorrido parcial de la lista.

Laboratorio 1, página 4: Eficiencia

La relación entre el tamaño de la entrada y el número de pasos requeridos para resolver un problema es la eficiencia (efficiency) del algoritmo utilizado para resolver el problema.

Laboratorio 1, página 5: Tiempo lineal, tiempo sublineal, tiempo constante y tiempo cuadrático

• Un algoritmo toma tiempo lineal (linear time) el número de pasos es proporcional al tamaño de la entrada; doblando el tamaño de la entrada se dobla el tiempo requerido.
• Un algoritmo toma tiempo sublineal (sublinear time) si el tiempo aumenta más lentamente que el tamaño.
• Un algoritmo toma tiempo constante (constant time) si toma la misma cantidad de tiempo sin importar el tamaño de la entrada.
• Un algoritmo toma tiempo cuadrático (quadratic time) si el número de pasos es proporcional al cuadrado del tamaño de la entrada.

Laboratorio 1, página 5: Tiempo polinómico y tiempo exponencial

• Un algoritmo toma tiempo polinómico si el número de pasos es menor o igual a una potencia del tamaño de la entrada, como la constante (n⁰), sublineal, lineal (n¹), cuadrático (n²), o cúbico (n³).
• Un algoritmo toma tiempo exponencial si el número de pasos es menor o igual a una función como 2ⁿ, 10ⁿ, etc., que es mucho más lento que cualquier polinomio.

Laboratorio 1, página 6: Problema de decisión vs. problema de optimización 

• Un problema de decisión (decision problem) es un problema con una respuesta verdadera/falsa (por ejemplo, "¿es 5,825,496,221 un número primo?").
• Un problema de optimización  (optimization problem) es uno con el objetivo de encontrar la mejor solución entre muchos (por ejemplo, "¿cuál es el mejor horario de la escuela para colocar a cada estudiante en la mayor cantidad posible de sus clases solicitadas?").

Laboratorio 1, página 6: Problema resoluble vs. problema indecidible

Un problema resoluble (decidable) es un problema de decisión para el cual es posible escribir un algoritmo que dará una salida correcta para todas las entradas.

Un problema indecidible (undecidable) es lo opuesto.  No es posible escribir un algoritmo que dará una salida correcta para todas las entradas—aunque podría ser posible para algunos de ellos.

Laboratorio 1, página 8: Computación secuencial vs. computación en paralelo

Esta sección cubre dos modelos de computación:

• En computación secuencial (sequential computing), las operaciones se realizan en orden de una en una.
• En computación en paralelo (parallel computing), el programa se divide en pasos más pequeños, algunos de los cuales se realizan al mismo tiempo. Las computadoras modernas tienen múltiples procesadores (2, 4, u 8) en una sola computadora, para que puedas hacer un procesamiento paralelo a pequeña escala en la máquina de tu escritorio.

Laboratorio 1, página 8: Computación distribuida

Computación distribuida (distributed computing) es una forma de computación paralela que utiliza múltiples computadoras (tal vez incluso se extienda por todo el mundo).

Laboratorio 1, página 8: Procesador

Un procesador (processor) es una pieza de circuitos dentro de una computadora que procesa las instrucciones de los programas de computación.

Créditos de la imagen: Wikipedia usuario Solipsist

Laboratorio 1, página 8: Aceleración

Los programadores se refieren a la aceleración (speedup) de la solución paralela para describir cuántas veces más rápido se compara la solución paralela con la solución secuencial:
\text{aceleración} = \frac{\text{tiempo secuencial}}{\text{tiemo paralelo}}

Laboratorio 2, página 1: Simulaciones

Las simulaciones (simulations) son representaciones por computadora de cosas o situaciones reales que varían con el tiempo. Una simulación es una abstracción diseñada para un propósito en particular.

Laboratorio 3, página 1: Datos vs. información

• Los datos (data) son los valores que los ordenadores reciben de varias fuentes, incluyendo la actividad humana, los sensores, etc.
• La información (information) son los patrones humanamente útiles extraídos de los datos.

Los datos proporcionan oportunidades para identificar tendencias, establecer conexiones y abordar problemas. La información es el resultado del análisis de esos datos.

Laboratorio 3, página 1: Correlación

Una correlación (correlation) es un tipo particular de información, es decir, una dependencia entre dos variables en una situación. Por ejemplo, en la primera imagen aquí, mientras una variable sube, la otra baja. También es una correlación cuando una variable sube o baja y la otra cambia de la misma manera.

Laboratorio 3, página 1: Insight

Insight es una conclusión significativa extraída del análisis de la información.

Laboratorio 3, página 3: Registros, campos y columnas

• Un registro (record) es una fila de un conjunto de datos (distinta de la primera fila, que contiene los títulos de las columnas). Un registro único puede ser los datos de un estudiante de su escuela, los datos de un terremoto que ocurrió, los datos de un hospital en los EE. UU., o los datos de un contacto en tu lista de contactos. En otras palabras, un registro es un segmento horizontal del conjunto de datos.
• Un campo (field) es un elemento de un registro en un conjunto de datos. Puede ser el tutor o maestro de una persona, la magnitud de un terremoto en Los Ángeles la semana pasada, el propietario de un hospital en Chicago, o el número de teléfono de una persona en tu lista de contactos.
• Una columna (column) es una lista que contiene los datos de un campo para todos los registros de un conjunto de datos. Una columna podría ser el profesor de un salón de clases para cada estudiante en tu escuela, la magnitud de cada terremoto en el conjunto de datos, el propietario de cada hospital en los EE. UU. o el número de teléfono de cada persona de tu lista de contactos. En otras palabras, una columna es un segmento vertical del conjunto de datos.

Laboratorio 3, página 3: Limpieza de datos

Limpieza de datos (cleaning data) es el proceso de hacer los datos uniformes sin cambiar su significado (como el reemplazo de abreviaturas, ortografía y mayúsculas por la palabra deseada o la conversión de millas a kilómetros). Los programadores pueden utilizar programas para filtrar y limpiar los datos digitales, obteniendo así una mayor visión y conocimiento.

Laboratorio 3, página 5: Clasificar los datos

Clasificar los datos (classifying data) es extraer grupos de datos con una característica en común.

Laboratorio 3, página 5: Modo

El modo (mode) de un conjunto de datos es el valor que aparece con más frecuencia.

Laboratorio 3, página 6: Metadatos

Los metadatos (metadata) son datos sobre datos. Por ejemplo, el dato puede ser una imagen, mientras que los metadatos pueden incluir la fecha de creación o el tamaño del archivo de la imagen.

Laboratorio 4, página 1: Prueba por contradicción

Una prueba por contradicción (proof by contradition) es una prueba de dos pasos para saber si algo es falso que se realiza:

1. asumiendo que es verdad
2. mostrando cómo eso es imposible (que crea una contradicción)

Laboratorio 4, página 1: Declaración indecidible vs. declaración autocontradictoria

Una declaración indecidible (undecidable) puede ser verdadera o falsa; no sabemos cuál.

Una declaración autocontradictoria (self-contradictory) no puede ser verdadera ni falsa.

Laboratorio 4, página 2: Bucle infinito, problema irresoluble y problema indecidible

Un bucle infinito (infinite loop) es una secuencia de instrucciones de computadora que se repite para siempre.

Un problema irresoluble (unsolvable problem) es aquel para el que nunca se puede escribir un algoritmo para encontrar la solución.

Un problema indecidible (undecidable problem) es aquel para el que nunca se puede escribir un algoritmo que siempre dé una decisión verdadero/falso correcta para cada valor de entrada. Los problemas indecidibles son una subcategoría de problemas irresolubles que incluyen solo problemas que deberían tener una respuesta sí/no (como: ¿mi código tiene un error?).