¿Cuál es la diferencia entre un algoritmo en línea y fuera de línea?

Un algoritmo en línea procesa la entrada solo pieza por pieza y no sabe sobre el tamaño real de la entrada al principio del algoritmo.

Un ejemplo de uso frecuente es la programación: tiene un conjunto de máquinas y una carga de trabajo desconocida. Cada máquina tiene una velocidad específica. Desea eliminar la carga de trabajo lo más rápido posible. Pero como no conoce todas las entradas desde el principio (a menudo puede ver solo la siguiente en la cola), solo puede estimar qué máquina es la mejor para el entrada actual. Esto puede resultar en una distribución no óptima de su carga de trabajo, ya que no puede hacer ninguna suposición sobre sus datos de entrada.

Por otro lado, un algoritmo offline solo funciona con datos de entrada completos. Toda la carga de trabajo debe conocerse antes de que el algoritmo comience a procesar los datos.

Ejemplo:

Workload:
   1. Unit (Weight: 1)
   2. Unit (Weight: 1)
   3. Unit (Weight: 3)
Machines:
   1. Machine (1 weight/hour)
   2. Machine (2 weights/hour)

Possible result (Online):
   1. Unit -> 2. Machine  // 2. Machine has now a workload of 30 minutes
   2. Unit -> 2. Machine  // 2. Machine has now a workload of one hour
  either
   3. Unit -> 1. Machine  // 1. Machine has now a workload of three hours
  or 
   3. Unit -> 2. Machine  // 1. Machine has now a workload of 2.5 hours

 ==> the work is done after 2.5 hours

Possible result (Offline):
   1. Unit -> 1. Machine  // 1. Machine has now a workload of one hour
   2. Unit -> 1. Machine  // 1. Machine has now a workload of two hours
   3. Unit -> 2. Machine  // 2. Machine has now a workload of 1.5 hours

 ==> the work is done after 2 hours

Tenga en cuenta que el mejor resultado en el algoritmo fuera de línea solo es posible ya que no usamos la mejor máquina desde el principio. Ya sabemos que habrá una unidad pesada (unidad 3), por lo que esta unidad debe ser procesada por la máquina más rápida.

Un algoritmo fuera de línea sabe todo sobre sus datos de entrada en el momento en que se invoca. Un algoritmo en línea, por otro lado, puede obtener partes o todos sus datos de entrada mientras se está ejecutando.

An se dice que el algoritmo está en línea si no lo hace conozca los datos en los que se ejecutará previamente. Un algoritmo sin conexión puede ver todos los datos por adelantado.

Un algoritmo en línea es aquel que recibe una secuencia de solicitudes y realiza una acción inmediata en respuesta a cada solicitud.

Por el contrario,un algoritmo fuera de línea realiza una acción después de que se toman todas las solicitudes.

Este artículo de Richard Karp da más información sobre algoritmos en línea y fuera de línea.

Cache Miss problem: En un sistema informático, la caché es una unidad de memoria utilizada para evitar el desajuste de velocidad entre el procesador más rápido y la memoria primaria más lenta. El objetivo de usar caché es minimizar el tiempo de acceso promedio manteniendo algunas páginas a las que se accede con frecuencia en la caché. El supuesto es que estas páginas pueden ser solicitadas por el procesador en un futuro próximo. Por lo general, cuando el procesador realiza una solicitud de página, la página se obtiene de la página principal o secundaria la memoria y una copia de la página se almacenan en la memoria caché. Supongamos que la caché está llena, entonces el algoritmo implementado en la caché tiene que tomar la decisión inmediata de reemplazar un bloque de caché sin conocimiento de futuras solicitudes de página. Surge la pregunta: ¿qué bloque de caché debe reemplazarse? (En el peor de los casos, puede suceder que reemplace un bloque de caché y en el siguiente momento, el procesador solicite el bloque de caché reemplazado). Por lo tanto, el algoritmo debe estar diseñado de tal manera que tome decisión inmediata a la llegada de una solicitud entrante sin conocimiento previo de toda la secuencia de solicitudes. Este tipo de algoritmos se conocen como ALGORITMO EN LÍNEA

Podemos diferenciar los algoritmos offline y online en función de la disponibilidad de las entradas antes del procesamiento del algoritmo.

Algoritmo fuera de línea: Toda la información de entrada está disponible para el algoritmo y procesada simultáneamente por el algoritmo. Con el conjunto completo de información de entrada, el algoritmo encuentra una manera de procesar eficientemente las entradas y obtener una solución óptima.

Algoritmo en línea: Las entradas vienen sobre la marcha, es decir, todas las entradas la información no está disponible para el algoritmo simultáneamente más bien parte por parte como una secuencia o en el tiempo. Sobre la disponibilidad de una entrada, el algoritmo tiene que tomar una decisión inmediata sin ningún conocimiento de la información de entrada futura. En este proceso, el algoritmo produce una secuencia de decisiones que tendrán un impacto en la calidad final de su rendimiento general.

Eg: Enrutamiento en la red de comunicación:

Los paquetes de datos de diferentes fuentes llegan a el router más cercano. Hay más de un enlace de comunicación conectado al router. Cuando un nuevo paquete de datos llega al enrutador, entonces el enrutador tiene que decidir inmediatamente a qué enlace se enviará el paquete de datos. (Supongamos que todos los enlaces se enrutan al destino, todos los enlaces tienen el mismo ancho de banda, todos los enlaces son la parte del camino más corto hacia el destino). Aquí, el objetivo es asignar cada paquete de datos entrante a uno de los enlaces sin conocer los paquetes de datos futuros de tal manera que la carga de cada enlace será equilibrada. Ningún enlace debe estar sobrecargado. Este es un problema de equilibrio de carga.

Aquí, el planificador implementado en el router no tiene idea acerca de los futuros paquetes de datos, pero tiene que tomar la decisión de programación para cada paquete de datos entrante. En contraste, un programador fuera de línea tiene un conocimiento completo sobre todos los paquetes de datos entrantes, luego asigna eficientemente los paquetes de datos a diferentes enlaces y puede equilibrar de manera óptima la carga entre diferentes enlaces.