Algorytm

Sprawdź hasło algorytm w Wikisłowniku

Algorytm – w matematyce oraz informatyce skończony 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 albo dla innego urządzenia. Gdy 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 potrafią ułatwić popełnienie przestępstwa komputerowego.

Jako przykład stosowanego w życiu codziennym algorytmu głosi się wielokrotnie przepis kulinarny. Dla przykładu, aby ugotować bigos trzeba w określonej kolejności oraz odstępach czasowych (imperatyw czasowy) dodawać właściwe rodzaje kapusty oraz innych składników. Może istnieć parę wielorakich przepisów dających na końcu bardzo podobną potrawę. Przykład ten ma jedynie charakter poglądowy, albowiem język przepisów kulinarnych nie stał się jasno zdefiniowany. Algorytmy zwykle formułowane są w sposób ścisły w oparciu o język matematyki.

W pewnych krajach, jak USA, algorytmy potrafią zostać opatentowane, jeżeli zostaną zaimplementowane w jakimś praktycznym celu. Pewni ludzie 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 pomiędzy sobą spory prawne dotyczące praw własności do poniektórych patentów. Kontrargumentem jest tzw. prawo własności intelektualnej (jaką objęty jest np. utwór muzyczny, będący wytworem intelektu oraz pracy muzyka) zakładające, że program jest intelektualną własnością twórcy.

Definicja klasyczna

• Algorytm to jednoznaczny przepis obliczenia w skończonym czasie pewnych danych wejściowych do pewnych danych wynikowych.

Zwykle 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 oraz weryfikacja danych.

Zgodnie z założeniem o jednoznaczności dla identycznego zestawu danych początkowych, algorytm zdefiniowany klasycznie stale zwróci identyczny wynik.

Przykład

Znalezienie największej wśród niepustej, nieposortowanej listy przypadkowych liczb da się przeprowadzić na wiele sposobów, jednym z najszybszych jest przedstawiony niżej. Niech oznacza wskazuje aktualnie badany element listy (jeśli jest ona numerowana, może on oznaczać np. jej numer), a oznacza największą dotychczas znalezioną wartość.

1. Niech wskazuje na pierwszy element (początek) listy.
2. Niech zawiera wartość elementu listy wskazywanego przez (tzn. pierwszego).
3. Jeżeli zawartość elementu listy wskazywanego przez jest większa od zawartości to przypisz wartość elementu wskazywanego przez
4. Niech wskazuje kolejny element listy; jeśli to niemożliwe (tzn. wskazuje ostatni element listy, czyli jej koniec), przejdź do punktu 6.
5. Wróć do punktu 3.
6. Koniec.

Wykonanie tego algorytmu spowoduje, że największa liczba na wspomnianej liście będzie wartością ciekawostką jest fakt, iż algorytm ten działa dla list dowolnej długości (nie wykorzystuje on liczby elementów listy, lecz tylko tzw. operację następnika 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
• algorytmy sortowania
• algorytmy kompresji
• algorytmy przeszukiwania drzew: min-max oraz alpha-beta
• algorytm unifikacji
• algorytmy kryptograficzne
• algorytm mrówkowy

Klasyfikacja

Istnieje wiele wielorakich sposobów podziału algorytmów na grupy. Problem ten wzbudza kontrowersje.

Podstawowe paradygmaty tworzenia algorytmów komputerowych:

• dziel oraz zwyciężaj – dzielimy problem na parę 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 oraz po pewnym wnioskowaniu wyniki analizy poniektó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 dylematu przez pewną funkcję jakości oraz szukamy jej minimum,
• poszukiwanie oraz wyliczanie – kiedy 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 stale 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, wedle 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 albo funkcja wywołuje sama siebie, aż do uzyskania wyniku albo błędu,
• obiektowość – procedury oraz dane łączymy w pewne klasy reprezentujące najważniejsze elementy algorytmu oraz stan wewnętrzny wykonującego je urządzenia,
• algorytm probabilistyczny – algorytm 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 równolegle na wielu wielorakich 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 oraz 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 leżą 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.

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 oraz optymalne pakowanie plecaka. Oznacza to, że szybkie algorytmy potrafią radzić sobie w takimi problemami tylko w przybliżeniu albo 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 bywa 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, da się maszynę wyposażyć w zdolność do samodzielnego uczenia się. Zagadnieniem tym zajmuje się dział określany jako sztuczna inteligencja. Tego podejścia nie trzeba 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 ma za podstawę na obserwacji praw natury oraz przeniesieniu ich na grunt informatyki. U podstaw algorytmów genetycznych istnieje 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 da się rozwiązać w ten sposób. Sprawdź więcej o algorytmach genetycznych.

Algorytmy kwantowe

Pewne algorytmy szyfrowania (np. RSA) opierają się na trudności rozkładu liczby na czynniki pierwsze. Dla tego dylematu nie jest znany algorytm wielomianowy na klasycznym komputerze.

Algorytmy zaimplementowane na komputerach kwantowych, w przeciwieństwie od komputerów elektronicznych opartych na bitach, posiadają posługiwać się qubitami oraz zjawiskiem splątania. Na komputerze kwantowym możliwy jest rozkład liczby na czynniki pierwsze w czasie wielomianowym

Dużym problemem komputerów kwantowych jest dekoherencja ich stanów. W wyniku tego 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. Z uwagi na 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. Aktualnie kierunki prac nad komputerami kwantowymi:

• fotonika – komputery oparte na fotonach,
• spinotronika – komputery operujące spinem elektronów zamiast napięcia.

Ograniczenia algorytmów

Prawidłowy algorytm komputerowy musi dawniej 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 powiada 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 dylematu NP-trudnego, to problem ten nazywamy NP-zupełnymi. Pytanie, czy P=NP, czyli czy są szybkie algorytmy rozwiązujące problemy NP-zupełne, jest najsłynniejszym problemem otwartym we współczesnej informatyce. Dodatkowo są problemy nierozwiązywalne za pomocą żadnego algorytmu - tzw. problemy nierozstrzygalne.

Implementacja algorytmów

Algorytmy komputerowe

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 oraz uzyskują z nich dane wyjściowe. Informacje zapisane w pamięci maszyny traktuje się jako jej stan wewnętrzny. Pewne algorytmy posiadają za zadanie jedynie 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 wielokrotnie komunikując się przesyłają pomiędzy sobą informację wieloznaczne. Komputery potrafią reagować tylko na całkowicie jednoznaczne instrukcje. Jeżeli dany algorytm da się wykonać na maszynie o dostępnej mocy obliczeniowej oraz pamięci oraz akceptowalnym czasie, to powiada się że jest obliczalny.

Poprawne działanie większości algorytmów implementowanych w komputerach ma za podstawę 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.

Algorytmy poza komputerami

Implementacja algorytmu w ogólności oznacza zachodzenie pewnego podobieństwa algorytmu opisanego w ludzkim języku do fizycznego zjawiska albo procesu. Czasami algorytm bywa podstawą budowy przez ludzi urządzenia, jak np. komputer. Jednak o implementacji możemy mówić również, kiedy pewien system zachowuje się analogicznie 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 bywa 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.

Algorytm a opisujący go język

Należy zdawać sobie sprawę z różnicy pomiędzy algorytmem, będącym niezależnym od jego implementacji przepisem, a programem, który może zostać zinterpretowany oraz 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 oraz = 0; oraz < 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 wielorakich językach programowania, używających wielorakich 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.

Błędy w implementacji

Wciąż rozwijana inżynieria oprogramowania dopuszcza na wykonywanie aplikacji których kod źródłowy ma setki tysięcy linii, przy równoczesnym zachowaniu kontroli nad całością projektu, co dopuszcza zminimalizować ilość błędów podczas implementacji algorytmów.

Historia algorytmów

Początki

Słowo algorytm pochodzi od nazwiska arabskiego matematyka z IX wieku Muhammeda ibn Musa Alchwarizmiego. Oryginalnie 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 oraz 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. Oryginalnie miały one osoba 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 wcale nie zbudował swojego mechanicznego komputera. Programy napisane przez Lovelace zostały przetestowane na modelu maszyny różnicowej wykonanym w XX wieku oraz 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 są 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ć oraz 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 30. XX wieku ukazało się parę niezależnie opracowanych matematycznych modeli wykonywania algorytmów. Najsłynniejszym była maszyna Turinga zaproponowana w pracy On Computable Numbers autorstwa Alana Turinga, brytyjskiego matematyka uznawanego za ojca informatyki. Równocześnie okazało się, że wszystkie modele są sobie równoważne, tj. każdym z nich da się wyrazić dowolny algorytm oraz zasymulować działanie jednego modelu na innym (patrz: kompletność Turinga). Okazało się, że nawet najbardziej złożone algorytmy da się wyrazić za pomocą prostego matematycznego opisu oraz 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 albo 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ę całkowicie niezależnie od prac brytyjskich oraz 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 albo 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 albo założeniach algorytmów, co jest procesem trudno poddającym się automatyzacji oraz wymagającym żmudnej pracy całych zespołów hackerów oraz programistów.

Przypisy

Sprawdź też

• automatyczne dowodzenie twierdzeń
• język programowania
• struktury danych
• teoria obliczeń
• dowód poprawności algorytmu

Bibliografia

• Neil Gershenfeld oraz Isaac L. Chuang, "Molekularne komputery kwantowe"; Świat Nauki, sierpień 1998
• Nadrian C. Seeman, "Na granicy życia oraz 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
• Donald E. Knuth "Sztuka programowania"; WNT, 2002-2008
• L. Banachowski, K. Diks, W. Rytter "Algorytmy oraz struktury danych"; WNT, wyd. V, 2006

Linki zewnętrzne

• (pol.) nullwww.algorytm.org/ - algorytmy oraz struktury danych
• (pol.) nullwazniak.mimuw.edu.pl/index.php?title=Algorytmy_i_struktury_danych - ogólnodostępny skrypt do przedmiotu Algorytmy oraz Struktury Danych
• (pol.) nullwazniak.mimuw.edu.pl/index.php?title=Zaawansowane_algorytmy_i_struktury_danych - ogólnodostępny skrypt do przedmiotu Zaawansowane Algorytmy oraz Struktury Danych
• (pol.) nullwas.zaa.mimuw.edu.pl/ - wykłady z algorytmiki stosowanej
• (ang.) nullwww.algana.co.uk/ - darmowe kody źródłowe podstawowych algorytmów w Javie oraz C
• (ang.) nullwww.dcc.uchile.cl/~rbaeza/handbook/ - inna strona z kodami źródłowymi
• (ang.) nullwww.nist.gov/dads/ - słownik algorytmów oraz struktur danych
• (ang.) nullwww.nr.com - algorytmy numeryczne