AlgorytmyTeoriaSortowanieNumeryczneSzyfrowanieKompresjaGrafikaLiczby kontrolneTurbo PascalC++JavaVisual Basic 6 Aplikacje internetowe MySQL Excel DOS

Algorytmy: trochę teorii

Algorytmem nazywamy precyzyjnie wyrażony przepis postępowania przy realizacji jakiegoś działania, niezależny od wykonawcy realizującego dane działanie. Algorytm stanowi ogólny schemat i może być zapisywany w różnych językach i konwencjach, zależnie od potrzeb, upodobań autora i wymagań użytkownika.

Każdy algorytm musi posiadać następujące cechy:

• uniwersalność - algorytm formułuje się dla całej klasy podobnych zadań, różniących się parametrami ustalanymi za pośrednictwem danych wejściowych określonego typu; sformułowanie algorytmu powinno być niezależne od specyficznych cech wykonawcy;
   
• jednoznaczność - w algorytmie nie może w żadnym miejscu wystąpić dowolność interpretacji; zamiast powiedzieć: weź jakąś liczbę, należy określić precyzyjnie sposób jej wyliczenia lub pobrania;
   
• skończoność - niezależnie od tego, czy liczba przewidzianych do wykonania czynności jest z góry znana, czy też zależy od danych, zapis poleceń musi być ujęty w skończonej formie;
   
• skuteczność - dla każdego prawidłowego zestawu danych algorytm powinien zatrzymać się w skończonym czasie (po wykonaniu lub mimo niewykonania zadania); pojęcie „prawidłowego zestawu danych” powinno być jednoznacznie wyjaśnione w specyfikacji danych algorytmu.

Poza wyżej wymienionymi - koniecznymi -cechami algorytmu, pożądaną cechą dodatkową jest jego efektywność: algorytm powinien osiągać efekt możliwie niskim kosztem. Koszty są związane z czasem pracy wykonawcy: im bardziej efektywny algorytm, tym mniej czasu zajmie jego wykonanie temu samemu wykonawcy. Niestety — na ogół tym więcej czasu musi mu poświęcić projektant i programista.

Przy rozwiązywaniu zadań praktycznych znaczenie ma również koszt opracowania i koszt przyszłej konserwacji algorytmu, mierzony wysiłkiem twórcy wkładanym w jego ulepszanie i rozbudowę. Algorytmy bardziej efektywne są często bardziej skomplikowane (więc trudniejsze w opracowaniu, analizie i implementacji).

Z punktu widzenia użytkownika algorytm - niezależnie od tego, jakie zadanie realizuje algorytm - jest czarną skrzynką.

W celu uzyskania poprawnych wyników użytkownik powinien przygotować odpowiednie dla algorytmu dane i zlecić wykonanie algorytmu jakiemuś wykonawcy, np. komputerowi. Możliwa jest również sytuacja, gdy sam użytkownik pełni rolę wykonawcy (posługując się np. kartką papieru i długopisem).

Algorytm może być wykonany tylko pod warunkiem, że zostaną dostarczone niezbędne dane wejściowe, tzn. dane niezbędne do tego, by pewne ogólne zadanie, które algorytm ma rozwiązywać, zostało sprowadzone do tego konkretnego zadania, które trzeba rozwiązać właśnie teraz dla konkretnie dostarczonych danych.. Dane te muszą być przygotowane w ściśle określony sposób uwzględniający między innymi: zakres wartości czy kolejność ich podawania.

W trybie wsadowym dane wejściowe muszą być przygotowane przed rozpoczęciem realizacji algorytmu. W trybie interaktywnym dane dostarcza się na żądanie w trakcie wykonywania algorytmu.

Wyniki algorytmu są przekazywane jako tzw. dane wyjściowe. Jak w przypadku danych wejściowych, tak i przy odczytywaniu wyników nie może być miejsca na żadną dowolność.

Musisz odróżniać dane wejściowe (przygotowane każdorazowo przez użytkownika) od wewnętrznych stałych algorytmu (np. liczba e, stałe fizyczne, liczba dni w tygodniu, prywatne stałe algorytmu, itp.), których wartość nigdy nie ulegnie zmianie w danym algorytmie.

Dane wejściowe zawsze pochodzą od użytkownika i nigdy ich wartości nie mogą być definiowane przez algorytm. Np. algorytm rozwiązania równania kwadratowego ma służyć do znajdowania pierwiastków dowolnego równania tej postaci, ale algorytm rozwiązania konkretnego równania kwadratowego -x² + 9x + 3 = 0 nie ma większej wartości. I odwrotnie: prostota rozwiązania i wielość zastosowań nadaje sens opracowywaniu i stosowaniu algorytmu rozwiązywania równania kwadratowego zamiast budowania ogólniejszego algorytmu wyznaczania miejsc zerowych wielomianu dowolnego stopnia.

Pozostańmy przy przykładzie algorytmu wyznaczania pierwiastków równania kwadratowego ax² + bx + c = 0. Może on pobierać dane w kolejności a, b, c lub dowolnej innej; może wyznaczać pierwiastki różnymi metodami; może wyznaczać rozwiązania rzeczywiste lub zespolone; może zwracać sensowy wynik zawsze lub tylko wtedy, gdy równanie jest naprawdę równaniem drugiego stopnia (tzn. a ≠ 0); może wreszcie udostępniać wyniki w różnej postaci i z różną dokładnością.

Realizacja konkretnego algorytmu wynika zawsze z wymagań stawianych danym wejściowym i wynikom. Wymagania te nazywamy specyfikacją wejścia i specyfikacją wyjścia. Charakteryzują one działanie algorytmu z punktu widzenia użytkownika, bez zagłębiania się w szczegóły mechanizmu przetwarzania danych wejściowych w wyjściowe.

Poniższe specyfikacje przedstawiają różne możliwości podania w zasadzie tego samego problemu:

Dla drugiego algorytmu zestaw danych wejściowych 0 1 2 jest nieprawidłowy. Użytkownikowi także nie będzie wszystko jedno, według której specyfikacji działa wykorzystywany przez niego algorytm choćby ze względu na dokładność wyników.

Algorytm możemy przedstawić w bardzo różny sposób. Najpopularniejsze metody prezentowania algorytmów to:

1. metody słowne oparte na:
    
   • języku naturalnym;
      
   • języku formalnym (programowania);
      
2. metody graficzne oparte na symbolach graficznych:
    
   • schematy blokowe;
      
   • tablice decyzyjne;
      
   • schematy czynnościowe (w tym obiegu dokumentów);
      
   • schematy przetwarzania (systemów przebiegu);
      
   • technika grafów;
      
   • tablice krzyżowe;
      
   • matryce sprzężeń.
      

Dla naszych potrzeb zajmiemy się tylko metodą języka formalnego (programowania) oraz schematami blokowymi.

Schematy blokowe są narzędziem stosunkowo prostym, nakierowanym przede wszystkim na prezentację kolejnych czynności w projektowanym algorytmie. Są szczególnie przydatne podczas pisania złożonych programów komputerowych. Cechuje je: prosta zasada budowy (mała liczba elementów), pewna elastyczność zapisów, możliwość zapisu z użyciem składu wybranego języka programowania, łatwa kontrola poprawności algorytmu. Pozwalają na stosunkowo prostą zamianę instrukcji na instrukcje programu komputerowego.

Elementy schematów blokowych:

Na poniższym rysunku przedstawiona jest przykładowa sieć działań algorytmu rozwiązywania równania drugiego stopnia:

  Weryfikacja algorytmu polega na zbadaniu, czy robi on to, co robić powinien z punktu widzenia specyfikacji danych, tzn. czy jest skuteczny.

Testowanie polega na badaniu, czy wyniki podawane przez schemat przetwarzania są takie, jak powinny być, tzn. zgodne z deklarowanym celem działania algorytmu. Dlatego należy znać wyniki, jakich oczekuje się dla używanych przez siebie zestawów danych testowych.

Użytkowanie algorytmu polega na przygotowywaniu dla niego danych, jego wykonania i odbieraniu wyników. Najczęściej użytkuje się nie tyle abstrakcyjną postać algorytmu, co realizujący go program

Program to algorytm przedstawiony w sformalizowany sposób dla konkretnego wykonawcy. W programach przeznaczonych dla procesora komputerowego dane są reprezentowane przez zmienne. Działanie takiego programu polega na przekształcaniu wartości zmiennych aż do uzyskania żądanego efektu.

W czasie wykonywania algorytmu dane przechowujemy w zmiennych. Dla nas zmienna będzie rozpoznawana po nadanej jej nazwie lub adresie. W danej chwili zmienna przechowuje jedną wartość określonego przez nas typu. Wartość można nadać zmiennej w drodze podstawienia lub pobrać z innej zmiennej i użyć w obliczeniach. Pobranie wartości ze zmiennej nie niszczy informacji przechowywanej w tej zmiennej. Natomiast przypisanie do zmiennej wartości gubi bezpowrotnie jej dotychczasową wartość.

Jeżeli zawartości zmiennej nie można przewidzieć z działania algorytmu, to mówimy, że ma ona stan nieokreślony. Co prawda zmienna zawsze przechowuje pewną wartość, ale w tym przypadku zależy ona od czynników zewnętrznych w stosunku do naszego algorytmu (np. od programu, który poprzednio używał tego obszaru pamięci). Pobieranie do obliczeń wartości zmiennych znajdujących się w stanie nieokreślonym jest poważnym błędem logicznym. Tym niemniej wina leży wtedy po stronie projektanta algorytmu lub programisty układającego program, gdyż wykonawca ma obowiązek wykonania każdej zleconej mu czynności, nawet z pozoru bezsensownej. Próba wykonania na ogół kończy się awaryjnym przerwaniem pracy na skutek błędu obliczeń lub w najlepszym przypadku zniekształconą wartością wyniku.

Rekurencja
Rekurencja to odwoływanie się funkcji do samej siebie. Każda funkcja rekurencyjna musi posiadać przynajmniej jeden przypadek bazowy (nie rekurencyjny), który pozwala zakończyć wywołania tej funkcji przez sama siebie. W przeciwnym przypadku nigdy się nie zakończy. Funkcje rekurencyjne są jednak unikane w rzeczywistych algorytmach, ze względu na większą złożoność obliczeniową niż odpowiadające im procedury iteracyjne, problemy z określeniem czy i kiedy procedura się zakończy itp., a także fakt, że trudno przewidzieć ilość pamięci potrzebną do prawidłowego zakończenia rekurencji. Rekurencja przydaje się znakomicie do opisu rozstrzyganego problemu.

Metoda dziel i zwyciężaj
Jeżeli problem można podzielić na kilka mniejszych, niezależnych podproblemów i rozwiązać je rekurencyjnie, a na końcu połączyć je jako rozwiązanie całego problemu, możemy zastosować metodę "dziel i zwyciężaj". Metoda ta jest często stosowana, np. w algorytmie sortowania szybkiego lub binarnego wyszukiwania elementu w posortowanej tablicy.

Programowanie dynamiczne
Jest to rozszerzenie metody "dziel i zwyciężaj". Jeżeli podproblemy, na które został podzielony problem główny, nie są niezależne to w różnych podproblemach wykonywane są wiele razy te same obliczenia. Warto jest wtedy zastosować ulepszenie tej metody: programowanie dynamiczne. Wyniki obliczeń są zapamiętywane w tablicy pomocniczej, która jest wykorzystywana w kolejnych krokach algorytmu, co eliminuje potrzebę wielokrotnego wykonywania tych samych obliczeń. Prowadzi to do widocznego obniżenia złożoności obliczeniowej. Programowanie dynamiczne polega więc na wykonania obliczeń każdego podproblemu tylko raz i zapamiętaniu jego wyniku w tabeli. W każdym kolejnym kroku można z tej tabeli korzystać. Programowanie dynamiczne jest zazwyczaj stosowane w rozwiązywaniu problemów optymalizacyjnych, prowadzi to często do wyznaczenia kilku równoznacznych, optymalnych rozwiązań.

Metoda zachłanna
Jeżeli mamy daną kombinację danych, które mogą być rozwiązaniem danego problemu można się posłużyć metodą "zachłanną". Metoda "zachłanna" polega na rozpatrywaniu danych w kolejności uporządkowanej, np. posortowane. W danym kroku wybierane są te dane, które są najodpowiedniejsze. Najczęściej metoda ta prowadzi do otrzymania rozwiązania przybliżonego, choć istnieją problemy, dla których metoda zachłanna daje rozwiązanie optymalne.