Algorytm deterministyczny

Z Wikipedii, wolnej encyklopedii
Przejdź do nawigacji Przejdź do wyszukiwania

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.

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

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.

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

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.

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


Podstrony: 1 [2] [3]




Warto wiedzieć że... beta

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

Reklama