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. Można go przedstawić na schemacie blokowym.
thumb|Wczesne użycie słowa algorytm w książce Bernarda Wojewódki Algorithm To iest, Nauka liczby po Polsku 1602. Słowo „algorytm” pochodzi od łacińskiego słowa algorithmus (lub algorismus), oznaczającego wykonywanie działań za pomocą liczb arabskich (w odróżnieniu od abacism – za pomocą abakusa), które z kolei wzięło się od nazwy „Algoritmi”, zlatynizowanej wersji nazwiska „al-Chwarizmi” Abu Abdullaha Muhammada ibn Musy al-Chuwarizmiego, matematyka perskiego z IX wieku.
Zadaniem algorytmu jest przeprowadzenie systemu 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 (między innymi Stanach Zjednoczonych) algorytmy mogą zostać opatentowane, jeżeli zostaną zaimplementowane w jakimś praktycznym celu. Przeciwnicy tego podejścia twierdzą, że patentowanie algorytmów spowalnia rozwój informatyki, bo jeden producent może uzyskać monopol na pisanie oprogramowania tworzącego pewne typy plików (jak było to w przypadku GIF). Wiele koncernów komputerowych prowadzi między sobą spory prawne dotyczące praw własności do niektórych patentów. Kontrargumentem zwolenników patentów na oprogramowanie jest prawo własności intelektualnej (którą jest na przykład utwór muzyczny, będący wytworem intelektu i pracy muzyka), zakładające, że program jest intelektualną własnością twórcy.
Definicja klasyczna Algorytm – jednoznaczny przepis obliczenia w skończonym czasie pewnych danych wejściowych do pewnych danych wynikowych.
Zazwyczaj przy analizowaniu bądź projektowaniu algorytmu zakłada się, że dostarczane dane wejściowe są poprawne, czasem istotną częścią algorytmu jest nie tylko przetwarzanie, ale i weryfikacja danych.
Zgodnie z założeniem o jednoznaczności – dla identycznego zestawu danych początkowych, algorytm zdefiniowany klasycznie zawsze zwróci identyczny wynik.
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 poniżej. Niech indeks wskazuje aktualnie badany element listy (jeśli jest ona numerowana, może on oznaczać np. jej numer), a maksimum oznacza największą dotychczas znalezioną wartość. Niech indeks wskazuje na pierwszy element (początek) listy. Niech maksimum zawiera wartość elementu listy wskazywanego przez indeks (tzn. pierwszego). Jeżeli zawartość elementu listy wskazywanego przez indeks jest większa od zawartości maksimum, to przypisz maksimum wartość elementu wskazywanego przez indeks. Niech indeks wskazuje kolejny element listy; jeśli to niemożliwe (tzn. indeks wskazuje ostatni element listy, czyli jej koniec), przejdź do punktu 6. Wróć do punktu 3. Koniec.
Wykonanie tego algorytmu spowoduje, że największa liczba na wspomnianej liście będzie wartością maksimum. Dodatkowym atutem jest fakt, iż algorytm ten działa dla list dowolnej długości, ponieważ nie wykorzystuje on liczby elementów listy, lecz tylko tzw. operację następnika elementu 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.
Inne przykłady algorytm Euklidesa algorytm Fermata algorytm Luhna algorytm mrówkowy algorytmy kompresji algorytmy kryptograficzne algorytmy przeszukiwania drzew: min-max i alpha-beta algorytmy sortowania algorytm unifikacji
Klasyfikacja algorytmów Istnieje wiele różnych sposobów podziału algorytmów na grupy, jednak problem ten wzbudza kontrowersje.
Podstawowe paradygmaty tworzenia algorytmów komputerowych: dziel i zwyciężaj – dzielimy problem na kilka mniejszych, a te znowu dzielimy, aż ich rozwiązania staną się oczywiste programowanie dynamiczne – problem dzielony jest na kilka, ważność każdego z nich jest oceniana i po pewnym wnioskowaniu wyniki analizy niektórych prostszych zagadnień wykorzystuje się do rozwiązania głównego problemu metoda zachłanna – nie analizujemy podproblemów dokładnie, tylko wybieramy najbardziej obiecującą w danym momencie drogę rozwiązania programowanie liniowe – oceniamy rozwiązanie problemu przez pewną funkcję jakości i szukamy jej minimum wyszukiwanie wyczerpujące – przeszukujemy zbiór danych, aż do odnalezienia rozwiązania heurystyka – człowiek na podstawie swojego doświadczenia tworzy algorytm, który działa w najbardziej prawdopodobnych warunkach; rozwiązanie zawsze jest przybliżone.
Najważniejsze techniki implementacji algorytmów komputerowych to: proceduralność – algorytm dzieli się na szereg podstawowych procedur. Wiele algorytmów ma wspólne biblioteki standardowych procedur, z których są one wywoływane w razie potrzeby. praca sekwencyjna – wykonywanie poszczególnych procedur algorytmu, według kolejności ich wywołań; naraz pracuje tylko jedna procedura praca wielowątkowa – procedury wykonywane są sekwencyjnie, lecz kolejność ich wykonania jest trudna do przewidzenia dla programisty praca równoległa – wiele procedur wykonywanych jest w tym samym czasie, wymieniają się one danymi rekurencja – procedura lub funkcja wywołuje sama siebie, aż do uzyskania wyniku lub błędu obiektowość – procedury i dane łączy się w pewne klasy reprezentujące najważniejsze elementy algorytmu oraz stan wewnętrzny wykonującego je systemu algorytm probabilistyczny – działa poprawnie z bardzo wysokim prawdopodobieństwem, ale wynik nie jest pewny.
Algorytmy równoległe
Jednym ze sposobów rozwiązywania złożonych problemów jest zastosowanie algorytmów równoległych. Oznacza to, że program nie jest wykonywany tylko jeden raz na jednym procesorze, ale wielokrotnie równolegle na wielu różnych maszynach. Podejście takie jest stosowane od lat w superkomputerach, jednak w takiej realizacji jest ono bardzo kosztowne. Nowym pomysłem jest tutaj zastosowanie sieci zwykłych komputerów tworzących klaster. Całe zadanie jest wtedy rozdzielane na wiele maszyn i obliczane równolegle przy pomocy tysięcy procesorów. Czasami taką potężną sieć rozproszoną nazywa się grid. Przykładem jej zastosowania może być program SETI@home, gdzie dane z nasłuchu kosmosu analizują dziesiątki tysięcy komputerów należących do zwykłych użytkowników. Maszyny są podłączone do Internetu, przez który przesyłają wyniki pracy uruchomionych na nich aplikacji. Rozwinięciem tego rozwiązania jest projekt parasolowy BOINC@home, który obejmuje kilkadziesiąt tego typu projektów co SETI@home, zajmujących się zagadnieniami z wielu dziedzin nauki, nie tylko ścisłych.
Obecnie algorytmy równoległe mogą być wykorzystywane na zwykłych domowych komputerach, ponieważ ogromna większość z nich posiada procesory wielordzeniowe, które w uproszczeniu są połączeniem kilku procesorów w jeden. Po roku 2010 rozpowszechniło się nowe podejście do obliczeń równoległych polegające na wykorzystywaniu w tym celu kart graficznych; nosi ono nazwę GPGPU. Kilka projektów z BOINC@home oraz projekt z zakresu biologii molekularnej Folding@home pozwala na zastosowanie karty graficznej, a nawet kilku zamontowanych w jednym komputerze, do realizacji obliczeń rozproszonych. Umożliwia to wykorzystanie ogromnej liczby (do kilku tysięcy) procesorów karty graficznej działających równolegle.
Nowym pomysłem na implementację algorytmów równoległych jest wykorzystanie do tego celu DNA. W jednej kropli wody znajdują się miliony cząstek tego kwasu. Jeżeli zsyntetyzujemy je tak, aby wykonywały pewien algorytm, to w ułamku sekundy potrzebnym na reakcje chemiczne komputer oparty na DNA znajdzie rozwiązanie bardzo złożonego problemu. Przykładem są tutaj bakterie, które zaprogramowano, aby rytmicznie emitowały światło. Dziedziną nauki zajmującą się algorytmami w połączeniu z biologią jest bioinformatyka.
Algorytmy sztucznej inteligencji Wiele problemów związanych z codziennym życiem to problemy NP-trudne. Przykładami ich mogą być znajdowanie najkrótszej trasy łączącej pewną liczbę miast lub optymalne pakowanie plecaka. Oznacza to, że algorytmy mogą radzić sobie z takimi problemami tylko w przybliżeniu lub w bardzo szczególnej sytuacji. Sterowany algorytmem niedeterministycznym (przybliżonym) robot nie potrafi odnaleźć najkrótszej drogi w bardzo złożonym środowisku, mimo że dla człowieka może być ona oczywista.
Inżynierowie próbują rozwiązywać problemy NP-trudne przez naśladowanie żywych organizmów. Jeżeli nie udaje się sformułować jasnego algorytmu rozwiązującego dany problem, można maszynę wyposażyć w zdolność do samodzielnego uczenia się. Zagadnieniem tym zajmuje się dział określany jako sztuczna inteligencja. Tego podejścia nie należy mylić z ludzką inteligencją. Maszyny naśladują tylko pewne cechy istot żywych, ale na razie nie są w stanie im dorównać na wielu polach.
Algorytmy genetyczne
Jest to cała grupa algorytmów służąca do poszukiwania najlepszych rozwiązań danego problemu. Zasada ich działania opiera się na obserwacji praw natury oraz przeniesieniu ich na grunt matematyki i informatyki. U podstaw algorytmów genetycznych znajduje się dobór naturalny oraz dziedziczność. Najlepiej przystosowane jednostki (niosące rozwiązania zbliżone do właściwego) są powielane oraz krzyżowane z sobą w celu powielenia informacji. Bardzo wiele rzeczywistych problemów można rozwiązać w ten sposób.
Algorytmy kwantowe
Niektóre algorytmy szyfrowania (np. RSA) opierają się na trudności rozkładu liczby na czynniki pierwsze (faktoryzacja). Dla tego problemu nie jest znany algorytm wielomianowy, którego można by użyć na klasycznym komputerze, czyli opartym na elementach półprzewodnikowych. Natomiast algorytmy zaimplementowane na komputerach kwantowych, w odróżnieniu od komputerów elektronicznych opartych na bitach, mogą posługiwać się kubitami oraz zjawiskiem splątania. Na tego typu komputerach możliwy jest rozkład liczby na czynniki pierwsze w czasie wielomianowym np. za pomocą algorytmu Shora.
Należy jednak mieć na uwadze, że dużym problemem komputerów kwantowych jest dekoherencja ich stanów – w ten sposób bardzo łatwo może dojść do utraty danych. Rozwiązaniem może być tutaj wykorzystanie splątania do teleportacji stanu kwantowego na kolejne cząstki elementarne. W związku z tym wielu naukowców pracuje już dziś nad implementacją algorytmów kryptografii kwantowej. Przykładem tego jest szyfrowanie danych z wykorzystaniem splątanych fotonów. Obecnie kierunki prac nad komputerami kwantowymi to: fotonika – komputery oparte na fotonach, spinotronika – komputery operujące spinem elektronów zamiast napięciem.
Ograniczenia algorytmów