Zawartość
- Definicja - Co oznacza algorytm niedeterministyczny?
- Wprowadzenie do Microsoft Azure i Microsoft Cloud | W tym przewodniku dowiesz się, na czym polega przetwarzanie w chmurze i jak Microsoft Azure może pomóc w migracji i prowadzeniu firmy z chmury.
- Techopedia wyjaśnia algorytm niedeterministyczny
Definicja - Co oznacza algorytm niedeterministyczny?
Algorytm niedeterministyczny może zapewniać różne dane wyjściowe dla tego samego wejścia w różnych wykonaniach. W przeciwieństwie do algorytmu deterministycznego, który wytwarza tylko jedno wyjście dla tego samego wejścia, nawet w różnych przebiegach, algorytm niedeterministyczny podróżuje różnymi drogami, aby osiągnąć różne wyniki.
Algorytmy niedeterministyczne są przydatne do znajdowania przybliżonych rozwiązań, gdy uzyskanie dokładnego rozwiązania jest trudne lub kosztowne przy użyciu algorytmu deterministycznego.
Wprowadzenie do Microsoft Azure i Microsoft Cloud | W tym przewodniku dowiesz się, na czym polega przetwarzanie w chmurze i jak Microsoft Azure może pomóc w migracji i prowadzeniu firmy z chmury.
Techopedia wyjaśnia algorytm niedeterministyczny
Jednym z przykładów niedeterministycznego algorytmu jest wykonywanie algorytmów współbieżnych z warunkami wyścigu, które mogą wykazywać różne wyniki w różnych przebiegach. W przeciwieństwie do algorytmu deterministycznego, który przemieszcza jedną ścieżkę od wejścia do wyjścia, algorytm niedeterministyczny może przyjmować wiele ścieżek, z których niektóre docierają do tych samych wyników, a inne docierają do różnych wyników. Ta funkcja jest matematycznie stosowana w niedeterministycznych modelach obliczeniowych, takich jak niedeterministyczny automat skończony.
Algorytm niedeterministyczny może być wykonywany na deterministycznym komputerze, który ma nieograniczoną liczbę równoległych procesorów. Algorytm niedeterministyczny zwykle składa się z dwóch faz i kroków wyjściowych. Pierwsza faza to faza zgadywania, która wykorzystuje dowolne znaki do uruchomienia problemu.
Druga faza to faza weryfikacji, która zwraca wartość true lub false dla wybranego ciągu. Istnieje wiele problemów, które można konceptualizować za pomocą niedeterministycznych algorytmów, w tym nierozwiązany problem P vs NP w teorii obliczeń.
Algorytmy niedeterministyczne są stosowane w rozwiązywaniu problemów, które pozwalają na wiele wyników. Każdy wynik, który wytwarza algorytm niedeterministyczny, jest prawidłowy, niezależnie od wyborów dokonanych przez algorytm podczas wykonywania.