1 algorytm 07-05-02
Jeżeli chcemy przyrządzić potrawę, a nie wiemy dokładnie jak ją zrobić, szukamy w przepisach kulinarnych opisu sposobu jej wykonania. Przypuśćmy, że mamy ochotę zjeść pizzę marynarską. W pierwszej kolejności musimy przygotować składniki potrzebne do jej upieczenia. A oto pełna ich lista:
· 40 dkg mąki,
· 4 dkg drożdży,
· ¾ szklanki wody,
· szczypta cukru,
· 1 łyżka oliwy,
· 25 dkg pomidorów,
· 1 główka czosnku,
· szczypta origano,
· 2 lub 3 łyżki oliwy,
· 10 oliwek,
· trochę soli.
Następnie musimy zapoznać się ze sposobem wykonania potrawy. Upieczenie pizzy marynarskiej wymaga postępowania według następującego przepisu:
1. rozmieszać drożdże z małą ilością letniej wody i szczyptą cukru. Mieszaninę pozostawić w ciepłym miejscu aż do wyrośnięcia drożdży,
2. Przesiać mąkę. Wlać do niej podgrzaną wodę, oliwę i drożdże oraz wsypać sół,
3. Ciasto dokładnie wyrobić, a następnie postawić na godzinę w ciepłym miejscu, aby wyrosło,
4. Uformować z ciasta 4 placki z rancikiem,
5. Blachę do pieczenia posmarować oliwą i ułożyć na niej placki,
6. Placki posmarować oliwą i roztartym czosnkiem, połozyć na nich plastry pomidorów, posypać origano i solą oraz skroplić oliwą. Następnie poczekać około 20 min. aby placki mogły podrosnąć,
7. wstawić do rozgrzanego piekarnika na około pół godziny.
8. Po upieczeniu wyjąć blachę z piekarnika i położyć pizzę na talerz.
Zwróćmy uwagę, że powyższy przepis umożliwia nam czysto mechaniczne wykonywanie czynności, bez dociekań, dlaczego którąś z czynności wykonujemy tak, a nie inaczej
W matematyce jest szeroko znana metoda Euklidesa obliczania największego wspólnego podzielnika (NWP) dwóch liczb naturalnych n, m.
Aby znaleźć NWP, postępujemy wówczas tak:
1. Wyznaczyć resztę r z podzielenia n przez m.
2. 2, Jeśli r=0, to skończyć postępowanie, Poszukiwaną wielkością jest m.
Jeśli r¹0, to w charakterze nowej dzielnej n przyjąć wielkość m, a w charakterze nowego dzielnika m przyjąć wielkość r.
Kontynuować postępowanie, począwszy od czynności 1. Również powyższy przepis umożliwia osiągnięcie zamierzonego celu (wyznaczenie największego wspólnego dzielnika dwóch liczb naturalnych ) bez prześledzenia drogi rozumowania Euklidesa, która doprowadziła go do opracowania metody.
Nie sposób nie docenić wartości tego rodzaju przepisów. Niezbędnym elementem bezpieczeństwa w ruchu pojazdów jest znajomość przepisów ruchu przez kierowców oraz ich respektowanie. Wyprodukowanie radioodbiornika polega na wykonaniu szeregu czynności, których rodzaj i kolejność określa technolog. Poprawne wypowiadanie się w określonym języku wymaga znajomości gramatyki tego języka. Schematycznie wykonujemy wiele czynności w życiu codziennym. Kto zastanawia się codziennie, jak zaparzyć kawę lub jak należy postępować, aby dodać lub pomnożyć dwie liczby naturalne w zapisie dziesiętnym ? Nie zawsze jednak uświadamiamy sobie, że wykonanie tych czynności umożliwia nam doskonała znajomość przepisów opracowanych przez inną osobę. Tego rodzaju przepisy noszą nazwę algorytmów.
Algorytmem będziemy nazywali przepis postępowanie, którego wykonanie prowadzi do rozwiązania określonego zadania w skończonym czasie, Powyższe określenie nie jest ścisłą definicją algorytmu. Aby można ją lepiej zrozumieć, omówimy pewne pojęcia integralnie związane z definicją algorytmu oraz wyjaśnimy szerzej niektóre własności wynikające bezpośrednio z definicji. Skoro algorytm jest przepisem postępowania, jest więc zbiorem pewnych reguł (zasad) określających rodzaj czynności, które należy wykonać. Jest oczywiste, że w algorytmie muszą być wyszczególnione wszystkie niezbędne czynności, potrzebne do rozwiązania postawionego zadania, oraz sprecyzowanie kolejność ich wykonywania. Przepis postępowania powinien być na tyle precyzyjny, aby posługiwanie się nim polegało tylko na automatycznym wykonaniu czynności.
Obiekty podlegające przekształceniu (przetworzeniu) podczas wykonania algorytmu będziemy nazywali danymi. Do upieczenia pizzy danymi są składniki wymienione na początku wykładu. Dla drugiego algorytmu danymi są dwie liczby naturalne, których największy wspólny dzielnik chcemy wyznaczyć. Ostateczne rezultaty wykonania algorytmu będziemy nazywać wynikami (upieczona pizza marynarska jest wynikiem wykonania pierwszego algorytmu, obliczony największy wspólny dzielnik - wynikiem drugiego ) . Należy rozróżniać pojęcie: algorytm, wykonanie (realizacja) algorytmu, opis (formalizacja) algorytmu. Algorytm jest zbiorem zasad. Realizacją algorytmu jest wierna (zgodne z zasadami) wykonanie jego wszystkich czynności. Mówiąc o wykonaniu algorytmu nie dopuszczamy jakichkolwiek różnic między zasadami sformułowanymi w algorytmie, i sposobem ich wykonania. Opisem algorytmu jest postać zapisu jego reguł,
Nazwa algorytm wywodzi się od nazwiska arabskiego matematyka i astronoma Muhammeda ibn Musa A1-Chwarizmi (Muhammed, syn Musy z Chorezmu) , który około 820 roku n.e. opisał pozycyjny system kodowania dziesiętnego liczb i sztukę wykonywania podstawowych działań arytmetycznych w tym systemie (system dziesiętny przedtem był stosowany wyłącznie w Indiach). Oczywiście algorytmy poznali ludzie dużo wcześniej. Od początku powstania najstarszej z nauk - matematyki, matematycy dostarczali rozwiązań zadań w postaci algorytmów. Teoria algorytmów powstała w połowie lat trzydziestych naszego stulecia dzięki pracom Hilberta, Posta i Turinga. Jej inspiracją były wewnętrzne potrzeby matematyki teoretycznej, Logika matematyczna, algebra, analiza matematyczna, geometria stały się też jednymi z głównych dziedzin rozwoju i zastosowań algorytmów.
Zwróćmy uwagę, że realizacja algorytmu nie wymaga znajomości problemu, który ten algorytm rozwiązuje, a sprowadza się do czysto mechanicznego wykonania reguł. Zatem wykonawcą algorytmu nie musi być człowiek. Może nim być automat. Obecnie najlepszymi i stosowanymi powszechnie automatami do wykonywania algorytmów są elektroniczne maszyny cyfrowe (komputery) . Algorytm przeznaczony do wykonania przez maszynę cyfrową musi być opisany w języku zrozumiałym dla maszyny; nosi on wówczas nazwę programu. Polecenia zapisane w języku programowania noszą nazwę instrukcji lub rozkazów. Zatem program dla komputera jest listą instrukcji, które komputer ma wykonać.
Elektroniczna maszyna cyfrowa składa się z czterech głównych zespołów funkcjonalnych: pamięci operacyjnej, arytmometru, układu sterowania i bloku wejścia - wyjścia. Blok składający się z arytmometru i układu sterowania nosi nazwę procesora, a zespół złożony z procesora i pamięci operacyjnej nazywa się jednostką centralną. Konfigurację komputera tworzą: mikroprocesor, pamięci zewnętrzne oraz urządzenia wejścia i wyjścia. Podział konfiguracji komputera na podstawowe części składowe oraz przepływ informacji między nimi są zilustrowane na rysunku . Pamięć operacyjna składa się z komórek. Są w niej przechowywane programy i dane w czasie wykonywania obliczeń. Arytmometr wykonuje operacje arytmetyczne i logiczne, Zadaniem układu sterowania jest kierowanie pracą zespołów
komputera według programu umieszczonego w pamięci operacyjnej. Blok wejścia-wyjścia służy do komunikacji jednostki centralnej z otoczeniem za
pośrednictwem urządzeń wejścia i wyjścia. Urządzenia wejścia są przeznaczone do wprowadzania informacji do komputera. Urządzenia wyjścia służą do wyprowadzenia Informacji z komputera oraz zapisania jej w postaci wygodnej dla odczytu przez człowieka ( wydruk, wykres ). Pamięci zewnętrzne służą do przechowywania dużych ilości informacji w dowolnie długim czasie.
Sensu stricto nie cały komputer, ale tylko jednostka centralna wykonuje program (algorytm zakodowany w języku komputera ) . Wykonanie wymaga jednak uprzedniego umieszczenia (wczytania) programu i danych w pamięci operacyjnej (ten sam proces jest realizowany przez blok wejścia-wyjścia oraz urządzenie wejścia lub pamięć zewnętrzną ) . Dlatego też w opisach algorytmów, które mają być wykonane przez komputer, pojawiają się dodatkowe polecenia "CZYTAJ DANE", oznaczające: wprowadź dane do pamięci operacyjnej umieszczając je w odpowiednich komórkach. Podobnie po wykonaniu programu przez jednostkę centralną jego wyniki znajdują się w komórkach pamięci operacyjnej. Następnie muszą zostać przedstawione w postaci czytelnej d1a człowieka, tj. w postaci wydrukowanego tekstu, wykresu itp., aby użytkownik mógł je w łatwy sposób odczytać. Tę czynność odnotowujemy w opisach algorytmów zapisując polecenia: "DRUKUJ dane".
Wykonywanie programu przez elektroniczną maszynę cyfrową ma również charakter realizacji algorytmu. Przedstawimy niżej jego ogólny zarys.
1) Po umieszczeniu programu w pamięci operacyjnej daje się polecenie rozpoczęcia obliczeń. W poleceniu jest zawarty numer instrukcji programu, która ma zostać wykonana jako pierwsza. Numer ten zostaje umieszczony w liczniku rozkazów, mieszczącym się w układzie sterowania.
2) Układ sterowania bada rodzaj instrukcji, której numer jest umieszczony w liczniku rozkazów:
(a) jeśli badaną instrukcją jest instrukcja STOP, to następuje zakończenie procesu wykonywania programu,
(b) jeśli badana instrukcja poleca wykonanie operacji arytmetycznej 1ub logicznej, to układ sterowania przekazuje jej wykonanie arytmometrowi,
(c) jeśli badana instrukcja poleca wprowadzenie danych do pamięci operacyjnej 1ub wyprowadzenie wyników z pamięci operacyjnej, to układ sterowania przekazuje kontrolę wykonania instrukcji blokowi wejścia-wyjścia.
3. Odpowiedni zespół funkcjonalny komputera wykonuje instrukcję. Po jej wykonaniu zespół przekazuje kontrolę realizacji programu układowi sterowania.
4. Zawartość licznika rozkazów powiększa się o 1. Powrót do kroku 2.
Bardziej precyzyjne wyjaśnienie pojęcia algorytmu wymaga omówienia podstawowych jego własności. Niektóre z nich są cechami algorytmu tkwiącymi w jego definicji. Pozostałe sygnalizują pewne problemy, z którymi spotyka się człowiek podczas tworzenia i realizacji algorytmów. A oto najważniejsze z nich:
Masowość. Zastosowanie oznaczeń symbolicznych (nazw przetwarzanych obiektów) umożliwia otrzymanie takiego opisu algorytmu, dzięki któremu możemy go zrealizować dla dowolnego zestawu danych. Powyższa własność jest często spotykana w matematyce. Aby obliczyć pewną wielkość, najpierw określa się wzór analityczny używając symboli. Następnie wykonuje się obliczenia przez przypisanie każdemu symbolowi konkretnej wartości i przeprowadzenie rachunku według reguł określonych wzorem analitycznym. Mając wzór analityczny możemy wykonać obliczenia wielokrotnie dla różnych zestawów wartości (liczb, stałych, logicznych) , postępując każdorazowo według tych samych reguł. Analogiczna sytuacja występuje w przypadku wykonywania obliczeń z wykorzystaniem komputerów. Opracowujemy program komputerowy ( określający reguły postępowania ) umożliwia wielokrotne wykonanie obliczeń dla różnych zestawów danych.
a*x2+bx+c=0; a¹0.
Ogólność. Rozważmy dwa algorytmy obliczania pierwiastków równania kwadratowego:
Pierwszy z nich oblicza tylko pierwiastki rzeczywiste równania , którego współczynniki a,b,c są liczbami rzeczywistymi. Przypadek wystąpienia pierwiastków zespolonych jest przez algorytm sygnalizowany odpowiedzią: "brak pierwiastków rzeczywistych". Drugi algorytm rozwiązuje równanie , którego współczynniki a,b,c, mogą być dowolnymi liczbami zespolonymi (w szczególności rzeczywistymi) , podając każdorazowo odpowiedź w postaci pary liczb zespolonych. Zauważmy, że drugi algorytm rozwiązuje ogólniejsze zadanie, ponieważ pierwszy jest szczególnym przypadkiem drugiego. Powiemy zatem, że drugi algorytm jest ogólniejszy od pierwszego. Z faktu, że każdy algorytm posiada ustalony stopień ogólności, wynika, że jego opis powinien obok listy czynności określać
precyzyjnie dziedzinę danych i postać wyników.
Przez skończoność wykonania algorytmu rozumiemy fakt, że wyniki powinno się otrzymać po wykonaniu skończonej ilości operacji - algorytm nie może być wykonywany wiecznie
Jedną z konsekwencji tej własności jest operowanie liczbami przybliżonymi. Przykładowo: rezultatem próby przedstawienia dowolnej liczby niewymiernej w postaci ułamka dziesiętnego jest jej przybliżona wartość (ex definitione każda liczba niewymierna posiada nieskończone rozwinięcie dziesiętne).
Poprawny zapis algorytmu powinien gwarantować, że każdorazowe jego wykonanie - dla tego samego zestawu danych - daje te same wyniki pośrednie i końcowe, niezależnie od tego, kto będzie wykonawcą jego poleceń. Tę własność nazywamy jednoznacznością zapisu. Algorytm może być zapisany w różnych systemach notacji . Również program komputerowy może być zapisany w różnych językach programowania. Bardzo często pojawiają się błędy w trakcie tłumaczenia (przekodowywania) z jednej postaci zapisu na inną. A zatem jest rzeczą istotną, aby zapis algorytmu był rozumiany jednoznacznie.
Do podstawowych kryteriów oceny jakości algorytmów zaliczamy złożoność i niezawodność algorytmów.
Niezawodność algorytmu jest prawdopodobieństwem tego, że dany algorytm będzie prawidłowo realizował dane zadania dla dowolnego zestawu danych. A zatem niezawodność algorytmu jest związana z jego poprawnością. Żądanie algorytmu niezawodnego jest żądaniem oczywistym, aczkolwiek w trakcie dążenia do otrzymania takiego algorytmu możemy napotkać szereg poważnych trudności. Istnieją w zasadzie trzy kierunki działań, aby sprostać temu wymaganiu:
- stosowanie takich metod konstruowania algorytmów, aby uzyskać odpowiednie parametry niezawodnościowe,
- opracowanie wyczerpujących i efektywnych metod badania (testowania) gotowego algorytmu, tak aby wykryć możliwie największą ilość błędów w nim zawartych,
- konstruowanie algorytmów w taki sposób, aby błąd, który może się ujawnić w trakcie jego wykonania, nie wpływał na poprawność rezultatów.
Wraz z powstaniem pierwszych algorytmów pojawił się problem ich zapisu, czyli formalizacji. Początkowo używano opisu słownego, który jednakże wymagał znajomości języka autora danego algorytmu i w związku z tym był wysoce nieprecyzyjny i niejednoznaczny. Te wady stawały się coraz bardziej uciążliwe w miarę narastania złożoności algorytmów. Sposobów formalizacji powstało wiele i mają one różny zakres rozpowszechnienia. Część z nich ma charakter jedynie teoretyczny, przydatny w badaniach samych algorytmów, inne są stosowane tylko do pewnych wyróżnionych klas zadań. Istnieją dwa zasadnicze kierunki formalizacji algorytmów:
algebraiczny i graficzny. Kierunek algebraiczny oparty jest na pewnej konkretnej symbolice, Możemy tu wyróżnić takie sposoby notacji algorytmów, jak tablice decyzyjne, opis funkcjami logicznymi, opis operatorowy Lapunowa, opis za pomocą funkcji rekurencyjnych. Powyższe metody, aczkolwiek ściśle sformalizowane, a zatem usuwające mankament niejednoznaczności, są niestety mało czytelne, Stąd w większości przypadków korzysta się z
metod zapisu opartych na notacji graficznej, W koncepcji tej algorytm jest przedstawiony w postaci grafu, którego wierzchołki odpowiadają działaniom algorytmu, a krawędzie ustalają relacje, (związki) pomiędzy poszczególnymi działaniami. Do tego kierunku możemy zaliczyć schematy operacyjne Janowa, drzewa decyzji oraz sieci działań. Ze wszystkich wymienionych sposobów notacji, najbardziej rozpowszechniona ze względu na swoje zalety jest metoda opisu algorytmów w postaci sieci działań. .
Tablica-decyzyjną jest pewnym sposobem opisu zbioru związanych ze sobą reguł decyzyjnych, tj. wyrażeń opisujących układ warunków, które muszą być spełnione dla wykonania określonych czynności. Jej podstawową strukturę tworzą cztery pola: pole definicji warunków, pole specyfikacji warunków, pole definicji czynności, pole specyfikacji czynności -
Pole definicji warunków zawiera wszystkie wyrażenia określające warunki, które wywierają wpływ na proces decyzyjny. Wyrażenia wypisuje się w kolumnie, Najwygodniej jest je zapisać w kolejności wynikającej z istoty opisywanego problemu.
Pole specyfikacji warunków zawiera znaki, które wskazują, czy warunek zamieszczony w danym wierszu jest spełniony (znak T ) , nie jest spełniony (znak N) lub też jego spełnienie bądź niespełnienie nie ma wpływu na daną decyzję (znak -) .
podstawowego problemu.
Pole specyfikacji czynności może zawierać znak X lub - .Znak X wskazuje, że czynność dla danego układu warunków ma być wykonana. Znak - wskazuje, że rozpatrywana czynność dla danego układu warunków ma zostać zignorowana niezależnie od tego czy są spełnione warunki danej reguły, czy też nie.
Pojedynczą regułę decyzyjną tworzy jedna kolumna pól specyfikacji warunków i specyfikacji czynności.
Układ warunków w regule decyzyjnej ma charakter koniunkcji, tzn. czynności odpowiadające danej regule decyzyjnej powinny być wykonane jedynie wtedy, gdy układ warunków jest
identyczny z zapisanym w polu specyfikacji warunków danej reguły.
Przykład 1 Podać w postaci tablicy decyzyjnej rozwiązanie następującego zadania: znaleźć minimalną z trzech liczb rzeczywistych: a',b,c.
Rozwiązanie. Wystarczy rozważyć tylko trzy warunki (każdy z nich może być prawdziwy lub fałszywy) , aby uwzględnić wszystkie, niezbędne do rozwiązania zadania, relacje między liczbami a,b,c. Przyjmujemy, że następujące trzy relacje wyszczególnimy w polu definicji warunków:
W1: a < b
W2: a < c ,
W3: b < c .
A2: minimalną liczbą jest b,
A3: minimalną liczbą jest c,
ponieważ każda z trzech rozważanych liczb może okazać się rozwiązaniem. Pełna tablica decyzyjna, której nadajemy nazwę MIN została przedstawiona jako tablica
Znaki X umieszczone w odpowiednich wierszach pola specyfikacji czynności wskazują odpowiedź.
Układ warunków w regułach R3, R6 jest sprzeczny, zatem w polu specyfikacji czynności tych reguł nie ma żadnych znaków.
Podstawowym dla techniki tablic decyzyjnych jest następujący aksjomat: każde jednoznaczne nadanie wartości wszystkim zmiennym występującym w polu definicji warunków powoduje spełnienie jednej i tylko jednej reguły.
Tablice decyzyjne są szczególnie przydatne w konstruowaniu algorytmów, gdzie w zależności od pewnych warunków należy wykonać określone czynności, podjąć określone decyzje itp.
Reguły decyzyjne dzielimy na: - reguły proste, tj. takie, które nie zawierają pozycji obojętnych (w polu specyfikacji warunków nie występują znaki -, a jedynie znaki T i N),
- reguły złożone, które powstają przez połączenie kilku reguł prostych i w związku z tym zawierają pozycje obojętne.
W zależności od postaci zapisu warunków, czynności oraz wartości, jakie mogą one przyjmować, rozróżniamy trzy rodzaje tablic decyzyjnych:
tablice decyzyjne proste,
tablice decyzyjne rozszerzone,
tablice decyzyjne mieszane.
Z tablicą decyzyjną prostą mamy do czynienia wówczas, gdy pole specyfikacji warunków zawiera jedynie znaki T, N, - a pole specyfikacji czynności znaki x, -.
Przykład 1.2. Układ zbiorowy pewnej gałęzi gospodarki przewiduje szereg świadczeń socjalnych w zależności od ilości przepracowanych lat i wielkości rodziny. świadczenia te, wraz z warunkami ich otrzymania, można zestawić w tablicy decyzyjnej prostej o nazwie TAB1.
Zwróćmy uwagę na prostą zasadę tworzenia reguł decyzyjnych tablicy prostej. Tablica decyzyjna prosta mająca n warunków posiada 2n reguł decyzyjnych elementarnych, tj. nie zawierających znaku - w polu specyfikacji warunków. W celu ich skompletowania wpisuje się w pierwszym wierszu pola specyfikacji warunków najpierw 2n-1 znaków T, a następnie 2n-1 znaków N; w i-tym wierszu wpisuje się na przemian 2n-1 znaków T i 2n-1 znaków N. Powyższa zasada gwarantuje, że zostaną wyczerpane wszystkie możliwe układy warunków oraz, że żadne z nich nie powtórzą się.
Jednakże w wielu przypadkach można z tablicy decyzyjnej usunąć pewną ilość reguł elementarnych i otrzymać równoważny opis, ale z mniejszą ilością reguł,
Zasady upraszczania tablic decyzyjnych wyjaśnimy na przykładzie tablicy TABl. Zwróćmy przede wszystkim uwagę, że reguły R5,R6,R9 ¸ R14,R16 tablicy TAB1 nie polecają wykonania żadnej czynności. Jest to zrozumiałe, gdyż reguły R5,R6,R9- R14 posiadają sprzeczne układy warunków, np. w regule R11 okres zatrudnienia ma być jednocześnie mniejszy od 2 lat i większy od 6 lat. Wymienione reguły sprzeczne można zatem pominąć. Pominąć można również regułę R16, gdyż nie wymaga ona wykonania żadnej czynności. Zwróćmy ponadto uwagę, że reguły R7 i R15 polecają wykonanie tych samych czynności A1, A5. Czynności te wykonuje się dla identycznych pozycji warunkowych: W2=N, W3=N, W4=T, niezależnie od tego, czy W1=T(reguła R7) czy też W1=N (Reguła R15). Tak więc warunek W1 jest nieistotny dla tych reguł, co zaznaczamy stawiając znak – w pierwszym wierszu reguły otrzymanej z połączenia reguł R7 i R15. Ogólne zasady upraszczania tablic decyzyjnych są następujące:
· reguły decyzyjne nie wymagające wykonania żadnej czynności można usunąć,
· dwie reguły o identycznych ciągach czynności można połączyć w jedną, jeśli różnią się tylko w jednej pozycji warunkowej i gdy ta różnica ma jedną z trzech postaci:
Lp.
Pozycja I
Pozycja II
1
MAXXDATA