Kamil KLOCH

(UJ)

Wymiar "on-line" porządków równoprzedziałowych

Tematyka on-line pojawia się w naturalny sposób w wielu zagadnieniach programistycznych takich jak szeregowanie zadań, dynamiczny przydział zasobów itd. Algorytmy on-line nie dysponują kompletem danych wejściowych w momencie rozpoczęcia działania i zmuszone są do podejmowania (często nieoptymalnych) decyzji w oparciu o dostarczane sukcesywnie dane częściowe. Okazuje się, że niektóre z wymienionych problemów on-line można rozwiązać badając wymiar częściowych porządków.

Prezentowane wyniki dotyczą wymiaru on-line porządków równoprzedziałowych. Porządek $\mathbf{P} = (P, \leqslant)$ nazywamy równoprzedziałowym jeśli jest on reprezentowalny przez przedziały równej długości, tzn. jeśli istnieje funkcja $I$ przyporządkowująca punktom porządku przedziały na osi rzeczywistej w taki sposób, że dla dowolnych $x, y \in P$ zachodzi $x < y$ wtw gdy przedział $I(x)$ leży całkowicie na lewo od przedziału $I(y)$.

Serdecznie zapraszamy wszystkich chętnych !