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.