Dziedzina algorytmiczna

Dziedzina algorytmiczna


Ważnym pojęciem przy określaniu algorytmu jest pojęcie dziedziny algorytmicznej. Algorytmy wykonują pewne operacje na argumentach i wyrażenie własności algorytmu, a w tym określenie jego złożoności, dokonywane jest za pomocą tych operacji. Dziedziną algorytmiczną nazwiemy zatem system relacyjny \( \langle A,\{o_i\}_{i\in I}, \{r_{j}\}_{j\in J}\rangle \), gdzie \( A \) nazywany jest nośnikiem, a zbiory \( \{o_i\}_{i\in I}, \{r_{j}\}_{j\in J} \), odpowiednio zbiorem operacji i relacji określonych w \( A \), których można używać w algorytmie. Zauważmy, że od tego, jakimi operacjami i relacjami dysponujemy zależą nasze możliwości opisywania algorytmów. Zawsze musimy wiedzieć, z jakich operacji można korzystać, zanim zabierzemy się za programowanie. Czasami takie operacje przyjmują postać bibliotek gotowych procedur i funkcji – cegiełek, z których składamy nasze algorytmy.

W przypadku naszych trzech algorytmów Euklidesa te trzy dziedziny, to:

  1. Euklides1: \( \langle {\cal N}, -,\le, =_0 \rangle \)
  2. Euklides2: \( \langle {\cal N}, \bmod, =_0 \rangle \)
  3. Euklides3: \( \langle {\cal N}, -,\div_2, *_2,\le, \in_P,=_0 \rangle \),

gdzie \( - \), to zwykłe odejmowanie, \( \bmod \) operacja znajdowania reszty, \( \div_2 \) - jednoargumentowa operacja dzielenia przez 2, \( *_2 \) jednoargumentowa operacja mnożenia przez 2 (zauważmy, że przez nic innego nie musimy dzielić ani mnożyć), \( \le \) relacja dwuargumentowa niemniejszości, \( \in_P \) jednoargumentowa relacja parzystości, zaś \( =_0 \) relacja jednoargumentowa bycia zerem.

Uświadomienie sobie, w jakiej dziedzinie algorytmicznej operujemy, jest ważne między innymi z punktu widzenia porównywania algorytmów. Łatwo jest bowiem "skrzywdzić" jakiś algorytm nie zauważając, że działa on w uboższej dziedzinie niż rzekomo lepszy, a przyjrzenie się kosztowi operacji podstawowych daje lepszy wgląd w istotę złożoności.
Jeszcze parę słów na temat złożoności algorytmów. Jak mogliśmy to zauważyć, brak analizy złożoności może doprowadzić do porażki – algorytm, nawet poprawny, może stać się praktycznie bezużyteczny, jeśli będzie miał zbyt dużą złożoność. Dokładniej o złożoności będzie jeszcze mowa na dalszych wykładach z bardziej zaawansowanej algorytmiki. Podkreślmy parę podstawowych spraw.

  1. Złożoność określamy obliczając liczbę operacji dominujących, czyli takich, które najczęściej będą wykonywane.
  2. Złożoność wyznacza się zazwyczaj z dokładnością do rzędu wielkości, a więc zaniedbując czynnik stały. Czasami czynnik ten bierze się pod uwagę, ale dopiero wtedy, gdy porównujemy algorytmy o podobnym rzędzie złożoności. Najczęściej do określenia złożoności używa się notacji \( O \), która pozwala uwolnić się od czynnika stałego i skupia się właśnie na rzędzie wielkości. #MatematykaDyskretna.xxx

    Definicja [Definicja notacji \( O \)]
    Mówimy, że funkcja \( f:{\cal N} arrow R \) jest \( O(g) \), jeśli istnieją stała \( c>0 \) oraz liczba \( m\in {\cal N} \) takie, że dla każdego \( n>m \) zachodzi \( f(n)\le cg(n) \).

  3. Złożoność zależy od rozmiaru danych. Przez rozmiar danych najczęściej rozumiemy liczbę bitów (czy bajtów) potrzebnych do zakodowania danych; znowu chodzi o rząd wielkości. Na przykład jeśli mówimy o sortowaniu liczb, to ważne jest ile ich jest, a nie to, z jaką dokładnością je podajemy – zwiększenie takiej dokładności w końcu rozmiar danych powiększy o stały czynnik. Stąd na przykład
    1. gdy sortujemy n obiektów, rozmiarem danych jest n;
    2. gdy rozważamy graf, rozmiarem danych jest suma liczby krawędzi i wierzchołków (czasem rozważamy osobno liczbę krawędzi i wierzchołków);
    3. gdy rozważamy algorytmy liczbowe – tak jak w naszych przykładach obliczania największego wspólnego dzielnika – rozmiarem danych jest długość zapisu cyfrowego liczby, bo tak złożone jest podanie jej wartości
  4. Czasami do wykonania algorytmu potrzeba dodatkowej pamięci na pomocnicze struktury. Wtedy również zastanawiamy się, ile tej pamięci potrzeba i wynik nazywamy złożonością pamięciową
  5. Dla różnych danych algorytm może różnie się wykonywać. W praktyce rozważa się dwa rodzaje danych: pesymistyczne (czyli najbardziej złośliwe) i losowe, czyli typowe. Mówimy wtedy odpowiednio o złożoności pesymistycznej i złożoności średniej.

Dobrzy informatycy wyrabiają sobie przy programowaniu nawyk myślenia o złożoności.