Algorytm

Strona tytułowa podręcznika Bernarda Wojewódki Algorithm To iest, Nauka liczby po Polsku z 1602 roku

Algorytm – skończony ciąg jasno zdefiniowanych czynności koniecznych do wykonania pewnego rodzaju zadań, sposób postępowania prowadzący do rozwiązania problemu. W informatyce algorytmem nazywa się dobrze określoną procedurę obliczeniową, która przyjmuje dane wejściowe i produkuje dane wyjściowe, czyli obliczalny zbiór kroków prowadzących do pożądanego rezultatu.

Słowo „algorytm” pochodzi od łacińskiego algorithmus (lub algorismus), oznaczającego wykonywanie działań za pomocą liczb arabskich, w odróżnieniu od abacism, czyli rachowania z użyciem abakusa. Wyraz ten wywodzi się od „Algoritmi”, zlatynizowanej wersji nazwiska al-Chuwarizmiego, matematyka działającego w IX wieku.

Definicja i własności

Definicja zakłada skończoność i jednoznaczność. Algorytm wykonuje skończoną liczbę kroków i dla danych wejściowych wyznacza dane wyjściowe. W przypadku algorytmów randomizowanych (losowych) przebieg obliczeń może zależeć nie tylko od danych wejściowych, lecz także od wartości losowych generowanych podczas działania algorytmu. Algorytmy te można opisywać za pomocą prawdopodobieństw uzyskania określonych wyników lub czasu wykonania.

Przykład algorytmu

Poniższa procedura wyznacza największą liczbę na niepustej, skończonej liście liczb. Niech indeks wskazuje aktualnie badany element listy, a maksimum oznacza największą dotychczas znalezioną wartość.

  1. Niech indeks wskazuje na pierwszy element listy.
  2. Niech maksimum przyjmuje wartość elementu wskazywanego przez indeks.
  3. Jeżeli wartość elementu wskazywanego przez indeks jest większa od maksimum, to przypisz maksimum wartość tego elementu.
  4. Niech indeks wskazuje kolejny element listy. Jeżeli to niemożliwe, przejdź do punktu 6.
  5. Wróć do punktu 3.
  6. Koniec.

Po wykonaniu procedury maksimum zawiera największą liczbę z listy. Procedura działa dla list o dowolnej długości, ponieważ korzysta wyłącznie z przejścia do kolejnego elementu.

Inne przykłady

Do znanych algorytmów należą m.in. algorytm Euklidesa, algorytm Dijkstry, algorytm Luhna, algorytm mrówkowy, algorytm Fermata, algorytmy kompresji i kryptograficzne, algorytmy sortowania, w tym sortowanie przez scalanie, algorytmy przeszukiwania drzew gier: min-max i alfa-beta oraz algorytm unifikacji.

Algorytm Euklidesa zapisany w postaci schematu blokowego

Reprezentacja algorytmów

Algorytmy opisuje się w języku naturalnym, w postaci schematów blokowych oraz w pseudokodzie.

Schemat blokowy diagnozowania niesprawnej lampy

Ten sam algorytm można wyrazić na różne sposoby, na różnych poziomach abstrakcji. Poniższe fragmenty programów realizują ten sam algorytm sumowania trójek.

Zapis w języku C:

  wynik  = 3;
  wynik += 3;
  wynik += 3;

Ten sam język, z zastosowaniem pętli:

  wynik = 0;
  for (int i = 0; i < 3; ++i) wynik += 3;

Zapis w asemblerze x86:

  mov eax, 0
  add eax, 3
  add eax, 3
  add eax, 3

Jednym z matematycznych modeli obliczeń jest maszyna Turinga, składająca się z głowicy czytająco-piszącej poruszającej się po podzielonej na komórki taśmie. W każdym kroku maszyna odczytuje symbol z komórki wskazywanej przez głowicę, a następnie, zgodnie z funkcją przejścia, może zapisać symbol, przesunąć głowicę i zmienić swój stan.

Klasyfikacja algorytmów

Podstawowe paradygmaty projektowania algorytmów komputerowych zestawia poniższa tabela.

Paradygmat Idea
dziel i zwyciężaj problem dzieli się na mniejsze podproblemy, rozwiązywane rekurencyjnie, a następnie łączy się ich wyniki
programowanie dynamiczne rozwiązania podproblemów zapamiętuje się i wykorzystuje ponownie przy rozwiązywaniu głównego problemu
metoda zachłanna w każdym kroku wybierane jest lokalnie najlepsze rozwiązanie
algorytm z nawrotami systematyczne wypróbowywanie możliwych rozwiązań z cofaniem się, gdy wybrana droga okazuje się błędna

Algorytmy klasyfikuje się także według wielu innych, niezależnych kryteriów: według użycia losowości (deterministyczne i randomizowane), trybu wykonania (sekwencyjne i równoległe), podstawy obliczeń (klasyczne i kwantowe) oraz rodzaju wyniku (dokładne i przybliżone).

Złożoność obliczeniowa i ograniczenia

Efektywność algorytmu ocenia się według czasu obliczeń w zależności od rozmiaru danych wejściowych, mierzona zgodnie z złożonością obliczeniową. Algorytmy działające w czasie wielomianowym uznaje się w teorii złożoności za efektywne. Jest to jednak kryterium asymptotyczne, które nie uwzględnia stałych współczynników ani stopnia wielomianu. W praktyce zależność ta bywa odwrócona: algorytm simpleks, nie działający w czasie wielomianowym w najgorszym przypadku, jest uznawany za efektywny i szeroko stosowany.

Klasa NP obejmuje problemy decyzyjne, których poprawne rozwiązanie da się zweryfikować w czasie wielomianowym. Problem decyzyjny nazywa się problemem NP-zupełnym, jeżeli należy do klasy NP i jest NP-trudny, czyli każdy problem z klasy NP można do niego zredukować w czasie wielomianowym. Do problemów NP-trudnych należy m.in. problem komiwojażera. Pytanie, czy P=NP, czyli czy istnieją wielomianowe algorytmy rozwiązywania problemów NP-zupełnych, należy do problemów milenijnych. Istnieją również problemy obliczeniowo nierozstrzygalne — Turing wykazał w pracy On Computable Numbers nierozstrzygalność problemu decyzyjnego (Entscheidungsproblem(inne języki)).

Algorytmy równoległe i obliczenia rozproszone

Wykorzystanie kart graficznych do obliczeń ogólnego przeznaczenia stało się istotnym nurtem obliczeń równoległych. Do obliczeń rozproszonych z udziałem ochotników służy otwarta platforma BOINC. W ramach tej platformy realizowano m.in. projekt SETI@home, w którym ochotnicze komputery analizowały dane obserwacji kosmicznych.

Algorytmy poza komputerami

Algorytm nie musi być wykonywany przez komputer. Może go wykonać człowiek, jak procedura z przykładu powyżej. Może też zostać zrealizowany przez urządzenie mechaniczne. Obliczenia realizuje się również w procesach molekularnych. W 1994 roku L. Adleman zademonstrował wykonanie obliczeń za pomocą cząsteczek DNA, rozwiązując instancję skierowanego problemu ścieżki Hamiltona.

Algorytmy genetyczne

 Osobny artykuł: Algorytm genetyczny.

Algorytmy genetyczne, oparte na doborze naturalnym i dziedziczności, służą do poszukiwania dobrych rozwiązań problemów optymalizacyjnych. Jakość rozwiązań ocenia się za pomocą funkcji przystosowania(inne języki). Populacje rozwiązań są powielane (selekcja), krzyżowane i modyfikowane przez mutacje, a najlepiej przystosowane jednostki mają największe szanse przejścia do kolejnej generacji.

Algorytmy kwantowe

 Osobny artykuł: Algorytm kwantowy.
Sfera Blocha — geometryczna reprezentacja dwupoziomowego układu kwantowego

Niektóre kryptosystemy, takie jak RSA, opierają się na trudności rozkładu liczby na czynniki pierwsze oraz obliczania logarytmów dyskretnych. Oba problemy uważane są za trudne dla komputerów klasycznych. Algorytm Shora rozwiązuje faktoryzację w czasie wielomianowym za pomocą komputera kwantowego. Komputery kwantowe wykorzystują kubity, superpozycję i interferencję kwantową.

Historia algorytmów

Pomnik al-Chuwarizmiego w Urgenczu

Algorytmy są znacznie starsze niż komputery. Najstarsze znane algorytmy zapisano na glinianych tabliczkach w matematyce babilońskiej ponad 4000 lat temu. W starożytnej Grecji opisano algorytm Euklidesa wyznaczania największego wspólnego dzielnika dwóch liczb oraz sito Eratostenesa. Al-Chuwarizmi, od którego nazwiska pochodzi nazwa pojęcia, nie był twórcą samej idei algorytmu.

W połowie lat 30. XIX wieku Charles Babbage opracował plany maszyny analitycznej, uważanej za prekursora nowoczesnych komputerów cyfrowych. Maszyny nigdy nie zbudowano, a Ada Lovelace, opisując w notach jej działanie, jest uznawana za pierwszą programistkę.

Pod koniec XIX wieku karty perforowane umożliwiły elektromechanicznym maszynom przetwarzanie dużych zbiorów danych. System Hermana Holleritha, oparty na elektrycznym odczytywaniu i sortowaniu kart perforowanych, posłużył do zliczania danych spisu ludności Stanów Zjednoczonych z 1890 roku, a firma Holleritha była jednym z zalążków IBM.

Replika maszyny Z3 w Deutsches Museum

W 1937 roku Alan Turing opublikował w „Proceedings of the London Mathematical Society” pracę On Computable Numbers, w której opisał matematyczny model obliczeń, dziś znany jako maszyna Turinga. Konrad Zuse ukończył w 1941 roku Z3, uznawany za pierwszy działający, swobodnie programowalny komputer, oparty na systemie binarnym.

W Stanach Zjednoczonych prace nad ENIAC rozpoczęto w 1943 roku, a maszynę ukończono w 1946 roku.

Fragmenty maszyny ENIAC w Moore School of Engineering and Applied Science

Ochrona prawna algorytmów

W Stanach Zjednoczonych sam algorytm, jako abstrakcyjna idea, nie podlega ochronie patentowej. W sprawie Alice Corp. v. CLS Bank International (2014) Sąd Najwyższy Stanów Zjednoczonych orzekł, że samo zrealizowanie abstrakcyjnej idei za pomocą komputera nie czyni wynalazku kwalifikowalnym do objęcia patentem.

W Europie art. 52 Europejskiej Konwencji Patentowej wyłącza spod patentowania m.in. odkrycia naukowe, metody matematyczne i programy komputerowe w zakresie, w jakim dotyczą ich „jako takich”. Zgodnie z wytycznymi EPO wyłączenie nie dotyczy programów komputerowych o charakterze technicznym — program komputerowy musi w trakcie wykonywania wywoływać dalszy skutek techniczny.

Zgodnie z unijną dyrektywą 2009/24/WE programy komputerowe podlegają ochronie prawnoautorskiej jako utwory literackie.

Zobacz też

Przypisy

  1. 1 2 Słownik terminologiczny informacji naukowej, red. Maria Dembowska, Zakład Narodowy imienia Ossolińskich, Wrocław 1979, s. 24.
  2. ↑ algorytm, [w:] Encyklopedia PWN [online], Wydawnictwo Naukowe PWN [dostęp 2017-03-11].
  3. ↑ T. H. Cormen, C. E. Leiserson, R. L. Rivest, C. Stein, Introduction to Algorithms, wyd. 3, MIT Press, Cambridge 2009, rozdz. 1 (ang.), ISBN 978-0-262-03384-8.
  4. ↑ algorithm, P. E. Black (red.), Dictionary of Algorithms and Data Structures, National Institute of Standards and Technology (ang.) [dostęp 2026-10-30].
  5. ↑ ALGORISMUS, Elektroniczny Słownik Łaciny Średniowiecznej w Polsce, Instytut Języka Polskiego PAN [dostęp 2026-10-30].
  6. ↑ D. E. Knuth, Sztuka programowania, t. 1, Wydawnictwa Naukowo-Techniczne, Warszawa 2002, ISBN 83-204-2540-9.
  7. 1 2 T. H. Cormen, C. E. Leiserson, R. L. Rivest, C. Stein, Introduction to Algorithms, wyd. 3, MIT Press, Cambridge 2009, rozdz. 5 (ang.), ISBN 978-0-262-03384-8.
  8. 1 2 T. H. Cormen, C. E. Leiserson, R. L. Rivest, C. Stein, Introduction to Algorithms, wyd. 3, MIT Press, Cambridge 2009, wstęp (ang.), ISBN 978-0-262-03384-8.
  9. 1 2 3 A. M. Turing, On Computable Numbers, with an Application to the Entscheidungsproblem, „Proceedings of the London Mathematical Society”, 1937, s. 230–265, doi:10.1112/plms/s2-42.1.230 (ang.) [dostęp 2026-10-30].
  10. ↑ T. H. Cormen, C. E. Leiserson, R. L. Rivest, C. Stein, Introduction to Algorithms, wyd. 3, MIT Press, Cambridge 2009, rozdz. 4 (ang.), ISBN 978-0-262-03384-8.
  11. ↑ T. H. Cormen, C. E. Leiserson, R. L. Rivest, C. Stein, Introduction to Algorithms, wyd. 3, MIT Press, Cambridge 2009, rozdz. 15 (ang.), ISBN 978-0-262-03384-8.
  12. ↑ T. H. Cormen, C. E. Leiserson, R. L. Rivest, C. Stein, Introduction to Algorithms, wyd. 3, MIT Press, Cambridge 2009, rozdz. 16 (ang.), ISBN 978-0-262-03384-8.
  13. ↑ backtracking, P. E. Black (red.), Dictionary of Algorithms and Data Structures, National Institute of Standards and Technology (ang.) [dostęp 2026-10-30].
  14. 1 2 J. D. Owens, M. Houston, D. Luebke, S. Green, J. E. Stone, J. C. Phillips, GPU computing, „Proceedings of the IEEE”, 2008, s. 879–899, doi:10.1109/JPROC.2008.917757 (ang.) [dostęp 2026-10-30].
  15. 1 2 3 P. W. Shor, Polynomial-Time Algorithms for Prime Factorization and Discrete Logarithms on a Quantum Computer, „SIAM Journal on Computing”, 1997, s. 1484–1509, doi:10.1137/S0097539795293172 (ang.) [dostęp 2026-10-30].
  16. 1 2 3 4 T. H. Cormen, C. E. Leiserson, R. L. Rivest, C. Stein, Introduction to Algorithms, wyd. 3, MIT Press, Cambridge 2009, rozdz. 34 (ang.), ISBN 978-0-262-03384-8.
  17. ↑ T. H. Cormen, C. E. Leiserson, R. L. Rivest, C. Stein, Introduction to Algorithms, wyd. 3, MIT Press, Cambridge 2009, rozdz. 29 (ang.), ISBN 978-0-262-03384-8.
  18. ↑ P vs NP Problem, Clay Mathematics Institute (ang.) [dostęp 2026-10-30].
  19. ↑ BOINC, University of California, Berkeley (ang.) [dostęp 2026-10-30].
  20. ↑ SETI@home, University of California, Berkeley (ang.) [dostęp 2026-10-30].
  21. 1 2 Charles Babbage, Encyclopaedia Britannica (ang.) [dostęp 2026-10-30].
  22. ↑ L. M. Adleman, Molecular computation of solutions to combinatorial problems, „Science”, 1994, s. 1021–1024, doi:10.1126/science.7973651 (ang.) [dostęp 2026-10-30].
  23. ↑ J. H. Holland, Adaptation in Natural and Artificial Systems, MIT Press, Cambridge 1992, ISBN 978-0-262-58111-0 (ang.).
  24. ↑ M. A. Nielsen, I. L. Chuang, Quantum Computation and Quantum Information, Cambridge University Press, Cambridge 2000, ISBN 978-0-521-63503-5 (ang.).
  25. 1 2 C. Bleakley, Ancient Algorithms, w: Poems That Solve Puzzles. The History and Science of Algorithms, Oxford University Press, 2020, doi:10.1093/oso/9780198853732.003.0001 (ang.) [dostęp 2026-10-30].
  26. ↑ Ada Lovelace, Encyclopaedia Britannica (ang.) [dostęp 2026-10-30].
  27. ↑ Herman Hollerith, Encyclopaedia Britannica (ang.) [dostęp 2026-10-30].
  28. ↑ Konrad Zuse, Deutsches Patent- und Markenamt (ang.) [dostęp 2026-10-30].
  29. ↑ ENIAC, Encyclopaedia Britannica (ang.) [dostęp 2026-10-30].
  30. ↑ Alice Corp. v. CLS Bank International, 573 U.S. 208 (2014), Oyez (ang.) [dostęp 2026-10-30].
  31. ↑ Konwencja o patencie europejskim, art. 52, European Patent Office (ang.) [dostęp 2026-10-30].
  32. ↑ Guidelines for Examination, G-II, 3.6, European Patent Office (ang.) [dostęp 2026-10-30].
  33. ↑ Dyrektywa 2009/24/WE, EUR-Lex (ang.) [dostęp 2026-10-30].

Linki zewnętrzne

Polskojęzyczne
Anglojęzyczne