Lasy Państwowe
Logo Encyklopedii Leśnej

algorytm

Opis
Rysunki
Zgłoś uwagę

(informatyka w leśnictwie, oprogramowanie i sprzęt),  algorytm, przepis postępowania prowadzący do rozwiązania ustalonego problemu, określający ciąg czynności elementarnych, które należy w tym celu wykonać. Algorytm może zawierać definicje obiektów (danych), na których te czynności są przeprowadzane; wykonawcą algorytmu może być człowiek lub urządzenie automatyczne (np. komputer) zdolne do wykonywania poleceń w odpowiedzi na sygnały reprezentujące te polecenia. Termin algorytm pochodzi od zlatynizowanej formy nazwiska uczonego arabskiego Al-Chuwarizmi (łac. Algorismus, Algorithmus), który w IX w. w Traktacie o rachowaniu na liczbach indyjskich podał przejęty z indyjskich tekstów astronomicznych pozycyjny sposób zapisywania liczb (za pomocą dziesięciu cyfr) i metody wykonywania działań arytmetycznych wykorzystujące ten zapis. Znaczenie terminu algorytm, ograniczone początkowo do przepisów na proste postępowania rachunkowe, uległo następnie rozszerzeniu; wraz z rozwojem informatyki algorytm stał się jej podstawowym pojęciem i obiektem badań (analiza algorytmów).

Cechy algorytmu:
1) możliwość wyrażania go w różnych postaciach (np. w języku naturalnym, w językach programowania, w postaci schematu graficznego); przez zapisanie w języku programowania algorytm staje się programem;
2) możliwość wyrażania go w postaci skończonego ciągu symboli, bez używania zwrotów odwołujących się do analogii, jak „itd.”;
3) realizowalność, tzn. fizyczna możliwość wykonania poleceń;
4) możliwość wielokrotnego wykonywania, na ogół z różnymi danymi. Poprawność algorytm polega na zgodności jego działania i wyników z intencjami twórców, użytkowników; w sensie formalnym oznacza to, że dla ustalonych warunków początkowych, spełnianych przez dane wejściowe, działanie algorytmu zawsze się kończy (tzw. własność stopu), a dane wynikowe spełniają określone warunki końcowe.
Kolejność wykonywania poszczególnych czynności w algorytmie zależy często od danych początkowych i od wyników pośrednich; określone fragmenty algorytmu mogą być wielokrotnie powtarzane (iteracja, rekurencja). Rozróżnia się algorytmy sekwencyjne, w których rozpoczęcie kolejnej czynności musi być poprzedzone zakończeniem poprzedniej, oraz algorytmy niesekwencyjne, w których pewne czynności mogą być wykonywane równocześnie (współbieżność).
Klasycznym algorytmem, odkrytym w IV w. p.n.e., jest algorytm Euklidesa, służący do obliczania największego wspólnego dzielnika (NWD) dwóch liczb naturalnych m i n (m > 0 i m ≥ n):
Czynność 1: sprawdź, czy n = 0; jeśli tak, to zakończ wykonywanie algorytmu — szukanym NWD jest m; jeśli nie, przejdź do czynności 2.
Czynność 2: oblicz resztę z dzielenia m przez n, oznacz ją przez r i przejdź do czynności 1, ale z innymi liczbami: n teraz równym r i m równym poprzedniej wartości n.
Jest to algorytm poprawny dzięki następującemu twierdzeniu arytmetyki: gdy m > 0, to NWD liczb m i n dla n = 0 jest równy m, a dla n > 0 jest równy NWD liczb n i r, gdzie r jest resztą z dzielenia m przez n. Algorytm zakończy działanie, gdyż ciąg reszt obliczanych w kolejnych wykonaniach czynności 2 jest malejący, a każdy malejący ciąg liczb naturalnych jest skończony.
Cechą decydującą dla praktycznej przydatności algorytmu jest jego złożoność obliczeniowa (zwana też kosztem algorytmu).

ŹRÓDŁO (AUTOR)

Encyklopedia PWN

Publikacje powiązane tematycznie

Rzecz o istocie informatyki - Algorytmika. Klasyka informatyki. Harel David, Feldman Yishai. Wydawnictwo Naukowo Techniczne 2008
 

Zgłoś uwagę do hasła

Maksymalny rozmiar: 5MB
algorytm

Indeks alfabetyczny:

POPRZEDNI NASTĘPNY

Indeks tematyczny:

POPRZEDNI NASTĘPNY
Kontakt

Szybki kontakt