Algorytm – w
matematyce
oraz
informatyce
skończony, uporządkowany 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
[1].
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
lub dla innego
urządzenia
. Kiedy podczas tego procesu programista popełni
błąd
(
ang.
bug), może to doprowadzić do poważnych konsekwencji np. błędy w implementacji algorytmów bezpieczeństwa mogą ułatwić popełnienie
przestępstwa 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ą
prawnicze
spory 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.
Algorytmy komputerowe
Implementacja
Komputery przetwarzają przekazywane im informacje z wykorzystaniem algorytmów. Program jest algorytmem zapisanym w języku zrozumiałym dla maszyny (
kodzie maszynowym
). Każdy poprawny kod maszynowy da się przełożyć na zestaw instrukcji dla teoretycznego modelu komputera –
maszyny Turinga
.
Zwykle algorytmy pracują na danych wejściowych i uzyskują z nich dane wyjściowe. Informacje zapisane w pamięci maszyny traktuje się jako jej stan wewnętrzny. Niektóre algorytmy mają za zadanie wyłącznie przeprowadzanie komputera z jednego stanu wewnętrznego do innego.
Każdy algorytm komputerowy musi być wprowadzony do komputera w bardzo rygorystycznie zdefiniowanym
języku
. Ludzie często komunikując się przesyłają między sobą
informację
wieloznaczne. Komputery mogą reagować tylko na całkowicie jednoznaczne instrukcje. Jeżeli dany algorytm da się wykonać na maszynie o dostępnej mocy obliczeniowej i pamięci oraz akceptowalnym czasie, to mówi się że jest obliczalny.
Poprawne działanie większości algorytmów implementowanych w komputerach opiera się na kolejnej realizacji pewnego zestawu warunków. Jeżeli któryś z nich nie zostanie spełniony, to program kończy się komunikatem błędu. Czasami podczas implementacji algorytmu ważny warunek zostanie pominięty. Dla przykładu, mamy program dzielący przez siebie dwie liczby. Użytkownik poleca wykonać
dzielenie
przez
zero
. Działanie aplikacji, która nie sprawdzi warunku “dzielnik nierówny zero”, zostanie przerwane przez system operacyjny komputera.
Warianty definicji
Istnieje wiele, nie zawsze równoważnych, definicji algorytmu.
- Ta sekcja jest . Jeśli możesz, .
Definicja klasyczna
- Algorytm to jednoznaczny przepis przetworzenia 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 przetworzenie, 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
Np. wzór na
pole
kwadratu
o boku a (P = a2) określa prosty algorytm:
- Jako dane wejściowe pobierz wartość długości boku kwadratu.
- Oblicz wartość pola – wynikiem jest szukana wartość pola kwadratu.
- Zwróć obliczoną wartość pola kwadratu.
Formalnie
- Algorytm to skończony ciąg działań elementarnych, który określa sposób otrzymania rozwiązania zadania z danych wejściowych. Załóżmy, że zadanie ma polegać na obliczeniu wartości wyniku dla danych wejściowych . Niech:
- i .
Rozwiązanie zadania jest równoważne wyznaczeniu wartości pewnej wielowartościowej funkcji wektorowej , , gdzie jest dana przez m+1 funkcji rzeczywistych :
W każdym etapie obliczeń zbiór argumentów składa się z pierwotnych wartości wejściowych xi lub z wartości obliczonych w poprzednich etapach. Pojedyncze działanie wyznacza nową wartość z jednego lub więcej elementów zbioru (aktualnych) argumentów. Nowa wartość jest wynikiem pośrednim lub końcowym, w obu przypadkach jest dołączana do zbioru argumentów. Następnie z tego zbioru usuwane są wszystkie elementy, które nie będą argumentami podczas pozostałych obliczeń. Elementy końcowe zbioru argumentów wyznaczą jednoznacznie rozwiązanie .
Zapisując kolejne zbiory argumentów jako wektory:
można z działaniem elementarnym związać odwzorowanie elementarne
takie, że
Wektor jest przedstawieniem przekształconego zbioru argumentów. Odwzorowanie elementarne jest wyznaczone jednoznacznie z dokładnością do kolejnych współrzędnych
Algorytm a opisujący go język
Należy zdawać sobie sprawę z różnicy między algorytmem, będącym "niezależnym" od jego implementacji przepisem, a
programem
, który może zostać zinterpretowany i wykonany przez komputer. Przykładowo, poniższe fragmenty programów są realizacją tego samego "algorytmu", sumującego trzy trójki:
Dodawanie w
języku C
:
wynik = 3; wynik += 3; wynik += 3;
Ten sam język, ale z
pętlą
:
wynik = 0; for (int i = 0; i < 3; ++i) wynik += 3;
Język C, zapis
proceduralny
:
int alg(int n) { if(n == 3) return 0; else return 3 + alg(n + 1); } void main() { int wynik = alg(0); }
Asembler
x86:
mov eax, 0 # zeruje akumulator add eax, 3 # dodaje 3 do akumulatora add eax, 3 add eax, 3 mov 0EF21A29Ch, eax # kopiuje zawartość akumulatora do komórki pamięci
Powyższe "programy" napisane są w różnych
językach programowania
, używających różnych poziomów abstrakcji, przy czym zapis w asemblerze jest na najniższym poziomie abstrakcji, tj. jest najbliżej "prawdziwego", wykonywanego bezpośrednio przez
procesor
komputera,
kodu
.
Klasyfikacja
Istnieje wiele różnych sposobów podziału algorytmów na grupy. 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 tym momencie drogę rozwiązania,
-
programowanie liniowe
– oceniamy rozwiązanie problemu przez pewną funkcję jakości i szukamy jej minimum,
-
poszukiwanie i wyliczanie
– kiedy przeszukujemy zbiór danych aż do odnalezienia rozwiązania,
-
algorytm probabilistyczny
– algorytm działa poprawnie z bardzo wysokim
prawdopodobieństwem
, ale wynik nie jest pewny,
-
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
-
proceduralność
– algorytm dzielimy na szereg podstawowych
procedur
, wiele algorytmów współdzieli wspólne biblioteki standardowych procedur, z których są one wywoływane w razie potrzeby,
- praca sekwencyjna – wykonywanie kolejnych procedur algorytmu, według kolejności ich wywołań, na raz 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 łączymy w pewne klasy reprezentujące najważniejsze elementy algorytmu oraz stan wewnętrzny wykonującego je urządzenia.
Przykłady
Błędy w implementacji
Wciąż rozwijana
inżynieria oprogramowania
pozwala na tworzenie aplikacji których kod źródłowy ma setki tysięcy linii, przy równoczesnym zachowaniu kontroli nad całością projektu, co pozwala zminimalizować ilość błędów podczas implementacji algorytmów.
Algorytmy poza komputerami
Implementacja algorytmu w ogólności oznacza występowanie pewnego podobieństwa algorytmu opisanego w ludzkim języku do fizycznego zjawiska lub procesu. Czasami algorytm może być podstawą budowy przez ludzi urządzenia, jak np. komputer. Jednak o implementacji możemy mówić również, kiedy pewien system zachowuje się podobnie do algorytmu. Dla przykładu mózg ptaka implementuje arytmetykę w postaci
sieci neuronowej
. Dzięki temu zwierzę jest w stanie porównywać pewne odstępy czasu. W przypadku maszyn algorytm może zostać zaimplementowany jako pewna sieć połączeń elektrycznych, pneumatycznych bądź mechanicznych. Przykładem może być tutaj analogowy regulator obrotów z pierwszych
silników
parowych, realizujący algorytm P (proporcjonalny). Przy takim podejściu sukces nie oznacza zatrzymanie algorytmu, lecz utrzymywanie pewnego stanu systemu. Możemy np. powiedzieć, że algorytm utrzymywania życia działa poprawnie, aż do śmierci organizmu. Poprawny algorytm ma utrzymywać pewne parametry żywej istoty (np.
temperaturę
) w optymalnym zakresie.
Przyszłość algorytmów
Ograniczenia algorytmów
Prawidłowy algorytm komputerowy musi kiedyś zakończyć swoją pracę. Oznacza to, że problem musi być rozwiązany z wykorzystaniem dostępnych zasobów obliczeniowych w skończonym czasie. Jeżeli czas obliczeń algorytmu dla coraz większego zbioru danych rośnie szybciej niż dowolna funkcja wielomianowa, to mówi się że nie jest
praktycznie obliczalny
. Jedną z klas problemów, dla których nie znamy wielomianowych rozwiązań, są
problemy NP-trudne
. Jeśli znamy wielomianowy algorytm weryfikujący poprawność rozwiązania problemu NP-trudnego, to problem ten nazywamy
NP-zupełnymi
. Pytanie, czy P=NP, czyli czy istnieją szybkie algorytmy rozwiązujące problemy NP-zupełne, jest najsłynniejszym problemem otwartym we współczesnej informatyce. Dodatkowo istnieją problemy nierozwiązywalne za pomocą żadnego algorytmu - tzw.
problemy nierozstrzygalne
.
Algorytmy sztucznej inteligencji
Wiele problemów związanych z codziennym życiem to
problemy NP-trudne
. Przykłady to
znajdowanie najkrótszej trasy łączącej pewną liczbę miast
i
optymalne pakowanie plecaka
. Oznacza to, że szybkie algorytmy mogą radzić sobie w takimi problemami tylko w przybliżeniu lub w bardzo szczególnej sytuacji. Sterowany algorytmem 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 da 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 i przeniesieniu ich na grunt 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 ze sobą w celu powielenia informacji. Bardzo wiele rzeczywistych problemów można rozwiązać w ten sposób. Zobacz więcej o
algorytmach genetycznych
.
Algorytmy kwantowe
Jednym z problemów NP-zupełnych jest łamanie kodów. Istnieją pewne algorytmy szyfrowania (
RSA
,
DES
), dla których szybkie znalezienie kluczy wymaga bardzo dużej mocy obliczeniowej. Tutaj rozwiązaniem mogą okazać się algorytmy zaimplementowane w
komputerach kwantowych
. W odróżnieniu od komputerów elektronicznych opartych na
bitach
, te kwantowe mają posługiwać się
qubitami
oraz zjawiskiem
splątania
. Pewne własności tych maszyn powodują, że niektóre problemy N-P zupełne dają się rozwiązać w jednym takcie obliczeń. Gdyby komuś udało się zbudować komputer
kwantowy
, byłby w stanie złamać wszystkie dzisiaj używane algorytmy kryptograficzne. 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 ma 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 jest tutaj szyfrowanie danych z wykorzystaniem splątanych
fotonów
. Obecnie kierunki prac nad komputerami kwantowymi:
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 równolegle na wielu różnych maszynach. Podejście to stosuje się 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
. Zadanie jest rozdzielane na wiele maszyn i
obliczane równolegle
w tysiącach komputerów. Czasami taką potężną sieć nazywa się z j. angielskiego grid. Przykłady to program
SETI@home
, gdzie dane z nasłuchu
kosmosu
, analizowały dziesiątki tysięcy komputerów należących do zwykłych użytkowników. Maszyny były podłączone do
Internetu
, przez który przesyłały wyniki pracy uruchomionych na nich aplikacji. Nowym pomysłem na implementację algorytmów równoległych jest wykorzystanie do tego
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 mrugały rytmicznie światłem. Dziedzina nauki zajmująca się algorytmami w połączeniu z biologią to
bioinformatyka
.
Przykład algorytmu
Wyobraź sobie, że masz nieposortowaną listę przypadkowych liczb. Masz znaleźć największą z nich. Istnieje wiele algorytmów rozwiązujących ten problem. Jeden z najszybszych można przedstawić jako listę poleceń:
- Rozpocznij pracę
- Stwórz rejestr przechowujący bieżącą wartość elementu tabeli i wczytaj do niego pierwszy element listy, jeżeli to się nie uda, wypisz na wyjście wartość błędną.
- Stwórz rejestr przechowujący największą liczbę, nadaj jej bieżącą wartość elementu tabeli.
- Początek pętli - wczytaj kolejny element tabeli, a jeżeli to się nie uda, zakończ pętlę.
- Jeżeli bieżąca wartość elementu tabeli, jest większa od rejestru największej liczby, to wpisz ją do tego rejestru.
- Powróć do początku pętli.
- Wypisz na wyjście wartość z rejestru największej liczby.
- Zwolnij rejestr bieżącej wartości oraz największej liczby i zakończ pracę, wypisując na wyjście wartość sukcesu.
Historia algorytmów
Początki
Słowo algorytm pochodzi od nazwiska
arabskiego
matematyka z
IX
wieku
Muhammeda ibn Musa Alchwarizmiego
. Początkowo słowem algorism nazywano czynności konieczne do wykonywania obliczeń z użyciem
dziesiętnego systemu liczbowego
. Obecne znaczenie słowa algorytm jako zestawu ścisłych reguł powstało wraz z rozwojem matematyki i techniki. Wynalezienie zbiorów zasad pozwalających na obliczanie parametrów konstruowanych maszyn, stało się podstawą
rewolucji przemysłowej
zapoczątkowanej w końcu
XVIII
stulecia. Jednak dopiero zbudowanie maszyn, które same mogły realizować pewne proste algorytmy, stało się przełomem. Początkowo miały one postać układów mechanicznych mogących dokonywać prostych obliczeń.
Ogromnego postępu dokonał w tej dziedzinie w
1842
roku
Charles Babbage
, który na podstawie swoich doświadczeń sformułował ideę
maszyny analitycznej
zdolnej do realizacji złożonych algorytmów matematycznych. W pracy Babbage wspierała
Ada Lovelace
, która przetłumaczyła dla niego prace włoskiego matematyka dotyczące algorytmu obliczania
liczb bernoulliego
. Prace Lovelace dotyczące implementacji na maszynę różnicową tego algorytmu zawierały opis swoistego
języka programowania
. Niestety, Babbage nigdy nie zbudował swojego mechanicznego komputera. Programy napisane 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 pod koniec
XIX
wieku
kart perforowanych
elektro-mechaniczne maszyny osiągnęły zdolność realizacji algorytmów przetwarzających ogromne zbiory danych. Karty perforowane stały się wejściem, z którego dane przetwarzały proste algorytmy sumujące. Jako wyjście służyły odpowiednie zegary. Ogromny postęp w tej dziedzinie zawdzięczamy firmie
IBM
, która zbudowała tego typu urządzenia, aby policzyć wszystkich mieszkańców
USA
.
W
XX
wieku postęp elektroniki pozwolił na budowę maszyn
analogowych
potrafiących w swoim wnętrzu odtwarzać pewne algorytmy matematyczne. Mogły one dokonywać operacji arytmetycznych oraz
różniczkować
i
całkować
.
Komputery
Zanim zbudowano pierwsze komputery, istniały już solidne podstawy informatyki teoretycznej. Algorytm wyrażony w najprostszym z możliwych języków okazał się dla urządzeń najlepszy. Na początku lat trzydziestych XX wieku ukazało się kilka niezależnie opracowanych matematycznych modeli wykonywania algorytmów. Najsłynniejszym została
Maszyna Turinga
zaproponowana w pracy On Computable Numbers autorstwa
Alana Turinga
, genialnego brytyjskiego matematyka uznawanego za ojca informatyki. Jednocześnie okazało się, że wszystkie modele są sobie równoważne, tj. każdym z nich można wyrazić dowolny algorytm oraz zasymulować działanie jednego modelu na innym (patrz:
Kompletność Turinga
). Okazało się, że nawet najbardziej złożone algorytmy można wyrazić za pomocą prostego matematycznego opisu i kilku elementarnych operacji. Maszyna Turinga miała składać się z głowicy czytająco-piszącej przesuwającej się po nieskończonej taśmie. W każdym kroku mogła zmienić wartość danej komórki taśmy, przesunąć się w lewo lub prawo oraz zmienić swój stan.
Pierwszy mechaniczny komputer zdolny, jak się później okazało, do wykonywania wszystkich algorytmów, powstał już w
1936
roku w Niemczech. Nazywał się
Z1
, a jego twórcą był niemiecki inżynier
Konrad Zuse
, który zaprojektował swoją maszynę zupełnie niezależnie od prac brytyjskich i angielskich matematyków. Z powodu ogromnej zawodności, w 1941 roku ukończył jej kopię bazującą na układach przekaźnikowych,
Z3
. Znalazła ona zastosowanie przy projektowaniu skrzydeł samolotów. Z3 miał wiele cech współczesnego komputera; wszystkie liczby reprezentowane były w
systemie binarnym
, programy wprowadzano na kartach perforowanych, a do wprowadzania danych służyła klawiatura. W
Wielkiej Brytanii
oraz
USA
pierwsze komputery zbudowane na początku lat 40. 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 wykonywania wszystkich algorytmów,
ENIAC
. Pracowała ona w systemie dziesiętnym, a programowania dokonywano poprzez przełączanie odpowiednich kabli.
W ostatnich trzydziestu latach, dzięki upowszechnieniu
komputerów osobistych
, informatyka stała się bardzo ważną gałęzią gospodarki. Na świecie pracują miliony
programistów
zajmujących się tworzeniem oraz doskonaleniem oprogramowania lub poszukiwaniem nowych, efektywniejszych algorytmów. Wraz z opieraniem na komputerach funkcjonowania całego społeczeństwa, coraz większą wagę przykłada się do wyszukiwania błędów w implementacjach lub założeniach algorytmów, co jest procesem trudno poddającym się automatyzacji i wymagającym żmudnej pracy całych zespołów
hackerów
i programistów.
Przypisy
- ↑
Donald E. Knuth
: Sztuka programowania. T. 1. Warszawa: Wydawnictwo Naukowo-Techniczne, 2002, s. 1. .
Zobacz też
Bibliografia
- Neil Gershenfeld i Isaac L. Chuang, "Molekularne komputery kwantowe"; Świat Nauki, sierpień 1998
- Nadrian C. Seeman, "Na granicy życia i nanotechnologii"; Świat Nauki, lipiec 2004 Dymek
- Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, Clifford Stein "Wprowadzenie do algorytmów (nowe wydanie)";WNT, wyd. VI
2004
Linki zewnętrzne