Algorytm

Algorytm to ograniczony zbiór jasno określonych kroków, które są niezbędne do zrealizowania określonego zadania. Stanowi on metodę działania prowadzącą do rozwiązania problemu i może być przedstawiony w formie schematu blokowego.

Pojęcie „algorytm” wywodzi się od łacińskiego terminu algorithmus, który odnosi się do wykonywania działań przy użyciu liczb arabskich (w przeciwieństwie do abacism, czyli obliczeń za pomocą abakusa). Termin ten z kolei pochodzi od „Algoritmi”, zlatynizowanej formy imienia al-Chwarizmi – perskiego matematyka z IX wieku.

Algorytmy mają na celu przekształcenie systemu z pewnego stanu początkowego do stanu końcowego, który jest pożądany. Dziedziną zajmującą się badaniem algorytmów jest algorytmika. Algorytm może być również zaimplementowany w formie programu komputerowego.

Przykładem algorytmu, który można spotkać w codziennym życiu, jest przepis kulinarny. Na przykład, aby przygotować bigos, należy w odpowiedniej kolejności oraz z zachowaniem określonych odstępów czasowych (imperatyw czasowy) dodawać różne rodzaje kapusty oraz inne składniki. Istnieje wiele przepisów, które prowadzą do uzyskania podobnego dania, jednak ten przykład ma charakter jedynie poglądowy, ponieważ język przepisów kulinarnych nie jest jasno zdefiniowany. Algorytmy są zazwyczaj formułowane w sposób precyzyjny, oparty na języku matematyki.

W niektórych krajach, takich jak Stany Zjednoczone, algorytmy mogą być opatentowane, jeśli są zaimplementowane w praktycznym celu. Krytycy tego podejścia argumentują, że patentowanie algorytmów hamuje rozwój informatyki, ponieważ jeden producent może zdobyć monopol na tworzenie oprogramowania dla określonych typów plików (jak miało to miejsce w przypadku GIF). Wiele firm zajmujących się technologią prowadzi spory prawne dotyczące praw do niektórych patentów. Zwolennicy patentów na oprogramowanie z kolei wskazują na prawo własności intelektualnej, które zakłada, że program jest intelektualną własnością twórcy.

Definicja klasyczna

Algorytm to jednoznaczny przepis przetwarzania danych wejściowych na dane wyjściowe w skończonym czasie.

W analizie lub projektowaniu algorytmu zakłada się zazwyczaj, że dane wejściowe są poprawne; czasami istotną częścią algorytmu jest nie tylko przetwarzanie, ale także weryfikacja danych.

Zgodnie z zasadą jednoznaczności, algorytm zdefiniowany klasycznie dla tego samego zestawu początkowych danych zawsze zwróci taki sam wynik.

Przykład

Aby znaleźć największą liczbę w niepustej, nieposortowanej liście losowych liczb, można zastosować wiele metod; jednym z najszybszych jest opisany poniżej algorytm. Niech indeks wskazuje aktualny element listy (jeśli lista jest numerowana, może on oznaczać np. jej numer), a maksimum to największa dotychczas znaleziona wartość.

1. Niech indeks wskazuje na pierwszy element (początek) listy.

2. Niech maksimum przyjmuje wartość elementu listy wskazywanego przez indeks (tzn. pierwszego).

3. Jeżeli wartość elementu listy wskazywanego przez indeks jest większa od wartości maksimum, to przypisz maksimum wartość elementu wskazywanego przez indeks.

4. Niech indeks wskazuje na kolejny element listy; jeśli nie jest to możliwe (tzn. indeks wskazuje na ostatni element listy, czyli jej koniec), przejdź do punktu 6.

5. Wróć do punktu 3.

6. Koniec.

Wdrożenie tego algorytmu sprawi, że największa liczba na wspomnianej liście stanie się wartością maksimum. Dodatkowym atutem jest to, że algorytm ten działa dla list o dowolnej długości, ponieważ nie zależy od liczby elementów listy, lecz jedynie od operacji przejścia do następnego elementu. Niemożność wskazania kolejnego elementu jest równoznaczna z tym, że 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 oraz alpha-beta
algorytmy sortowania
algorytm unifikacji

Klasyfikacja algorytmów

Istnieje wiele sposobów na podział algorytmów na różne grupy, jednak temat ten budzi kontrowersje.

Podstawowe paradygmaty tworzenia algorytmów komputerowych to:

dziel i zwyciężaj – dzielimy problem na mniejsze części, które następnie dzielimy dalej, aż ich rozwiązania staną się oczywiste
programowanie dynamiczne – problem dzielony jest na mniejsze, których ważność jest oceniana, a wyniki analizy prostszych zagadnień wykorzystywane są do rozwiązania głównego problemu
metoda zachłanna – nie analizujemy dokładnie podproblemów, lecz wybieramy najbardziej obiecującą opcję w danym momencie
programowanie liniowe – oceniamy rozwiązanie problemu poprzez pewną funkcję jakości i szukamy jej minimum
wyszukiwanie wyczerpujące – przeszukujemy zbiór danych, aż znajdziemy rozwiązanie
heurystyka – na podstawie doświadczenia tworzony jest algorytm działający 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 korzysta z wspólnych bibliotek standardowych procedur, które są wywoływane w razie potrzeby.
praca sekwencyjna – wykonywanie poszczególnych procedur algorytmu zgodnie z kolejnością ich wywołań; w danym momencie działa tylko jedna procedura.
praca wielowątkowa – procedury są wykonywane sekwencyjnie, ale kolejność ich realizacji jest trudna do przewidzenia dla programisty.
praca równoległa – wiele procedur działa jednocześnie, wymieniając się danymi.
rekurencja – procedura lub funkcja wywołuje samą siebie, aż do uzyskania wyniku lub wystąpienia błędu.
obiektowość – procedury i dane łączą się w klasy reprezentujące kluczowe elementy algorytmu oraz stan wewnętrzny systemu, który je wykonuje.
algorytm probabilistyczny – działa z bardzo wysokim prawdopodobieństwem, ale nie daje pewnego wyniku.

Algorytmy równoległe

Jednym z podejść do rozwiązywania złożonych problemów jest wykorzystanie algorytmów równoległych. Oznacza to, że program jest wykonywany nie tylko raz na jednym procesorze, ale wielokrotnie równolegle na wielu różnych maszynach. Takie podejście stosowane jest od lat w superkomputerach, jednak jego realizacja jest bardzo kosztowna. Nowym pomysłem jest wykorzystanie sieci zwykłych komputerów tworzących klaster. Całe zadanie jest wtedy rozdzielane pomiędzy wiele maszyn, obliczając równolegle z wykorzystaniem tysięcy procesorów. Czasami taką potężną sieć rozproszoną określa się mianem grid. Przykładem jej zastosowania jest program SETI@home, który analizuje dane z nasłuchu kosmosu przy pomocy dziesiątek tysięcy komputerów należących do zwykłych użytkowników. Komputery są podłączone do Internetu, przez który przesyłają wyniki pracy uruchomionych na nich aplikacji. Rozwinięciem tego rozwiązania jest projekt BOINC@home, który obejmuje wiele projektów zajmujących się różnymi dziedzinami nauki, nie tylko ścisłymi.

Obecnie algorytmy równoległe mogą być wykorzystywane na standardowych komputerach domowych, ponieważ większość z nich ma procesory wielordzeniowe, które w uproszczeniu są połączeniem kilku procesorów w jeden. Po roku 2010 popularność zyskało nowe podejście do obliczeń równoległych, polegające na wykorzystaniu kart graficznych (GPGPU). Niektóre projekty z BOINC@home oraz projekt z biologii molekularnej Folding@home umożliwiają stosowanie kart graficznych, a nawet kilku w jednym komputerze, do realizacji obliczeń rozproszonych. Dzięki temu można wykorzystać ogromną liczbę (do kilku tysięcy) procesorów kart graficznych działających równolegle.

Innowacyjnym pomysłem na implementację algorytmów równoległych jest użycie DNA. W jednej kropli wody znajduje się miliony cząsteczek tego kwasu. Jeśli zsyntetyzujemy je tak, aby wykonywały dany algorytm, to w ułamku sekundy, dzięki reakcjom chemicznym, komputer oparty na DNA znajdzie rozwiązanie skomplikowanego problemu. Przykładem są bakterie, które zostały zaprogramowane do rytmicznego emitowania światła. Dziedziną nauki zajmującą się algorytmami w kontekście biologii jest bioinformatyka.

Algorytmy sztucznej inteligencji

Wiele problemów związanych z codziennym życiem to tzw. problemy NP-trudne. Przykładami są znajdowanie najkrótszej trasy łączącej kilka miast lub optymalne pakowanie plecaka. Oznacza to, że algorytmy potrafią radzić sobie z takimi problemami jedynie w przybliżeniu lub w bardzo specyficznych przypadkach. Robot sterowany algorytmem niedeterministycznym (przybliżonym) nie jest w stanie znaleźć najkrótszej drogi w skomplikowanym środowisku, mimo że dla człowieka może być ona oczywista.

Inżynierowie starają się rozwiązywać problemy NP-trudne poprzez naśladowanie organizmów żywych. Jeśli nie można sformułować jasnego algorytmu do rozwiązania danego problemu, można wyposażyć maszynę w zdolność do samodzielnego uczenia się. Tą problematyką zajmuje się dziedzina znana jako sztuczna inteligencja. Należy jednak pamiętać, że podejście to nie jest równoznaczne z ludzką inteligencją. Maszyny naśladują jedynie pewne cechy istot żywych, ale nie są w stanie dorównać im w wielu aspektach.

Algorytmy genetyczne

Algorytmy genetyczne to grupa algorytmów służących do poszukiwania najlepszych rozwiązań dla danego problemu. Ich działanie opiera się na obserwacji praw natury oraz przeniesieniu ich na grunt matematyki i informatyki. W podstawie algorytmów genetycznych leży dobór naturalny oraz dziedziczność. Najlepiej przystosowane jednostki (z rozwiązaniami bliskimi poprawnym) są powielane oraz krzyżowane, aby wzmocnić przekazywanie informacji. Wiele rzeczywistych problemów można efektywnie rozwiązać w ten sposób.

Algorytmy kwantowe

Niektóre algorytmy szyfrowania, takie jak RSA, opierają się na trudności faktoryzacji liczb. Dla tego problemu nie istnieje znany algorytm wielomianowy do wykorzystania na klasycznych komputerach opartych na półprzewodnikach. Natomiast algorytmy działające na komputerach kwantowych mogą wykorzystywać qubity oraz zjawisko splatana. Na takich komputerach możliwe jest rozkładanie liczb na czynniki pierwsze w czasie wielomianowym, na przykład za pomocą algorytmu Shora.

Jednakże dużym wyzwaniem dla komputerów kwantowych jest dekoherencja ich stanów, co może prowadzić do utraty danych. Potencjalnym rozwiązaniem może być wykorzystanie splątania do teleportacji stanu kwantowego na inne cząstki elementarne. W związku z tym wielu naukowców pracuje nad implementacją algorytmów kryptografii kwantowej, takich jak szyfrowanie danych z użyciem splątanych fotonów. Obecnie kierunki prac nad komputerami kwantowymi obejmują:

fotonika – komputery oparte na fotonach
spinotronika – komputery operujące spinem elektronów zamiast napięciem

Ograniczenia algorytmów

Algorytm komputerowy musi w końcu zakończyć swoje działanie. Oznacza to, że problem musi zostać rozwiązany w dostępnych zasobach obliczeniowych w skończonym czasie. Jeżeli czas obliczeń algorytmu, dla rosnącego zbioru danych, rośnie szybciej niż jakakolwiek funkcja wielomianowa, to uznaje się, że nie jest on praktycznie obliczalny. Jedną z klas problemów, dla których nie znamy algorytmów wielomianowych, są problemy NP-trudne. Jeśli istnieje algorytm wielomianowy do weryfikacji poprawności rozwiązania problemu NP-trudnego, nazywamy go NP-zupełnym. Pytanie, czy P=NP, czyli czy istnieją szybkie algorytmy do rozwiązywania problemów NP-zupełnych, pozostaje jednym z najbardziej palących pytań we współczesnej informatyce. Ponadto istnieją problemy, które nie mogą być rozwiązane przez żaden algorytm.

Implementacja algorytmów

Algorytmy komputerowe

Komputery przetwarzają informacje przy użyciu algorytmów. Program jest algorytmem zapisanym w języku zrozumiałym dla maszyny (kodzie maszynowym). Każdy poprawny kod maszynowy można przełożyć na zestaw instrukcji dla teoretycznego modelu komputera, jakim jest maszyna Turinga.

Algorytmy zazwyczaj operują na danych wejściowych, przekształcając je w dane wyjściowe. Informacje zapisane w pamięci komputera traktowane są jako jego stan wewnętrzny. Niektóre algorytmy mają na celu jedynie przeprowadzanie komputera z jednego stanu wewnętrznego do innego.

Każdy algorytm komputerowy musi być wprowadzony do systemu w precyzyjnie zdefiniowanym języku. Ludzie często komunikują się, przesyłając wieloznaczne informacje. Komputery mogą reagować tylko na całkowicie jednoznaczne instrukcje. Jeśli algorytm da się wykonać na maszynie o dostępnych zasobach obliczeniowych i pamięci oraz w akceptowalnym czasie, uznaje się go za obliczalny.

Poprawne działanie większości algorytmów w komputerach opiera się na spełnieniu zestawu warunków. Jeśli którykolwiek z nich nie zostanie spełniony, program kończy się komunikatem o błędzie. Czasami podczas implementacji algorytmu kluczowy warunek może zostać pominięty. Na przykład, w programie dzielącym dwie liczby użytkownik może zlecić dzielenie przez zero. Działanie aplikacji, która nie sprawdzi warunku „czy dzielnik jest różny od zera”, zostanie przerwane przez system operacyjny.

Algorytmy poza komputerami

Implementacja algorytmu ogólnie odnosi się do podobieństwa między algorytmem opisanym w ludzkim języku a fizycznym zjawiskiem lub procesem. Czasami algorytm może być podstawą budowanego przez ludzi urządzenia, takiego jak komputer. Możemy również mówić o implementacji, gdy pewien system zachowuje się podobnie do algorytmu. Na przykład, mózg ptaka implementuje arytmetykę w formie sieci neuronowej, co pozwala zwierzęciu na porównywanie pewnych odstępów czasu. W przypadku maszyn algorytm może być zaimplementowany jako sieć połączeń elektrycznych, pneumatycznych lub mechanicznych. Przykładem może być analogowy regulator obrotów z pierwszych silników parowych, realizujący algorytm proporcjonalny. W takim ujęciu sukces nie oznacza zatrzymania algorytmu, lecz utrzymywanie pewnego stanu systemu. Możemy stwierdzić, że algorytm utrzymania życia działa poprawnie, aż do śmierci organizmu. Poprawny algorytm powinien utrzymywać pewne parametry żywej istoty (np. temperaturę) w optymalnym zakresie.

Algorytm a opisujący go język

Warto zauważyć różnicę między algorytmem, który jest niezależnym od jego implementacji przepisem, a programem, który może być zinterpretowany i wykonany przez komputer. Poniższe fragmenty programów stanowią realizację tego samego algorytmu sumującego trzy trójki:

Dodawanie w języku C:

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

Język C, zapis proceduralny z zastosowaniem rekurencji:

Asembler x86:

Przykłady te zostały napisane w różnych językach programowania, stosujących różne poziomy abstrakcji, przy czym zapis w asemblerze jest na najniższym poziomie abstrakcji, co oznacza, że jest najbliżej „prawdziwego”, wykonywanego bezpośrednio przez procesor komputera, kodu.

Błędy w implementacji

Wciąż rozwijana inżynieria oprogramowania pozwala na tworzenie aplikacji, których kod źródłowy liczy setki tysięcy linii, jednocześnie zachowując kontrolę nad całością projektu, co minimalizuje liczbę błędów podczas implementacji algorytmów.

Historia algorytmów

Początki

Pojęcie algorytmu pochodzi od nazwiska arabskiego matematyka z IX wieku, Muhammada ibn Musy al-Chuwarizmiego. Początkowo termin algorytm odnosił się do czynności koniecznych do wykonania obliczeń z użyciem dziesiętnego systemu liczbowego. Obecne znaczenie tego terminu jako zbioru ścisłych reguł powstało w miarę rozwoju matematyki i techniki. Wynalezienie zasad umożliwiających obliczanie parametrów konstruowanych maszyn przyczyniło się do rewolucji przemysłowej, która rozpoczęła się pod koniec XVIII wieku. Jednak przełom miał miejsce dopiero w momencie, gdy zbudowano maszyny zdolne do realizacji prostych algorytmów.

Ogromny postęp w tej dziedzinie dokonał Charles Babbage w 1842 roku, formułując ideę maszyny analitycznej, zdolnej do realizacji złożonych algorytmów matematycznych. W jego pracy wspierała go Ada Lovelace, która przetłumaczyła dla niego prace włoskiego matematyka dotyczące algorytmu obliczania liczb Bernoulliego. Prace Lovelace odnoszące się do implementacji tego algorytmu na maszynie różnicowej zawierały opis swoistego języka programowania. Niestety, Babbage nigdy nie zrealizował swojego mechanicznego komputera. Programy stworzone przez Lovelace zostały przetestowane na modelu maszyny różnicowej wykonanym w XX wieku i okazały się poprawne.

Rozwój maszyn liczących

Wraz z wynalezieniem kart perforowanych pod koniec XIX wieku elektro-mechaniczne maszyny zyskały zdolność realizacji algorytmów przetwarzających ogromne zbiory danych. Karty perforowane stały się źródłem danych przetwarzanych przez proste algorytmy sumujące, a jako wyjście służyły odpowiednie zegary. Ogromny postęp w tej dziedzinie zawdzięczamy firmie, która była protoplastą IBM, zbudowanej do realizacji spisu ludności w Stanach Zjednoczonych.

W XX wieku postęp w elektronice pozwolił na budowę maszyn analogowych, które mogły odtwarzać pewne algorytmy matematyczne wewnętrznie. Potrafiły one dokonywać operacji arytmetycznych oraz różniczkować i całkować.

Komputery

Zanim powstały pierwsze komputery, istniały już solidne fundamenty teoretycznej informatyki. Algorytm wyrażony w najprostszym możliwym języku okazał się najlepszy dla tych urządzeń. Na początku lat 30. XX wieku opracowano kilka niezależnych matematycznych modeli do wykonywania algorytmów. Najsłynniejszym z nich jest maszyna Turinga, zaprezentowana w pracy „On Computable Numbers” autorstwa Alana Turinga, brytyjskiego matematyka uznawanego za ojca informatyki. Zauważono również, że wszystkie te modele są równoważne, co oznacza, że można w nich wyrazić dowolny algorytm i zasymulować działanie jednego modelu na innym (patrz: kompletność Turinga). Okazało się, że nawet najbardziej złożone algorytmy można opisać prostym matematycznym zapisem i kilkoma elementarnymi operacjami. Maszyna Turinga składała się z głowicy czytająco-piszącej przesuwającej się po nieskończonej taśmie. W każdym kroku mogła zmieniać wartość danej komórki taśmy, przesunąć się w lewo lub prawo oraz zmieniać swój stan.

Pierwszy mechaniczny komputer zdolny, jak się później okazało, do wykonywania wszystkich algorytmów, powstał w 1936 roku w Niemczech. Nazywał się Z1, a jego twórcą był niemiecki inżynier Konrad Zuse, który zaprojektował swoją maszynę niezależnie od brytyjskich i amerykańskich matematyków. Z powodu dużej awaryjności w 1941 roku ukończył jej wersję opartą na układach przekaźnikowych, czyli Z3, która znalazła zastosowanie w projektowaniu skrzydeł samolotów. Z3 miała wiele cech współczesnego komputera; wszystkie liczby były reprezentowane w systemie binarnym, programy wprowadzano na kartach perforowanych, a do wprowadzania danych służyła klawiatura. W Wielkiej Brytanii i Stanach Zjednoczonych powstały pierwsze komputery, zbudowane na początku lat 40., które miały ściśle określone zadanie łamania niemieckich szyfrów oraz wykonywania obliczeń na potrzeby wojska. Dopiero w 1944 roku skonstruowano tam programowalną maszynę zdolną do realizacji dowolnych algorytmów, ENIAC. Pracowała ona w systemie dziesiętnym, a programowanie odbywało się przez przełączanie odpowiednich kabli.

W ostatnich trzydziestu latach, dzięki upowszechnieniu komputerów osobistych, informatyka stała się bardzo istotną gałęzią gospodarki. Na całym świecie pracują miliony programistów zajmujących się tworzeniem oraz doskonaleniem oprogramowania czy poszukiwaniem nowych, efektywniejszych algorytmów. Z uwagi na oparcie funkcjonowania całego społeczeństwa na komputerach, coraz większą wagę przykłada się do wyszukiwania błędów w implementacjach lub założeniach algorytmów, co jest procesem trudnym do zautomatyzowania, wymagającym żmudnej pracy zespołów programistów i hakerów.

Zobacz też

dowód poprawności algorytmu
struktura danych

Przypisy

Bibliografia

Donald E. Knuth: Sztuka programowania. Grzegorz Jakacki (tłum.). T. 1. Warszawa: Wydawnictwa Naukowo-Techniczne, 2002. ISBN 83-204-2540-9. OCLC 749477969.