En matemáticas teóricas de órdenes , un orden parcial en serie-paralelo es un conjunto parcialmente ordenado construido a partir de órdenes parciales en serie-paralelas más pequeñas mediante dos operaciones de composición simples. [1] [2]
Los órdenes parciales serie-paralelos pueden caracterizarse como los órdenes parciales finitos libres de N; tienen una dimensión de orden como máximo dos. [1] [3] Incluyen órdenes débiles y la relación de accesibilidad en árboles dirigidos y gráficos de series paralelas dirigidas . [2] [3] Las gráficas de comparabilidad de órdenes parciales serie-paralelas son cografías . [2] [4]
Se han aplicado órdenes parciales en serie en paralelo en la programación del taller de trabajo , [5] aprendizaje automático de la secuenciación de eventos en datos de series de tiempo , [6] secuenciación de transmisión de datos multimedia , [7] y maximización del rendimiento en la programación del flujo de datos . [8]
Los pedidos parciales serie-paralelos también se han denominado multitárboles; [4] sin embargo, ese nombre es ambiguo: los árboles múltiples también se refieren a órdenes parciales sin suborden de diamantes de cuatro elementos [9] ya otras estructuras formadas a partir de múltiples árboles.
Definición
Considere P y Q , dos conjuntos parcialmente ordenados. La composición en serie de P y Q , escrita P ; Q , [7] P * Q , [2] o P ⧀ Q , [1] es el conjunto parcialmente ordenado cuyos elementos son la unión de la desunión de los elementos de P y Q . En P ; Q , dos elementos x y y que ambos pertenecen a P o que tanto pertenecen a Q tienen el mismo relación de orden que lo hacen en P o Q , respectivamente. Sin embargo, para cada par x , y donde x pertenece a P e y pertenece a Q , existe una relación de orden adicional x ≤ y en la composición de la serie. La composición de series es una operación asociativa : se puede escribir P ; Q ; R como la composición en serie de tres órdenes, sin ambigüedad sobre cómo combinarlos por pares, porque ambos paréntesis ( P ; Q ); R y P ; ( Q ; R ) describen el mismo orden parcial. Sin embargo, no es una operación conmutativa , porque la conmutación de los papeles de P y Q producirá un orden parcial diferente que invierte las relaciones de orden de pares con un elemento en P y uno en Q . [1]
La composición paralela de P y Q , escrita P || Q , [7] P + Q , [2] o P ⊕ Q , [1] se define de manera similar, a partir de la unión disjunta de los elementos en P y los elementos en Q , con pares de elementos que pertenecen a P o ambos a Q teniendo el mismo orden que en P o Q respectivamente. En P || Q , un par x , y es incomparable siempre que x pertenece a P y y pertenece a Q . La composición paralela es tanto conmutativa como asociativa. [1]
La clase de órdenes parciales serie-paralelas es el conjunto de órdenes parciales que se pueden construir a partir de órdenes parciales de un solo elemento utilizando estas dos operaciones. De manera equivalente, es el conjunto más pequeño de órdenes parciales que incluye el orden parcial de un solo elemento y se cierra bajo las operaciones de composición en serie y en paralelo. [1] [2]
Un orden débil es el orden parcial paralelo en serie obtenido a partir de una secuencia de operaciones de composición en la que todas las composiciones paralelas se realizan primero, y luego los resultados de estas composiciones se combinan utilizando solo composiciones en serie. [2]
Caracterización de suborden prohibido
El orden parcial N con los cuatro elementos de un , b , c , y d y exactamente las tres relaciones de orden un ≤ b ≥ c ≤ d es un ejemplo de una valla o en zigzag poset; su diagrama de Hasse tiene la forma de la letra mayúscula "N". No es serie-paralelo, porque no hay forma de dividirlo en series o composición paralela de dos órdenes parciales más pequeños. Una orden parcial P se dice que es libre de N si no existe un conjunto de cuatro elementos en P tal que la restricción de P a los elementos es el orden-isomorfo a N . Los órdenes parciales serie-paralelos son exactamente los órdenes parciales finitos libres de N no vacíos. [1] [2] [3]
De esto se deduce inmediatamente (aunque también se puede probar 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 de la orden
La dimensión orden de un orden parcial P es el tamaño mínimo de un realizador de P , un conjunto de extensiones lineales de P con la propiedad de que, por cada dos elementos distintos x y y de P , x ≤ Y en P si y sólo si x tiene una posición anterior a y en cada extensión lineal del realizador. Los pedidos parciales serie-paralelos tienen una dimensión de pedido como máximo dos. Si P y Q tienen realizadores { L 1 , L 2 } y { L 3 , L 4 }, respectivamente, entonces { L 1 L 3 , L 2 L 4 } es un realizador de la composición en serie P ; Q , y { L 1 L 3 , L 4 L 2 } es un materializador de la composición paralela P || Q . [2] [3] Un orden parcial es serie-paralelo si y solo si tiene un realizador en el que una de las dos permutaciones es la identidad y la otra es una permutación separable .
Se sabe que un orden parcial P tiene dimensión orden dos si y sólo si existe un orden conjugado Q en los mismos elementos, con la propiedad de que cualquiera de los dos elementos distintos x y y son comparables en exactamente uno de estos dos órdenes. En el caso de órdenes parciales en serie paralela, un orden conjugado que es en sí mismo serie paralelo puede obtenerse realizando una secuencia de operaciones de composición en el mismo orden que las que definen P en los mismos elementos, pero realizando una composición en serie para cada composición paralela. en la descomposición de P y viceversa. Más fuertemente, aunque un orden parcial puede tener muchos conjugados diferentes, cada conjugado de un orden parcial paralelo en serie debe ser él mismo en serie paralela. [2]
Conexiones con la teoría de grafos
Cualquier orden parcial puede ser representado (generalmente en más de una manera) por un gráfico acíclico dirigido en la que hay un camino desde x a y cuando x y y son elementos del orden parcial con x ≤ y . Las gráficas que representan órdenes parciales serie-paralelas de esta manera se han denominado gráficas paralelas de series de vértices, y sus reducciones transitivas (las gráficas de las relaciones de cobertura del orden parcial) se denominan gráficas paralelas de series de vértices mínimos. [3] Los árboles dirigidos y los gráficos paralelos en serie (de dos terminales) son ejemplos de gráficos paralelos en serie de vértice mínimo; por lo tanto, se pueden usar órdenes parciales en serie paralela para representar relaciones de accesibilidad en árboles dirigidos y gráficos en serie paralela. [2] [3]
El gráfico de la comparabilidad de un orden parcial es el grafo no dirigido con un vértice de cada elemento y un borde no dirigida para cada par de elementos distintos x , y , ya sea con x ≤ y o y ≤ x . Es decir, se forma a partir de un gráfico paralelo de serie de vértices mínimos olvidando la orientación de cada borde. El gráfico de comparabilidad de un orden parcial serie-paralelo es un cógrafo : las operaciones de composición en serie y en paralelo del orden parcial dan lugar a operaciones sobre el gráfico de comparabilidad que forman la unión disjunta de dos subgrafos o que conectan dos subgrafos por todos los bordes posibles; estas dos operaciones son las operaciones básicas a partir de las cuales se definen las cografías. Por el contrario, cada cograph es el gráfico de comparabilidad de un orden parcial en serie-paralelo. Si un orden parcial tiene un cografo como gráfico de comparabilidad, entonces debe ser un orden parcial paralelo en serie, porque cualquier otro tipo de orden parcial tiene un suborden N que correspondería a una ruta inducida de cuatro vértices en su gráfico de comparabilidad, y tales caminos están prohibidos en las cografías. [2] [4]
Complejidad computacional
La caracterización de suborden prohibido de órdenes parciales serie-paralelo se puede utilizar como base para un algoritmo que prueba si una relación binaria dada es un orden parcial serie-paralelo, en una cantidad de tiempo lineal en el número de pares relacionados. [2] [3] Alternativamente, si un orden parcial se describe como el orden de accesibilidad de un grafo acíclico dirigido , es posible probar si es un orden parcial serie-paralelo y, de ser así, calcular su cierre transitivo, en tiempo proporcional al número de vértices y aristas en el cierre transitivo; Queda pendiente si el tiempo para reconocer las órdenes de accesibilidad en serie-paralelo puede mejorarse para que sea lineal en el tamaño del gráfico de entrada. [10]
Si un orden parcial serie-paralelo se representa como un árbol de expresión que describe las operaciones de composición en serie y en paralelo que lo formaron, entonces los elementos del orden parcial se pueden representar mediante las hojas del árbol de expresión. Se puede realizar una comparación entre dos elementos cualesquiera de forma algorítmica buscando el antepasado común más bajo de las dos hojas correspondientes; si ese antepasado es una composición paralela, los dos elementos son incomparables y, de lo contrario, el orden de los operandos de la composición en serie determina el orden de los elementos. De esta manera, un orden parcial serie-paralelo en n elementos se puede representar en el espacio O ( n ) con el tiempo O (1) para determinar cualquier valor de comparación. [2]
Es NP-completo a prueba, para los pedidos parciales dos dados serie-paralelo P y Q , si P contiene una restricción isomorfo a Q . [3]
Aunque el problema de contar el número de extensiones lineales de un orden parcial arbitrario es # P-completo , [11] puede resolverse en tiempo polinómico para órdenes parciales serie-paralelo. Específicamente, si L ( P ) denota el número de extensiones lineales de un orden parcial P , entonces L ( P ; Q ) = L ( P ) L ( Q ) y
por lo que el número de extensiones lineales se puede calcular usando un árbol de expresión con la misma forma que el árbol de descomposición del orden de serie-paralelo dado. [2]
Aplicaciones
Mannila y Meek (2000) utilizan órdenes parciales de series paralelas como modelo para las secuencias de eventos en datos de series de tiempo . Describen algoritmos de aprendizaje automático para inferir modelos de este tipo y demuestran su eficacia para inferir los requisitos previos del curso a partir de los datos de inscripción de los estudiantes y para modelar patrones de uso del navegador web. [6]
Amer y col. (1994) argumentan que los órdenes parciales en serie-paralelo son una buena opción para modelar los requisitos de secuenciación de transmisión de presentaciones multimedia . Utilizan la fórmula para calcular el número de extensiones lineales de un orden parcial serie-paralelo como base para analizar los algoritmos de transmisión multimedia. [7]
Choudhary y col. (1994) utilizan órdenes parciales de series paralelas para modelar las dependencias de tareas en un modelo de flujo de datos de procesamiento masivo de datos para visión por computadora . Muestran que, al utilizar órdenes en serie-paralelo para este problema, es posible construir de manera eficiente un programa optimizado que asigne diferentes tareas a diferentes procesadores de un sistema informático paralelo para optimizar el rendimiento del sistema. [8]
Los árboles PQ , estructuras de datos que se han aplicado en algoritmos para probar si un gráfico es plano y reconocer gráficos de intervalo, proporcionan una clase de ordenaciones algo más general que las órdenes parciales en serie-paralelas . [12] Un nodo P de un árbol PQ permite todos los posibles ordenamientos de sus hijos, como una composición paralela de órdenes parciales, mientras que un nodo Q requiere que los hijos ocurran en un orden lineal fijo, como una composición en serie de órdenes parciales. Sin embargo, a diferencia de los órdenes parciales serie-paralelos, los árboles PQ permiten invertir el orden lineal de cualquier nodo Q.
Ver también
- Circuitos en serie y en paralelo
Referencias
- ^ a b c d e f g h i Bechet, Denis; De Groote, Philippe; Retoré, Christian (1997), "Una axiomatización completa para la inclusión de órdenes parciales en serie-paralelos", Técnicas y aplicaciones de reescritura , Lecture Notes in Computer Science, 1232 , Springer-Verlag, pp. 230-240, doi : 10.1007 / 3 -540-62950-5_74.
- ^ a b c d e f g h i j k l m n o Möhring, Rolf H. (1989), "Clases computacionalmente manejables de conjuntos ordenados", en Rival, Ivan (ed.), Algorithms and Order: Proceedings of the NATO Advanced Study Institute on Algorithms and Order, Ottawa, Canadá, 31 de mayo 13 de junio de 1987 , NATO Science Series C, 255 , Springer-Verlag, págs. 105-194, ISBN 978-0-7923-0007-6.
- ^ a b c d e f g h Valdés, Jacobo; Tarjan, Robert E .; Lawler, Eugene L. (1982), "El reconocimiento de dígrafos paralelos en serie", SIAM Journal on Computing , 11 (2): 298–313, doi : 10.1137 / 0211023.
- ^ a b c Jung, HA (1978), "Sobre una clase de posets y los gráficos de comparabilidad correspondientes", Journal of Combinatorial Theory, Serie B , 24 (2): 125-133, doi : 10.1016 / 0095-8956 (78) 90013-8 , MR 0491356.
- ^ Lawler, Eugene L. (1978), "Secuenciación de trabajos para minimizar el tiempo total ponderado de finalización sujeto a restricciones de precedencia", Annals of Discrete Mathematics , 2 : 75–90, doi : 10.1016 / S0167-5060 (08) 70323-6 , ISBN 9780720410433, MR 0495156.
- ^ a b Mannila, Heikki ; Meek, Christopher (2000), "Órdenes parciales globales a partir de datos secuenciales", Proc. 6a Conferencia Internacional ACM SIGKDD sobre Descubrimiento de Conocimiento y Minería de Datos (KDD 2000) , págs. 161–168, doi : 10.1145 / 347090.347122 , S2CID 14735932.
- ^ a b c d Amer, Paul D .; Chassot, Christophe; Connolly, Thomas J .; Díaz, Michel; Conrad, Phillip (1994), "Servicio de transporte de pedido parcial para aplicaciones multimedia y otras", IEEE / ACM Transactions on Networking , 2 (5): 440–456, doi : 10.1109 / 90.336326 , S2CID 1974607.
- ^ a b Choudhary, AN; Narahari, B .; Nicol, DM; Simha, R. (1994), "Asignación de procesador óptima para una clase de cálculos en cadena " , Transacciones IEEE en sistemas paralelos y distribuidos , 5 (4): 439–445, doi : 10.1109 / 71.273050.
- ^ Furnas, George W .; Zacks, Jeff (1994), "Multiárboles: enriquecimiento y reutilización de la estructura jerárquica", Proc. Conferencia SIGCHI sobre factores humanos en sistemas informáticos (CHI '94) , págs. 330–336, doi : 10.1145 / 191666.191778 , S2CID 18710118.
- ^ Ma, Tze-Heng; Spinrad, Jeremy (1991), "Cierre transitivo para clases restringidas de órdenes parciales", Orden , 8 (2): 175–183, doi : 10.1007 / BF00383402 , S2CID 120935610.
- ^ Brightwell, Graham R .; Winkler, Peter (1991), "Contando extensiones lineales", Pedido , 8 (3): 225–242, doi : 10.1007 / BF00383444 , S2CID 119697949.
- ^ Booth, Kellogg S .; Lueker, George S. (1976), "Prueba de la propiedad de unidades consecutivas, gráficos de intervalo y planaridad de gráfico mediante algoritmos de árbol PQ", Journal of Computer and System Sciences , 13 (3): 335–379, doi : 10.1016 / S0022-0000 (76) 80045-1.