• Artykuły
  • Forum
  • Ciekawostki
  • Encyklopedia
  • Algorytm deterministyczny

    Przeczytaj także...
    Kwantowy algorytm Shora – algorytm kwantowy umożliwiający rozkład na czynniki pierwsze liczby naturalnej N w czasie O((log N)) i pamięci O(log N), przy wykorzystaniu komputera kwantowego. Algorytm ten stanowi teoretyczne zagrożenie dla powszechnie używanego w internecie kryptosystemu RSA. Klucz publiczny w RSA jest iloczynem dwóch dużych liczb pierwszych. Możliwość efektywnego odtworzenia tych liczb na podstawie klucza publicznego pozwalałaby poznać klucz prywatny i tym samym złamać cały szyfr.Generator liczb pseudolosowych (Pseudo-Random Number Generator, lub PRNG) to program lub podprogram, który na podstawie niewielkiej ilości informacji (ziarno, zarodek, ang. seed) generuje deterministycznie ciąg bitów, który pod pewnymi względami jest nieodróżnialny od ciągu uzyskanego z prawdziwie losowego źródła.
    Komputer (z ang. computer od łac. computare – liczyć, sumować; dawne nazwy używane w Polsce: mózg elektronowy, elektroniczna maszyna cyfrowa, maszyna matematyczna) – maszyna elektroniczna przeznaczona do przetwarzania informacji, które da się zapisać w formie ciągu cyfr albo sygnału ciągłego.

    Algorytm deterministycznyalgorytm, którego działanie jest całkowicie zdeterminowane przez warunki początkowe (wejście). Oznacza to, że kilkukrotne uruchomienie takiego algorytmu doprowadzi za każdym razem do takiego samego wyniku. Algorytmy deterministyczne stanowią główny obszar badań informatycznych i są najczęściej stosowane, ponieważ mogą być łatwo realizowane na współczesnych komputerach.

    Determinizm przyczynowy (łac. determinare — oddzielić, ograniczyć, określić) — koncepcja filozoficzna, według której wszystkie zdarzenia w ramach przyjętych paradygmatów są połączone związkiem przyczynowo-skutkowym, a zatem każde zdarzenie i stan jest zdeterminowane przez swoje uprzednio istniejące przyczyny (również zdarzenia i stany). 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.

    Formalna definicja[ | edytuj kod]

    Formalnie algorytm deterministyczny może być zdefiniowany w terminach zmiany stanów maszyny wykonującej ten algorytm. Algorytm jest deterministyczny, jeśli dla dowolnego stanu i dowolnych danych wejściowych istnieje dokładnie jedna dopuszczalna zmiana stanu. Oznacza to, że rozpoczynając od stanu początkowego można dokładnie określić, jakie będą wszystkie kolejne stany tej maszyny.

    Kryptologia (z gr. κρυπτός – kryptos – "ukryty" i λόγος – logos – "słowo") – dziedzina wiedzy 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.Komputer kwantowy – układ fizyczny do opisu którego wymagana jest mechanika kwantowa, zaprojektowany tak, aby wynik ewolucji tego układu reprezentował rozwiązanie określonego problemu obliczeniowego.

    Obecnie algorytmy deterministyczne są wykorzystywane również przy projektowaniu niehazardowych automatów do gier, które nie zawierają elementu losowości, w tym generatora liczb pseudolosowych. W tej chwili na świecie istnieją zaledwie dwa rozwiązania o takiej charakterystyce.

    Algorytmy, które nie są deterministyczne[ | edytuj kod]

    W informatyce bada się również algorytmy nienależące do tej klasy. Przykładami takich algorytmów są:

    Algorytm kwantowy – rodzaj algorytmu przeznaczonego do działania na maszynie kwantowej (komputer kwantowy). Dotychczas powstało kilkanaście algorytmów wykorzystujących możliwości oferowane przez maszyny kwantowe. Należą do nich algorytmy Grovera, Deutscha, Simona, Shora, Kitaeva i Bernsteina-Vaziraniego.Test Millera-Rabina jest testem pierwszości, czyli algorytmem określającym czy dana liczba jest pierwsza. Podobnie jak test Fermata i test Solovaya-Strassena jest testem probabilistycznym, wymagającym stosowania liczb losowych. Oryginalna wersja tego algorytmu (Millera) została zaprojektowana jako algorytm deterministyczny, jednak jej poprawność zależy od nieudowodnionej dotychczas uogólnionej hipotezy Riemanna. Michael O. Rabin zmodyfikował ten algorytm do postaci randomizacyjnej i dowiódł jego poprawności w tej postaci.
  • niektóre algorytmy równoległe i rozproszone – w których interakcja pomiędzy niezależnie wykonywanymi obliczeniami może prowadzić do różnych rezultatów,
  • algorytmy probabilistyczne – w których używane są ciągi losowych (lub pseudolosowych) bitów,
  • algorytmy kwantowe – w których do obliczeń wykorzystywane są zjawiska kwantowe.
  • Wady algorytmów deterministycznych[ | edytuj kod]

    Istnieje wiele problemów, dla których nie znamy efektywnych deterministycznych algorytmów. Przykładowo sprawdzenie, czy dana liczba jest pierwsza, można przeprowadzić bardzo efektywnie za pomocą prostych probabilistycznych algorytmów, znanych od lat siedemdziesiątych (np. test Millera-Rabina). Algorytm deterministyczny dla tego problemu został znaleziony dopiero w 2002 r. (patrz test pierwszości AKS) i jest bardziej skomplikowany i mniej efektywny.

    Test pierwszości AKS (lub Test pierwszości Agrawal-Kayal-Saxena) jest deterministycznym testem pierwszości opublikowanym przez Manindra Agrawal, Neeraj Kayal i Nitin Saxena z IIT Kanpur 6 sierpnia 2002 roku w artykule zatytułowanym PRIMES is in P. Za jego opracowanie autorzy zostali uhonorowani Nagrodą Gödla w 2006 roku.Algorytm – w matematyce 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.

    Kolejnym przykładem jest problem rozkładu podanej liczby na czynniki pierwsze. Istnieje dla tego problemu rozwiązanie kwantowe: probabilistyczny (algorytm Shora), jego praktyczna implementacja wymaga zbudowania komputera kwantowego. Brak możliwości efektywnego (obecne komputery kwantowe są zbyt słabe) rozkładu dużych liczb na czynniki pierwsze stanowi podstawę bezpieczeństwa większości algorytmów kryptografii asymetrycznej.

    Generator liczb pseudolosowych (Pseudo-Random Number Generator, lub PRNG) to program lub podprogram, który na podstawie niewielkiej ilości informacji (ziarno, zarodek, ang. seed) generuje deterministycznie ciąg bitów, który pod pewnymi względami jest nieodróżnialny od ciągu uzyskanego z prawdziwie losowego źródła.Problem NP-zupełny (NPC) czyli problem zupełny w klasie NP ze względu na redukcje wielomianowe, to problem, który należy do klasy NP oraz dowolny problem należący do NP może być do niego zredukowany w czasie wielomianowym. Czasami zamiast redukcji w czasie wielomianowym używa się redukcji w pamięci logarytmicznej. Pytanie, czy są to definicje równoważne pozostaje pytaniem otwartym. Taka definicja problemów NP-zupełnych implikuje fakt, że jeśli tylko potrafimy rozwiązać jakikolwiek problem NP-zupełny w czasie wielomianowym, to potrafimy rozwiązać w czasie wielomianowym wszystkie problemy NP. Problemy NP-zupełne można więc traktować jako najtrudniejsze problemy klasy NP (z punktu widzenia wielomianowej rozwiązywalności).

    Istnieją wreszcie problemy NP-zupełne, dla których nie są znane efektywne algorytmy deterministyczne, probabilistyczne ani kwantowe (choć nie udowodniono, że nie istnieją). Problemy te są o tyle ważne, że obejmują większość istotnych praktycznych zagadnień występujących w przemyśle. Obecnie znane są jedynie sposoby efektywnego znajdowania przybliżonych rozwiązań i to tylko dla niektórych problemów tego typu.

    Obliczenia rozproszone (ang. distributed computing) – obliczenia, umożliwiające współdzielenie zasobów obliczeniowych, często rozproszonych geograficznie.Algorytm probabilistyczny albo randomizowany to algorytm który do swojego działania używa losowości. W praktyce oznacza to że implementacja takiego algorytmu korzysta przy obliczeniach z generatora liczb losowych. Główną zaletą algorytmów probabilistycznych w porównaniu z deterministycznymi jest działanie zawsze w "średnim przypadku", dzięki czemu złośliwe dane wejściowe nie wydłużają jego działania. Formalnie efektywność takiego algorytmu jest zmienną losową określoną na przestrzeni możliwych losowych ciągów. Wartość oczekiwana takiej zmiennej nazywana jest oczekiwanym czasem działania. Przypadek pesymistyczny jest zwykle na tyle mało prawdopodobny, że można go pominąć w analizie.

    W niektórych przypadkach problemem jest sama przewidywalność zachowania algorytmów deterministycznych. Przykładowo przy algorytmach kryptograficznych niezbędne jest, aby nikt z zewnątrz nie był w stanie zgadnąć zachowania algorytmu, który generuje klucze. Najczęściej realizowane jest to przy użyciu kryptograficznie bezpiecznych generatorów pseudolosowych.

    Kryptografia klucza publicznego (nazywana również kryptografią asymetryczną) to rodzaj kryptografii, w którym używa się zestawów dwu lub więcej powiązanych ze sobą kluczy, umożliwiających wykonywanie różnych czynności kryptograficznych. Jeden z kluczy może być udostępniony publicznie bez utraty bezpieczeństwa danych zabezpieczanych tym kryptosystemem.

    Przypisy[ | edytuj kod]

    1. Futura i Futura Eclipse cieszą się stale rosnącą popularnością – E-PLAY.PL, „E-PLAY.PL”, 26 kwietnia 2018 [dostęp 2018-04-27] (pol.).




    Reklama

    Czas generowania strony: 0.022 sek.