Algorytm jest to, określony ciąg czynności, który prowadzi do rozwiązania danego problemu



Strona1/5
Data03.07.2018
Rozmiar1 Mb.
  1   2   3   4   5

RZECZ ALGORYTMACH
Algorytmy

Aby zrozumieć, czym są i dlaczego w tak wielu dziedzinach stosuje się algorytmy należy zapoznać się kilkoma definicjami, które odpowiadają na powyższe niejasności. W celu szerszego zrozumienia zagadnienia algorytmu przytaczam poniżej trzy różne jego znaczenia.

1.1 Definicja algorytmu

Algorytm – algorytm jest to, określony ciąg czynności, który prowadzi do rozwiązania danego problemu. 1


Algorytm – w matematyce oraz informatyce to skończony, uporządkowany ciąg jasno zdefiniowanych czynności, koniecznych do wykonania pewnego zadania. Algorytm ma przeprowadzić system z pewnego stanu początkowego do pożądanego stanu końcowego. 2
Algorytm – algorytm jest to sformalizowany ciąg logicznie powiązanych instrukcji (poleceń, rozkazów), których wykonanie pozwoli na przetworzenie informacji wejściowych (danych) w informacje wyjściowe (wyniki). Przetwarzanie informacji to zadanie problemowe, które możemy nazwać "rozwiązywaniem zadań". Szerzej algorytmem możemy nazwać sformalizowane rozwiązywanie krok po kroku dowolnego problemu. 3
Wszystkie wyżej przytoczone definicje wskazują na to, iż algorytm jest ciągiem zadań niezbędnych do przeprowadzenia, aby z danych wejściowych uzyskać określony rezultat. Same instrukcje muszą być jasne i zrozumiale dla osoby i/lub maszyny wykonywającej dane czynności. Różnice powyższych definicji wynikają jedynie z mniej lub bardziej szczegółowego sprecyzowania zagadnienia tworzenia algorytmów oraz poleceń, jakie należy przeprowadzić, aby z punktu początkowego przejść do fazy końcowej. Na całościowe rozwiązanie problemu składają się:

• wybór metody rozwiązania problemu;


• plan zastosowania tej metody do rozwiązania problemu;
• opis czynności wykonywanych podczas realizacji tego planu wraz z opisem ich skutków;
• ostateczny wynik wykonywanych czynności;
Czynności służące do rozwiązania zadania to :
• analiza treści zadania;
• wykaz danych wejściowych; wiadomych i niewiadomych oraz relacji między nimi;
• sprawdzenie czy zadanie posiada jednoznaczne rozwiązanie;
• wybór metody rozwiązania zadania;
• opis czynności, które należy wykonać z danymi wejściowymi przy zastosowaniu;
wybranej metody rozwiązania;
• sporządzenie i przedstawienie wyników rozwiązania zadania;
• Urządzenie techniczne, które może realizować algorytm nosi nazwę automatu (żelazko z termoregulatorem, lodówka, pralka automatyczna). Uniwersalnym automatem do realizacji algorytmów z zakresu przetwarzania danych jest komputer.

1.2 Właściwości algorytmu

W celu poprawnego, a zarazem łatwego i przejrzystego tworzenia procedur, każda z nich powinna zawierać szereg podstawowych składowych. Jest to istotne zarówno dla osób projektujących nowe algorytmy, jak i dla odbiorców, dla których jest on przeznaczony. Ważna jest także estetyka i łatwość przypisania danej procedury do konkretnego wykonywanego przez nią zadania. Aby sprostać tym potrzebą wymienia się takie składowe algorytmu jak:

• nazwa algorytmu;


opis obiektów;
• deklaracja stałych i zmiennych tekstowych i liczbowych;
• deklaracja funkcji użytkownika;
• opis czynności, jakie należy wykonać z obiektami, co realizujemy za pomocą instrukcji, które opisują nie tylko sposób działania i kolejność ich wykonywania, ale również ewentualne warunki, jakie muszą być spełnione w celu uzyskania prawidłowego rozwiązania;
• opis wyników - zawiera sposób udostępnienia wyników rozwiązanego zadania.

1.3 Algorytm rekurencyjny



Jednym z rodzajów algorytmów stosowanych w dość powszechny sposób są: algorytmy rekurencyjne. Potrzeba ich stosowania polega na jak najprostszym, a zarazem najkrótszym przedstawieniu procedury, co znacznie upraszcza schemat i jego prostotę odbioru. Jak wynika z następującej definicji:
Algorytm rekurencyjny (recursive algorithm), algorytm, który wywołuje sam siebie do rozwiązania tego samego problemu.
Metoda rozwiązywania zadań w sposób rekurencyjny powszechnie stosowana jest w nawigacji. Jako przykład wymienić mogę uzyskiwanie podstawowych informacji antykolizyjnych z nakresów radarowych, mianowicie CPA, TCPA. Dla każdego obiektu radarowego postępujemy w identyczny sposób nanosząc jego kolejne namiary i odległości względem naszej centralnej pozycji. Dalej łącząc uzyskane punkty otrzymujemy kurs i prędkość względną śledzonego obiektu. Odpowiednio przenosząc wektor naszego kursu i prędkości rzeczywistej jesteśmy w stanie odpowiedzieć sobie na pytanie: Jaki jest kurs i prędkość interesującej nas jednostki. Idąc dalej i przedłużając linię kursu względnego oraz po wykreśleniu prostopadłej łączącej wspomnianą linię z centralna pozycją naszej jednostki otrzymujemy: Najbliższą odległość zbliżenia oraz czas, po którym ona nastąpi. Szereg opisanych przeze mnie czynności obrazuje nam prosty algorytm rekurencyjny, ponieważ wielokrotnie korzystamy z tych samych kroków, aby otrzymać CPA, TCPA większej ilości śledzonych obiektów naraz. Dodatkowo należy tutaj wspomnieć, że w obecnych czasach, gdzie każda jednostka powyżej 10000GT jest zobowiązana posiadać, Arpę na burcie. Czynności te zostały w pełni zautomatyzowane, a ich wyniki przedstawiane są m.in. na radarze, Ais-ie i wyświetlaczu elektronicznych map nawigacyjnych.
Zasadność stosowania takich algorytmów wynika z zastępowania wielu takich samych działań w algorytmie, do jednego, który daje nam wynik po wielokrotnym przeprowadzeniu podobnego działania.

podziału problemu na podproblemy;

rekurencyjnego rozwiązania podproblemów, chyba, że można je rozwiązać metodą bezpośrednią – takie postępowanie prowadzi do szybkiego rozwiązywania problemu;

“połączenia” rozwiązań, podproblemów w rozwiązanie całego problemu.



- Algorytm rekurencyjny

Algorytm, w którego definicji występuje odwołanie się do siebie samego. Algorytm ten musi zawierać warunek zakończenia kolejnego odwołania

1.4 Prezentacja algorytmu - schemat blokowy

Najczęstszym sposobem prezentacji algorytmu jest postać graficzna w postaci schematu blokowego. Podobnie jak to ma miejsce przy tworzeniu algorytmu, kierujemy się określonymi zasadami odnośnie jego nazewnictwa oraz deklaracji danych, którymi się posługujemy, tak i w tym miejscu należy stosować jasno sprecyzowane i łatwe do wyodrębnienia bloki. Łącząc ze sobą kilka lub więcej bloków uzyskujemy tzw. Schemat blokowy. Należy, więc wspomnieć, czym one są i z jakich elementów się składają:
Schemat blokowy (ang. Block diagram, flowchart) - są narzędziem nakierowanym na prezentację kolejnych czynności w projektowanym algorytmie. Realizowane jako diagram, na którym procedura, system albo program komputerowy są reprezentowane przez opisane figury geometryczne, połączone liniami zgodnie z kolejnością wykonywania czynności wynikających z przyjętego algorytmu rozwiązania zadania.
Cechuje je:

Prosta zasada budowy,

Elastyczność zapisów,

Możliwość zapisu z użyciem składu wybranego języka programowania,

Łatwa kontrola poprawności algorytmu.

Elementy schematu blokowego

Przyjmuje się, że w każdym schemacie blokowym już na etapie jego projektowania posługujemy się pewnymi podstawowymi elementami, wśród których znajdują się:

Strzałka - wskazuje jednoznacznie powiązania i ich kierunek,

Operand - prostokąt, do którego wpisywane są wszystkie operacje z wyjątkiem instrukcji wyboru,

Predykat - romb, do którego wpisywane są wyłącznie instrukcje wyboru,

Etykieta - owal służący do oznaczania początku bądź końca sekwencji schematu (kończą, zaczynają lub przerywają/przenoszą schemat).

Schemat blokowy pozwala dostrzec istotne etapy algorytmu i logiczne zależności między nimi. Kierunek przepływu informacji reprezentuje grot strzałki. Zależnie od przedstawianego algorytmu stosowane są różne zestawy figur geometrycznych zwanych blokami, których kształty reprezentują umownie rodzaje elementów składowych. Wyróżnia się następujące rodzaje bloków:



- Graficzne przedstawienie bloków

a) Blok graniczny - oznacza on początek, koniec, przerwanie lub wstrzymanie wykonywania działania, Np. blok startu programu.

b) Blok wejścia-wyjścia - przedstawia czynność wprowadzania danych do programu i przyporządkowania ich zmiennym dla późniejszego wykorzystania, jak i wyprowadzenia wyników obliczeń, Np. czytaj z, pisz φ i λ.

c) Blok obliczeniowy - oznacza wykonanie operacji, w efekcie, której zmienią się wartości, postać lub miejsce zapisu danych, Np. φ := -φ(S), φ := φ(N).

d) Blok decyzyjny - przedstawia wybór jednego z dwóch wariantów wykonywania programu na podstawie sprawdzenia warunku wpisanego w ów blok, Np. λ > 180º.

e) Blok wywołania podprogramu - oznacza zmianę wykonywanej czynności na skutek wywołania podprogramu, Np. sprawdzenie poprawności wprowadzonych współrzędnych φ i λ, dla φ N lub S, natomiast λ E lub W.

f) Blok fragmentu - przedstawia część programu zdefiniowanego odrębnie, Np. sortowanie współrzędnych.



Przykładowy schemat blokowy dotyczący algorytmu sprawdzającego działanie świateł nawigacyjnych:

- Przykładowy schemat blokowy



  1   2   3   4   5


©operacji.org 2019
wyślij wiadomość

    Strona główna