Orden parcial serie-paralelo

Un orden parcial en serie-paralelo  es un conjunto parcialmente ordenado construido a partir de pedidos parciales en serie-paralelo más pequeños mediante dos operaciones de unión simples [1] [2] .

Los pedidos parciales paralelos en serie se pueden describir como pedidos parciales finitos sin orden N. Tienen dimensión ordinal como máximo dos [1] [3] . Estos órdenes incluyen ordenamientos débiles y la relación de accesibilidad en árboles dirigidos y grafos secuenciales paralelos dirigidos [2] [3] . Los gráficos de comparabilidad de órdenes parciales seriales-paralelos son cographs [2] [4] .

Los pedidos parciales paralelos en serie se aplican en la teoría de la programación [5] , el aprendizaje automático de secuencias de eventos en datos de series temporales [6] , la secuencia de transferencia de datos multimedia [7] y la maximización del rendimiento en flujos de datos [8] .

Los órdenes parciales serie-paralelo también se denominan multiárboles [4] . Sin embargo, este nombre es ambiguo: los árboles múltiples también se denominan órdenes parciales sin subórdenes de cuatro elementos ("diamantes") [9] , así como otras estructuras formadas a partir de varios árboles.

Definición

Sean P y Q dos conjuntos parcialmente ordenados. Conexión serial de P y Q , escrito P ; Q [7] , P * Q [2] , o P ⧀ Q [1] , es un poset cuyos elementos son la unión disjunta de los elementos de P y Q . en P ; Q , dos elementos x e y que pertenecen simultáneamente a P o Q tienen la misma relación de orden que tenían en P o Q respectivamente. Sin embargo, para cualquier par x , y en el que x pertenezca a P e y pertenezca a Q , existe una relación de orden adicional x ≤ y definida por conexión en serie. La conexión en serie es una operación asociativa : puede escribir P ; q ; R como una concatenación de tres órdenes sin introducir ambigüedad sobre cómo combinarlos en pares, ya que entre paréntesis ( P ; Q ); R & P ; ( Q ; R ) describe el mismo orden parcial. Sin embargo, esta unión no es una operación conmutativa , ya que invertir los roles de P y Q dará un orden parcial diferente, en el que se invierten las relaciones de orden para pares de elementos, uno de P y el otro de Q [1] .

Conexión en paralelo de P y Q , escrito P  || Q [7] , P + Q [2] o P ⊕ Q [1] , se define a partir de la unión disjunta de elementos de P y elementos de Q de manera similar. Si un par de elementos pertenece completamente a P o Q , el orden sigue siendo el mismo que en P o Q respectivamente. Si un elemento x pertenece a P y un elemento y pertenece a Q , los elementos x e y son incomparables. La conexión en paralelo es asociativa y conmutativa [1] .

La clase de órdenes parciales serie-paralelo es el conjunto de órdenes parciales que se pueden construir a partir de órdenes parciales singleton utilizando estas dos operaciones. De manera equivalente, una clase es el conjunto más pequeño de órdenes parciales que incluye una orden parcial singleton y que se cierra bajo operaciones de conexión en serie y en paralelo [1] [2] .

El ordenamiento débil es un orden parcial en serie-paralelo que resulta de una secuencia de operaciones de combinación en las que primero se realizan todas las operaciones de combinación en paralelo, y luego los resultados de estas operaciones se combinan solo con operaciones secuenciales [2] .

Descripción por subórdenes prohibidos

Un orden parcial N con cuatro elementos a , b , c y d y exactamente tres relaciones de orden a ≤ b ≥ c ≤ d es un ejemplo de una valla (u orden en zigzag). Su diagrama de Hasse tiene la forma de una letra "N" mayúscula. Este orden no es serie-paralelo ya que no hay forma de dividirlo en secuencias de conexiones paralelas de dos órdenes parciales más pequeños. Se dice que un orden parcial P está libre de N-orden si no hay conjuntos de cuatro elementos en P tales que la restricción de P a estos elementos sea isomorfa a N en el sentido del orden parcial. Las órdenes parciales seriales-paralelas son exactamente esas órdenes parciales finitas no vacías de orden N [1] [2] [3] .

Esto implica inmediatamente (aunque esto puede probarse directamente) que cualquier restricción no vacía de un orden parcial serie-paralelo es en sí misma un orden parcial serie-paralelo [1] .

Dimensión ordinal

La dimensión ordinal de un orden parcial P es el tamaño mínimo de las realizaciones P , el conjunto de extensiones lineales (linealizaciones) de orden P con la propiedad de que para cualesquiera dos elementos distintos x e y de orden P , x ≤ y si y solo si x precede a y en cualquier continuación lineal de la implementación.

Se puede encontrar una definición alternativa en Internet: "El número más pequeño de órdenes lineales que dan un conjunto parcialmente ordenado dado en la intersección se llama su (dimensión ordinal)", por ejemplo, en conferencias de Gurov S.I. [10] o Kuznetsova S.O. [11] .

Las órdenes parciales serie-paralelo tienen una dimensión no superior a dos. Si P y Q tienen implementadores { L 1 ,  L 2 } y { L 3 ,  L 4 } respectivamente, entonces { L 1 L 3 ,  L 2 L 4 } es el implementador de la conexión serial de P ; Q , y { L 1 L 3 ,  L 4 L 2 } es el implementador de la conexión paralela P  || P [2] [3] . Una orden parcial es serial-paralela si y solo si tiene un implementador en el que una de las dos permutaciones es idéntica y la otra es separable .

Se sabe que un orden parcial P tiene dimensión de orden dos si y sólo si existe un orden Q conjugado sobre los mismos elementos con la propiedad de que cualesquiera dos elementos distintos x e y sean comparables exactamente en uno de estos órdenes. En el caso de órdenes parciales serie-paralelo, el orden conjugado, que es en sí mismo serie-paralelo, puede obtenerse realizando una secuencia de operaciones de unión en el mismo orden que para P en los mismos elementos, pero en lugar de unión en serie, P usa unión paralela y viceversa. Más estrictamente, aunque un orden parcial puede tener diferentes órdenes conjugados, cualquier orden conjugado de un orden parcial serial-paralelo también debe ser serial-paralelo [2] .

Relación con la teoría de grafos

Cualquier orden parcial se puede representar (normalmente de forma no única) mediante un gráfico acíclico dirigido que tiene una ruta de x a y para todos los elementos x e y del orden parcial para el que x ≤ y . Los gráficos que representan órdenes parciales en serie-paralelo de esta manera se denominan gráficos en serie-paralelo de vértice y sus reducciones transitivas (gráficos de orden parcial que cubren relaciones ) se denominan gráficos en serie-paralelo de vértice mínimo 3] . Los árboles dirigidos y (con un par de terminales) los gráficos paralelos en serie son ejemplos de gráficos mínimos en serie-paralelos. Por lo tanto, los órdenes parciales seriales-paralelos se pueden usar para representar la relación de accesibilidad en árboles dirigidos y gráficos paralelos [2] [3] .

Un gráfico de comparabilidad de orden parcial es un gráfico no dirigido con vértices para cada elemento y una arista no dirigida para cada par de elementos distintos x , y si x ≤ y o y ≤ x . Es decir, se forma a partir de un gráfico serial-paralelo mínimo eliminando la orientación del borde . El gráfico de comparabilidad de orden serial-paralelo es un cografo : las operaciones de unión de orden paralelo serial y paralelo dan operaciones en el gráfico de comparabilidad que forman una unión disjunta de dos subgrafos o conectan dos subgrafos por todos los bordes posibles. Estas dos operaciones son las operaciones básicas en la definición de cographs. Por el contrario, cualquier cografo es un gráfico de comparabilidad de orden parcial paralelo en serie. Si un orden parcial tiene como grafo de comparabilidad un cografo, entonces debe ser un orden parcial serial-paralelo, ya que cualquier otro tipo de orden parcial tiene un suborden N, que debe corresponder a un camino generado con cuatro vértices en su grafo de comparabilidad. , y tales caminos están prohibidos en los cografos [2] [4] .

Complejidad computacional

Puede utilizar la descripción de suborden prohibido de órdenes parciales en serie-paralelo como base para un algoritmo que comprueba, en función lineal del tiempo del número de pares en una relación, si una relación binaria dada es un orden parcial en serie-paralelo [2] [3] . Alternativamente, si un orden parcial se describe como el orden de accesibilidad de un gráfico acíclico dirigido , es posible probar si es un orden parcial serial-paralelo y, de ser así, calcular su cierre transitivo en el tiempo proporcional a la número de vértices y aristas en la clausura transitiva. Sigue siendo una pregunta abierta si es posible mejorar el tiempo de reconocimiento de las órdenes de accesibilidad en serie-paralelo a lineal en el tamaño del gráfico de entrada [12] .

Si una orden parcial en serie-paralelo se representa como un árbol de expresión que describe la ejecución de operaciones en serie y en paralelo, entonces los elementos de la orden parcial se pueden representar mediante las hojas del árbol de expresión. La comparación de dos elementos cualquiera se puede hacer algorítmicamente encontrando el antepasado menos común de las dos hojas correspondientes. Si este ancestro es una conexión en paralelo, los dos elementos son incomparables, de lo contrario, el orden de las conexiones en serie de los operandos determina el orden de los elementos. De esta forma, un orden parcial serie-paralelo de n elementos se puede representar en el espacio O( n ) para determinar cualquier valor a comparar en el tiempo O(1) [2] .

El problema de verificar para dos órdenes parciales P y Q dados en serie-paralelo que P contiene una restricción isomorfa a Q es NP-completo [3] .

Aunque el problema de contar el número de extensiones lineales de un orden parcial arbitrario es #P-completo [13] , se puede demostrar que se puede resolver en tiempo polinomial para órdenes parciales seriales-paralelos. Es decir, si L ( P ) denota el número de extensiones lineales de orden parcial P , entonces L ( P ; Q )= L ( P ) L ( Q ) y

[2] .

Aplicaciones

Mannila y Meek [14] utilizaron órdenes parciales en serie-paralelo como modelo para la secuencia de eventos en datos de series de tiempo . Describieron algoritmos de aprendizaje automático para modelos de inferencia para este tipo y demostraron la eficacia de los algoritmos para generar requisitos de cursos requeridos en función de los datos de registro de los estudiantes, así como para modelar patrones de uso del navegador [6] .

Amer et al .[15] argumentan que los órdenes parciales en serie-paralelo son convenientes para modelar las solicitudes de secuenciación de presentación de medios . Utilizaron la fórmula para calcular el número de continuaciones lineales de un orden parcial en serie-paralelo como base para el análisis de algoritmos de transmisión multimedia [7] .

Chaudhary y otros [16] utilizaron órdenes parciales en serie-paralelo para modelar dependencias de tareas en un flujo de datos de procesamiento masivo de datos para visión artificial . Demostraron que cuando se usan órdenes en serie-paralelo para esta tarea, es posible construir de manera efectiva un programa óptimo que asigna diferentes tareas a diferentes procesadores de un sistema de cómputo paralelo para optimizar el rendimiento del sistema [8] .

La clase de órdenes, algo más general que el concepto de órdenes parciales en serie-paralelo, está dada por árboles PQ , estructuras de datos utilizadas en algoritmos para verificar si un gráfico es plano y para reconocer gráficos de intervalos [17] . Un nodo P de un árbol PQ permite todos los ordenamientos posibles de sus descendientes como una conexión paralela en órdenes parciales, mientras que un nodo Q requiere que los sucesores sigan un orden lineal fijo como órdenes parciales secuenciales. Sin embargo, a diferencia de los órdenes parciales paralelos en serie, los árboles PQ le permiten invertir el orden lineal en cualquier nodo de Q.

Notas

  1. ↑ 1 2 3 4 5 6 7 8 9 Bechet, De Groote, Retoré, 1997 , p. 230–240.
  2. ↑ 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 Möhring, 1989 , pág. 105–194.
  3. ↑ 1 2 3 4 5 6 7 8 Valdés, Tarjan, Lawler, 1982 , p. 298–313.
  4. ↑ 1 2 3 Jung, 1978 , pág. 125-133.
  5. ↑ Lawler, 1978 , pág. 75–90.
  6. ↑ 1 2 Mannila, Meek, 2000 , p. 161–168.
  7. ↑ 1 2 3 4 Amer, Chassot, Connolly et al., 1994 , pág. 440–456.
  8. ↑ 1 2 Choudhary, Narahari, Nicol, Simha, 1994 , p. 439–445.
  9. ↑ Furnas y Zacks 1994 , p. 330–336.
  10. ↑ Gurov, 2012 , pág. 111 Definición 3.14.
  11. ↑ Kuznetsov .
  12. ↑ Ma, Spinrad, 1991 , pág. 175–183.
  13. ↑ Brightwell, Winkler, 1991 , pág. 225–242.
  14. ↑ Mannila, Manso, 2000 .
  15. ↑ Amer, Chassot, Connolly y otros, 1994 .
  16. ↑ Choudhary, Narahari, Nicol, Simha, 1994 .
  17. ↑ Booth y Lueker 1976 , pág. 335–379.

Literatura