Algorytmy i struktury danych/Wstęp: elementarne techniki algorytmiczne i struktury danych

Podstawowe techniki i struktury

Nie ma formalnej teorii ani gotowych "recept" na konstrukcję efektywnych algorytmów. Opiszemy nieformalnie kilka podstawowych technik. Niektóre z nich są wstępnie omawiane na kursie metod programowania. Tutaj rozważymy je przede wszystkim w aspekcie złożoności obliczeniowej i analizy algorytmów.

Metoda dziel i zwyciężaj

Metoda ta polega na podzieleniu problemu na podproblemy, które rozwiązujemy niezależnie, a następnie "scalamy". Metoda działa dobrze gdy "scalanie" podproblemów jest łatwe, oraz podproblemy są "małe" w stosunku do $n$.

Jako przykład rozważmy jeszcze raz problem liczenia przywódcy tablicy (patrz Moduł 1. Wstęp: poprawność i złożoność algorytmów.). Stosując metodę dziel i zwyciężaj możemy otrzymać następujący algorytm:

Algorytm Rekurencyjny-Przywódca;

   if n=1 then przywódcą jest pojedyńczy element tablicy
   else
      podziel tablicę na dwie połowy;
      rekurencyjnie oblicz przywódcę lewej i prawej połowy tablicy;
      sprawdź w czasie O(n) który z nich jest przywódcą całości;

Jeśli algorytm ten wykonuje $T(n)$ kroków to:

$T(n)=2\cdot T(n/2)+O(n),T(1)=1$

Rozwiązaniem jest $T(n)=O(n\log n)$ (jak wiadomo z kursu matematyki dyskretnej).

Metoda zachłanna

Metoda ta dobrze działa w sytuacjach gdy maksymalizujemy lub minimalizujemy pewną wartość. Algorytm w każdej iteracji ma do wyboru pewną liczbę "lokalnych" akcji. W przypadku maksymalizacji wybiera tę, która lokalnie maksymalizuje wartość docelową, w przypadku minimalizacji wybiera akcję o minimalnej wartości. Przedyskutujemy tę metodę na następujących dwóch pzykładach.

Wieże na szachownicy

Przypuśćmy, że mamy szachownicę n na n, na polu (i,j)-tym leży x(i,j) monet. Chcemy umieŚciĆ n wież na szachownicy tak aby żadne dwie się nie biły. Zyskiem jest suma monet na wybranych pozycjach. Lokalna akcja to wybranie jednej dopuszczalnej pozycji (tzn. takiej, że wieża umieszczona na tej pozycji nie bije żadnej wieży umieszczonej dotychczas. Zysk akcji to liczba monet na pozycji. Algorytm zachłanny działa trywialnie: wybieramy pozycję z maksymalnym x(i,j). Łatwo widać, że ten algorytm niekoniecznie da optymalny zysk, ale da co najmniej połowę optymalnego zysku. Pozostawiamy to jako ćwiczenie. Bardziej formalnie można wyrazić ten problem w terminach skojarzeń w grafach. Najciekawszym przypadkiem jest sytuacja, gdy tablica x(i,j) jest zero-jedynkowa.

Przejdziemy teraz do wersji minimalizacyjnej.

Minimalne Sklejanie Par

Przypuśćmy, że mamy ciąg $n$ nieujemnych liczb $p_1,p_2,\dots ,p_n$. Lokalna akcja sklejania polega na pobraniu dwóch elementów z ciągu i zastąpieniu ich przez sumę ich wartości, kosztem akcji jest suma wartości "sklejanych" elemenów. Ciąg operacji sklejania kończy się gdy skleiliśmy wszystko do jednej wartości.

Interesuje nas policzenie minimalnego sumarycznego kosztu sklejania $n$ elementów w jeden element. Metoda zachłanna zawsze wybiera akcję o minimalnej wartości.

Algorytm Schemat-Zachłanny;
   while zbior mozliwych lokalnych akcji jest niepusty do
      wykonaj akcję o minimalnym koszcie;
   return (suma kosztow wykonanych akcji)

Można to zapisać bardziej formalnie:

Algorytm Optymalne-Sklejanie-Par;
   wynik := 0</math>;
   while mamy co najmniej dwa elementy do
      zastąp dwa minimalne elementy a,b przez a+b
      wynik := wynik + a+b;

Pozostawiamy jako ćwiczenie dowód tego, że algorytm ten daje minimalny ciąg sklejeń. Co będzie, jeśli zamiast liczyć minimalny koszt chcielibyśmy policzyć ciąg, który maksymalizuje sumaryczną sumę kosztów a+b? Pozostawiamy to jako ćwiczenie.

W naszym przykładzie mogliśmy sklejać elementy, które niekoniecznie są sąsiednie, kolejność elementów w ciągu nie odgrywała roli. Zastanówmy się co będzie gdy wprowadzimy do gry kolejność elementów. Załóżmy teraz, że możemy sklejajać tylko elementy sąsiednie. Tak zmodyfikowany problem nazwijmy problemem Minimalego Sklejania Sąsiadów. Możemy w poprzednim algorytmie zastąpić zwrot "dwa minimalne elementy" przez "dwa sąsiednie elementy o minimalnej sumie". Niespodziewanie, nasz algorytm nie zawsze liczy minimalną wartość, czyli nie jest poprawny. Kontrprzykładem jest ciąg

$(p1,p2,p3,p4)=(100,99,99,100)$

Programowanie dynamiczne

Rozwiązaniem danego problemu często jest kombinacja wartości podproblemów na które można problem zdekomponować. Natomiast nie bardzo od razu wiemy jaka dekompozycja jest optymalna, początkowo mamy nideterministyczny wybór wielu różnych dekompozycji. W sytuacji gdy nie wiemy jaka dekompozycja jest optymalna nie mozemy uruchomić rekursji ponieważ na każdym etapie mielibyśmy wiele wyborów i w sumie złożoność mogłaby być wykładnicza. Przykładem jest rekurencyjne liczenie liczb Fibonacciego.

W takich sytuacjach stosujemy nieformalną metodę zwaną programowaniem dynamicznym. Metoda ta, z grubsza biorąc, wygląda następująco. Jeśli problem możemy rozbić na podproblemy i liczba wszystkich potencjalnych podproblemów jest wielomianowa to zamiast korzystać z rekursji możemy obliczyć wartości wszystkich podproblemów stosując odpowiednią kolejność: od mniejszych podproblemów do większych. Wartości policzone dla podproblemów zapamiętujemy w tablicy. Mając policzone wartości podproblemów na które można rozbić dany problem wartośc tego problemu liczymy korzystając z wartości zapamiętanych w tablicy.

Najistotniejszym jest tutaj określenie zbioru potencjalnych podproblemów. Z reguły zbiór ten jest znacznie większy niż zbiór podproblemów będących częściami jednego optymalnego rozwiązania.

Spróbujmy skonstruować wielomianowy algorytm dla problemu minimalego sklejania sąsiadów korzystając z programowania dynamicznego.

Jeśli mamy dany ciąg

$p_1,p_2,\dots p_n$

to w tym przypadku podproblem można utożsamić z pewnym przedziałem

$[i..j]$

, niech

$wynik[i,j]$

będzie wartością problemu minimalnego sklejania sąsiadów dla ciągu

$(p_i,p_{i+1},\dots p_j)$

, oznaczmy ponadto

${\sigma }_{i,j}=\sum _{k=i}^j{p}_i$

Algorytm Optymalne-Sklejanie-Sąsiadów;
   for each i wynik[i,i]:=0;
   for i:=1 to n do
      for j:=i+1 to n do
         $wynik[i,j]:=\underset{i\le k<j}{\min }wynik[i,k]+wynik[k+1,j]+{\sigma }_{i,j}$
   return wynik[1,n];

Algorytm ma złożoność czasową $O(n^3)$ i jest to "typowa" złożoność algorytmów tego typu. Duża złożoność wynika stąd że liczymy wartości dla mnóstwa podproblemów, które mogą być zupełnie nieistotne ze względu na optymalne rozwiązanie.

Dygresja

Problem sklejania sąsiadów można rozwiązać inaczej, modyfikując w sposób nietrywialny algorytm Optymalne-Sklejanie-Par. W algorytmie tym instrukcję

zastąp dwa minimalne elementy a,b przez a+b

zamieńmy na:

zastąp dwa sąsiednie elementy a,b o minimalnej sumie przez a+b
przesuń a+b przed najbliższy na prawo (w ciągu) element c większy od a+b
ewentualnie na koniec ciągu, jeśli takiego c nie ma

Otrzymany algorytm, wersja algorytmu Garsia-Wachsa, liczy koszt minimalnego sklejania sąsiadów. Jest to przykład pozornie prostego algorytmu, dla którego odpowiedź na pytanie "dlaczego to działa" jest niezwykle skomplikowana i wykracza poza zakres tego kursu. Pozostawiamy jako ćwiczenie implementację tego algorytmu w czasie $O(n\log n)$ zakładając, że jest on poprawny. Jeśli liczby $p_i$ są liczbami naturalnymi z przedziału $[1..n]$ to istnieje nawet (bardzo trudna) implementacja w czasie liniowym.

Konstruowanie algorytmu metodą transformacji

Algorytm efektywny otrzymujemy często startując od prostszego, ale mało efektywnego algorytmu. Następnie staramy się, za pomocą prostych transformacji, przekształcić prosty algorytm w algorytm docelowy. Można to równieź nazwać stosowaniem metody kolejnych przybliżeń w aspekcie inżynierii algorytmicznej. Większość prostych algorytmów z Modułu 1 można potraktować jako produkty transformacji algorytmów naiwnych. Pozostawiamy jako ćwiczenie pokazanie tego. Pokażemy jedynie prosty przykład obliczania liczby inwersji

Liczba inwersji

Mamy dane dwie posortowane rosnąco tablice $A[1..n],B[1..n]$, mamy policzyć liczbę par $i,j$ takich, że $A[i]>B[j]$. Jeśli $A[1..n],B[1..n]$ są posortowanymi rosnąco tablicami, to liczbę inwersji między A, B oblicza następujący naiwny algorytm.

Algorytm Liczba-Inwersji-Naiwnie;
wynik := 0;
for i := 1 to n do
   j := 0;
   while (j<n and A[i]>B[j+1]) j := j+1;
      wynik := wynik + j;

Algorytm ma złożoność kwadratową. Załóżmy, że początkową wartością j jest zero. Wtedy, przyglądając się dokładniej algorytmowi, widzimy że instrukcję "j := 0;" można usunąć bez szkody dla poprawności i złożoność stanie się liniowa. Pozostawiamy to jako ćwiczenie. W ten sposób mamy prostą transformację kwadratowego algorytmu naiwnego na algorytm liniowy.

Przykład ten był dosyć ubogi i przedyskutujemy jezcze bardziej skomplikowany przykład. Podamy przykład transformacji pewnego prostego algorytmu B(n) w nietrywialny algorytm $A_n$, transformacja ta bazuje na własnościach B(n). Kluczem do efektywnej transformacji jest analiza własności algorytmu B(n).

Wykrywanie fałszywej monety

Mamy zbiór monet o numerach 1,2,..,N, wszystkie o tej samej wadze, wiemy że wsśród nich jest dokładnie jedna fałszywa moneta o innej wadze. Modelem algorytmu jest ciąg ważeń na wadze szalkowej. Niech waga(A) oznacza sume wag monet ze zbioru A. W jednym wazeniu mozemy wykonac operacje Porównaj(A,B), gdzie A,B sa rozlacznymi podzbiorami 1,2,..,N. Otrzymujemy jedną z trzech możliwych odpowiedzi:

• L - gdy waga(A)<waga(B)
• P - gdy waga(A)>waga(B)
• R - gdy wagi sa równe.

Algorytmem w naszym modelu jest ciąg operacji $o{p}_1,o{p}_2,...,o{p}_n$ taki, że z otrzymanego ciagu opdpowedzi można jednoznacznie wyznaczyc fałszywą monetę i określić czy jest ona cięższa czy lżejsza niż inne. Operację Porównaj(A,B) będziemy w skrócie zapisywać jako parę (A,B). Nasz algorytm można zatem zapisać jako ciąg par rozłacznych zbiorów, na przykład:

Algorytm dla n=2, N=3: ({1}, {2}), ({1}, {3})
Algorytm dla n=3, N=12: ({1,2,3,10},{4,5,6,11}), ({1,2,3,11},{7,8,9,10}), ({1,4,7,11},{2,5,8,12})

Naszym głównym zadaniem jest dla danego n znalezienie algorytmu ważeń, który maksymalizuje N.

Pokażemy najpierw jak rozwiązać zadanie dla $N=3^{n-1}$. Załóżmy, że liczba monet jest poteęgą trójki i monety są ponumerowane $0,1,2..3^n-1$ . Niech S(k,0), S(k,1) oznaczają zbiory numerów monet, które na k-tym bicie (licząc od końca) w reprezentacji trójkowej mają odpowiednio 0, 1. GdybyŚmy wiedzieli od razu czy fałszywa moneta jest lżejsza czy cięższa, to mamy następujący prosty algorytm, który działa podobnie jak wyszukiwanie ternarne:

$(S(1,0),S(1,1)),(S(2,0),S(2,1)),...(S(n,0),S(n,1))$

Ponieważ nie znamy statusu fałszywej monety dodajemy jedno porównanie i otrzymujemy algorytm B(n) który obsługuje za pomocą n ważeń $N=3^{n-1}$ monet (mamy teraz tylko n-1 bitów ternarnych). $B(n)=(S(1,0),S(1,2)),(S(1,0),S(1,1)),(S(2,0),S(2,1)),...(S(n-1,0),S(n-1,1))$

Dzięki dodaniu na początku jednego ważenia już po pierwszych dwóch ważeniach wiemy jaki jest status fałszywej monety (lżejsza, cięższa). Poza tym wynikiem pierwszych dwóch ważeń nie może być LR ani RL. Te dwie własności algorytmu B(n) są kluczem do transformacji tego algorytmu w algorytm $A_n$.

Jeśli mamy w naszym modelu algorytmy

$A1(n)=(A_1,B_1),(A_2,B_2)...(A_n,B_n)$ oraz $A2(n)=(C_1,D_1),(C_2,D_2)...(C_n,D_n)$,

to definiujemy algorytm

$A1\cup A2=(A1\cup C1,B1\cup D1),(A1\cup C2,B2\cup D2)...(An\cup Cn,Bn\cup Dn)$

Załóżmy, że mamy algorytm $A_{n-1}=(A_1,B_1),(A_2,B_2)...(A_{n-1},B_{n-1})$ na zbiorze rozmiaru $N_{n-1}$ to oznaczmy przez $przeskaluj(A_{n-1})$ algorytm, który działa na zmodyfikownych numerach monet, do każdego numeru dodajemy $3^{n-1}$. Ponadto dodajemy jedno porównanie:

$przeskaluj(A_{n-1})=(B1,A1),(A1,B1),(A2,B2),...(A_{n-1},B_{n-1})$

Docelowy algorytm definiujemy rekurencyjnie:

$A_n=przeskaluj(A_{n-1})\cup B(n)$

Poprawność takiej konstrukcji wynika stąd że na podstawie wyników 2 pierwszych ważeń wiemy, czy fałszywa moneta jest mniejsza od $3^{n-1}$. Jeśli tak to traktujemy odpowedzi jak w B(n),jesli nie to jak w A(n-1). Zostawiamy jako ćwiczenie opisanie sposobu takiego przełączania się.

W ten sposób mamy algorytym, który za pomocą n ważeń obsługuje $N_n$ monet, gdzie

$N_2=3;N_n=3^{n-1}+N_{n-1}$

Dla n = 2,3,4,5,6,7 mamy: $N_n=3,12,39,117,351,1053\dots$

Dygresja

Teoretycznie interesujące w tym jest to, że są to maksymalne wartości N. Pozostawiamy dowód jako ćwiczenie. Istnieją różne optymalne algorytmy dla tego problemu.

Znaczenie struktury danych

Podstawową strukturą danych jest struktura "obsługująca" operacje delete(S), insert(x,S), dla zadanego zbioru S. Operacja delete pobiera z S i zwraca jako wartość "pewien" element S. Nie interesuje nas na razie który element zostanie usunęty. Niedeterminizm pozwala nam użyć w takim wypadku jednej z kilku struktur danych które dyskutujemy poniżej. W niektórych zastosowaniach istotne jest który element jest pobierany i wtedy nazwy operacji insert, delete często zmieniamy na nazwy bardziej odpowiadające terminologicznie tym strukturom, ale będziemy też używć nazewnictwa delete, insert, o ile nie prowadzi to do niejednoznaczności. Elementarne struktury danych w których zdeterminowane są operacje insert, delete to:

• lista,
• stos,
• kolejka.

Są one punktem wyjścia do bardziej skomplikowanych struktur.

Prosty przypadek kolejki priorytetowej

Wariantem kolejki jest kolejka priorytetowa, jest to struktura danych, która "obsługuje" ciąg operacji insert, delete, gdzie operacja delete zawsze pobiera minimalny element. Operację tę nazwiemy w tym przypadku ExtractMin. Operacja delete jest tutaj w duzym stopniu zdeterminowana.

Zalozmy, ze ciag operacji insert mozna podzielic na dwa ciagi, nastepujace po sobie, w kazdym z nich w operacji insert wstawiamy elementy w porzadku rosnaczym. Wtedy kolejke priorytetowa mozna latwo zaimplementowac tak, by operacje insert, delete mozna bylo wykonac w czasei stalym.

Pokażemy na przykładzie algorytmu Optymalne-Sklejanie-Par zastosowanie tego typu kolejki priorytetowej. W algorytmie tym podstawowową operacją jest:

zastąp elementy

$a,b$

przez

$a+b$

.

Operacja ta jest równoważna operacjom:

$a=ExtracMin(S)$

;

$b=ExtractMin(S)$

;

$Insert(a+b,S)$

;

W dalszej części kursu pokażemy, jak każdą z operacji Insert, ExtractMin zaimplementować w czasie logarytmicznym. W szczególnym przypadku, rozważonym poniżej, można je zaimplementować w czasie stałym. Załóżmy, że początkowy zbiór $S$ jest posortowany i jego elementy są umieszczone na stosie $ST$ w kolejności rosnącej (od wierzchołka "w dół"). Załóżmy, że mamy dodatkowo zwykłą kolejkę $Q$ początkowo pustą. Wtedy ciąg operacji

$a=ExtracMin(S)$

;

$b=ExtractMin(S)$

;

$Insert(a+b,S)$

możemy wykonać w czasie stałym: element minimalny jest na wierzchołu $ST$ lub na początku kolejki $Q$, element $a+b$ wstawiamy na koniec $Q$. Zatem algorytm Optymalne-Sklejanie-Par mozemy zaimplementować w czasie liniowym gdy początkowy zbiór jest od razu posortowany. Widzimy na tym przykładzie w jaki sposób złożoność algorytm zależy od struktury danych związanych z algorytmem.

W następujących dwóch przykłądach możemy sobie pozwolić na niedeterministyczny wariant operacji delete.

Maksymalna bijekcja

Przypuśćmy, że mamy funkcję $f:\{1,2,\dots n\}\to \{1,2,\dots n\}$, zadaną tablicą $f[1..n]$ i chcemy znaleźć rozmiar maksymalnego podzbioru, na którym ta funkcja jest bijekcją.

Dwie funkcje

Jest to zadanie bardzo podobne, mamy dwie funkcje $f_1,f_2$ ze zbioru $[1..n]$ w siebie. Chcemy znaleźć taką permutację $\pi =(i_1,i_2,\dots i_n)$, żeby $\pi (f_k(i))>\pi (i),\mathrm{\forall }1\le i\le n,k=1,2$

Oba te przykłady możemy wyrazić w terminach teorii grafów. Zakładamy, że czytelnik dowiedział się na matematyce dyskretnej co to jest graf. Zbiorem wierzachołków jest tutaj zbiór $[1..n]$. W pierwszym przykładzie krawędzie są postaci $(i,f(i))$, w drugim postaci $(i,f_k(i)$, gdzie $k=1,2$. W pierwszym przykładzie chcemy znaleźć maksymalny podzbiór grafu, na którym podgraf indukowany jest zbiorem cykli. W drugim przypadku mamy szczególną instancję tzw. sortowania topologicznego grafu. WIerzchołek nazywamy roboczym, gdy nie wchodzi do niego żadna krawę"dź.

Niech $S$ będzie początkowo zbiorem wszystkich wierzchołków roboczych. Algorytmy dla obu powyższych problemów działają w podobny sposób. Pobieramy element $v\in S$, odpowiednio przetwarzamy $v$, i usuwamy $v$ z grafu. Wskutek usunięcia pewne nowe wierzchołki stają się roboczymi i wstawiamy je do S. Kontynuujemy,dopóki S jest niepusty.

W przypadku problemu maksymalnej bijekcji po prostu usuwamy v, w przypadku numeracji $\pi$, $\pi (v)$ staje się kolejnym numerem. Pomimo interpretacji grafowej nie musimy implementować żadnej reprezentacji grafu, wszystko się dzieje w wejściowych tablicach i w dodatkowej tablicy licznik[v], w której trzymamy dla każdego $v$ ile jest krawędzi aktualnie wchodzących do v. Konkretną implementację pozostawiamy jako ćwiczenie. Zbiór S jest tutaj zbiorem wierzchołków roboczych, które są w pewnym sensie akcjami do wykonania. Do S wkładamy akcje które mamy wykonać, kolejność nie jest istotna. S może być listĄ, stosem lub kolejką.

Pokażemy jeszcze jeden ciekawy problem dla którego właśnie lista jest świetną strukturą danych.

Panorama Warszawy

Rozważmy inny przykład algorytmu, ktorego złożoność istotnie zależy od (bardzo prostej) struktury danych. Przypuśćmy, że mamy na wejściu $n$ trójek postaci $[p,q,s]$, gdzie $p,q\in \{1,2,\dots ,n\},s\ge 0$. Każdej trójce odpowiada funkcja $f_{p,q,s}$ taka, że:

$f_{p,q,s}(i)=s$ gdy $p\le i\le q$, oraz $f_{p,q,s}(i)=0$ w przeciwnym przypadku.

Naszym zadaniem jest dla każdego $1\le i\le n$ obliczyć wartość $F(i)$, będącą maksimum z danych funkcji $f_{p,q,s}$ dla argumentu $i$. Można podać następującą interpretację. Każda funkcja $f_{p,q,s}$ opisuje kształt wieżowca w Warszawie patrząc z prawej strony Wisły. Wtedy funkcja $F$ opisuje panoramę centrum Warszawy.

Załóżmy, że trójki $(p,q,s)$ są posortowane ze względu na $s$. Wtedy rozważamy kolejno funkcje $f_{p,q,s}$, w kolejności rosnącego $s$, i nadajemy za każdym razem końcowe wartości dla pozycji z przedziału $[p,q]$ dla których jeszcze wartości nie są policzone. Taki algorytm miałby złożoność kwadratową.

Jeśli użyjemy listy dwukierunkowej i za każdym razem usuniemy zbiór pozycji dla których wartości końcowe są już policzone to otrzymamy algorytm działający w czasie liniowym. Dokładny zapis algorytmu pozostawiamy czytelnikowi jako ćwiczenie.

Wariantem kolejki jest kolejka priorytetowa, jest to struktura danych, która "obsługuje" ciąg operacji insert, delete, gdzie operacja delete zawsze pobiera minimalny element. Operację tę nazwiemy w tym przypadku ExtractMin.

Pokażemy na przykładzie algorytmu Optymalne-Sklejanie-Par zastosowanie kolejki priorytetowej. W algorytmie tym podstawowową operacją jest:

zastąp elementy

$a,b$

przez

$a+b$

.

Operacja ta jest równoważna operacjom:

$a=ExtracMin(S)$

;

$b=ExtractMin(S)$

;

$Insert(a+b,S)$

;

W dalszej części kursu pokażemy, jak każdą z operacji Insert, ExtractMin zaimplemnetować w czasie logarytmicznym. W szczególnym przypadku, rozważonym poniżej, można je zaimplementować w czasie stałym. Załóżmy, że początkowy zbiór $S$ jest posortowany i jego elementy są umieszczone na stosie $ST$ w kolejności rosnącej (od wierzchołka "w dół"). Załóżmy, że mamy dodatkowo zwykłą kolejkę $Q$ początkowo pustą. Wtedy ciąg operacji

$a=ExtracMin(S)$

;

$b=ExtractMin(S)$

;

$Insert(a+b,S)$

możemy wykonać w czasie stałym: element minimalny jest na wierzchołu $ST$ lub na początku kolejki $Q$, element $a+b$ wstawiamy na koniec $Q$. Zatem algorytm Optymalne-Sklejanie-Par mozemy zaimplementować w czasie liniowym gdy początkowy zbiór jest od razu posortowany. Widzimy na tym przykładzie w jaki sposób złożoność algorytm zależy od struktury danych związanych z algorytmem.

Sortowanie kolejkowe i stosowe

Działanie stosu i kolejki świetnie ilustrują różne warianty problemu sortowania z użyciem stosów i kolejek. Niech $\pi$ będzie permutacją liczb $\{1,2,\dots n\}$. Możemy posortować $\pi$ stosując niedeterministyczny algorytm:

while na wyjściu nie są wszystkie elementy do
   wstaw kolejny element $\pi (i)$ do jednej z kolejek
   lub wypisz $\pi (i)$ na wyjściu \\
   lub pobierz i wypisz na wyjściu pierwszy element jednej z kolejek

Zdefiniujmy liczbę kolejkową permutacji $\pi$ jako minimalną liczbę kolejek potrzebnych do posortowania permutacji $\pi$. Na przykład dla $\pi =(1,2,3)$ liczba ta wynosi 0, a dla $\pi =(3,2,1)$ wynosi 2.

Jak policzyć liczbę kolejkową w czasie liniowym ? Porównajmy ten problem z problemem maksymalnego malejącego podciągu. Pozostawiamy tojako ćwiczenie. Podobnie definiujemy liczbę stosową, w tym wypadku w powyższym nieformalnym algorytmie zastępujemy kolejkę przez stos. Można również zdefiniować liczbę kolejkowo-stosową, pytając o minimalną liczbę stosów i kolejek, które razem posortują daną permutację. Jest to trudne pytanie.

W poprzedniej wersji sortowania każdy element może trafić tylko do jednej kolejki. Rozważmy teraz wersję w której mamy $k$ kolejek $Q_1,Q_2,Q_3,\dots Q_k$ i element może trafiać do kolejek o coraz mniejszych numerach. Pojedyńcza operacja polega na wstawieniu kolejnego elementu z $\pi$ do jednej z kolejek, wypisaniu bezpośrednio na wyjście o ile jest on pierwszym niepobranym elementem w $\pi$ lub pierwszym elementem pewnej kolejki, lub przełożeniu pierwszego elementu pewnej kolejki $Q_i$ do kolejki $Q_j$, dla $j<i$. Można pokazać, że wystarczy logarytmiczna liczba kolejek do posortowania każdej permutacji.

Podobny fakt zachodzi, gdy kolejki zastąpimy stosami. Pozostawiamy ten problem (zrówno dla kolejek jak i stosów) jako ćwiczenie.

Scalanie kolejkowe

Załóżmy, że każdy elemnet ciągu $\pi$ jest początkowo listą jednolelementową, oznaczmy zbiór tych list przez $S$. Załóżmy też, że umiemy scalić dwie posortowane listy w czasie równym sumie ich długości za pomocą operacji merge (patrz następne wykłady).

Algorytm Scalanie-Kolejkowe
while |S|>1 do
   lista1 = delete(S); lista2 = delete(S);
   insert(merge(lista1,lista2),S) 

Pozostawiamy jako ćwiczenie pokazanie tego, że algorytm ten działa w czasie $O(n\log n)$, a jeśli $S$ stanie się stosem to działa w czasie kwadratowym. Widać na tym przykładzie przewagę kolejki nad listą. Załóżmy, że mamy posortować tablicę $A[0,1,\dots ,n-1]$ i $n$ jest potęgą dwójki. Wtedy następujący algorytm wykonuje ten sam ciąg scaleń co algorytm Scalanie-Kolejkowe. Dowód tego pozostawiamy jako ćwiczenie.

Algorytm Scalanie-Kolejkowe bez kolejki
m = 1;
while m < n do
   for i=0 to n/(2m) do
      merge(A[i..i+m-1], A[i+m..i+2m-1]);
   m = 2m;