Lasy Państwowe
Logo Encyklopedii Leśnej
Ilość znalezionych haseł: 392

Oprogramowanie i sprzęt

algorytm

(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).

Zobacz więcej...
Kontakt

Szybki kontakt