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[1][2]. Można go przedstawić naschemacie blokowym.
Wczesne użycie słowa algorytm w książceBernarda WojewódkiAlgorithm To iest, Nauka liczby po Polsku 1602.
Słowo „algorytm” pochodzi odłacińskiego słowaalgorithmus (lubalgorismus[3]), oznaczającego wykonywanie działań przy pomocyliczb arabskich (w odróżnieniu odabacism – przy pomocyabakusa), 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[4].
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ęstoprzepis 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 innymiStanach 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 przypadkuGIF). 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 naoprogramowanie jestprawo własności intelektualnej (którą jest na przykładutwór muzyczny, będący wytworemintelektu i pracy muzyka), zakładające, że program jest intelektualną własnością twórcy.
Algorytm –jednoznaczny przepis obliczenia w skończonym czasie pewnych danychwejściowych do pewnych danychwynikowych.
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 iweryfikacja danych.
Zgodnie z założeniem o jednoznaczności – dla identycznego zestawu danych początkowych, algorytm zdefiniowany klasycznie zawsze zwróci identyczny wynik.
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. Niechindeks wskazuje aktualnie badany element listy (jeśli jest ona numerowana, może on oznaczać np. jej numer), amaksimum oznacza największą dotychczas znalezioną wartość.
Niechindeks wskazuje na pierwszy element (początek) listy.
Niechmaksimum zawiera wartość elementu listy wskazywanego przezindeks (tzn. pierwszego).
Jeżeli zawartość elementu listy wskazywanego przezindeks jest większa od zawartościmaksimum, to przypiszmaksimum wartość elementu wskazywanego przezindeks.
Niechindeks 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.
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
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 podstawowychprocedur. 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.
Niektóre z zamieszczonych tu informacji od 2023-09 wymagająweryfikacji. Dokładniejsze informacje o tym, co należy poprawić, być może znajdują się wdyskusji tej sekcji. Po wyeliminowaniu niedoskonałości należy usunąć szablon{{Dopracować}} z tej sekcji.
Jednym ze sposobów rozwiązywania złożonych problemów jest zastosowaniealgorytmó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 wsuperkomputerach, jednak w takiej realizacji jest ono bardzo kosztowne. Nowym pomysłem jest tutaj zastosowanie sieci zwykłych komputerów tworzącychklaster. Całe zadanie jest wtedy rozdzielane na wiele maszyn iobliczane równolegle przy pomocy tysięcy procesorów. Czasami taką potężną sieć rozproszoną nazywa sięgrid. Przykładem jej zastosowania może być programSETI@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 parasolowyBOINC@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 posiadaprocesory 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 celukart graficznych; nosi ono nazwęGPGPU. Kilka projektów z BOINC@home oraz projekt z zakresu biologii molekularnejFolding@home pozwala na zastosowanie karty graficznej, a nawet kilku zamontowanych w jednym komputerze, do realizacjiobliczeń 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 celuDNA. 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 nareakcje 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ą jestbioinformatyka.
Wiele problemów związanych z codziennym życiem toproblemy NP-trudne. Przykładami ich mogą byćznajdowanie najkrótszej trasy łączącej pewną liczbę miast luboptymalne 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 jakosztuczna 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.
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 podstawalgorytmó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.
Niektóre algorytmy szyfrowania (np.RSA) opierają się na trudności rozkładu liczby naczynniki pierwsze (faktoryzacja). Dla tego problemu nie jest znanyalgorytm wielomianowy, którego można by użyć na klasycznym komputerze, czyli opartym na elementach półprzewodnikowych. Natomiast algorytmy zaimplementowane nakomputerach kwantowych, w odróżnieniu od komputerów elektronicznych opartych nabitach, mogą posługiwać siękubitami oraz zjawiskiemsplą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 jestdekoherencja ich stanów – w ten sposób bardzo łatwo może dojść do utraty danych. Rozwiązaniem może być tutaj wykorzystanie splątania doteleportacji stanu kwantowego na kolejnecząstki elementarne. W związku z tym wielu naukowców pracuje już dziś nad implementacją algorytmówkryptografii kwantowej. Przykładem tego jest szyfrowanie danych z wykorzystaniem splątanychfotonów. Obecnie kierunki prac nad komputerami kwantowymi to:
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ż dowolnafunkcja wielomianowa, to mówi się, że nie jestpraktycznie 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 nazywamyNP-zupełnym. Pytanie, czy P=NP, czyli czy istnieją szybkie algorytmy rozwiązujące problemy NP-zupełne, jest jednym z najbardziej palących pytań we współczesnej informatyce. Ponadto istniejąproblemy nierozwiązywalne za pomocą żadnego algorytmu.
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 rygorystyczniezdefiniowanym języku. Ludzie często komunikując się, przesyłają między sobą informacje wieloznaczne. Komputery mogą reagować tylko na całkowicie jednoznaczne instrukcje. Jeżeli dany algorytm da się wykonać na maszynie o dostępnejmocy obliczeniowej i pamięci oraz w 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 o błędzie. Czasami podczas implementacji algorytmu nawet istotny warunek może zostać pominięty. Przykładowo, w programie dzielącym przez siebie dwie liczby użytkownik poleca wykonaćdzielenie przez zero. Działanie aplikacji, która nie sprawdzi warunku „czy dzielnik nierówny zero”, zostanie przerwane przezsystem operacyjny komputera.
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ą budowanego przez ludzi urządzenia, jak np. komputer. Jednak o implementacji możemy mówić również wtedy, kiedy pewien system zachowuje się podobnie do algorytmu. Dla przykładu mózgptaka implementuje arytmetykę w postacisieci 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 pierwszychsilników parowych, realizujący algorytm P (proporcjonalny). Przy takim podejściu sukces nie oznacza zatrzymania się 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.
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. Poniższe fragmenty programów sąrealizacją tego samego algorytmu sumującego trzy trójki:
moveax,0# zeruje akumulatoraddeax,3# dodaje 3 do akumulatoraaddeax,3addeax,3mov0EF21A29Ch,eax# kopiuje zawartość akumulatora do komórki pamięci
Powyższe programy napisane są w różnychjęzykach programowania, używających różnych poziomów abstrakcji, przy czym zapis w asemblerze jest na najniższym poziomie abstrakcji, to znaczy jest najbliżej „prawdziwego”, wykonywanego bezpośrednio przez procesor komputera,kodu.
Wciąż rozwijanainżynieria oprogramowania pozwala na tworzenie aplikacji, którychkod ź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.
Słowoalgorytm pochodzi od nazwiska arabskiego matematyka z IX wieku,Muhammada ibn Musa al-Chuwarizmiego. Początkowo słowemalgorism nazywano czynności konieczne do wykonywania obliczeń z użyciemdziesiętnego systemu liczbowego. Obecne znaczenie słowaalgorytm, 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 realizować proste obliczenia.
Ogromnego postępu dokonał w tej dziedzinie w 1842 rokuCharles 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łaAda Lovelace, która przetłumaczyła dla niego prace włoskiego matematyka dotyczące algorytmu obliczanialiczb Bernoulliego. Prace Lovelace dotyczące implementacji tego algorytmu na maszynę różnicową zawierały opis swoistegojęzyka programowania. 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.
Wraz z wynalezieniem pod koniec XIX wiekukart 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, a jako wyjście służyły odpowiednie zegary. Ogromny postęp w tej dziedzinie zawdzięczamy firmie będącej protoplastąIBM, która zbudowała tego typu urządzenia, aby zrealizować spis ludności w Stanach Zjednoczonych.
W XX wieku postęp elektroniki pozwolił na budowę maszynanalogowych potrafiących w swoim wnętrzu odtwarzać pewne algorytmy matematyczne. Mogły one dokonywać operacji arytmetycznych orazróżniczkować icałkować.
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 30. XX wieku pojawiło się kilka niezależnie opracowanych matematycznych modeli wykonywania algorytmów. Najsłynniejszym zostałamaszyna Turinga zaproponowana w pracyOn Computable Numbers autorstwaAlana Turinga, 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 wNiemczech. Nazywał sięZ1, a jego twórcą był niemiecki inżynierKonrad 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, czyliZ3, która znalazła zastosowanie przy projektowaniu skrzydeł samolotów. Z3 miał wiele cech współczesnego komputera; wszystkie liczby reprezentowane były wsystemie binarnym, programy wprowadzano nakartach perforowanych[potrzebny przypis], a do wprowadzania danych służyłaklawiatura. W Wielkiej Brytanii oraz Stanach Zjednoczonych 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 dowolnych algorytmów,ENIAC. Pracowała ona w systemie dziesiętnym, a programowania dokonywano poprzez przełączanie odpowiednich kabli.
W ostatnich trzydziestu latach, dzięki upowszechnieniukomputerów osobistych, informatyka stała się bardzo ważną gałęzią gospodarki. Na świecie pracują milionyprogramistów, zajmujących się tworzeniem oraz doskonaleniem oprogramowania lub poszukiwaniem nowych, efektywniejszych algorytmów. Wraz z oparciem 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 programistów ihakerów.
.jpg)
