Algorytmy - Polski Serwis Naukowy

Zobacz 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.

Ronald Linn Rivest (ur. w 1947 w Schenectady, Nowy Jork) – informatyk, kryptograf. Za swój wkład w rozwój kryptografii asymetrycznej otrzymał w 2002 roku nagrodę Turinga. Pracuje na stanowisku profesora informatyki uniwersytetu MIT.
Patent – potocznie: dokument wydawany przez urzędy patentowe; właściwie: prawo wydane osobie fizycznej lub prawnej do zabronienia innym osobom fizycznym lub prawnym zarobkowego bądź zawodowego użytkowania danego wynalazku bądź wynalazków (będących przedmiotem patentu).

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.

Abakus lub abak (łac. abacus, gr. ábaks) – deska z wyżłobionymi rowkami, które symbolizowały kolejne potęgi dziesięciu. Ułatwiało liczenie, używane w Rzymie i Grecji od 440 p.n.e. do XVIII wieku - prekursor liczydła i maszyn liczących. Był używany także w innych krajach Europy. Obliczeń dokonywano poprzez wkładanie i przekładanie kamyków w rowkach. Zasada liczenia była taka sama jak na liczydle. Jedną z odmian abaku, stanowiącą poważne udoskonalenie, przypisywali Rzymianie pitagorejczykom i nazwali mensa pythagoreana. Chińczycy używali liczydła zwanego swan-pan. Jest ono wytworem własnym pomysłowości chińskiej. Odmiana japońska nosi nazwę soroban (jap. 算盤, soroban ?).
Teoria złożoności obliczeniowej to dział teorii obliczeń. Głównym jej celem jest określanie ilości zasobów potrzebnych do rozwiązania problemów obliczeniowych. Rozważanymi zasobami są takie wielkości jak czas, pamięć lub liczba procesorów. Za twórców tej teorii uważani są Juris Hartmanis i Richard Stearns. Jako przykłady problemów t.z.o. można podać: problem spełnialności, problem najkrótszej ścieżki, problem faktoryzacji oraz wiele innych o których wiadomo że są obliczalne. Kwestią obliczalności zajmuje się teoria obliczalności, będąca drugą ważną gałęzią teorii obliczeń.

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.

Algorytm zachłanny (ang. greedy algorithm) – algorytm, który w celu wyznaczenia rozwiązania w każdym kroku dokonuje zachłannego, tj. najlepiej rokującego w danym momencie wyboru rozwiązania częściowego. Innymi słowy algorytm zachłanny nie patrzy czy w kolejnych krokach jest sens wykonywać dane działanie, dokonuje decyzji lokalnie optymalnej, dokonuje on wyboru wydającego się w danej chwili najlepszym, kontynuując rozwiązanie podproblemu wynikającego z podjętej decyzji. Typowe zadanie rozwiązywane metodą zachłanną ma charakter optymalizacyjny. W dziedzinie sztucznej inteligencji zachłanna odmiana przeszukiwania lokalnego jest nazywana "podchodzeniem pod wzgórze".
Algorytm Luhna – jeden z najczęściej wykorzystywanych algorytmów służących do sprawdzania poprawności wpisania danej liczby. Jest on używany m.in. do walidacji numerów kart kredytowych, ciągów liczbowych, itd. Nazwa algorytmu pochodzi od nazwiska niemieckiego naukowca Hansa Petera Luhna (1896–1964).

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ą spory prawne 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.

Wszechświat – wszystko, co fizycznie istnieje: cała przestrzeń, czas, wszystkie formy materii i energii oraz prawa fizyki i stałe fizyczne określające ich zachowanie. Słowo "wszechświat" może być też używane w innych kontekstach, jako synonim słów kosmos (w rozumieniu filozofii), świat czy Natura. Natomiast w naukach ścisłych słowa wszechświat i kosmos są równoważne.
Zero (zapisywane jako 0) – element neutralny dodawania; najmniejsza nieujemna liczba. To, czy zero jest uznawane za liczbę naturalną, jest kwestią umowy – czasem włącza się, a czasem wyklucza się je z tego zbioru. Zero nie jest ani liczbą pierwszą ani liczbą złożoną.

Definicja klasyczna

Algorytm to 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 przetworzenie, ale i weryfikacja danych.

Wielka Brytania (), Zjednoczone Królestwo Wielkiej Brytanii i Irlandii Północnej (ang. United Kingdom of Great Britain and Northern Ireland) – unitarne państwo wyspiarskie położone w Europie Zachodniej. W skład Wielkiej Brytanii wchodzą: Anglia, Walia i Szkocja położone na wyspie Wielka Brytania, Irlandia Północna leżąca w północnej części wyspy Irlandia. Guernsey, Jersey i Wyspa Man, posiadają odrębny status dependencji Korony brytyjskiej i nie wchodzą w skład Zjednoczonego Królestwa.
Programowanie liniowe to klasa problemów programowania matematycznego, w której wszystkie warunki ograniczające oraz funkcja celu mają postać liniową. Warunki ograniczające mają postać:

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 niżej. Niech $\scriptstyle \mathrm{indeks}$ oznacza wskazuje aktualnie badany element listy (jeśli jest ona numerowana, może on oznaczać np. jej numer), a $\scriptstyle \mathrm{maksimum}$ oznacza największą dotychczas znalezioną wartość.

Dowód poprawności algorytmu jest rozumowaniem matematycznym prowadzącym do formalnego wykazania, że dany algorytm przy poprawnych danych wejściowych da nam wynik spełniający wymagania, np. że algorytm quicksort po podaniu mu niepustej tablicy elementów porównywalnych na wyjściu da nam tablicę zawierającą te same elementy, ale uporządkowane w kolejności od najmniejszego do największego.
Konrad Zuse (ur. 22 czerwca 1910 r. w Berlinie - zm. 18 grudnia 1995 r. w Hünfeld) - niemiecki inżynier, konstruktor, pionier informatyki; konstruktor pierwszego komputera działającego w systemie binarnym; studia na Politechnice Berlińskiej; od 1935 roku, w którym ukończył studia, pracował w Henschel Flugzeug-Werke AG; 1936 uzyskał patent na pamięć mechaniczną; 1939-1958 skonstruował serię elektromechanicznych i elektronicznych maszyn liczących (wykorzystywanych m.in. do projektowania geometrii skrzydeł samolotów niemieckich w czasie II wojny światowej) - najbardziej znana to Z3, 1941, pierwsza w historii w pełni działająca programowalna maszyna licząca; 1958 zaprojektował ploter (maszyna Z64). Od roku 1949 do 1969 prowadził własną firmę Zuse KG.

Niech $\scriptstyle \mathrm{indeks}$ wskazuje na pierwszy element (początek) listy.
Niech $\scriptstyle \mathrm{maksimum}$ zawiera wartość elementu listy wskazywanego przez $\scriptstyle \mathrm{indeks}$ (tzn. pierwszego).
Jeżeli zawartość elementu listy wskazywanego przez $\scriptstyle \mathrm{indeks}$ jest większa od zawartości $\scriptstyle \mathrm{maksimum},$ to przypisz $\scriptstyle \mathrm{maksimum}$ wartość elementu wskazywanego przez $\scriptstyle \mathrm{indeks}.$
Niech $\scriptstyle \mathrm{indeks}$ wskazuje kolejny element listy; jeśli to niemożliwe (tzn. $\scriptstyle \mathrm{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ą $\scriptstyle \mathrm{maksimum};$ 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).

RSA - jeden z pierwszych i obecnie jeden z najpopularniejszych asymetrycznych algorytmów kryptograficznych, zaprojektowany w 1977 przez Rona Rivesta, Adi Shamira oraz Leonarda Adlemana. Pierwszy, który można stosować zarówno do szyfrowania jak i do podpisów cyfrowych. Bezpieczeństwo szyfrowania opiera się na trudności faktoryzacji dużych liczb złożonych. Jego nazwa pochodzi od pierwszych liter nazwisk jego twórców.
Komputer osobisty (ang. personal computer) – mikrokomputer przeznaczony przede wszystkim do użytku osobistego, spotyka się je zarówno w domach, jak i biurach. Mają zazwyczaj postać desktopów albo notebooków. Służą głównie do uruchamiania oprogramowania biurowego, dostępu do zasobów Internetu, prezentacji treści multimedialnych (tekst, obrazy, dźwięki, filmy i inne), jak i gier.

Inne przykłady

algorytm Euklidesa

algorytm Fermata

algorytm Luhna

algorytmy sortowania

algorytmy kompresji

algorytmy przeszukiwania drzew: min-max i alpha-beta

algorytm unifikacji

algorytmy kryptograficzne

algorytm mrówkowy

Klasyfikacja

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

Rekurencja albo rekursja (ang. recursion, z łac. recurrere, przybiec z powrotem) to w logice, programowaniu i w matematyce odwoływanie się np. funkcji lub definicji do samej siebie. Wbrew próbom rozróżnienia terminów [potrzebne źródło] rekursja i rekurencja w rzeczywistości słowa te mają identyczne znaczenie[potrzebne źródło].
Kompresja danych (ang. data compression) – polega na zmianie sposobu zapisu informacji tak, aby zmniejszyć redundancję i tym samym objętość zbioru. Innymi słowy chodzi o wyrażenie tego samego zestawu informacji, lecz za pomocą mniejszej liczby bitów.

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,

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

Plik (ang. file), jest to ciąg danych (inaczej zbiór danych), o skończonej długości, posiadający szereg atrybutów i stanowiący dla systemu operacyjnego całość. Nazwa pliku nie należy do niego, lecz jest przechowywana w systemie plików.
Spintronika, (elektronika spinowa, elektronika kwantowa, magnetronika) jest odmianą elektroniki. Podczas gdy w tradycyjnych układach scalonych nośnikiem informacji są zmiany w przepływie prądu, w spintronice brany jest pod uwagę również spin elektronu.

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,

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 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.

Stany Zjednoczone, Stany Zjednoczone Ameryki (ang.: United States, United States of America, US, USA) – państwo w Ameryce Północnej graniczące z Kanadą od północy, Meksykiem od południa, Oceanem Spokojnym od zachodu, Oceanem Arktycznym od północnego zachodu, Oceanem Atlantyckim od wschodu.
Foton (gr. φως – światło, w dopełniaczu – φοτος) jest cząstką elementarną nie posiadającą ładunku elektrycznego ani momentu magnetycznego, o masie spoczynkowej równej zero (m0 = 0), liczbie spinowej s = 1 (fotony są zatem bozonami). Fotony są nośnikami oddziaływań elektromagnetycznych, a ponieważ wykazują dualizm korpuskularno-falowy są równocześnie falą elektromagnetyczną.

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.

Z1 – mechaniczny komputer zerowej generacji nie będący jednak maszyną Turinga z braku rozkazów warunkowych, które zostały dodane dopiero w modelu Z4. Pierwszy komputer Konrada Zuse i pierwszy posiadający liczby zmiennoprzecinkowe.
Podprogram (inaczej funkcja lub procedura) - termin związany z programowaniem proceduralnym. Podprogram to wydzielona część programu wykonująca jakieś operacje. Podprogramy stosuje się, aby uprościć program główny i zwiększyć czytelność kodu.

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.

Całka – ogólne określenie wielu różnych, choć powiązanych ze sobą pojęć analizy matematycznej. W artykule rachunek różniczkowy i całkowy podana jest historia ewolucji znaczenia samego słowa całka. Najczęściej przez "całkę" rozumie się całkę oznaczoną lub całkę nieoznaczoną (rozróżnia się je zwykle z kontekstu).
Reakcja chemiczna – każdy proces, w wyniku którego pierwotna substancja zwana substratem przemienia się w inną substancję zwaną produktem. Aby cząsteczka substratu zamieniła się w cząsteczkę produktu konieczne jest rozerwanie przynajmniej jednego z obecnych w niej wiązań chemicznych pomiędzy atomami, bądź też utworzenie się przynajmniej jednego nowego wiązania. Reakcje chemiczne przebiegają z reguły z wydzieleniem lub pochłonięciem energii cieplnej, promienistej (alfa lub beta) lub elektrycznej.

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.

Kryptologia (z gr. κρυπτός – kryptos – "ukryty" i λόγος – logos – "słowo") – nauka o przekazywaniu informacji w sposób zabezpieczony przed niepowołanym dostępem. Współcześnie kryptologia jest uznawana za gałąź zarówno matematyki, jak i informatyki; ponadto jest blisko związana z teorią informacji, inżynierią oraz bezpieczeństwem komputerowym.
Charles Babbage (ur. 26 grudnia 1791 r. w Teignmouth, Devonshire – zm. 18 października 1871 r. w Londynie) – angielski matematyk, astronom i mechanik, autor tablic logarytmicznych.

Algorytmy kwantowe

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

Algorytmy zaimplementowane na komputerach kwantowych, w odróżnieniu od komputerów elektronicznych opartych na bitach, mają 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 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:

Algorytm mrówkowy, zaproponowany przez Marco Dorigo, jest probabilistyczną techniką rozwiązywania problemów poprzez szukanie dobrych dróg w grafach. Jest on zainspirowany zachowaniem mrówek szukających pożywienia dla swojej kolonii.
Definicja intuicyjna: Maszyna Turinga stanowi najprostszy, wyidealizowany matematyczny model komputera, zbudowany z taśmy, na której zapisuje się dane i poruszającej się wzdłuż niej "głowicy", wykonującej proste operacje na zapisanych na taśmie wartościach.

fotonika – komputery oparte na fotonach,

spinotronika – komputery operujące spinem elektronów zamiast napięcia.

czytaj dalej: [2], [3]

w oparciu o Wikipedię (licencja GFDL, CC-BY-SA 3.0, autorzy, historia, edycja)