Różnice i związki między algorytmami losowymi i niedeterministycznymi?

Jakie różnice i zależności występują między algorytmami losowymi a algorytmami niedeterministycznymi?

Z Wikipedii

Randomizowane algorytm jest algorytmem, w którym stosuje się stopniem losowości jako część logiki. Algorytm zwykle wykorzystuje jednolicie losowe bity jako pomocnicze dane wejściowe do kierowania jego zachowaniem, w nadziei na osiągnięcie dobrej wydajności w „przeciętnym przypadku” względem wszystkich możliwych wyborów losowych bitów. Formalnie wydajność algorytmu będzie zmienną losową określoną przez losowe bity; zatem albo czas działania, albo wynik (lub oba) są zmiennymi losowymi.

Niedeterministyczny algorytm jest algorytmem, który może wykazywać różne zachowania w różnych seriach, w przeciwieństwie do algorytmu deterministycznego. Istnieje kilka sposobów, w których algorytm może zachowywać się inaczej w różnych uruchomieniach. Współbieżne algorytm może działać inaczej na różnych tras z powodu sytuacji wyścigu. Zachowanie algorytmu probabilistycznego zależy od generatora liczb losowych. Algorytm, który rozwiązuje problem w niedeterministycznym czasie wielomianowym, może działać w czasie wielomianowym lub wykładniczym, w zależności od wyborów dokonanych podczas wykonywania.

Czy algorytmy losowe i algorytmy probabilistyczne to ta sama koncepcja?

Jeśli tak, to czy algorytmy losowe są rodzajem algorytmów niedeterministycznych?

Algorytmy niedeterministyczne bardzo różnią się od algorytmów probabilistycznych.

Algorytmy probabilistyczne wykorzystują rzuty monetami i działają „przez większość czasu”. Na przykład, losowe warianty szybkiego sortowania działają w czasie w oczekiwaniu (i z dużym prawdopodobieństwem), ale jeśli masz pecha, może zająć tyle co . Algorytmy probabilistyczne są praktyczne i są wykorzystywane na przykład przez komputer podczas generowania kluczy RSA (w celu sprawdzenia, czy dwa czynniki tajnego klucza są pierwsze). Algorytm probabilistyczny, który nie wykorzystuje rzutów monetą, jest czasem nazywany „deterministycznym”.Θ ( n 2$\Theta(n\log n)$$\Theta(n^2)$

Algorytmy niedeterministyczne to takie, które „potrzebują podpowiedzi”, ale zawsze są poprawne: nie można ich oszukać, podając niewłaściwą wskazówkę. Jako przykład podajemy niedeterministyczny algorytm, który uwzględnia liczbę całkowitą : zgadnij faktoryzację i sprawdź, czy wszystkie czynniki są pierwsze (istnieje do tego algorytm deterministyczny „szybki w teorii”). Ten algorytm jest bardzo szybki i odrzuca fałszywe wskazówki. Większość ludzi uważa, że ​​algorytmy randomizowane nie mogą tak szybko uwzględniać liczb całkowitych. Oczywiście ten model obliczeń nie jest realistyczny.$n$$n$

Dlaczego dbamy o algorytmy niedeterministyczne? Istnieje klasa problemów zwana NP, która składa się z problemów decyzyjnych, które mają wydajne algorytmy niedeterministyczne. Większość ludzi uważa, że ​​najtrudniejsze problemy w tej klasie, tak zwane problemy NP-zupełne, nie mają wydajnych algorytmów deterministycznych (a nawet losowych); jest to znane jako pytanie P vs NP. Ponieważ wiele naturalnych problemów jest NP-zupełnych, warto wiedzieć, czy w najgorszym przypadku nie da się ich skutecznie rozwiązać (w praktyce często przypadki, które powstają w praktyce, są w rzeczywistości możliwe do rozwiązania w rozsądnym czasie).

Algorytm określa metodę przejścia z danego wejścia do pożądanego wyjścia, które ma pewną relację z wejściem. Mówimy, że ten algorytm jest deterministyczny, jeśli w dowolnym momencie zostanie dokładnie i jednoznacznie określony, jaki następny krok w algorytmie należy wykonać w ramach tej metody, potencjalnie zależny od danych wejściowych lub obliczonych do tej pory częściowych danych, ale zawsze jednoznacznie zidentyfikowane.

Niedeterminizm oznacza, że ​​pewna część algorytmu pozostała niedokładna lub nawet nieokreślona. Na przykład „int i = liczba parzysta od 0 do n” jest nieokreślona. Oznacza to, że w tym momencie nie określono żadnego unikalnego zachowania.

Aby to rozróżnienie było przydatne, potrzebujesz (zwykłej) koncepcji „poprawności” algorytmów (deterministycznych), która nieoficjalnie polega na tym, że „algorytm zawsze oblicza to, co chcę, aby został obliczony”. Interesujące staje się wtedy zastanowienie się, co poprawność oznaczałoby dla niedeterministycznych algorytmów, które muszą uwzględniać wybory możliwe w nieokreślonych instrukcjach.

Istnieją dwa sposoby definiowania poprawności niedeterminizmu. Pierwszy jest raczej prosty i mniej interesujący, dla którego poprawność oznacza „algorytm zawsze oblicza to, co chcę, aby obliczyć, dla wszystkich sekwencji wyborów, których wolno mi dokonywać”. Zdarza się to czasami, gdy autor fragmentu pseudokodu jest zbyt leniwy, aby wybrać liczbę i mówi „wybierz dowolną liczbę parzystą z przedziału od 0 do n”, gdy „wybór 0” uczyniłby algorytm deterministycznym. Zasadniczo, zastępując cały niedeterminizm wynikiem pewnego wyboru, można uczynić algorytm deterministycznym.

Jest to również „niedeterminizm”, o którym mowa w drugim akapicie. Jest to również niedeterminizm w algorytmach równoległych: w tych algorytmach nie jesteś całkiem pewien, jak dokładnie wygląda wykonanie, ale wiesz, że zawsze zadziała, bez względu na to, co się dokładnie wydarzy (w przeciwnym razie twój algorytm równoległyby byłby nieprawidłowy).

Interesującą definicją poprawności dla algorytmu niedeterministycznego jest „algorytm zawsze oblicza to, co chcę, aby obliczyć, dla pewnych sekwencji wyborów, których wolno mi dokonywać”. Oznacza to, że mogą istnieć wybory, które są błędne, w tym sensie, że powodują, że algorytm podaje złą odpowiedź, a nawet przechodzi w nieskończoną pętlę. W przykładzie „wybierz dowolną liczbę parzystą z przedziału od 0 do n”, być może 4 i 16 są prawidłowymi wyborami, ale wszystkie inne liczby są błędne, a liczby te mogą się różnić w zależności od danych wejściowych, częściowych wyników i dokonanych dotychczas wyborów.

W przypadku informatyki niedeterminizm jest zwykle ograniczony do niedeterministycznego wybrania wartości 0 lub 1. Jednak jeśli wybierzesz wiele takich bitów niedeterministycznie, możesz wygenerować długie niedeterministyczne liczby lub inne obiekty, a także dokonać niedeterministycznych wyborów, więc trudno (jeśli w ogóle) ogranicza jego zastosowanie - jeśli jest ono ograniczone, niedeterminizm był zbyt silny.

Niedeterminizm to narzędzie, które jest tak samo potężne, jak algorytm deterministyczny oparty na certyfikacie, to znaczy algorytm, który sprawdza właściwość na podstawie wystąpienia i certyfikatu dla tej właściwości. Możesz po prostu niedeterministycznie odgadnąć certyfikat dla jednego kierunku, i możesz dać certyfikat, który zawiera wszystkie „prawidłowe” odpowiedzi dla niedeterministycznych domysłów 0 i 1 twojego programu dla drugiego kierunku.

Jeśli wrzucimy czas do miksu, sprawy staną się jeszcze bardziej interesujące. Czas działania algorytmu niedeterministycznego jest zwykle uważany za minimum dla wszystkich (właściwych) wyborów. Jednak inne wybory mogą prowadzić do dramatycznie gorszego czasu działania (który może być asymptotycznie gorszy lub nawet arbitralnie gorszy od minimum) lub nawet nieskończonej pętli. Dlatego bierzemy minimum: nie dbamy o te dziwne przypadki.

Teraz przechodzimy do algorytmów losowych. Algorytmy randomizowane są podobne do algorytmów niedeterministycznych, ale zamiast „pozwalać” na wybór między 0 a 1 w niektórych punktach, wybór ten zależy od losowego rzutu monetą w momencie, w którym należy dokonać wyboru (który może różnić się w zależności od przebiegu lub gdy ten sam wybór musi być dokonany ponownie później podczas wykonywania algorytmu). Oznacza to, że wynik wynosi 0 lub 1 z jednakowym prawdopodobieństwem. Poprawność staje się teraz albo „algorytm prawie zawsze oblicza to, co chcę, aby go obliczyć”, albo „algorytm zawsze oblicza to, co chcę, aby to obliczyć” (tylko wersja deterministyczna). W drugim przypadku czas potrzebny algorytmowi na obliczenie odpowiedzi jest zwykle „prawie zawsze szybki”, co kontrastuje z deterministycznym „zawsze szybkim”.

W przeciwieństwie do trzech: algorytmy deterministyczne dokładnie określają odpowiedź na wybór, niedeterminizm pozostawia ją całkowicie otwartą, ale mówi, że istnieje „właściwa” odpowiedź, a randomizacja pozostawia odpowiedź przypadkowi. Zauważ, że można po prostu zgadnąć, jakie rzuty monetą są właściwe, co prowadzi do hierarchii między tymi trzema: niedeterminizm jest równie potężny jak randomizacja, która z kolei jest równie silna jak determinizm, lub, w odniesieniu do czasu wielomianowego, . W tym ustawieniu nie są znane żadne dowody na to, że któryś jest silniejszy od innego.$P \subseteq ZPP \subseteq NP$

W skrócie: niedeterminizm oznacza posiadanie wielu, równie ważnych wyborów dotyczących sposobu kontynuowania obliczeń. Randomizacja oznacza użycie zewnętrznego źródła (losowych) bitów do kierowania obliczeniami.

Aby zrozumieć niedeterminizm, proponuję spojrzeć na automaty skończone (FA). Dla deterministycznego FA (DFA) funkcja przejścia jest, no cóż, funkcją. Biorąc pod uwagę aktualny stan i następny symbol wejściowy, następny stan jest jednoznacznie zdefiniowany.

Z drugiej strony automat niedeterministyczny (NFA) ma relację przejściową : biorąc pod uwagę aktualny stan i następny symbol wejściowy, istnieje wiele możliwych następnych stanów! Weźmy na przykład ten automat dla języka :$(ab)^*(ac)^*$

^{[ źródło ]}

Automat zgaduje, która oznacza granicę między i ; automat deterministyczny musiałby odłożyć swoją decyzję, dopóki nie przeczyta symbolu po każdym .( a b ) ∗ ( a c ) ∗$a$$(ab)^*$$(ac)^*$$a$

Kluczową kwestią jest tutaj to, że akceptacja jest zdefiniowana jako „zaakceptuj, jeśli istnieje akceptacja” dla NFA. To kryterium istnienia można interpretować jako „zawsze zgadywanie poprawnie”, nawet jeśli nie ma zgadywania.

Zauważ, że nie ma tu żadnych prawdopodobieństw. Jeśli przetłumaczysz niedeterminizm na języki programowania, będziesz mieć instrukcje, które mogą powodować przeskakiwanie do innych instrukcji o tym samym stanie . Coś takiego nie istnieje, z wyjątkiem być może ezoterycznych języków programowania zaprojektowanych, by rozwiać twój umysł.

Randomizacja jest zupełnie inna. Jeśli się zepsujemy, automat / program nie będzie miał wielu opcji do dalszego wykonania. Po losowaniu bitów losowych następna instrukcja jest jednoznacznie zdefiniowana:

if ( rand() > 5 )
  do_stuff();
else
  do_other_stuff();

Jeśli chodzi o automaty skończone, rozważ to:

^{[ źródło ]}

Teraz każde słowo ma prawdopodobieństwo, a automat określa rozkład prawdopodobieństwa na (różnice między a sumą krawędzi wychodzących to prawdopodobieństwo zakończenia; słowa, których nie można zaakceptować, mają prawdopodobieństwo ). 1 $\{a,b,c\}^*$$1$$0$

Możemy to potraktować jako deterministyczny automat, biorąc pod uwagę sekwencję losowych decyzji (które modele ćwiczą całkiem dobrze, ponieważ zwykle nie używamy prawdziwych losowych źródeł); można to wymodelować jako DFA na gdzie jest wystarczająco dużym alfabetem używanym przez losowe źródło.$\Sigma \times \Pi$$\Pi$

Ostatnia uwaga: widzimy, że niedeterminizm jest koncepcją czysto teoretyczną, której nie można wdrożyć! Dlaczego więc go wykorzystujemy?

1. Często pozwala na mniejsze reprezentacje. Być może wiesz, że istnieją NFA, dla których najmniejszy DFA jest wykładniczo tak duży¹. Korzystanie z mniejszych jest jedynie kwestią uproszczenia projektu automatu i technicznych dowodów.

2. Tłumaczenie między modelami jest często prostsze, jeśli niedozwolony jest model docelowy. Rozważmy na przykład konwersję wyrażeń regularnych na DFA: zwykłym (i prostym) sposobem jest przetłumaczenie go na NFA i określenie tego. Nie jestem świadomy bezpośredniej konstrukcji.

3. Może to stanowić problem akademicki, ale interesujące jest to, że niedeterminizm może zwiększyć moc urządzenia. Nie dotyczy to automatów skończonych i maszyn Turinga, argumentujących najpopularniejsze modele modeli urządzeń, ale na przykład deterministyczne automaty pushdown, automaty Büchi i automaty drzewa top-down mogą przyjmować znacznie mniej języków niż ich niedeterministyczne rodzeństwo².

1. Zobacz to pytanie na cstheory.SE jako przykład.
2. Zobacz tutaj , tutaj i tutaj (Propozycja 1.6.2) , odpowiednio.

Powinieneś wiedzieć, że są tu rzucane dwie różne definicje niedeterminizmu.

1. Jak definiuje to wikipedia, prawie „nie determinizm”, to znaczy każdy algorytm, który nie zawsze ma takie samo zachowanie na tych samych danych wejściowych. Algorytmy randomizowane są szczególnym przypadkiem algorytmów „niedeterministycznych”, ponieważ pasują do definicji, którą właśnie podałem.

2. Niedeterministyczne modele obliczeń (podobnie jak niedeterministyczne maszyny Turinga) są teoretycznymi modelami obliczeń. Mogą mieć wiele możliwych ścieżek wykonania i „akceptują”, jeśli którakolwiek z tych ścieżek akceptuje. Należy pamiętać, że nie są prawdziwe. Nie ma możliwości fizycznego uruchomienia algorytmu, który nie jest deterministyczny w tym sensie, chociaż można go zasymulować za pomocą algorytmu losowego lub deterministycznego.

W CS niedeterminizm zwykle oznacza (2), więc podana przez ciebie definicja Wikipedii (która jest (1)) wprowadza w błąd. Większość udzielonych dotychczas odpowiedzi wyjaśnia (2), a nie (1).

Wracając do tego z powodu niektórych powiązanych badań, które przeprowadzam, nieporozumienia między mną a niektórymi innymi, którzy odpowiedzieli, można zasymilować w całościowe zrozumienie, w którym wszyscy mieliśmy rację. Ale przyjęta przez IMO terminologia informatyczna „ograniczony niedeterminizm” jest niepoprawnym oksymoronem (o czym wcześniej mówiłem).

Kluczową kwestią jest rozróżnienie między niedeterminizmem ograniczonym i nieograniczonym. [1]

Niedeterministyczne maszyny Turinga (znane również jako „NTM”) ograniczyły niedeterminizm, ponieważ każda zmiana stanu ma ograniczoną liczbę możliwości, tzn. Liczba programów (zwanych również „konfiguracjami”) jest skończona. Taśma pozostaje nieograniczona, więc dowód zakończenia pozostaje nierozstrzygalny. Ale dla każdego zatrzymanego wejścia wynik jest deterministyczny i ograniczony czasowo, tj. Dla każdego wejścia wynik jest deterministyczny lub nie kończy się. Również NTM wykonują wszystkie możliwe konfiguracje równolegle, więc działają wykładniczo szybciej niż emulacja NTM na deterministycznych maszynach Turinga (inaczej „DTM”). [2]

Tak naprawdę nie ma żadnego niedeterministycznego związku między danymi wejściowymi a wynikami w NTM, ponieważ wynik jest zawsze taki sam dla każdego stanu wejściowego lub początkowego, co jest oczywiste, ponieważ można je emulować przez DTM bez żadnej dodatkowej losowości. [2] Nierozstrzygalne nie jest antytezą deterministycznego, ponieważ nie zatrzymanie jest również deterministycznym rezultatem. Maszyny deterministyczne zawsze mają taki sam wynik dla danych wejściowych, nawet jeśli taki wynik nie zostanie zatrzymany. Zlokalizowany niedeterminizm NTM występuje w każdym stanie przejścia algorytmu wykonującego. Jest nierozstrzygalne a priori, która ścieżka drzewa może się zakończyć, podając stan wyjściowy. Ale nierozstrzygalność nie jest niedeterminizmem. Zatem termin „ograniczony niedeterminizm” ma na celu opisanie zlokalizowanej nieokreśloności w maszynie stanu, ale nie relacji między danymi wejściowymi a wynikami, stąd koncepcja „ograniczona”. Nadal uważam, że termin „ograniczony niedeterminizm” jest oksymoronem i można go dokładniej opisać jako „maszynę Turinga z„ równoległym przejściem stanu ”.

Natomiast dla dowolnego stanu wejściowego lub początkowego nieograniczony niedeterminizm (zwany również „indeterminizmem”) ma nieograniczoną liczbę możliwych stanów. Nieograniczony niedeterminizm obejmuje nie tylko liczbę możliwych konfiguracji programów, ale także pewien nieokreślony stan zewnętrzny, który nie jest częścią stanu wejściowego lub początkowego, taki jak nieograniczone opóźnienia. I tak wyniki mogą się różnić przy powtarzanych wykonaniach dla tego samego warunku wejściowego lub początkowego; dlatego nie jest deterministycznym związkiem między nakładami a wynikami [3]

Algorytmy randomizowane i probabilistyczne wykorzystują pewien niedeterminizm, tj. Losowy wybór możliwych konfiguracji, prawdopodobnie ograniczonych liczbą konfiguracji, ale nie wykonują wszystkich możliwych konfiguracji, jak robią to NTM. Zatem nie są deterministyczne, chyba że losowość jest deterministyczna (np. PRNG), a stan początkowy entropii dla losowości jest uważany za część danych wejściowych.

[1] https://en.wikipedia.org/w/index.php?title=Unbounded_nondeterminism&oldid=710628370#Nondeterministic_automata

[2] https://en.wikipedia.org/w/index.php?title=Non-deterministic_Turing_machine&oldid=754212081#Equivalence_with_DTMs

[3] Hewitt, Meijer i Szyperski: Model aktora (wszystko, co chciałeś wiedzieć ...) . Przejdź do znaku minuty 17:44.

Oprócz wszystkich odpowiedzi, które wyjaśniają różnicę, mam przykład, który może pomóc ci uzyskać to, co chcą powiedzieć.
Rozważmy monetą, to albo dostać H lub T . Jeśli losowanie jest przypadkowy, to jest wysoce prawdopodobne, że na 1000 rzutów moneta, 500 byłaby H i jest całkiem prawdopodobne, że 999 z nich byłoby H . Ale jeśli rzut monetą nie jest deterministyczny, nie możemy powiedzieć, że uzyskanie 999 H byłoby bardzo mało prawdopodobne.

Algorytmy randomizowane (czas wielomianowy, wynik boolowski) należą do klasy złożoności obliczeniowej RP, która jest podzbiorem NP, w którym znajdują się algorytmy niedeterministyczne (czas wielomianowy, wynik boolowski) i nadzbiór P, gdzie deterministyczny (czas wielomianowy, wynik boolowski) algorytmy rezydują.

Złożoność podzbiorów polega na zmniejszaniu problemów z jednego zestawu do drugiego. Zatem RP ⊆ NP wyklucza możliwość zrandomizowanych algorytmów, które są również niedeterministyczne, ponieważ definitywnie nadzbiór zawiera podzbiór. Podzbiór oznacza, że ​​każdy algorytm RP (lub dowolny algorytm RP-complete) może zostać zredukowany do jakiegoś algorytmu NP (lub dowolnego algorytmu NP-complete). P jest podzbiorem RP, ponieważ każdy problem w P może zostać zredukowany do problemu w RP, w którym ilość niekontrolowanej entropii wynosi 0.

_{Stycznie jest to analogiczne do tego, jak każdy problem w NC (obliczenia równoległe) można zredukować do problemu w P , symulując obliczenia równoległe w redukcji do problemu szeregowego w P, ale nie zostało jeszcze udowodnione, że odwrotność jest prawdziwa, tj. że każdy problem w P można zredukować do problemu w NC, ani nie udowodniono, że nie jest prawdziwy, tj. nieprawdopodobny dowód, że problem P-zupełny nie daje się zredukować do problemu w NC. Możliwe, że występują problemy, które są z natury szeregowe i nie mogą być obliczane równolegle, ale udowodnienie, że udowodnienie P ≠ NC wydaje się nieprawdopodobne (z powodów zbyt stycznych, aby omawiać w tej odpowiedzi).}

Mówiąc bardziej ogólnie (tj. Nie ograniczając się do wyników typu boolowskiego), algorytmy losowe różnią się od algorytmów deterministycznych tym, że część entropii pochodzi z zewnątrz . Algorytmy randomizowane odróżnia się od algorytmów niedeterministycznych, ponieważ entropia jest ograniczona , a zatem można udowodnić, że algorytmy randomizowane (a nie niedeterministyczne) zawsze kończą się.

Nieprzewidywalność niedeterministycznych algorytmów wynika z niemożności wyliczenia wszystkich możliwych permutacji entropii wejściowej (co skutkuje nieprzewidywalnością zakończenia). Nieprzewidywalność losowego algorytmu wynika z niemożności sterowaniacała entropia wejściowa (co powoduje nieprzewidywalność wyniku nieokreślonego, chociaż można przewidzieć szybkość nieprzewidywalności). Żadne z nich nie jest stwierdzeniem o nieprzewidywalności poprawnej odpowiedzi na problem, ale raczej nieprzewidywalność przejawia się odpowiednio w bocznym kanale zakończenia i nieokreślonym wyniku. Wygląda na to, że wielu czytelników łączy nieprzewidywalność w jednym obszarze z nieprzewidywalnością poprawnego wyniku, co jest splotem, którego nigdy nie napisałem (przejrzyj historię edycji).

Kluczowe jest zrozumienie, że niedeterminizm jest zawsze (w jakiejkolwiek nauce lub w użyciu tego terminu) niezdolnością do wyliczenia uniwersalnej (tj. Nieograniczonej) entropii. Natomiast randomizacja odnosi się do dostępu do innego źródła entropii (w programach entropii innej niż, a zatem nie pod kontrolą zmiennych wejściowych), które mogą, ale nie muszą być nieograniczone.

Dodałem następujący komentarz poniżej najpopularniejszej obecnie odpowiedzi do drugiego wątku, który zadaje podobne pytanie.

Wszystkie nauki stosują tę samą definicję niedeterminizmu zjednoczoną na koncepcji nieograniczonej entropii. Nieprzewidywalne wyniki we wszystkich naukach wynikają z niemożności wyliczenia z góry wszystkich możliwych wyników algorytmu (lub systemu), ponieważ akceptuje on stany nieograniczone, tj. Klasę złożoności NP. Określenie konkretnego wkładu w celu zaobserwowania, czy się on zatrzymuje, i zauważenie, że wynik jest idempotentny, jest równoważne w innych naukach z utrzymaniem reszty entropii wszechświata na stałym poziomie, powtarzając tę ​​samą zmianę stanu. Obliczenia umożliwiają izolację entropii, podczas gdy nauki przyrodnicze nie.

Dodając jedne z najlepszych komentarzy, aby dodać wyjaśnienie mojego punktu na temat jedynego istotnego rozróżnienia między randomizowanym a niedeterministycznym.

To naprawdę dość eleganckie i łatwe do dostrzeżenia rozróżnienie, gdy wszyscy przestaniecie go mętnić, próbując opisać go z operacyjnego punktu widzenia, a nie z istotnego punktu widzenia entropii.

@reinierpost wszyscy łączą różnicę między randomizacją a niedeterminizmem. To powoduje, że twój komentarz jest zagmatwany. Algorytm reaguje na interakcje entropii wejściowej (zmiennej) i jej wewnętrznej entropii kodu źródłowego (niezmienniczej). Niedeterminizm jest nieograniczoną entropią. Niezmienna entropia może nawet być wewnętrznie nieograniczona, na przykład poprzez rozszerzenie cyfr π . Randomizowane jest to, że część entropii nie jest sprzężona z określonym wejściem (tzn. Może pochodzić z wywołania systemowego /dev/randomlub symulowanej losowości, np. NFA lub PRNG).

.

@Raphael formalna definicja niedeterministycznego skończonego automa (NFA) jest skończoną entropią wejściową (dane: 5-krotna). Zatem każdy NFA może działać na deterministycznej maszynie Turinga, tj. Nie wymaga niedeterministycznej maszyny Turinga. Zatem NFA nie należą do klasy niedeterministycznych problemów. Pojęcie „niedeterminizmu” w NFA polega na tym, że jego determinizm (choć wyraźnie obecny, ponieważ każdy NFA można przekształcić w DFA) nie jest wyraźnie rozszerzony - nie to samo co niedeterminizm obliczeń

.

@Raphael twierdzenie, że „niedeterminizm” w NFA jest naprawdę przypadkowością, jest sensem mojej definicji rozróżnienia między przypadkowością a niedeterminizmem. Z mojej definicji wynika, że ​​przypadkowość polega na tym, że część entropii, która nie jest pod kontrolą, wiedzy (lub pożądanego nieprecyzyjnego rozszerzenia w przypadku NFA) danych wejściowych do programu lub funkcji. Natomiast prawdziwy niedeterminizm to niemożność poznania entropii w każdym przypadku, ponieważ jest ona nieograniczona. Właśnie to odróżnia losowość od niedeterminizmu. Zatem NFA powinien być przykładem tego pierwszego, a nie drugiego, jak twierdziłeś.

.

@Raphael, jak już wyjaśniłem, pojęcie niedeterminizmu w NFA łączy niedeterministyczny ze skończoną entropią. Zatem niedeterminizm jest lokalną koncepcją nie rozszerzania determinizmu jako formy kompresji lub wygody, dlatego nie mówimy, że NFA są niedeterministyczne, a raczej mają wygląd losowości wyroczni, która nie chce obliczyć deterministycznej ekspansji. Ale wszystko to jest mirażem, ponieważ określa się go mianem rozwinięcia deterministycznie, bo entropia nie jest nieograniczona, czyli skończona.

Słowniki to narzędzia. Naucz się z nich korzystać.

losowy przymiotnik

Statystyka. lub charakteryzujący proces selekcji, w którym każda pozycja zestawu ma równe prawdopodobieństwo wyboru.

będąc lub odnosząc się do zbioru lub elementu zbioru, z których każdy element ma równe prawdopodobieństwo wystąpienia

Zatem randomizacja wymaga jedynie, aby część wejściowej entropii była możliwa do przywrócenia, co jest zatem zgodne z moją definicją, że część entropii wejściowej nie jest kontrolowana przez wywołującą funkcję. Zauważ, że randomizacja nie wymaga, aby entropia wejściowa była nierozstrzygalna w stosunku do zakończenia.

W informatyce algorytm deterministyczny jest algorytmem, który przy określonym wejściu zawsze będzie wytwarzał ten sam wynik, a maszyna leżąca u jego podstaw zawsze przechodzi przez tę samą sekwencję stanów.

Formalnie algorytm deterministyczny oblicza funkcję matematyczną; funkcja ma unikalną wartość dla dowolnego wejścia w swojej dziedzinie, a algorytm jest procesem, który wytwarza tę konkretną wartość jako wynik.

Algorytmy deterministyczne można zdefiniować w kategoriach maszyny stanu: stan opisuje, co robi maszyna w określonym momencie. Maszyny stanowe przechodzą dyskretnie z jednego stanu do drugiego. Zaraz po wprowadzeniu danych wejściowych maszyna znajduje się w stanie początkowym lub początkowym. Jeśli maszyna jest deterministyczna, oznacza to, że od tego momentu jej obecny stan określa, jaki będzie jej następny stan; jego przebieg przez zbiór stanów jest z góry określony. Zauważ, że maszyna może być deterministyczna i wciąż nigdy się nie zatrzyma ani nie zakończy, dlatego nie może dostarczyć wyniku.

To mówi nam, że algorytmy deterministyczne muszą być całkowicie określone przez stan wejściowy funkcji, tzn. Musimy być w stanie udowodnić, że funkcja zakończy się (lub nie zakończy) i że nie może być nierozstrzygalna. Pomimo mętnej próby Wikipedii opisania niedeterministycznego, jedyną antytezą deterministycznej, jak zdefiniowano powyżej w Wikipedii, są algorytmy, których stan wejściowy (entropia) jest źle zdefiniowany. Jedynym sposobem, w jaki stan wejściowy może być źle zdefiniowany, jest to, kiedy jest on nieograniczony (dlatego nie można go deterministycznie wstępnie przeanalizować). Właśnie to odróżnia niedeterministyczną maszynę Turinga (i wiele rzeczywistych programów, które są napisane we wspólnych kompletnych językach Turinga, takich jak C, Java, JavaScript, ML itp.) Od deterministycznych baz TM i języków programowania, takich jak HTML, formuły arkuszy kalkulacyjnych, Coq, Epigram,

W teorii złożoności obliczeniowej algorytmy niedeterministyczne to takie, które na każdym możliwym kroku mogą pozwolić na wiele kontynuacji (wyobraź sobie człowieka idącego ścieżką w lesie i za każdym razem, gdy idzie dalej, musi wybrać widelec na drodze, którą chce brać). Algorytmy te nie znajdują rozwiązania dla każdej możliwej ścieżki obliczeniowej; mają jednak gwarancję, że dojdą do właściwego rozwiązania dla pewnej ścieżki (tj. człowiek idący przez las może znaleźć swoją kabinę tylko wtedy, gdy wybierze kombinację „prawidłowych” ścieżek). Wybory można interpretować jako domysły w procesie wyszukiwania.

Wikipedia i inni starają się połączyć losowość z niedeterminizmem, ale jaki jest sens posiadania tych dwóch pojęć, jeśli nie chcesz ich elokwentnie rozróżniać?

Wyraźnie determinizm dotyczy zdolności do określania. Wyraźnie randomizacja polega na tym, aby część entropii była możliwa do wyposażenia.

Włączenie losowej entropii w stanie algorytmu nie jest konieczne, aby stało się nieokreślone. Na przykład PRNG może mieć wymagany rozkład statystyczny, ale może również być całkowicie deterministyczny.

Ludzie z niskim ilorazem inteligencji łączą pojęcia ortogonalne. Oczekuję od tej społeczności czegoś lepszego!