Algorytmy i struktury danych/Wstęp: elementarne techniki algorytmiczne i struktury danych: Różnice pomiędzy wersjami

Z Studia Informatyczne
Przejdź do nawigacjiPrzejdź do wyszukiwania
m
m (Zastępowanie tekstu - "\ =\" na "=")
 
(Nie pokazano 94 wersji utworzonych przez 6 użytkowników)
Linia 1: Linia 1:
Nie ma formalnej teorii ani gotowych "recept" na konstrukcję efektywnych algorytmów. Opiszemy
+
W tym drugim, wstępnym module opiszemy
nieformalnie kilka podstawowych technik.
+
nieformalnie kilka podstawowych technik algorytmicznych i elementarnych struktur danych.
Niektóre z nich są  wstępnie omawiane na kursie metod programowania. Tutaj rozważymy je przede  
+
Niektóre z nich były wstępnie omawiane na kursie ''Metody programowania''. Teraz rozważymy je przede  
wszystkim w aspekcie złożoności obliczeniowej i analizy algorytmów.
+
wszystkim w aspekcie złożoności obliczeniowej i analizy algorytmów.
  
  
Linia 10: Linia 10:
 
Metoda ta polega na podzieleniu problemu na podproblemy, które rozwiązujemy niezależnie, a następnie  
 
Metoda ta polega na podzieleniu problemu na podproblemy, które rozwiązujemy niezależnie, a następnie  
 
"scalamy". Metoda działa
 
"scalamy". Metoda działa
dobrze, gdy "scalanie" podproblemów jest łatwe oraz podproblemy są "małe" w stosunku do rozmiaru problemu
+
dobrze, gdy "scalanie" podproblemów jest łatwe, oraz same podproblemy są "małe" w stosunku do rozmiaru problemu
 
<math>n</math>.
 
<math>n</math>.
  
Jako przykład rozważmy jeszcze raz problem wyznaczenia przywódcy tablicy (patrz [[ASD_Moduł_1|Moduł 1.
+
Jako przykład rozważmy jeszcze raz problem wyznaczenia przywódcy tablicy (patrz [[ASD_Moduł_1|Wstęp: poprawność i złożoność algorytmów.]]).  
Wstęp: poprawność i złożoność algorytmów.]]).  
 
 
Stosując metodę ''dziel i zwyciężaj'', możemy otrzymać  następujący algorytm:
 
Stosując metodę ''dziel i zwyciężaj'', możemy otrzymać  następujący algorytm:
 
{{algorytm|Rekurencyjny Przywódca|algorytm_rekurencyjny_przywodca|
 
{{algorytm|Rekurencyjny Przywódca|algorytm_rekurencyjny_przywodca|
    '''if''' <math>n=1</math> then przywódcą jest pojedyńczy element tablicy
+
'''if''' <math>n=1</math> '''then''' przywódcą jest pojedynczy element tablicy
    '''else'''
+
'''else'''  
      podziel tablicę na dwie połowy;
+
3      podziel tablicę na dwie połowy;
      rekurencyjnie oblicz przywódcę lewej i prawej połowy tablicy;
+
4      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;
+
5      sprawdź w czasie <math>O(n)</math>, który z nich jest przywódcą całości
 
}}
 
}}
Jeśli algorytm ten wykonuje  <math>T(n)</math> kroków to:
+
Jeśli algorytm ten wykonuje  <math>T(n)</math> kroków, to:
  
<center><math>T(n)\  =\ 2\cdot T(n/2)+O(n),\ T(1)=1</math></center>
+
<center><math>T(n)\  =\ T(\lfloor \frac{n}{2}\rfloor)+T(\lceil \frac{n}{2}\rceil)+O(n),\ T(1)=1</math></center>
  
 
Rozwiązaniem jest <math> T(n)=O(n \log n)</math>  (jak wiadomo z kursu matematyki dyskretnej).
 
Rozwiązaniem jest <math> T(n)=O(n \log n)</math>  (jak wiadomo z kursu matematyki dyskretnej).
Linia 33: Linia 32:
 
w każdej iteracji ma do wyboru pewną  
 
w każdej iteracji ma do wyboru pewną  
 
liczbę "lokalnych" akcji. W przypadku maksymalizacji wybiera tę, która lokalnie maksymalizuje wartość  
 
liczbę "lokalnych" akcji. W przypadku maksymalizacji wybiera tę, która lokalnie maksymalizuje wartość  
docelową, w przypadku minimalizacji  
+
docelową. W przypadku minimalizacji  
 
wybiera akcję o minimalnej wartości. Przedyskutujemy tę metodę na następujących dwóch przykładach.
 
wybiera akcję o minimalnej wartości. Przedyskutujemy tę metodę na następujących dwóch przykładach.
  
 
===Wieże na szachownicy===
 
===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  
+
Przypuśćmy, że mamy szachownicę <math>n</math> na <math>n</math>, na polu <math>(i,j)</math>-tym leży <math>x(i,j)</math> monet. Chcemy umieścić <math>n</math> wież na  
 
szachownicy tak, aby żadne dwie się nie atakowały.
 
szachownicy tak, aby żadne dwie się nie atakowały.
Zyskiem jest suma monet na wybranych pozycjach. Lokalna akcja to wybranie jednej dopuszczalnej pozycji  
+
Zyskiem jest suma monet na wybranych pozycjach. Lokalna akcja to wybranie jednej dopuszczalnej pozycji. Zysk akcji to liczba monet na pozycji.  
(tzn. takiej, że wieża umieszczona
 
na tej pozycji nie atakuje żadnej wieży umieszczonej dotychczas. Zysk akcji to liczba monet na pozycji.  
 
 
Algorytm zachłanny działa trywialnie: wybieramy
 
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  
+
pozycję z maksymalnym <math>x(i,j)</math>. Można łatwo zobaczyć, że ten algorytm niekoniecznie da optymalny zysk - da jednak co  
 
najmniej połowę  
 
najmniej połowę  
 
optymalnego zysku. Pozostawiamy to jako ćwiczenie. Bardziej formalnie można wyrazić ten problem w  
 
optymalnego zysku. Pozostawiamy to jako ćwiczenie. Bardziej formalnie można wyrazić ten problem w  
 
terminach skojarzeń w grafach.  
 
terminach skojarzeń w grafach.  
Najciekawszym przypadkiem jest sytuacja, gdy tablica x(i,j) jest zero-jedynkowa.
+
Najciekawszym przypadkiem jest sytuacja, gdy tablica <math>x(i,j)</math> jest zerojedynkowa.
 
 
Przejdziemy teraz do wersji minimalizacyjnej.
 
  
 
===Minimalne Sklejanie Par===
 
===Minimalne Sklejanie Par===
 
Przypuśćmy, że mamy ciąg <math>n</math> nieujemnych liczb <math>p_1,p_2,\ldots,p_n</math>.  
 
Przypuśćmy, że mamy ciąg <math>n</math> nieujemnych liczb <math>p_1,p_2,\ldots,p_n</math>.  
 
Lokalna akcja sklejania polega  
 
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  
+
na pobraniu dwóch elementów z ciągu i zastąpieniu ich przez sumę ich wartości.
wartości "sklejanych" elementów.  
+
Kosztem akcji jest suma wartości "sklejanych" elementów.  
 
Ciąg operacji sklejania kończy się, gdy skleiliśmy wszystko do jednej wartości.
 
Ciąg operacji sklejania kończy się, gdy skleiliśmy wszystko do jednej wartości.
  
Linia 62: Linia 57:
 
Metoda zachłanna zawsze wybiera akcję o minimalnej wartości.  
 
Metoda zachłanna zawsze wybiera akcję o minimalnej wartości.  
 
{{algorytm|Schemat-Zachłanny|algorytm_schemat_zachlanny|
 
{{algorytm|Schemat-Zachłanny|algorytm_schemat_zachlanny|
    '''while''' zbiór możliwych lokalnych akcji jest niepusty '''do'''
+
'''while''' zbiór możliwych lokalnych akcji jest niepusty '''do'''
      wykonaj akcję o minimalnym koszcie;
+
2      wykonaj akcję o minimalnym koszcie;
    '''return''' (suma kosztów wykonanych akcji)
+
'''return''' suma kosztów wykonanych akcji;
 
}}
 
}}
  
Linia 72: Linia 67:
 
Można to zapisać bardziej formalnie:
 
Można to zapisać bardziej formalnie:
 
{{algorytm|Optymalne-Sklejanie-Par|algorytm_optymalne_sklejanie_par|
 
{{algorytm|Optymalne-Sklejanie-Par|algorytm_optymalne_sklejanie_par|
    <math>wynik := 0</math>;
+
<math>wynik := 0</math>;
    '''while''' mamy co najmniej dwa elementy '''do'''
+
'''while''' mamy co najmniej dwa elementy '''do'''
      zastąp dwa minimalne elementy a,b przez a+b
+
3      zastąp dwa najmniejsze elementy <math>a,b</math> przez <math>a+b</math>
      <math>wynik := wynik + a+b;</math>
+
4      <math>wynik := wynik + a+b;</math>
 
}}
 
}}
Pozostawiamy jako ćwiczenie dowód tego, że algorytm ten daje minimalny  ciąg sklejeń. Co będzie, jeśli  
+
Pozostawiamy jako ćwiczenie dowód tego, że algorytm ten wyznacza ciąg sklejeń o najmniejszym koszcie. Co będzie, jeśli  
 
zamiast  
 
zamiast  
 
obliczać minimalny koszt chcielibyśmy wyznaczyć ciąg, który maksymalizuje sumaryczny koszt?  
 
obliczać minimalny koszt chcielibyśmy wyznaczyć ciąg, który maksymalizuje sumaryczny koszt?  
 
Pozostawiamy to jako ćwiczenie.  
 
Pozostawiamy to jako ćwiczenie.  
 +
Algorytm ten jest "szkieletem" efektywnego konstruowania tzw. "drzewa Huffmana".
  
  
 
W naszym przykładzie mogliśmy sklejać elementy, które niekoniecznie są sąsiednie, kolejność elementów  
 
W naszym przykładzie mogliśmy sklejać elementy, które niekoniecznie są sąsiednie, kolejność elementów  
 
w ciągu nie odgrywała roli.
 
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  
+
Zastanówmy się, co będzie, gdy wprowadzimy do gry kolejność elementów. Załóżmy teraz, że możemy  
 
sklejać tylko elementy sąsiednie.  
 
sklejać tylko elementy sąsiednie.  
 
Tak zmodyfikowany problem nazwijmy problemem '''Minimalnego Sklejania  Sąsiadów'''. Możemy w  
 
Tak zmodyfikowany problem nazwijmy problemem '''Minimalnego Sklejania  Sąsiadów'''. Możemy w  
 
poprzednim algorytmie zastąpić zwrot  
 
poprzednim algorytmie zastąpić zwrot  
"dwa minimalne elementy" przez "dwa sąsiednie elementy o minimalnej sumie".  
+
"dwa najmniejsze elementy" przez "dwa sąsiednie elementy o minimalnej sumie".  
 
<br>
 
<br>
  
Linia 96: Linia 92:
 
Kontrprzykładem jest ciąg
 
Kontrprzykładem jest ciąg
  
<center> <math>  (p1,p2,p3,p4) = (100,99,99,100)</math></center>
+
<center> <math>  (p1,p2,p3,p4) = (100,99,99,100).</math></center>
  
 
==Programowanie dynamiczne==
 
==Programowanie dynamiczne==
  
Rozwiązaniem danego problemu często jest kombinacja wartości podproblemów na które można problem  
+
Rozwiązaniem danego problemu często jest kombinacja rozwiązań podproblemów, na które można problem  
rozłożyć. Natomiast nie bardzo od
+
rozłożyć. Natomiast nie od
 
razu wiemy, jaka dekompozycja jest optymalna; początkowo mamy niedeterministyczny wybór wielu  
 
razu wiemy, jaka dekompozycja jest optymalna; początkowo mamy niedeterministyczny wybór wielu  
 
różnych dekompozycji. W sytuacji, gdy nie  
 
różnych dekompozycji. W sytuacji, gdy nie  
 
wiemy, jaka dekompozycja jest optymalna, nie możemy uruchomić rekursji, ponieważ na każdym etapie  
 
wiemy, jaka dekompozycja jest optymalna, nie możemy uruchomić rekursji, ponieważ na każdym etapie  
 
mielibyśmy wiele wyborów i w sumie  
 
mielibyśmy wiele wyborów i w sumie  
złożoność mogłaby być wykładnicza. Przykładem jest rekurencyjne liczenie liczb Fibonacciego.
+
złożoność mogłaby być wykładnicza.  
  
W takich sytuacjach stosujemy nieformalną metodę zwaną  '''programowaniem dynamicznym'''. Metoda ta, z  
+
W takich sytuacjach stosujemy metodę zwaną  '''programowaniem dynamicznym'''. Metoda ta, z  
grubsza biorąc, wygląda następująco.
+
grubsza biorąc, wygląda następująco:
 
Jeśli problem możemy rozbić na podproblemy i liczba wszystkich potencjalnych podproblemów jest  
 
Jeśli problem możemy rozbić na podproblemy i liczba wszystkich potencjalnych podproblemów jest  
wielomianowa, to zamiast korzystać z rekursji,
+
wielomianowa, to zamiast korzystać z rekursji
możemy obliczyć wartości wszystkich podproblemów stosując odpowiednią kolejność: od mniejszych  
+
możemy obliczyć wartości wszystkich podproblemów stosując odpowiednią kolejność: od "mniejszych"
podproblemów do większych. Wartości obliczone  
+
podproblemów do "większych". Rozmiary problemów muszą być odpowiednio zdefiniowane, nie powinno być zależności cyklicznej.
 +
 
 +
Wartości obliczone  
 
dla podproblemów zapamiętujemy w tablicy. Mając obliczone wartości podproblemów, na które można  
 
dla podproblemów zapamiętujemy w tablicy. Mając obliczone wartości podproblemów, na które można  
rozbić dany problem, wartość tego problemu obliczamy korzystając z wartości zapamiętanych w tablicy.
+
rozbić dany problem, wartość problemu obliczamy korzystając z wartości zapamiętanych w tablicy.
  
 
Najistotniejsze jest tutaj określenie zbioru potencjalnych podproblemów. Z reguły zbiór ten jest znacznie  
 
Najistotniejsze jest tutaj określenie zbioru potencjalnych podproblemów. Z reguły zbiór ten jest znacznie  
Linia 127: Linia 125:
 
Niech <math>wynik[i,j]</math> będzie wartością problemu minimalnego sklejania sąsiadów dla ciągu  
 
Niech <math>wynik[i,j]</math> będzie wartością problemu minimalnego sklejania sąsiadów dla ciągu  
 
<math>(p_i,p_{i+1}, \ldots p_j)</math>;
 
<math>(p_i,p_{i+1}, \ldots p_j)</math>;
oznaczmy ponadto <center> <math>\sigma_{i,j}\ =\ \sum_{k=i}^j\ p_k </math></center>
+
oznaczmy ponadto <center> <math>\sigma_{i,j}= \sum_{k=i}^j\ p_k </math></center>
 
{{algorytm|Optymalne-Sklejanie-Sąsiadow|algorytm_optymalne_sklejanie_sasiadow|
 
{{algorytm|Optymalne-Sklejanie-Sąsiadow|algorytm_optymalne_sklejanie_sasiadow|
    '''for each''' i <math>wynik[i,i]:=0;</math>
+
'''for''' <math>i:=1</math> '''to''' <math>n</math> '''do''' <math>wynik[i,i]:=0;</math>
    '''for''' <math>i:=1</math> to n '''do'''
+
'''for''' <math>j:=2</math> '''to''' <math>n</math> '''do'''
      '''for''' <math>j:=i+1</math> to n '''do'''
+
3      '''for''' <math>i:=j-1</math> '''downto''' <math>1</math> '''do'''
          <math>wynik[i,j] := \min_{i \le k <j}\ wynik[i,k]+wynik[k+1,j]+\sigma_{i,j}</math>
+
4        <math>wynik[i,j] := \min_{i \le k <j}\ (wynik[i,k]+wynik[k+1,j]+\sigma_{i,j})</math><br>
    '''return''' <math>wynik[1,n];</math>
+
'''return''' <math>wynik[1,n]</math>;
 
}}
 
}}
 +
W algorytmie zasadniczą instrukcję <br>
 +
<center> <math>wynik[i,j] := \min_{i \le k <j}\ (wynik[i,k]+wynik[k+1,j]+\sigma_{i,j})</math></center><br>
 +
można wykonywać w dowolnym ''przyzwoitym'' porządku ze względu na (i,j) (na przykład po
 +
przekątnych, zaczynając od ''głównej '' przekątnej). Przyzwoitość polega na tym, że jest już
 +
ostatecznie policzone to, z czego w danym momencie korzystamy.<br>
 +
 
Algorytm ma złożoność czasową <math>O(n^3)</math> i jest to "typowa" złożoność algorytmów tego  
 
Algorytm ma złożoność czasową <math>O(n^3)</math> i jest to "typowa" złożoność algorytmów tego  
 
typu. Duża złożoność wynika stąd,  
 
typu. Duża złożoność wynika stąd,  
Linia 145: Linia 149:
 
W algorytmie tym instrukcję  
 
W algorytmie tym instrukcję  
  
''zastąp dwa minimalne elementy a,b przez a+b''<br>
+
''zastąp dwa najmniejsze elementy <math>a,b</math> przez <math>a+b</math>''<br>
  
 
zamieńmy na:
 
zamieńmy na:
  
''zastąp dwa sąsiednie elementy a,b o minimalnej sumie przez a+b''<br>
+
''zastąp dwa sąsiednie elementy <math>a,b</math> o minimalnej sumie przez <math>a+b</math>''<br>
''przesuń a+b przed najbliższy na prawo (w ciągu) element c większy od a+b''<br>
+
''przesuń <math>a+b</math> przed najbliższy na prawo (w ciągu) element <math>c</math> większy od <math>a+b</math>''<br>
''ewentualnie na koniec ciągu, jeśli takiego c nie ma''
+
''(na koniec ciągu, jeśli takiego <math>c</math> nie ma)''
  
Otrzymany algorytm, wersja algorytmu Garsia-Wachsa, liczy koszt minimalnego sklejania sąsiadów. Jest to  
+
Otrzymany algorytm (wersja algorytmu Garsia-Wachsa) liczy koszt minimalnego sklejania sąsiadów. Jest to  
 
przykład pozornie prostego algorytmu,  
 
przykład pozornie prostego algorytmu,  
dla którego odpowiedź na pytanie "dlaczego to działa" jest niezwykle skomplikowana i wykracza poza  
+
dla którego odpowiedź na pytanie, "dlaczego to działa" jest niezwykle skomplikowana i wykracza poza  
 
zakres tego kursu. Pozostawiamy jako  
 
zakres tego kursu. Pozostawiamy jako  
 
ćwiczenie implementację tego algorytmu w czasie <math>O(n \log n)</math>, przy założeniu, że jest on  
 
ćwiczenie implementację tego algorytmu w czasie <math>O(n \log n)</math>, przy założeniu, że jest on  
 
poprawny. Jeśli liczby <math>p_i</math> są  
 
poprawny. Jeśli liczby <math>p_i</math> są  
liczbami naturalnymi z przedziału <math>[1..n]</math> to istnieje nawet (bardzo trudna) implementacja w  
+
liczbami naturalnymi z przedziału <math>[1..n]</math>, to istnieje nawet (bardzo trudna) implementacja w  
 
czasie liniowym.
 
czasie liniowym.
  
Linia 165: Linia 169:
  
 
Algorytm efektywny otrzymujemy często startując od prostszego, ale mało efektywnego algorytmu.  
 
Algorytm efektywny otrzymujemy często startując od prostszego, ale mało efektywnego algorytmu.  
 +
 
Następnie staramy się za pomocą prostych  
 
Następnie staramy się za pomocą prostych  
transformacji przekształcić prosty algorytm w algorytm docelowy. Można to również nazwać stosowaniem  
+
transformacji przekształcić prosty algorytm w algorytm docelowy.  
 +
 
 +
Można to również nazwać stosowaniem  
 
metody kolejnych przybliżeń w  
 
metody kolejnych przybliżeń w  
aspekcie inżynierii algorytmicznej. Większość prostych algorytmów z [[ASD_Moduł_1|Modułu 1]] można  
+
aspekcie inżynierii algorytmicznej.
 +
Czasami można to (w przenośni algorytmicznej) nazwać ''chirurgią algorytmiczną'', ponieważ możemy amputować
 +
''chore'' lub ''zbędne''
 +
tkanki algorytmu, aby go usprawnić.
 +
Czasami, zamiast amputacji,  potrzebne jest ''wzmocnienie'' algorytmu poprzez
 +
''doszycie'' pewnej dodatkowej
 +
części (np. 
 +
funkcji ''buty siedmiomilowe'', funkcji ''większy-biceps'' lub ''czaso-przyspieszacz'').
 +
Oczywiście w chirurgii zdarzają się pomyłki i można doszyć to, czego nie należałoby doszywać, np.
 +
funkcję ''czaso-wstrzymywacz''.
 +
Słaba kondycja algorytmu
 +
może mieć przyczyny niezwiązane z chirurgią, np. ''nadwaga
 +
algorytmiczna'',  lub tzw. ''połknięcie paradygmatu''.
 +
Istotna jest również prostota algorytmu. Stosując zbyt wiele transformacji i udziwnień,
 +
możemy przerobić algorytm, który jest naiwny, ale zrozumiały, w genialny algorytm, który jest zdziwaczały i niezrozumiały. Algorytm, który stracił zdrowy rozsądek, może być świetnym wynikiem teoretycznym,  może być nawet przedmiotem
 +
podziwu w sensie artystycznym, ale jego praktyczne stosowanie może być niewielkie (nie dotyczy to dydaktyki).
 +
 
 +
 
 +
Większość prostych algorytmów z wykładu [[ASD_Moduł_1|Wstęp: poprawność i złożoność algorytmów]] można  
 
potraktować jako produkty  
 
potraktować jako produkty  
transformacji algorytmów naiwnych. Pozostawiamy jako ćwiczenie pokazanie tego. Pokażemy jedynie
+
transformacji algorytmów naiwnych. Pokazanie tego pozostawiamy jako ćwiczenie. Pokażemy teraz
prosty przykład obliczania liczby inwersji
+
dwa proste przykłady transformacji.
 
 
  
 
===Liczba inwersji===
 
===Liczba inwersji===
Mając dane dwie posortowane rosnąco tablice <math>A[1..n], B[1..n]</math>, należy wyznaczyć liczbę par  
+
Mając dane dwie posortowane rosnąco tablice <math>A[1..n], B[1..n]</math>, należy wyznaczyć liczbę (''inwersji'') par  
 
<math>i,j </math> takich,  
 
<math>i,j </math> takich,  
 
że <math>A[i]>B[j] </math>.  
 
że <math>A[i]>B[j] </math>.  
Liczbę inwersji między tablicami A, B oblicza następujący naiwny algorytm:
+
Liczbę inwersji między tablicami <math>A</math>, <math>B</math> oblicza następujący naiwny algorytm:
 
{{algorytm|Liczba-Inwersji-Naiwnie|algorytm_liczba_inwersji_naiwnie|
 
{{algorytm|Liczba-Inwersji-Naiwnie|algorytm_liczba_inwersji_naiwnie|
  Liczba-Inwersji-Naiwnie
+
  1 <math>wynik := 0;</math>
  <math>wynik := 0;</math>
+
2 '''for''' <math>i := 1</math> to <math>n</math> '''do'''  
  '''for''' <math>i := 1</math> to n '''do'''
+
3     <math>j := 0;</math>
     <math>j := 0;</math>
+
4     '''while''' <math>j<n</math> '''and''' <math>A[i]>B[j+1]</math> '''do''' <math>j := j+1;</math>
     '''while''' <math>j<n</math> and <math>A[i]>B[j+1]</math> '''do''' <math>j := j+1;</math>
+
5    <math>wynik := wynik + j;</math>
      <math>wynik := wynik + j;</math>
 
 
}}
 
}}
  
Algorytm ma złożoność kwadratową. Załóżmy, że początkową wartością j jest zero. Wtedy, przyglądając się  
+
Algorytm ma złożoność kwadratową. Załóżmy, że początkową wartością <math>j</math> jest zero. Wtedy przyglądając się  
dokładniej algorytmowi,
+
dokładniej algorytmowi  
widzimy że bez szkody dla poprawności instrukcję "j := 0;" można przesunąć przed pętlę '''for''' i złożoność stanie się liniowa.  
+
widzimy, że bez szkody dla poprawności instrukcję <math>j := 0;</math> można przesunąć przed pętlę '''for''' i złożoność stanie się liniowa.  
 
Dowód pozostawiamy jako ćwiczenie. W ten sposób mamy prostą
 
Dowód pozostawiamy jako ćwiczenie. W ten sposób mamy prostą
 
transformację kwadratowego algorytmu naiwnego na algorytm liniowy.  
 
transformację kwadratowego algorytmu naiwnego na algorytm liniowy.  
  
Przykład ten był dosyć ubogi i przedyskutujemy jeszcze bardziej skomplikowany przykład.  Podamy  
+
Przykład ten był dosyć ubogi i dlatego przedyskutujemy dodatkowo bardziej skomplikowany przykład.  Podamy  
przykład transformacji pewnego  
+
transformację pewnego  
prostego algorytmu B(n)  w nietrywialny algorytm <math>A_n</math>, transformacja ta bazuje na  
+
prostego algorytmu <math>B(n)</math> w nietrywialny algorytm <math>A_n</math>. Transformacja ta bazuje na  
własnościach B(n). Kluczem do  
+
własnościach <math>B(n)</math>. Kluczem do  
efektywnej transformacji jest analiza własności algorytmu B(n).
+
efektywnej transformacji jest analiza własności algorytmu <math>B(n)</math>.
 
 
  
 
===Wykrywanie fałszywej monety===
 
===Wykrywanie fałszywej monety===
Linia 205: Linia 227:
 
Mamy zbiór monet o numerach 1,2,..,N, wszystkie o tej samej wadze, i wiemy że wśród nich jest dokładnie  
 
Mamy zbiór monet o numerach 1,2,..,N, wszystkie o tej samej wadze, i wiemy że wśród nich jest dokładnie  
 
jedna fałszywa moneta  
 
jedna fałszywa moneta  
o innej wadze. Modelem algorytmu jest ciąg ważeń na wadze szalkowej. Niech waga(A) oznacza sume wag  
+
o innej wadze. Modelem algorytmu jest ciąg ważeń na wadze szalkowej. Niech waga(A) oznacza sumę wag  
 
monet ze zbioru A. W jednym  
 
monet ze zbioru A. W jednym  
ważeniu możemy wykonać operację Porównaj(A,B), gdzie A,B sa rozłącznymi podzbiorami zbioru <math>\{ 1,2,\ldots,N\}</math>.  
+
ważeniu możemy wykonać operację Porównaj(A,B), gdzie A,B rozłącznymi podzbiorami zbioru <math>\{ 1,2,\ldots,N\}</math>.  
 
Otrzymujemy jedną z trzech możliwych odpowiedzi:  
 
Otrzymujemy jedną z trzech możliwych odpowiedzi:  
  
 
*L - gdy waga(A)<waga(B)
 
*L - gdy waga(A)<waga(B)
 
*P - gdy waga(A)>waga(B)
 
*P - gdy waga(A)>waga(B)
*R - gdy wagi sa równe.
+
*R - gdy wagi równe.
  
 
Algorytmem w naszym modelu jest ciąg operacji <math>op_1, op_2,..., op_n</math> taki, że  z  
 
Algorytmem w naszym modelu jest ciąg operacji <math>op_1, op_2,..., op_n</math> taki, że  z  
Linia 224: Linia 246:
 
({1,4,7,11},{2,5,8,12})</center>
 
({1,4,7,11},{2,5,8,12})</center>
  
Naszym głównym zadaniem jest dla danego n znalezienie algorytmu ważeń, który maksymalizuje N.
+
Naszym głównym zadaniem jest dla danego ''n'' znalezienie algorytmu ważeń, który maksymalizuje ''N''.
  
Pokażemy najpierw jak rozwiązać zadanie dla <math>N=3^{n-1}</math>. Załóżmy, że liczba monet jest  
+
Pokażemy najpierw, jak rozwiązać zadanie dla <math>N=3^{n-1}</math>. Załóżmy, że liczba monet jest  
 
potęgą trójki i monety są  
 
potęgą trójki i monety są  
 
ponumerowane <math>0,1,2.. 3^{n}-1</math> . Niech S(k,0), S(k,1) oznaczają zbiory numerów monet,  
 
ponumerowane <math>0,1,2.. 3^{n}-1</math> . Niech S(k,0), S(k,1) oznaczają zbiory numerów monet,  
Linia 242: Linia 264:
 
<center><math> B(n)= (S(1,0),S(1,2)), (S(1,0),S(1,1)), ... (S(n-1,0),S(n-1,1))</math></center>
 
<center><math> B(n)= (S(1,0),S(1,2)), (S(1,0),S(1,1)), ... (S(n-1,0),S(n-1,1))</math></center>
  
Dzięki dodaniu na początku jednego ważenia już po pierwszych dwóch ważeniach wiemy, jaki jest status  
+
Dzięki dodaniu na początku jednego ważenia, już po pierwszych dwóch ważeniach wiemy, jaki jest status  
 
fałszywej  
 
fałszywej  
monety (lżejsza, cięższa). Poza tym wynikiem pierwszych dwóch ważeń nie może być LR ani RL. Te dwie  
+
monety (lżejsza, cięższa). Poza tym wynikiem pierwszych dwóch ważeń nie może być LP ani PL. Te dwie  
 
własności  
 
własności  
 
algorytmu B(n) są kluczem do transformacji tego algorytmu w algorytm <math>A_n</math>.
 
algorytmu B(n) są kluczem do transformacji tego algorytmu w algorytm <math>A_n</math>.
Linia 262: Linia 284:
 
Załóżmy, że mamy algorytm <math>A_{n-1} = (A_1,B_1),(A_2,B_2)...(A_{n-1},B_{n-1})</math> na  
 
Załóżmy, że mamy algorytm <math>A_{n-1} = (A_1,B_1),(A_2,B_2)...(A_{n-1},B_{n-1})</math> na  
 
zbiorze rozmiaru  
 
zbiorze rozmiaru  
<math>N_{n-1}</math>, i oznaczmy przez <math>przeskaluj(A_{n-1})</math> algorytm, który działa na  
+
<math>N_{n-1}</math> i oznaczmy przez <math>przeskaluj(A_{n-1})</math> algorytm, który działa na  
 
zmodyfikowanych  
 
zmodyfikowanych  
 
numerach monet: do każdego numeru dodajemy <math>3^{n-1}</math>. Ponadto dodajemy jedno  
 
numerach monet: do każdego numeru dodajemy <math>3^{n-1}</math>. Ponadto dodajemy jedno  
Linia 277: Linia 299:
 
Poprawność takiej konstrukcji wynika stąd, że na podstawie wyników dwóch pierwszych ważeń wiemy, czy  
 
Poprawność takiej konstrukcji wynika stąd, że na podstawie wyników dwóch pierwszych ważeń wiemy, czy  
 
fałszywa moneta jest  
 
fałszywa moneta jest  
mniejsza od <math>3^{n-1}</math>. Jeśli tak to traktujemy odpowiedzi jak w B(n),jesli nie to jak w A(n-
+
mniejsza od <math>3^{n-1}</math>. Jeśli tak, to traktujemy odpowiedzi jak w B(n), jeśli nie, to jak w A(n-1).  
1).  
 
 
Zostawiamy jako ćwiczenie opisanie sposobu takiego przełączania się.
 
Zostawiamy jako ćwiczenie opisanie sposobu takiego przełączania się.
  
Linia 287: Linia 308:
  
  
Dla n = 2,3,4,5,6,7 mamy: <math> N_n = 3, 12, 39, 117, 351, 1053\ldots</math>
+
Dla n = 2,3,4,5,6,7 mamy więc: <math> N_n = 3, 12, 39, 117, 351, 1053</math>.
  
  
 
==== Dygresja====
 
==== Dygresja====
Teoretycznie interesujące w tym jest to, że są to maksymalne wartości N. Pozostawiamy dowód jako  
+
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.
 
ćwiczenie. Istnieją różne optymalne algorytmy dla tego problemu.
 
Wzór rekurencyjny na liczbę monet można zapisać również w postaci
 
Wzór rekurencyjny na liczbę monet można zapisać również w postaci
  
<center><math> N_2=3; N_n=3*N_{n-1}+3</math></center>
+
<center><math> N_2=3; N_n=3*N_{n-1}+3</math>.</center>
  
  
Na podstawie tego wzoru można otrzymać drugi algorytm, który pozostawiamy jako ćwiczenie. Jest jeszcze  
+
Na podstawie tego wzoru można otrzymać drugi algorytm, który pozostawiamy jako ćwiczenie. Jest jeszcze  
 
następujący zwarty wzór, z którego ''wynika'' trzeci algorytm rozwiązujący problem bezpośrednio (bez rekursji)  
 
następujący zwarty wzór, z którego ''wynika'' trzeci algorytm rozwiązujący problem bezpośrednio (bez rekursji)  
<center><math>  
+
<center><math>N_n=(3^{n}-3)/2</math>.</center>
N_n=(3^{n}-3)/2 </math></center>
 
 
Na razie byliśmy zainteresowani głównie zmaksymalizowaniem liczby <math> N_n </math> oraz ogólną  
 
Na razie byliśmy zainteresowani głównie zmaksymalizowaniem liczby <math> N_n </math> oraz ogólną  
 
strukturą algorytmów ważenia.   
 
strukturą algorytmów ważenia.   
Linia 308: Linia 328:
 
wyjściu odpowiadającą im ciągi ważeń w czasie  
 
wyjściu odpowiadającą im ciągi ważeń w czasie  
 
liniowym ze względu na rozmiar wyjścia.
 
liniowym ze względu na rozmiar wyjścia.
 +
 +
==Dwa dodatkowe zadania o wadze szalkowej==
 +
 +
===Waga czwórkowa===
 +
Zupełnie innym problemem jest obliczenie minimalnej liczby odważników potrzebnych
 +
do zważenia na wadze
 +
szalkowej przedmiotu o wadze <math> n</math>.
 +
 +
Zakładamy, że mamy tylko odważniki o wagach będących potęgami czwórki.
 +
 +
W tym przypadku algorytm opiera się na obserwacji, że na lewo w ciągu generuje się co
 +
janwyżej przeniesienie jednej jedynki (reprezentującej następną wartść czwórki).
 +
 +
 +
Algorytm korzysta istotnie z reprezentacji czwórkowej liczby <math>n</math>.
 +
Niech
 +
 +
<center> <math> repr(n)= [n_0,n_1,n_2,\ldots,n_k]</math></center>
 +
 +
oznacza reprezentację czwórkową liczby <math>n</math>
 +
 +
 +
Cały algorytm nieformalnie wygląda następująco:
 +
 +
 +
{{algorytm|WagaCzwórkowa|algorytm_wagaczw"orkowa|
 +
<math>x_0 = 0</math>, <math>y_0 = 1</math>
 +
''for'' <math>i:=0</math>  ''to''  <math>k-1</math>  ''do'' 
 +
      <math>
 +
\begin{array}{rcl}
 +
n_{i+1} = 0 & \Longrightarrow & (x_{i+1}, y_{i+1}) := (x_i, x_i+1) \\
 +
n_{i+1} = 1 & \Longrightarrow & (x_{i+1}, y_{i+1}) := (x_i+1, \min(x_i+2,
 +
            y_i+2)) \\
 +
n_{i+1} = 2 & \Longrightarrow & (x_{i+1}, y_{i+1}) := (\min(x_i+2,
 +
            y_i+2), y_i+1) \\
 +
n_{i+1} = 3 & \Longrightarrow & (x_{i+1}, y_{i+1}) := (y_i+1, y_i)
 +
\end{array}
 +
</math>
 +
<math>wynik\ :=\ x_k</math>
 +
}}
 +
 +
Pozostawiamy jako ćwiczenie modyfikację (rozszerzeie) algorytmu tak aby
 +
obliczał on liczbę możliwych ważeń używających minimalnej liczby odważników.
 +
 +
=== Permutacje wagowe===
 +
 +
Przedstawimy jeszcze jeden problem związany z wagą. Rozważmy wagę
 +
szalkową, na której początkowo obie szalki są puste. Mamy do dyspozycji odważniki o numerach  <math>1,2,\ldots,n</math>.
 +
Waga ''i''-tego odważnika wynosi <math> a_i</math> i wagi są parami różne.
 +
Dla danej permutacji <math>\Pi</math> numerów odważników będziemy je wkładać na wagę
 +
zgodnie z permutacją. Kładziemy kolejno odważniki
 +
w kolejności <math> \Pi </math> na lewą lub prawa szalkę, raz położony odważnik nie zmienia już
 +
nigdy swego położenia na szalce (wybór szalki jest
 +
niedeterministyczny). Otrzymujemy ciąg wyników ważenia: +1, gdy lewa szalka  przeważa, a -1
 +
w przeciwnym wypadku.
 +
Ciąg ten oznaczamy przez ''Input''.
 +
Mówimy, że  permutacja <math> \Pi </math> jest zgodna z ciągiem wyników ważeń, danych tablicą
 +
''Input''. Zajmiemy się problemem: dany
 +
jest na wejściu ciąg ''Input'' wyników ważeń i mamy znaleźć
 +
jakąkolwiek permutację <math> \Pi </math> zgodną z ciągiem ''Input''. Takich permutacji może być
 +
wiele. Zauważmy, że
 +
liczba permutacji wynosi n!, a liczba ciągów wyników ważeń wynosi <math> 2^n</math>, co jest
 +
liczbą znacznie mniejszą. <br>
 +
Następujący algorytm znajduje pewną permutację zgodną ''Input''.
 +
Zakładamy, że
 +
 +
<center><math> a_1<a_2<a_3<\ldots a_n.</math></center>
 +
 +
{{algorytm|Permutacja-Wagowa|algorytm_permutacja_wagowa|
 +
1  <math> p:=1; q:=n;</math>
 +
2  '''for'''  <math>i:=n  </math> '''downto''' <math>1</math> '''do'''
 +
3    '''if''' <math>(i>1)</math> '''and''' <math>(Input[i-1] \ne Input[i])</math> '''then'''
 +
4      <math> Wynik[i]:= q; q:=q-1; </math>
 +
5    '''else '''
 +
6        <math> Wynik[i] := p; p:=p+1</math>;
 +
}}
 +
 +
Jeśli <math>Input</math> = [+1,+1,+1,-1,-1,-1,+1,+1,-1], to <math>Wynik</math> = [6, 5, 4, 7, 3, 2, 8, 1, 9].
 +
Ciąg <math>Input</math> jest zrealizowany przez następujący ciąg wyborów wkładania kolejnego odważnika:
 +
<center>  L  P  L  P  P  L  L  P  P, </center>
 +
 +
gdzie L oznacza połóż na lewą szalkę, P na prawą.
 +
 +
Nie jest jasne, jak policzyć efektywnie liczbę wszystkich
 +
permutacji zgodnych z danym ciągiem wyników, albo
 +
znaleźć jakąś szczególną permutację, np. leksykograficznie pierwszą lub ostatnią.
 +
Co stanie się, jeśli tablica <math>Input</math> zawiera również zera (wagi szalek są równe)? Wtedy nie każdy ciąg <math>Input</math>
 +
jest realizowalny.  Jak to można efektywnie sprawdzać?
  
 
==Znaczenie struktury danych==
 
==Znaczenie struktury danych==
  
Podstawową strukturą danych jest struktura "obsługująca" operacje delete(S), insert(x,S), dla zadanego  
+
Podstawową strukturą danych jest struktura "obsługująca" operacje Delete(x,S), Insert(x,S), dla zadanego  
 
zbioru S. Operacja ''delete'' pobiera z S i  
 
zbioru S. Operacja ''delete'' pobiera z S i  
zwraca jako wartość "pewien" element S. Nie interesuje nas na razie który element zostanie usunięty.  
+
zwraca jako wartość "pewien" element S. Nie interesuje nas na razie, który element zostanie usunięty.  
Niedeterminizm pozwala nam użyć w takim  
+
Niedeterminizm pozwala nam użyć w takim  
wypadku jednej z kilku struktur danych które omawiamy poniżej. W niektórych zastosowaniach istotne  
+
wypadku jednej z kilku struktur danych, które omawiamy poniżej. W niektórych zastosowaniach istotne  
 
jest, który element jest pobierany, i  
 
jest, który element jest pobierany, i  
wtedy nazwy operacji insert, delete często zmieniamy na nazwy bardziej odpowiadające terminologicznie  
+
wtedy nazwy operacji Insert i Delete często zmieniamy na nazwy bardziej odpowiadające terminologicznie  
tym strukturom, ale będziemy
+
tym strukturom. Będziemy jednak
też używać nazewnictwa delete, insert, o ile nie prowadzi to do niejednoznaczności.  Elementarne struktury  
+
też używać nazewnictwa Delete, Insert, o ile nie prowadzi to do niejednoznaczności.  Elementarne struktury  
danych, w których określone są operacje insert, delete, to:<br>
+
danych, w których określone są operacje Insert, Delete, to:<br>
 
*lista,  
 
*lista,  
 
*stos,  
 
*stos,  
 
*kolejka.  
 
*kolejka.  
Są one punktem wyjścia do bardziej skomplikowanych struktur.
+
Są one punktem wyjścia do bardziej skomplikowanych struktur, w szczególności różnego typu drzew.
  
 
====Prosty przypadek kolejki priorytetowej====
 
====Prosty przypadek kolejki priorytetowej====
  
Wariantem kolejki jest ''kolejka priorytetowa''. Jest to struktura danych, która "obsługuje" ciąg operacji insert,  
+
Wariantem kolejki jest ''kolejka priorytetowa'' typu min. Jest to struktura danych, która "obsługuje" ciąg operacji insert,  
 
delete, gdzie operacja  
 
delete, gdzie operacja  
delete zawsze pobiera minimalny element. Operację tę nazwiemy w tym przypadku ExtractMin. Operacja  
+
delete zawsze pobiera minimalny (maksymalny) element. Operację tę nazwiemy w tym przypadku DeleteMin (DeleteMax). Operacja  
 
delete jest tutaj w dużym stopniu zdeterminowana.
 
delete jest tutaj w dużym stopniu zdeterminowana.
  
Załóżmy, że ciąg operacji insert można podzielić na dwa ciągi następujące po sobie; w każdym z nich w  
+
Załóżmy, że ciąg operacji Insert można podzielić na dwa ciągi następujące po sobie; w każdym z nich w  
operacji insert wstawiamy
+
operacji Insert wstawiamy
 
elementy w porządku rosnącym. Wtedy kolejkę priorytetową można łatwo zaimplementować tak, by  
 
elementy w porządku rosnącym. Wtedy kolejkę priorytetową można łatwo zaimplementować tak, by  
operacje insert, delete mozna było wykonac w czasie stalym.
+
operacje Insert, Delete można było wykonać w czasie stałym.
  
 
Pokażemy na przykładzie algorytmu Optymalne-Sklejanie-Par zastosowanie tego typu kolejki priorytetowej.  
 
Pokażemy na przykładzie algorytmu Optymalne-Sklejanie-Par zastosowanie tego typu kolejki priorytetowej.  
Linia 346: Linia 454:
 
Operacja ta jest równoważna operacjom:
 
Operacja ta jest równoważna operacjom:
  
<blockquote><math>a = ExtracMin(S)</math>; <math>b = ExtractMin(S)</math>;  
+
<blockquote><math>a = DeleteMin(S)</math>; <math>b = DeleteMin(S)</math>;  
 
<math>Insert(a+b,S)</math>; </blockquote>
 
<math>Insert(a+b,S)</math>; </blockquote>
 
+
W dalszej części kursu pokażemy, jak każdą z operacji Insert, ExtractMin zaimplementować w czasie
+
W szczególnym przypadku, rozważonym poniżej, operacje Insert, DeleteMin można zaimplementować w czasie stałym.
logarytmicznym.
 
W szczególnym przypadku, rozważonym poniżej, można je zaimplementować w czasie stałym.
 
 
Załóżmy, że początkowy zbiór <math>S</math> jest posortowany i jego elementy są umieszczone na stosie  
 
Załóżmy, że początkowy zbiór <math>S</math> jest posortowany i jego elementy są umieszczone na stosie  
 
<math>ST</math>
 
<math>ST</math>
w kolejności rosnącej (od wierzchołka "w dół"). Załóżmy, że mamy dodatkowo zwykłą kolejkę  
+
w kolejności rosnącej (od szczytu "w dół"). Załóżmy, że mamy dodatkowo zwykłą kolejkę  
 
<math>Q</math> początkowo pustą. Wtedy ciąg operacji  
 
<math>Q</math> początkowo pustą. Wtedy ciąg operacji  
  
<blockquote><math>a = ExtracMin(S)</math>; <math>b = ExtractMin(S)</math>;  
+
<blockquote><math>a = DeleteMin(S)</math>; <math>b = DeleteMin(S)</math>;  
 
<math>Insert(a+b,S)</math></blockquote>
 
<math>Insert(a+b,S)</math></blockquote>
  
możemy wykonać w czasie stałym: element minimalny jest na wierzchołu <math>ST</math> lub na  
+
możemy wykonać w czasie stałym: element minimalny jest na wierzchołku <math>ST</math> lub na  
 
początku kolejki
 
początku kolejki
 
<math>Q</math>, element <math>a+b</math> wstawiamy na koniec <math>Q</math>. Zatem algorytm  
 
<math>Q</math>, element <math>a+b</math> wstawiamy na koniec <math>Q</math>. Zatem algorytm  
 
Optymalne-Sklejanie-Par  
 
Optymalne-Sklejanie-Par  
możemy zaimplementować w czasie liniowym gdy początkowy zbiór jest od razu posortowany. Widzimy na  
+
możemy 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.
 
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ładach możemy sobie pozwolić na niedeterministyczny wariant operacji
 
W następujących dwóch przykładach możemy sobie pozwolić na niedeterministyczny wariant operacji
delete.
+
Delete.
  
 
====Maksymalna bijekcja====
 
====Maksymalna bijekcja====
Linia 377: Linia 483:
  
 
====Dwie funkcje====
 
====Dwie funkcje====
Jest to zadanie bardzo podobne: mamy dwie częściowo określone funkcje <math>f_1, f_2</math> ze zbioru  
+
Jest to zadanie bardzo podobne. Mamy dwie częściowo określone funkcje <math>f_1, f_2</math> ze zbioru  
 
<math>[1..n]</math>  
 
<math>[1..n]</math>  
 
w siebie. Chcemy znaleźć taką permutację <math>\pi = (i_1,i_2,\ldots i_n)</math>, żeby <math>\pi(f_k(i))  
 
w siebie. Chcemy znaleźć taką permutację <math>\pi = (i_1,i_2,\ldots i_n)</math>, żeby <math>\pi(f_k(i))  
Linia 385: Linia 491:
  
  
Oba te przykłady możemy wyrazić w terminach teorii grafów. Zakładamy, że czytelnik dowiedział się na
+
Oba te przykłady możemy wyrazić w terminach teorii grafów. Zbiorem wierzchołków jest tutaj zbiór <math>[1..n]</math>.  
matematyce
 
dyskretnej, co to jest graf.  Zbiorem wierzchołków jest tutaj zbiór <math>[1..n]</math>.  
 
 
W pierwszym przykładzie krawędzie są postaci <math>(i,f(i))</math>, w drugim postaci  
 
W pierwszym przykładzie krawędzie są postaci <math>(i,f(i))</math>, w drugim postaci  
 
<math>(i,f_k(i)</math>, gdzie <math>k=1,2</math>.  
 
<math>(i,f_k(i)</math>, gdzie <math>k=1,2</math>.  
Linia 394: Linia 498:
 
zbiorem cykli.   
 
zbiorem cykli.   
  
W drugim przypadku mamy szczególny przypadek tzw. sortowania topologicznego grafu. WIerzchołek
+
W drugim przypadku mamy szczególny przypadek tzw. sortowania topologicznego grafu. Wierzchołek
 
nazywamy roboczym, gdy nie wchodzi do niego żadna krawędź.
 
nazywamy roboczym, gdy nie wchodzi do niego żadna krawędź.
 
Niech <math>S</math> będzie początkowo zbiorem wszystkich wierzchołków roboczych.  
 
Niech <math>S</math> 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 <math>v \in  
 
Algorytmy dla obu powyższych problemów działają w podobny sposób.  Pobieramy  element <math>v \in  
 
S</math>, odpowiednio przetwarzamy i usuwamy z grafu. Wskutek usunięcia  <math>v</math> pewne nowe wierzchołki stają się roboczymi i  
 
S</math>, odpowiednio przetwarzamy i usuwamy z grafu. Wskutek usunięcia  <math>v</math> pewne nowe wierzchołki stają się roboczymi i  
wstawiamy je do S. Kontynuujemy dopóki S jest niepusty.
+
wstawiamy je do ''S''. Kontynuujemy, dopóki ''S'' jest niepusty.
  
 
W przypadku problemu maksymalnej bijekcji po prostu usuwamy <math>v</math>, a w przypadku numeracji  
 
W przypadku problemu maksymalnej bijekcji po prostu usuwamy <math>v</math>, a w przypadku numeracji  
<math>\pi</math>, <math>\pi(v)</math> staje się
+
<math>\pi</math> <math>\pi(v)</math> staje się
 
kolejnym numerem. Pomimo interpretacji teorio-grafowej nie musimy implementować żadnej reprezentacji  
 
kolejnym numerem. Pomimo interpretacji teorio-grafowej nie musimy implementować żadnej reprezentacji  
 
grafu:
 
grafu:
wszystko się dzieje w wejściowych tablicach i w dodatkowej tablicy licznik[v], w której trzymamy dla  
+
wszystko się dzieje w wejściowych tablicach i w dodatkowej tablicy ''licznik[v]'', w której trzymamy dla  
 
każdego <math>v</math>  
 
każdego <math>v</math>  
 
liczbę krawędzi aktualnie wchodzących do <math>v</math>. Konkretną implementację pozostawiamy jako ćwiczenie.  
 
liczbę krawędzi aktualnie wchodzących do <math>v</math>. Konkretną implementację pozostawiamy jako ćwiczenie.  
Zbiór S  
+
Zbiór ''S''
jest tutaj zbiorem wierzchołków roboczych, które są w pewnym sensie akcjami do wykonania. Do S  
+
jest tutaj zbiorem wierzchołków roboczych, które są w pewnym sensie akcjami do wykonania. Do ''S''
 
wkładamy akcje,
 
wkładamy akcje,
 
które mamy wykonać; kolejność nie jest istotna. S może być listą, stosem lub kolejką.
 
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, którego złożoność istotnie zależy od (bardzo prostej) struktury danych (lista jednokierunkowa, która się zamienia w drzewo skierowane w stronę korzenia).  
  
====Panorama Warszawy====
 
Rozważmy inny przykład algorytmu, którego złożoność istotnie zależy od (bardzo prostej) struktury danych.
 
 
Przypuśćmy, że mamy na wejściu <math>n</math> trójek postaci <math>[p,q,s]</math>, gdzie <math> p,q  
 
Przypuśćmy, że mamy na wejściu <math>n</math> trójek postaci <math>[p,q,s]</math>, gdzie <math> p,q  
 
\in \{1,2,\ldots,n\} , s\ge 0</math>.
 
\in \{1,2,\ldots,n\} , s\ge 0</math>.
Linia 422: Linia 525:
  
  
<math>f_{p,q,s}(i)\ =\ s</math> gdy <math>p \le i \le q</math>, oraz <math>f_{p,q,s}(i)\ =\ 0</math> w  
+
<math>f_{p,q,s}(i)= s</math>, gdy <math>p \le i \le q</math>, oraz <math>f_{p,q,s}(i)= 0</math> w  
 
przeciwnym przypadku.
 
przeciwnym przypadku.
  
  
Naszym zadaniem jest dla każdego <math>1 \le i \le n</math> obliczyć wartość <math>F(i)</math>,
+
Naszym zadaniem jest dla każdego <math>1 \le i \le n</math> obliczyć wartość <math>F(i)</math>  
 
będącą maksimum z danych funkcji <math>f_{p,q,s}</math> dla argumentu <math>i</math>.  
 
będącą maksimum z danych funkcji <math>f_{p,q,s}</math> dla argumentu <math>i</math>.  
 
Można podać następującą interpretację. Każda funkcja <math>f_{p,q,s}</math> opisuje
 
Można podać następującą interpretację. Każda funkcja <math>f_{p,q,s}</math> opisuje
kształt wieżowca w Warszawie patrząc z prawej strony Wisły. Wtedy funkcja <math>F</math> opisuje  
+
kształt wieżowca w Warszawie patrząc z prawej strony Wisły. Wtedy funkcja <math>F</math> opisuje panoramę centrum Warszawy.
panoramę centrum Warszawy.
 
  
 
Załóżmy, że trójki <math>(p,q,s)</math> są posortowane ze względu na <math>s</math>.  
 
Załóżmy, że trójki <math>(p,q,s)</math> są posortowane ze względu na <math>s</math>.  
Wtedy rozważamy kolejno funkcje <math>f_{p,q,s}</math>, w kolejności rosnącego <math>s</math>,
+
Wtedy rozważamy kolejno funkcje <math>f_{p,q,s}</math> w kolejności rosnącego <math>s</math>  
 
i nadajemy za każdym razem końcowe wartości dla pozycji z przedziału <math>[p,q]</math>, dla których  
 
i nadajemy za każdym razem końcowe wartości dla pozycji z przedziału <math>[p,q]</math>, dla których  
 
jeszcze wartości nie są obliczone.
 
jeszcze wartości nie są obliczone.
 
Taki algorytm miałby złożoność kwadratową.
 
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
+
Początkowo elementy trzymamy w liscie jednokierunkowej, element i-ty wskazuje na (i+1)-szy dla i<n+1. Element n na n+1. Zakładamy więc, że mamy na przykład tablicę NEXT taką, że
końcowe są
+
NEXT[i]=i+1, dla i<n+1, NEXT[n+1]=n+1, oraz początkowo Wynik[i]=0 dla każdego i.
już obliczone, to otrzymamy algorytm działający w czasie liniowym. Dokładny zapis algorytmu
+
Trójki trzymamy w trzech tablicach, i-ta trójka jest dana przez P[i], Q[i], S[i].
pozostawiamy czytelnikowi jako ćwiczenie.
+
Nasze podstawowe założenie:<br>
 +
<center> tablica S jest posortowana malejąco </center>
 +
 
 +
Jeśli przetwarzamy w kolejnej iteracji przedział <math>[p,q]</math>, to
 +
zaczynamy od elementu p i poruszamy się na liście dopóki nie przekroczymy q, w tym
 +
momencie jesteśmy w jakimś elemencie r. Wszystkie elementy, które przeglądaliśmy, zmieniają
 +
swoje dowiązanie na r. W pewnym sensie możemy powiedzieć, że ''kompresujemy'' ścieżkę,
 +
którą przeszliśmy. Koszt iteracji to, z grubsza, długość ścieżki (liczba dowiązań, które
 +
się zmieniły).
 +
Z listy jednokierunkowej robi nam się ''drzewo jednokierunkowe''.
 +
{{algorytm|Panorama-Warszawy1|algorytm_Panorama_Warszawy1|
 +
1  '''for''' <math>i := 1</math> to n '''do'''
 +
2        <math>j := P[i];</math>
 +
3        '''while''' <math>j\le Q[i]</math>  '''do'''
 +
4            <math>Wynik[j]\ :=\ \max( Wynik[j],S[i] );</math>
 +
5            <math>j:=NEXT[j];</math>
 +
*
 +
6      ''Kompresja ścieżki:''
 +
 +
7          <math>k := P[i];</math>
 +
8          '''while''' <math>k <j</math>  '''do'''
 +
9            <math>pom:=NEXT[k]; NEXT[k]:=j; k:=pom;</math>
 +
}}
 +
 
 +
Algorytm ten powstał w ten sposób, że do algorytmu naiwnego ''doszyliśmy'' dodatkową część: ''Czaso-Przyspieszacz''.
 +
 
 +
Dosyć łatwo pokazać, że czas tego algorytmu będzie rzędu co najwyżej <math> n^{3/2} </math>, a więc lepszy niż algorytmu naiwnego. Jeśli "kompresujemy" ścieżkę długości k (w części Czaso-Przyspieszacz), to zmniejszamy sumaryczną odległość elementów do korzenia (elementu n) o wielkość co najmniej taką, jak suma liczb 1,2,3..,k, a więc mniej więcej o <math>
 +
k^2</math>.  Początkowa suma jest rzędu <math> n^{2} </math>. Za każdym razem zmniejszamy tę sumę o kwadrat kosztu danej iteracji.
 +
 
 +
Jeśli mamy n liczb, których kwadraty w sumie dają <math>
 +
n^2</math>, to suma tych liczb jest co najwyżej <math> n^{3/2} </math>. Zapisując bardziej matematycznie:
 +
<br>
 +
 
 +
<center>
 +
<math> a_1^2+a_2^2+a_3^2+\ldots a_n^2 \le n^2 \ \Rightarrow\ a_1+a_2+a_3+\ldots a_n \le n\cdot \sqrt{n} </math>
 +
</center>
 +
<br>
 +
 
 +
Podobne algorytmy poznamy
 +
w module o problemie find-union, wtedy też będziemy mogli lepiej zanalizować algorytm rozwiązujący problem Panoramy.
 +
 
 +
Rozważmy jeszcze przypadek (nazwijmy go "specjalnym"), gdy wszystkie przedziały odpowiadające  wejściowym
 +
funkcjom maja wspólne przecięcie teorio-mnogościowe. Nazwijmy ten przypadek specjalnym. Wtedy mamy bardzo prosty algorytm działający w czasie liniowym.
 +
{{algorytm|Panorama-Warszawy2|algorytm_Panorama_Warszawy2|
 +
1  <math>lewy:=Q[1]+1; prawy:=Q[1];</math><br>
 +
2  '''for''' <math>i := 1</math> to n '''do'''
 +
3        '''for''' <math>j := lewy-1</math> downto P[i] '''do'''
 +
4            <math>Wynik[j]\ :=\ \max( Wynik[j],S[i] );</math>
 +
5        '''for''' <math>j := prawy+1</math> to Q[i] '''do'''
 +
6            <math>Wynik[j]\ :=\ \max( Wynik[j],S[i] );</math><br>
 +
7        <math>lewy:=min(lewy,P[i]), prawy:=max(prawy,Q[i]);</math>
 +
}}
 +
 +
Dlaczego przypadek specjalny jest interesujący? Otóż wykorzystując algorytm dla tego
 +
przypadku, możemy łatwo otrzymać algorytm typu ''dziel i zwyciężaj'' działający w czasie <math> O(n \log n)</math>.
 +
 
 +
Podzielmy przedział [1..n] na dwie połowy. Rozważmy najpierw tylko te wieżowce, których przedziały są całkowicie w lewej części. Stosujemy do nich algorytm rekurencyjny. Podobnie robimy dla prawej połowy. Zostają nam jeszcze wieżowce, których przedziały mają punkty wspólne z obu połówkami, a to jest właśnie przypadek specjalny, który rozwiązaliśmy w prosty sposób.  
 +
 
 +
Pomimo tego wydaje się, że algorytm Panorama-Warszawy1 jest znacznie prostszy, gdyż nie wymaga rekursji ani specjalnych przypadków.
  
 
====Sortowanie kolejkowe i stosowe====
 
====Sortowanie kolejkowe i stosowe====
Linia 461: Linia 621:
  
 
Jak wyznaczyć liczbę kolejkową w czasie liniowym? Porównajmy ten problem z problemem maksymalnego  
 
Jak wyznaczyć liczbę kolejkową w czasie liniowym? Porównajmy ten problem z problemem maksymalnego  
malejącego podciągu.  
+
malejącego podciągu.
 
 
 
Pozostawiamy to jako ćwiczenie.
 
Pozostawiamy to jako ćwiczenie.
  
Podobnie definiujemy liczbę stosową, w tym wypadku w powyższym nieformalnym algorytmie  
+
Podobnie definiujemy liczbę stosową. W tym wypadku w powyższym nieformalnym algorytmie  
 
zastępujemy kolejkę przez stos.
 
zastępujemy kolejkę przez stos.
 
Można również zdefiniować liczbę kolejkowo-stosową, pytając o minimalną liczbę stosów i kolejek, które  
 
Można również zdefiniować liczbę kolejkowo-stosową, pytając o minimalną liczbę stosów i kolejek, które  
Linia 474: Linia 633:
 
do kolejek o coraz mniejszych numerach.  
 
do kolejek o coraz mniejszych numerach.  
  
Pojedyńcza operacja polega na wstawieniu kolejnego elementu z <math>\pi</math> do jednej z kolejek,   
+
Pojedyncza operacja polega na wstawieniu kolejnego elementu z <math>\pi</math> do jednej z kolejek,   
wypisaniu bezpośrednio na wyjście o ile jest on pierwszym niepobranym elementem w <math>\pi</math>  
+
wypisaniu bezpośrednio na wyjście, o ile jest on pierwszym niepobranym elementem w <math>\pi</math>  
 
lub pierwszym elementem pewnej kolejki,  
 
lub pierwszym elementem pewnej kolejki,  
albo przełożeniu pierwszego elementu pewnej kolejki <math>Q_i</math> do kolejki <math>Q_j</math>, dla  
+
albo przełożeniu pierwszego elementu pewnej kolejki <math>Q_i</math> do kolejki <math>Q_j</math> dla  
 
<math>j<i</math>.  
 
<math>j<i</math>.  
  
Linia 486: Linia 645:
  
 
====Sortowanie kolejkowe====
 
====Sortowanie kolejkowe====
Załóżmy, że każdy element ciągu <math>\pi</math> jest początkowo listą jednolelementową; oznaczmy
+
Załóżmy, że każdy element ciągu <math>\pi</math> jest początkowo listą jednoelementową. Oznaczmy
 
zbiór tych list przez <math>S</math>. Załóżmy też, że umiemy scalić dwie posortowane listy w czasie proporcjonalnym do sumy
 
zbiór tych list przez <math>S</math>. Załóżmy też, że umiemy scalić dwie posortowane listy w czasie proporcjonalnym do sumy
 
ich długości za pomocą operacji ''merge''  
 
ich długości za pomocą operacji ''merge''  
Linia 492: Linia 651:
  
 
{{algorytm|Sortowanie-Kolejkowe-1|algorytm_sortowanie_kolejkowe|
 
{{algorytm|Sortowanie-Kolejkowe-1|algorytm_sortowanie_kolejkowe|
  Scalanie-Kolejkowe
+
  1 '''while''' <math>|S|>1</math> '''do'''  
  '''while''' <math>|S|>1</math> '''do'''
+
2      <math>lista1 := delete(S); lista2 := delete(S);</math>
    <math>lista1 = delete(S); lista2 = delete(S);</math>
+
3      <math>insert(merge(lista1,lista2),S) </math>
    <math>insert(merge(lista1,lista2),S) </math>
 
 
}}
 
}}
 
Pozostawiamy jako ćwiczenie pokazanie tego, że jeśli S jest kolejką, to algorytm ten działa w czasie <math>O(n \log n)</math>, a  
 
Pozostawiamy jako ćwiczenie pokazanie tego, że jeśli S jest kolejką, to algorytm ten działa w czasie <math>O(n \log n)</math>, a  
 
jeśli <math>S</math> jest
 
jeśli <math>S</math> jest
stosem, to algorytm działa w czasie kwadratowym. Widać na tym przykładzie przewagę kolejki nad listą.  Załóżmy, że  
+
stosem, to algorytm działa w czasie kwadratowym. Widać na tym przykładzie przewagę kolejki nad stosem.  Załóżmy, że  
 
mamy posortować tablicę
 
mamy posortować tablicę
 
<math>A[0,1,\ldots, n-1]</math> i <math>n</math> jest potęgą dwójki. Wtedy następujący algorytm  
 
<math>A[0,1,\ldots, n-1]</math> i <math>n</math> jest potęgą dwójki. Wtedy następujący algorytm  
Linia 507: Linia 665:
 
{{algorytm|Sortowanie-Kolejkowe-2|algorytm_sortowanie_kolejkowe_bez_kolejki|
 
{{algorytm|Sortowanie-Kolejkowe-2|algorytm_sortowanie_kolejkowe_bez_kolejki|
 
  Scalanie-Kolejkowe bez kolejki
 
  Scalanie-Kolejkowe bez kolejki
  <math> m = 1;</math>
+
1 <math> m := 1;</math>
  '''while''' <math>m < n </math>do
+
2 '''while''' <math>m < n </math> '''do'''
     '''for''' <math>i=0</math> to <math>n/(2m)</math> do
+
3     '''for''' <math>i:=0</math> '''to''' <math>n/(2m)</math> '''do'''
       <math>merge(A[i..i+m-1], A[i+m..i+2m-1]);</math>
+
4       <math>merge(A[i..i+m-1], A[i+m..i+2m-1]);</math>
     <math>m = 2m;</math>
+
5     <math>m := 2m;</math>
 
}}
 
}}

Aktualna wersja na dzień 12:52, 9 cze 2020

W tym drugim, wstępnym module opiszemy nieformalnie kilka podstawowych technik algorytmicznych i elementarnych struktur danych. Niektóre z nich były wstępnie omawiane na kursie Metody programowania. Teraz 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 same podproblemy są "małe" w stosunku do rozmiaru problemu .

Jako przykład rozważmy jeszcze raz problem wyznaczenia przywódcy tablicy (patrz 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


1   if  then przywódcą jest pojedynczy element tablicy
2   else 
3       podziel tablicę na dwie połowy;
4       rekurencyjnie oblicz przywódcę lewej i prawej połowy tablicy;
5       sprawdź w czasie , który z nich jest przywódcą całości

Jeśli algorytm ten wykonuje kroków, to:

Rozwiązaniem jest (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 przykładach.

Wieże na szachownicy

Przypuśćmy, że mamy szachownicę na , na polu -tym leży monet. Chcemy umieścić wież na szachownicy tak, aby żadne dwie się nie atakowały. Zyskiem jest suma monet na wybranych pozycjach. Lokalna akcja to wybranie jednej dopuszczalnej pozycji. Zysk akcji to liczba monet na pozycji. Algorytm zachłanny działa trywialnie: wybieramy pozycję z maksymalnym . Można łatwo zobaczyć, że ten algorytm niekoniecznie da optymalny zysk - da jednak 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 jest zerojedynkowa.

Minimalne Sklejanie Par

Przypuśćmy, że mamy ciąg nieujemnych liczb . 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" elementów. Ciąg operacji sklejania kończy się, gdy skleiliśmy wszystko do jednej wartości.

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

Algorytm Schemat-Zachłanny


1   while zbiór możliwych lokalnych akcji jest niepusty do
2      wykonaj akcję o minimalnym koszcie;
3   return suma kosztów wykonanych akcji;


<flash>file=Sklejanie_par.swf|width=550|height=400</flash>

Można to zapisać bardziej formalnie:

Algorytm Optymalne-Sklejanie-Par


1   ;
2   while mamy co najmniej dwa elementy do
3      zastąp dwa najmniejsze elementy  przez 
4      

Pozostawiamy jako ćwiczenie dowód tego, że algorytm ten wyznacza ciąg sklejeń o najmniejszym koszcie. Co będzie, jeśli zamiast obliczać minimalny koszt chcielibyśmy wyznaczyć ciąg, który maksymalizuje sumaryczny koszt? Pozostawiamy to jako ćwiczenie. Algorytm ten jest "szkieletem" efektywnego konstruowania tzw. "drzewa Huffmana".


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 sklejać tylko elementy sąsiednie. Tak zmodyfikowany problem nazwijmy problemem Minimalnego Sklejania Sąsiadów. Możemy w poprzednim algorytmie zastąpić zwrot "dwa najmniejsze elementy" przez "dwa sąsiednie elementy o minimalnej sumie".


Niespodziewanie, nasz algorytm nie zawsze oblicza minimalną wartość, czyli nie jest poprawny. Kontrprzykładem jest ciąg

Programowanie dynamiczne

Rozwiązaniem danego problemu często jest kombinacja rozwiązań podproblemów, na które można problem rozłożyć. Natomiast nie od razu wiemy, jaka dekompozycja jest optymalna; początkowo mamy niedeterministyczny wybór wielu różnych dekompozycji. W sytuacji, gdy nie wiemy, jaka dekompozycja jest optymalna, nie możemy uruchomić rekursji, ponieważ na każdym etapie mielibyśmy wiele wyborów i w sumie złożoność mogłaby być wykładnicza.

W takich sytuacjach stosujemy 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". Rozmiary problemów muszą być odpowiednio zdefiniowane, nie powinno być zależności cyklicznej.

Wartości obliczone dla podproblemów zapamiętujemy w tablicy. Mając obliczone wartości podproblemów, na które można rozbić dany problem, wartość problemu obliczamy korzystając z wartości zapamiętanych w tablicy.

Najistotniejsze 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 minimalnego sklejania sąsiadów korzystając z programowania dynamicznego. Jeśli mamy dany ciąg , to w tym przypadku podproblem można utożsamić z pewnym przedziałem . Niech będzie wartością problemu minimalnego sklejania sąsiadów dla ciągu ;

oznaczmy ponadto

Algorytm Optymalne-Sklejanie-Sąsiadow


1   for  to  do 
2   for  to  do
3      for  downto  do
4         
5 return ;

W algorytmie zasadniczą instrukcję


można wykonywać w dowolnym przyzwoitym porządku ze względu na (i,j) (na przykład po przekątnych, zaczynając od głównej przekątnej). Przyzwoitość polega na tym, że jest już ostatecznie policzone to, z czego w danym momencie korzystamy.

Algorytm ma złożoność czasową 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 z punktu widzenia optymalnego rozwiązania.

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 najmniejsze elementy przez

zamieńmy na:

zastąp dwa sąsiednie elementy o minimalnej sumie przez
przesuń przed najbliższy na prawo (w ciągu) element większy od
(na koniec ciągu, jeśli takiego 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 , przy założeniu, że jest on poprawny. Jeśli liczby są liczbami naturalnymi z przedziału , 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. Czasami można to (w przenośni algorytmicznej) nazwać chirurgią algorytmiczną, ponieważ możemy amputować chore lub zbędne tkanki algorytmu, aby go usprawnić. Czasami, zamiast amputacji, potrzebne jest wzmocnienie algorytmu poprzez doszycie pewnej dodatkowej części (np. funkcji buty siedmiomilowe, funkcji większy-biceps lub czaso-przyspieszacz). Oczywiście w chirurgii zdarzają się pomyłki i można doszyć to, czego nie należałoby doszywać, np. funkcję czaso-wstrzymywacz. Słaba kondycja algorytmu może mieć przyczyny niezwiązane z chirurgią, np. nadwaga algorytmiczna, lub tzw. połknięcie paradygmatu. Istotna jest również prostota algorytmu. Stosując zbyt wiele transformacji i udziwnień, możemy przerobić algorytm, który jest naiwny, ale zrozumiały, w genialny algorytm, który jest zdziwaczały i niezrozumiały. Algorytm, który stracił zdrowy rozsądek, może być świetnym wynikiem teoretycznym, może być nawet przedmiotem podziwu w sensie artystycznym, ale jego praktyczne stosowanie może być niewielkie (nie dotyczy to dydaktyki).


Większość prostych algorytmów z wykładu Wstęp: poprawność i złożoność algorytmów można potraktować jako produkty transformacji algorytmów naiwnych. Pokazanie tego pozostawiamy jako ćwiczenie. Pokażemy teraz dwa proste przykłady transformacji.

Liczba inwersji

Mając dane dwie posortowane rosnąco tablice , należy wyznaczyć liczbę (inwersji) par takich, że . Liczbę inwersji między tablicami , oblicza następujący naiwny algorytm:

Algorytm Liczba-Inwersji-Naiwnie


1  
2  for  to  do 
3     
4     while  and  do 
5     

Algorytm ma złożoność kwadratową. Załóżmy, że początkową wartością jest zero. Wtedy przyglądając się dokładniej algorytmowi widzimy, że bez szkody dla poprawności instrukcję można przesunąć przed pętlę for i złożoność stanie się liniowa. Dowód pozostawiamy jako ćwiczenie. W ten sposób mamy prostą transformację kwadratowego algorytmu naiwnego na algorytm liniowy.

Przykład ten był dosyć ubogi i dlatego przedyskutujemy dodatkowo bardziej skomplikowany przykład. Podamy transformację pewnego prostego algorytmu w nietrywialny algorytm . Transformacja ta bazuje na własnościach . Kluczem do efektywnej transformacji jest analiza własności algorytmu .

Wykrywanie fałszywej monety

Mamy zbiór monet o numerach 1,2,..,N, wszystkie o tej samej wadze, i wiemy że wś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 sumę wag monet ze zbioru A. W jednym ważeniu możemy wykonać operację Porównaj(A,B), gdzie A,B są rozłącznymi podzbiorami zbioru . Otrzymujemy jedną z trzech możliwych odpowiedzi:

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

Algorytmem w naszym modelu jest ciąg operacji taki, że z otrzymanego ciągu odpowiedzi można jednoznacznie wyznaczyć 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łącznych 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 . Załóżmy, że liczba monet jest potęgą trójki i monety są ponumerowane . 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:

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ń monet (mamy teraz tylko n-1 bitów ternarnych).

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ć LP ani PL. Te dwie własności algorytmu B(n) są kluczem do transformacji tego algorytmu w algorytm .

Jeśli mamy w naszym modelu algorytmy

oraz ,

to definiujemy algorytm


Załóżmy, że mamy algorytm na zbiorze rozmiaru i oznaczmy przez algorytm, który działa na zmodyfikowanych numerach monet: do każdego numeru dodajemy . Ponadto dodajemy jedno porównanie:


Docelowy algorytm definiujemy rekurencyjnie:

Poprawność takiej konstrukcji wynika stąd, że na podstawie wyników dwóch pierwszych ważeń wiemy, czy fałszywa moneta jest mniejsza od . Jeśli tak, to traktujemy odpowiedzi jak w B(n), jeśli 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 monet, gdzie



Dla n = 2,3,4,5,6,7 mamy więc: .


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. Wzór rekurencyjny na liczbę monet można zapisać również w postaci

.


Na podstawie tego wzoru można otrzymać drugi algorytm, który pozostawiamy jako ćwiczenie. Jest jeszcze następujący zwarty wzór, z którego wynika trzeci algorytm rozwiązujący problem bezpośrednio (bez rekursji)

.

Na razie byliśmy zainteresowani głównie zmaksymalizowaniem liczby oraz ogólną strukturą algorytmów ważenia. Pozostawiamy jako ćwiczenie pokazanie, że wszystkie trzy powyższe algorytmy można zaimplementować tak, aby wypisywały one na wyjściu odpowiadającą im ciągi ważeń w czasie liniowym ze względu na rozmiar wyjścia.

Dwa dodatkowe zadania o wadze szalkowej

Waga czwórkowa

Zupełnie innym problemem jest obliczenie minimalnej liczby odważników potrzebnych do zważenia na wadze szalkowej przedmiotu o wadze .

Zakładamy, że mamy tylko odważniki o wagach będących potęgami czwórki.

W tym przypadku algorytm opiera się na obserwacji, że na lewo w ciągu generuje się co janwyżej przeniesienie jednej jedynki (reprezentującej następną wartść czwórki).


Algorytm korzysta istotnie z reprezentacji czwórkowej liczby . Niech

oznacza reprezentację czwórkową liczby


Cały algorytm nieformalnie wygląda następująco:


Algorytm WagaCzwórkowa


, 
for    to    do   
     
 

Pozostawiamy jako ćwiczenie modyfikację (rozszerzeie) algorytmu tak aby obliczał on liczbę możliwych ważeń używających minimalnej liczby odważników.

Permutacje wagowe

Przedstawimy jeszcze jeden problem związany z wagą. Rozważmy wagę szalkową, na której początkowo obie szalki są puste. Mamy do dyspozycji odważniki o numerach . Waga i-tego odważnika wynosi i wagi są parami różne. Dla danej permutacji numerów odważników będziemy je wkładać na wagę zgodnie z permutacją. Kładziemy kolejno odważniki w kolejności na lewą lub prawa szalkę, raz położony odważnik nie zmienia już nigdy swego położenia na szalce (wybór szalki jest niedeterministyczny). Otrzymujemy ciąg wyników ważenia: +1, gdy lewa szalka przeważa, a -1 w przeciwnym wypadku. Ciąg ten oznaczamy przez Input. Mówimy, że permutacja jest zgodna z ciągiem wyników ważeń, danych tablicą Input. Zajmiemy się problemem: dany jest na wejściu ciąg Input wyników ważeń i mamy znaleźć jakąkolwiek permutację zgodną z ciągiem Input. Takich permutacji może być wiele. Zauważmy, że liczba permutacji wynosi n!, a liczba ciągów wyników ważeń wynosi , co jest liczbą znacznie mniejszą.
Następujący algorytm znajduje pewną permutację zgodną Input. Zakładamy, że

Algorytm Permutacja-Wagowa


1  
2  for   downto  do
3     if  and  then
4       
5     else  
6         ;

Jeśli = [+1,+1,+1,-1,-1,-1,+1,+1,-1], to = [6, 5, 4, 7, 3, 2, 8, 1, 9]. Ciąg jest zrealizowany przez następujący ciąg wyborów wkładania kolejnego odważnika:

L P L P P L L P P,

gdzie L oznacza połóż na lewą szalkę, P na prawą.

Nie jest jasne, jak policzyć efektywnie liczbę wszystkich permutacji zgodnych z danym ciągiem wyników, albo znaleźć jakąś szczególną permutację, np. leksykograficznie pierwszą lub ostatnią. Co stanie się, jeśli tablica zawiera również zera (wagi szalek są równe)? Wtedy nie każdy ciąg jest realizowalny. Jak to można efektywnie sprawdzać?

Znaczenie struktury danych

Podstawową strukturą danych jest struktura "obsługująca" operacje Delete(x,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 usunięty. Niedeterminizm pozwala nam użyć w takim wypadku jednej z kilku struktur danych, które omawiamy poniżej. W niektórych zastosowaniach istotne jest, który element jest pobierany, i wtedy nazwy operacji Insert i Delete często zmieniamy na nazwy bardziej odpowiadające terminologicznie tym strukturom. Będziemy jednak też używać nazewnictwa Delete, Insert, o ile nie prowadzi to do niejednoznaczności. Elementarne struktury danych, w których określone są operacje Insert, Delete, to:

  • lista,
  • stos,
  • kolejka.

Są one punktem wyjścia do bardziej skomplikowanych struktur, w szczególności różnego typu drzew.

Prosty przypadek kolejki priorytetowej

Wariantem kolejki jest kolejka priorytetowa typu min. Jest to struktura danych, która "obsługuje" ciąg operacji insert, delete, gdzie operacja delete zawsze pobiera minimalny (maksymalny) element. Operację tę nazwiemy w tym przypadku DeleteMin (DeleteMax). Operacja delete jest tutaj w dużym stopniu zdeterminowana.

Załóżmy, że ciąg operacji Insert można podzielić na dwa ciągi następujące po sobie; w każdym z nich w operacji Insert wstawiamy elementy w porządku rosnącym. Wtedy kolejkę priorytetową można łatwo zaimplementować tak, by operacje Insert, Delete można było wykonać w czasie stałym.

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

zastąp dwa minimalne elementy przez .

Operacja ta jest równoważna operacjom:

; ; ;

W szczególnym przypadku, rozważonym poniżej, operacje Insert, DeleteMin można zaimplementować w czasie stałym. Załóżmy, że początkowy zbiór jest posortowany i jego elementy są umieszczone na stosie w kolejności rosnącej (od szczytu "w dół"). Załóżmy, że mamy dodatkowo zwykłą kolejkę początkowo pustą. Wtedy ciąg operacji

; ;

możemy wykonać w czasie stałym: element minimalny jest na wierzchołku lub na początku kolejki , element wstawiamy na koniec . Zatem algorytm Optymalne-Sklejanie-Par możemy 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ładach możemy sobie pozwolić na niedeterministyczny wariant operacji Delete.

Maksymalna bijekcja

Przypuśćmy, że mamy funkcję , zadaną tablicą , i chcemy znaleźć rozmiar maksymalnego podzbioru, na którym ta funkcja jest bijekcją.

Dwie funkcje

Jest to zadanie bardzo podobne. Mamy dwie częściowo określone funkcje ze zbioru w siebie. Chcemy znaleźć taką permutację , żeby , jeśli określone.


Oba te przykłady możemy wyrazić w terminach teorii grafów. Zbiorem wierzchołków jest tutaj zbiór . W pierwszym przykładzie krawędzie są postaci , w drugim postaci , gdzie .

W pierwszym przykładzie chcemy znaleźć maksymalny podzbiór grafu, na którym podgraf indukowany jest zbiorem cykli.

W drugim przypadku mamy szczególny przypadek tzw. sortowania topologicznego grafu. Wierzchołek nazywamy roboczym, gdy nie wchodzi do niego żadna krawędź. Niech 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 , odpowiednio przetwarzamy i usuwamy 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 , a w przypadku numeracji staje się kolejnym numerem. Pomimo interpretacji teorio-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 liczbę krawędzi aktualnie wchodzących do . 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ą.

Panorama Warszawy

Rozważmy inny przykład algorytmu, którego złożoność istotnie zależy od (bardzo prostej) struktury danych (lista jednokierunkowa, która się zamienia w drzewo skierowane w stronę korzenia).

Przypuśćmy, że mamy na wejściu trójek postaci , gdzie . Każdej trójce odpowiada funkcja taka, że:


, gdy , oraz w przeciwnym przypadku.


Naszym zadaniem jest dla każdego obliczyć wartość będącą maksimum z danych funkcji dla argumentu . Można podać następującą interpretację. Każda funkcja opisuje kształt wieżowca w Warszawie patrząc z prawej strony Wisły. Wtedy funkcja opisuje panoramę centrum Warszawy.

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

Początkowo elementy trzymamy w liscie jednokierunkowej, element i-ty wskazuje na (i+1)-szy dla i<n+1. Element n na n+1. Zakładamy więc, że mamy na przykład tablicę NEXT taką, że NEXT[i]=i+1, dla i<n+1, NEXT[n+1]=n+1, oraz początkowo Wynik[i]=0 dla każdego i. Trójki trzymamy w trzech tablicach, i-ta trójka jest dana przez P[i], Q[i], S[i]. Nasze podstawowe założenie:

tablica S jest posortowana malejąco

Jeśli przetwarzamy w kolejnej iteracji przedział , to zaczynamy od elementu p i poruszamy się na liście dopóki nie przekroczymy q, w tym momencie jesteśmy w jakimś elemencie r. Wszystkie elementy, które przeglądaliśmy, zmieniają swoje dowiązanie na r. W pewnym sensie możemy powiedzieć, że kompresujemy ścieżkę, którą przeszliśmy. Koszt iteracji to, z grubsza, długość ścieżki (liczba dowiązań, które się zmieniły). Z listy jednokierunkowej robi nam się drzewo jednokierunkowe.

Algorytm Panorama-Warszawy1


1  for  to n do 
2         
3         while   do 
4             
5             
*
6       Kompresja ścieżki:
*  
7           
8          while   do 
9             

Algorytm ten powstał w ten sposób, że do algorytmu naiwnego doszyliśmy dodatkową część: Czaso-Przyspieszacz.

Dosyć łatwo pokazać, że czas tego algorytmu będzie rzędu co najwyżej , a więc lepszy niż algorytmu naiwnego. Jeśli "kompresujemy" ścieżkę długości k (w części Czaso-Przyspieszacz), to zmniejszamy sumaryczną odległość elementów do korzenia (elementu n) o wielkość co najmniej taką, jak suma liczb 1,2,3..,k, a więc mniej więcej o . Początkowa suma jest rzędu . Za każdym razem zmniejszamy tę sumę o kwadrat kosztu danej iteracji.

Jeśli mamy n liczb, których kwadraty w sumie dają , to suma tych liczb jest co najwyżej . Zapisując bardziej matematycznie:


Podobne algorytmy poznamy w module o problemie find-union, wtedy też będziemy mogli lepiej zanalizować algorytm rozwiązujący problem Panoramy.

Rozważmy jeszcze przypadek (nazwijmy go "specjalnym"), gdy wszystkie przedziały odpowiadające wejściowym funkcjom maja wspólne przecięcie teorio-mnogościowe. Nazwijmy ten przypadek specjalnym. Wtedy mamy bardzo prosty algorytm działający w czasie liniowym.

Algorytm Panorama-Warszawy2


1  
2 for to n do 3 for downto P[i] do 4 5 for to Q[i] do 6
7

Dlaczego przypadek specjalny jest interesujący? Otóż wykorzystując algorytm dla tego przypadku, możemy łatwo otrzymać algorytm typu dziel i zwyciężaj działający w czasie .

Podzielmy przedział [1..n] na dwie połowy. Rozważmy najpierw tylko te wieżowce, których przedziały są całkowicie w lewej części. Stosujemy do nich algorytm rekurencyjny. Podobnie robimy dla prawej połowy. Zostają nam jeszcze wieżowce, których przedziały mają punkty wspólne z obu połówkami, a to jest właśnie przypadek specjalny, który rozwiązaliśmy w prosty sposób.

Pomimo tego wydaje się, że algorytm Panorama-Warszawy1 jest znacznie prostszy, gdyż nie wymaga rekursji ani specjalnych przypadków.

Sortowanie kolejkowe i stosowe

Działanie stosu i kolejki świetnie ilustrują różne warianty problemu sortowania z użyciem stosów i kolejek. Niech będzie permutacją liczb . Możemy posortować stosując niedeterministyczny algorytm:

while na wyjściu nie są wypisane wszystkie elementy do
   wykonaj dokładnie jedną z trzech instrukcji:
     (1) wstaw kolejny element  do jednej z kolejek; i=i+1
     (2) lub wypisz  na wyjściu; i=i+1 
     (3) lub pobierz i wypisz na wyjściu pierwszy element jednej z kolejek


Zdefiniujmy liczbę kolejkową permutacji jako minimalną liczbę kolejek potrzebnych do posortowania permutacji . Na przykład dla liczba ta wynosi 0, a dla wynosi 2.

Jak wyznaczyć liczbę kolejkową w czasie liniowym? Porównajmy ten problem z problemem maksymalnego malejącego podciągu. Pozostawiamy to jako ć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 kolejek i element może trafiać do kolejek o coraz mniejszych numerach.

Pojedyncza operacja polega na wstawieniu kolejnego elementu z do jednej z kolejek, wypisaniu bezpośrednio na wyjście, o ile jest on pierwszym niepobranym elementem w lub pierwszym elementem pewnej kolejki, albo przełożeniu pierwszego elementu pewnej kolejki do kolejki dla .

Można pokazać, że do posortowania każdej permutacji wystarczy logarytmiczna liczba kolejek.

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

Sortowanie kolejkowe

Załóżmy, że każdy element ciągu jest początkowo listą jednoelementową. Oznaczmy zbiór tych list przez . Załóżmy też, że umiemy scalić dwie posortowane listy w czasie proporcjonalnym do sumy ich długości za pomocą operacji merge (patrz następne wykłady).

Algorytm Sortowanie-Kolejkowe-1


1  while  do 
2       
3       

Pozostawiamy jako ćwiczenie pokazanie tego, że jeśli S jest kolejką, to algorytm ten działa w czasie , a jeśli jest stosem, to algorytm działa w czasie kwadratowym. Widać na tym przykładzie przewagę kolejki nad stosem. Załóżmy, że mamy posortować tablicę i 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 Sortowanie-Kolejkowe-2


Scalanie-Kolejkowe bez kolejki
1  
2  while  do
3     for  to  do
4        
5