Komputerowo wspomagane badanie własności porządków częściowych

Speaker(s)

Marcin Peczarski

Affiliation

Uniwersytet Warszawski

Date

Oct. 20, 2005, 12:15 p.m.

Room

room 5870

Seminar

Seminar Algorithms

---

Własności, o których będę mówił, związane są z sortowaniem za pomocą porównań. Sortowanie porządku częściowego polega na znalezieniu jednego z jego rozszerzeń liniowych. Sortowanie możemy sobie wyobrazić jako grę. W każdym ruchu my wybieramy parę elementów do porównania, a przeciwnik wskazuje nam kolejność tych elementów. Wskazane porównanie dzieli możliwy zbiór rozszerzeń liniowych na dwa rozłączne podzbiory. Czyli gra polega na tym, że w każdym kroku my wybieramy podział zbioru rozszerzeń liniowych, a przeciwnik wskazuje ten podzbiór, który zawiera poszukiwane rozszerzenie liniowe. Gra kończy się, gdy pozostanie zbiór jednoelementowy. Omówię trzy problemy badawcze, którymi się zajmuję. 1. Hipoteza o złotym podziale Sformułuję hipotezę o złotym podziale porządku częściowego. Prawdziwość tej hipotezy implikuje prawdziwość bardzo znanej hipotezy 1/3--2/3 oraz ciasną górną granicę dla sortowania porządków częściowych. Przedstawię wybrane wyniki badań, w tym moje, nad dowodami powyższych hipotez. 2. Najgorzej zbalansowane porządki - drabiny z powyłamywanymi szczeblami Dość naturalną, choć nie zawsze optymalną, strategią sortowania porządku częściowego jest wskazywanie podziału zbioru jego rozszerzeń liniowych na możliwie równoliczne podzbiory. Złośliwy przeciwnik, starając się utrudnić nam zadanie, będzie wybierał podzbiór o większej mocy. Współczynnik zbalansowania porządku częściowego określa, jak bliski idealnemu (na równoliczne podzbiory) podział możemy wskazać. Zatem istotne jest pytanie, jak źle może być zbalansowany porządek częściowy. Brightwell [1999] wskazał znane mu najgorzej zbalansowane porządki częściowe. Przedstawię, znalezioną za pomocą komputera, nieskończoną klasę gorzej zbalansowanych porządków częściowych. 3. Sortowanie z minimalną liczbą porównań Interesuje nas minimalna liczba porównań, zawsze wystarczająca do posortowania n elementów. Wiadomo, że dla n < 12 i n = 20, 21 minimum to realizuje algorytm Forda-Johnsona. Algorytm ten jest również optymalny dla n = 12 [Wells 1969] oraz n = 13, 14, 15, 22 [Peczarski 2002,2004]. Najmniejszą liczbą elementów, dla której znamy algorytm lepszy od algorytmu Forda-Jonhnsona, jest n = 47 [Moenting 1981]. Przedstawię aktualny stan moich poszukiwań najmniejszego n, dla którego algorytm Forda-Johnsona nie jest optymalny.

---