Algoritmo en línea

En informática , un algoritmo en línea ^{[ 1 ]} es aquel que puede procesar su entrada pieza por pieza de forma secuencial, es decir, en el orden en que se le proporciona , sin tener toda la entrada disponible desde el principio. Por el contrario, a un algoritmo fuera de línea se le proporcionan todos los datos del problema desde el principio y se le exige que genere una respuesta que resuelva el problema en cuestión.

En la investigación operativa , el área en la que se desarrollan algoritmos en línea se denomina optimización en línea .

Como ejemplo, consideremos los algoritmos de ordenación por selección y por inserción : la ordenación por selección elige repetidamente el elemento mínimo del resto sin ordenar y lo coloca al principio, lo que requiere acceso a toda la entrada; por lo tanto, es un algoritmo fuera de línea. Por otro lado, la ordenación por inserción considera un elemento de entrada por iteración y produce una solución parcial sin considerar los elementos posteriores. Por lo tanto, la ordenación por inserción es un algoritmo en línea.

Cabe destacar que el resultado final de una ordenación por inserción es óptimo, es decir, una lista correctamente ordenada. Para muchos problemas, los algoritmos en línea no pueden igualar el rendimiento de los algoritmos fuera de línea. Si la relación entre el rendimiento de un algoritmo en línea y un algoritmo fuera de línea óptimo está acotada, el algoritmo en línea se denomina competitivo . ^{[ 1 ]}

No todos los algoritmos offline tienen una contraparte online eficiente .

En teoría gramatical, se asocian con las gramáticas lineales .

Debido a que desconoce la totalidad de la entrada, un algoritmo en línea se ve obligado a tomar decisiones que posteriormente podrían no ser óptimas. El estudio de los algoritmos en línea se ha centrado en la calidad de la toma de decisiones posible en este contexto. El análisis competitivo formaliza esta idea comparando el rendimiento relativo de un algoritmo en línea y uno fuera de línea para la misma instancia del problema. Específicamente, la razón de competitividad de un algoritmo se define como la razón en el peor de los casos entre su costo y el costo óptimo, considerando todas las entradas posibles. La razón de competitividad de un problema en línea es la mejor razón de competitividad alcanzada por un algoritmo en línea. Intuitivamente, la razón de competitividad de un algoritmo proporciona una medida de la calidad de las soluciones que produce, mientras que la razón de competitividad de un problema muestra la importancia de conocer el futuro para dicho problema.

Un problema que ejemplifica los conceptos de algoritmos en línea es el problema del viajero canadiense . El objetivo de este problema es minimizar el costo de llegar a un destino en un grafo ponderado donde algunas aristas no son confiables y pueden haber sido eliminadas del grafo. Sin embargo, que una arista ha sido eliminada ( fallado ) solo se revela al viajero cuando llega a uno de los extremos de la arista. El peor caso para este problema es simplemente que todas las aristas no confiables fallen y el problema se reduce al problema habitual del camino más corto . Se puede realizar un análisis alternativo del problema con la ayuda del análisis competitivo. Para este método de análisis, el algoritmo fuera de línea sabe de antemano qué aristas fallarán y el objetivo es minimizar la relación entre el rendimiento de los algoritmos en línea y fuera de línea. Este problema es PSPACE-completo .

Existen muchos problemas formales que ofrecen más de un algoritmo en línea como solución:

• Problema del servidor k
• problema de programación de taller
• Problema de actualización de la lista
• Problema del bandido
• Problema de secretaria
• Buscar juegos
• Problema con el alquiler de esquís
• Problema de búsqueda lineal
• Problema de selección de cartera ^{[ 2 ]}
• Problema de paginación
• Sistemas de tareas métricas
• Emparejamiento bipartito en línea

• Modelo adversario
• Algoritmo dinámico
• Desigualdad del profeta
• Computación en tiempo real
• Algoritmo de transmisión
• Algoritmo secuencial
• Aprendizaje automático en línea / Aprendizaje fuera de línea

• Borodin, A.; El-Yaniv, R. (1998). Computación en línea y análisis competitivo . Cambridge University Press. ISBN 0-521-56392-5.

• Bibliografía de artículos sobre algoritmos en línea