Ocena brak

ALGORYTM

Autor /koles8181000xd Dodano /19.12.2012

(średniowieczno-łac. algorithmus, od przydomka perskiego matematyka
Abu Gˇ afara Muh. ammada Ibn Mu sà al-H
uwarizmı zw. Al-Chwarizmi,
zmieniony pod wpływem gr. na arithmos)—dokładny opis postepowania gwarantujacy
osiagniecie okreslonego rezultatu w skonczonej ilosci elementarnych
kroków.

Najistotniejsze cechy a.:

1) okreslona jest sytuacja poczatkowa, w której mozna
a. zastosowac, sytuacja docelowa oraz rodzaje czynnosci, jakie moga byc wykonywane;

2) wykonywane elementarne czynnosci sa całkowicie jednoznaczne
i mozliwe do zrealizowania przez okreslonego wykonawce a. Mozliwosc konstruowania
a. przeznaczonych dla róznych wykonawców sprawia, ze kwestia,
czy dany przepis jest a., staje sie relatywna—przy jednym wykonawcy przepis
jest a., przy innym nie jest. Czasami zada sie, aby wykonanie poszczególnych
kroków było czysto mechaniczne, tzn. nie wymagajace rozumienia sensu czynnosci;

3) po wykonaniu kolejnego kroku przepisy wskazuja, jaki ma byc krok
nastepny, badz informuja, ze zadanie zostało wykonane. Przepis moze przybierac
postac instrukcji warunkowej: jesli spełniony jest okreslony warunek, to
wykonaj pewne działanie;

4) osiagniecie pozadanego rezultatu jest gwarantowane—
niezaleznie od parametrów sytuacji poczatkowej wykonanie a. konczy sie
osiagnieciem sytuacji docelowej. Moze sie jednak zdarzyc, iz a. jest praktycznie
niewykonalny, gdyz wymaga zbyt wielu srodków róznego rodzaju (np. czasu,
pamieci, materiałów);

5) a. jest zawsze ogólny, a wiec moze byc wykorzystywany
wielokrotnie do sytuacji poczatkowych o róznych parametrach;

6) wykonanie
a. jest zawsze skonczone. Wyjatkiem moze byc tu a. sterowania procesem ciagłym,
który ma charakter nieskonczony. W tej sytuacji mozna jednak mówic
o pozadanym stanie równowagi i skonczonym procesie osiagania go;

7) a. jest
przedmiotem abstrakcyjnym i moze byc zapisywany na wiele sposobów, wyrazony
w róznych jezykach.

Jest wiec czyms innym, niz jego zapis. Nie pokrywa
sie równiez z zadaniem, które rozwiazuje. Rozwój elektroniki, prowadzacy do konstrukcji komputerów sprawił, ze a.
nabrały duzego znaczenia w zwiazku z mozliwoscia automatycznego ich wykonywania
w postaci programów komputerowych. Wokół a. skoncentrowana jest
znaczna czesc badan z dziedziny informatyki. Rozwaza sie m.in. nastepujace zagadnienia:

a) poprawnosc a.—zwł. dowodzenie, ze dany a. gwarantuje rozwiazanie
postawionego problemu;

b) szacowanie efektywnosci a.;

c) znajdowanie
najlepszych a., rozwiazujacych typowe problemy;

d) niezawodne przechodzenie
od opisu problemu do a. rozwiazujacego problem.

Na osobne omówienie zasługuje kwestia efektywnosci a., okreslana inaczej
jako złozonosc obliczeniowa, tzn. ilosc czasu (elementarnych operacji) i miejsca
w pamieci potrzebnych do realizacji a., oszacowana w odniesieniu do wielkosci
danych wejsciowych. Klasy a. o podobnej złozonosci obliczeniowej okresla
sie zazwyczaj przy pomocy maszyny Turinga. Najwazniejszymi z tych klas sa
a. wykonalne w czasie wielomianowym na zwykłej maszynie Turinga (P-Time)
oraz na niedeterministycznej maszynie Turinga (NP-Time).

Intuicyjnie mozna
te dwie klasy rozumiec odpowiednio jako zawierajace a., dla których znany
jest przepis, pozwalajacy na znalezienie zadanej odpowiedzi w czasie okreslanym
jako wielomian parametru danych wejsciowych i takie, dla których istnieje
droga do rezultatu zajmujaca taki czas, choc niekoniecznie jestesmy w stanie
ja wskazac. Te pierwsza klase interpretuje sie czasem jako klase a. praktycznie
realizowalnych, druga natomiast zawiera wiekszosc pozostałych a., rozwiazujacych
wazne z praktycznego punktu widzenia problemy.

Mimo intensywnych
badan nie udało sie dotychczas ustalic, czy klasy te sie pokrywaja. W przypadku,
gdy praktycznie wykonalnego a. nie daje sie znalezc, stosuje sie inne
metody, które nie gwarantuja uzyskania rezultatu, ale daja praktyczne szanse
znalezienia (za pomoca symulacji komputerowej) rozwiazania przyblizonego,
np. a. ewolucyjne (genetyczne), sztuczne sieci neuronowe.

Podobne prace

Do góry