Algorytm, systematyczna procedura, która daje - w skończonej liczbie kroków - odpowiedź na pytanie lub rozwiązanie problemu. Nazwa pochodzi od łacińskiego tłumaczenia Algoritmi de numero Indorum z IX-wiecznego muzułmańskiego matematyka al-Khwarizmi'ego „Al-Khwarizmi o hinduskiej sztuce rozrachunku”.
informatyka: Algorytmy i złożoność
Algorytm to specyficzna procedura rozwiązywania dobrze zdefiniowanego problemu obliczeniowego. Opracowanie i analiza algorytmów ma fundamentalne znaczenie
W przypadku pytań lub problemów z ograniczonym zestawem przypadków lub wartości algorytm zawsze istnieje (przynajmniej w zasadzie); składa się z tabeli wartości odpowiedzi. Zasadniczo udzielanie odpowiedzi na pytania lub problemy o nieskończonej liczbie przypadków lub wartości, takie jak „Czy liczba naturalna (1, 2, 3, …) jest liczbą pierwszą, nie jest tak proste”? lub „Jaki jest największy wspólny dzielnik liczb naturalnych a i b?” Pierwsze z tych pytań należy do klasy o nazwie decidable; algorytm, który daje odpowiedź tak lub nie, nazywa się procedurą decyzyjną. Drugie pytanie należy do klasy o nazwie computable; algorytm prowadzący do odpowiedzi na konkretną liczbę nazywa się procedurą obliczeniową.
Istnieją algorytmy dla wielu takich nieskończonych klas pytań; Elementy Euklidesa, opublikowane około 300 pne, zawierały jeden dla znalezienia największego wspólnego dzielnika dwóch liczb naturalnych. Każdy uczeń szkoły podstawowej jest wiercony długim podziałem, co jest algorytmem dla pytania „Po podzieleniu liczby naturalnej a przez inną liczbę naturalną b, jaki jest iloraz i reszta?” Zastosowanie tej procedury obliczeniowej prowadzi do odpowiedzi na rozstrzygające pytanie „Czy b dzieli a?” (odpowiedź brzmi tak, jeśli reszta to zero). Wielokrotne stosowanie tych algorytmów ostatecznie daje odpowiedź na rozstrzygające pytanie „Czy liczba pierwsza?” (odpowiedź brzmi „nie”, jeśli a jest podzielne przez jakąkolwiek mniejszą liczbę naturalną oprócz 1).
Czasami nie może istnieć algorytm rozwiązywania nieskończonej klasy problemów, szczególnie gdy pewne dalsze ograniczenia dotyczą przyjętej metody. Na przykład dwa problemy z czasów Euklidesa wymagające użycia tylko kompasu i prostej (nieoznakowanej linijki) - przecięcie kąta i zbudowanie kwadratu o powierzchni równej danemu kręgowi - były rozwiązywane przez wieki, zanim okazały się niemożliwe.. Na przełomie XIX i XX wieku wpływowy niemiecki matematyk David Hilbert zaproponował matematykom 23 problemy do rozwiązania w nadchodzącym wieku. Drugi problem z jego listy wymagał zbadania spójności aksjomatów arytmetyki. Większość matematyków nie miała wątpliwości co do ostatecznego osiągnięcia tego celu do 1931 r., Kiedy urodzony w Austrii logik Kurt Gödel wykazał zaskakujący wynik, że muszą istnieć zdania arytmetyczne (lub pytania), których nie można udowodnić ani obalić. Zasadniczo każda taka propozycja prowadzi do procedury determinacji, która nigdy się nie kończy (warunek znany jako problem zatrzymania). Próbując ustalić, które twierdzenia są nierozwiązywalne, angielski matematyk i logik Alan Turing rygorystycznie zdefiniował luźno rozumianą koncepcję algorytmu. Chociaż Turing ostatecznie udowodnił, że muszą istnieć niezdecydowane twierdzenia, jego opis zasadniczych cech jakiejkolwiek maszyny algorytmu ogólnego przeznaczenia lub maszyny Turinga stał się podstawą informatyki. Dziś kwestie rozstrzygalności i obliczalności są kluczowe w projektowaniu programu komputerowego - specjalnego rodzaju algorytmu.
