Lekcja

Algorytm – w matematyce skończony ciąg jasno zdefiniowanych czynności, koniecznych do wykonania pewnego rodzaju zadań. Słowo "algorytm" pochodzi od starego angielskiego słowa algorism, oznaczającego wykonywanie działań przy pomocy liczb arabskich (w odróżnieniu od abacism – przy pomocy abakusa), które z kolei wzięło się od nazwiska, które nosił Muhammad ibn Musa al-Chuwarizmi (أبو عبد الله محمد بن موسى الخوارزمي), matematyk perski z IX wieku.

Algorytm ma przeprowadzić system z pewnego stanu początkowego do pożądanego stanu końcowego. Badaniem algorytmów zajmuje się algorytmika. Algorytm może zostać zaimplementowany w postaci programu komputerowego.

Jako przykład stosowanego w życiu codziennym algorytmu podaje się często przepis kulinarny. Dla przykładu, aby ugotować bigos należy w określonej kolejności oraz odstępach czasowych (imperatyw czasowy) dodawać właściwe rodzaje kapusty i innych składników. Może istnieć kilka różnych przepisów dających na końcu bardzo podobną potrawę. Przykład ten ma wyłącznie charakter poglądowy, ponieważ język przepisów kulinarnych nie został jasno zdefiniowany. Algorytmy zwykle formułowane są w sposób ścisły w oparciu o język matematyki.

W niektórych krajach, jak USA, algorytmy mogą zostać opatentowane, jeżeli zostaną zaimplementowane w jakimś praktycznym celu. Niektórzy twierdzą, że patentowanie algorytmów spowalnia rozwój informatyki, bo jeden producent może uzyskać monopol, np. na pisanie oprogramowania tworzącego pewne typy plików(np. GIF). Wiele koncernów komputerowych prowadzi między sobą spory prawne dotyczące praw własności do niektórych patentów. Kontrargumentem jest tzw. prawo własności intelektualnej (jaką objęty jest np. utwór muzyczny, będący wytworem intelektu i pracy muzyka) zakładające, że program jest intelektualną własnością twórcy.

 

Przykład

Znalezienie największej wśród niepustej, nieposortowanej listy przypadkowych liczb można przeprowadzić na wiele sposobów, jednym z najszybszych jest przedstawiony niżej. Niech \scriptstyle \mathrm{indeks} oznacza wskazuje aktualnie badany element listy (jeśli jest ona numerowana, może on oznaczać np. jej numer), a \scriptstyle \mathrm{maksimum}oznacza największą dotychczas znalezioną wartość.

  1. Niech \scriptstyle \mathrm{indeks} wskazuje na pierwszy element (początek) listy.
  2. Niech \scriptstyle \mathrm{maksimum} zawiera wartość elementu listy wskazywanego przez \scriptstyle \mathrm{indeks} (tzn. pierwszego).
  3. Jeżeli zawartość elementu listy wskazywanego przez \scriptstyle \mathrm{indeks} jest większa od zawartości \scriptstyle \mathrm{maksimum}, to przypisz \scriptstyle \mathrm{maksimum} wartość elementu wskazywanego przez \scriptstyle \mathrm{indeks}.
  4. Niech \scriptstyle \mathrm{indeks} wskazuje kolejny element listy; jeśli to niemożliwe (tzn. \scriptstyle \mathrm{indeks} wskazuje ostatni element listy, czyli jej koniec), przejdź do punktu 6.
  5. Wróć do punktu 3.
  6. Koniec.

Wykonanie tego algorytmu spowoduje, że największa liczba na wspomnianej liście będzie wartością \scriptstyle \mathrm{maksimum}; ciekawostką jest fakt, iż algorytm ten działa dla list dowolnej długości (nie wykorzystuje on liczby elementów listy, lecz tylko tzw. operację następnika danej listy, tzn. przejścia do następnego jej elementu; niemożność wskazania kolejnego elementu jest wtedy równoważna temu, iż dany element jest ostatni na liście).



Dodaj komentarz






Dodaj

© 2013-2024 PRV.pl
Strona została stworzona kreatorem stron w serwisie PRV.pl