Złożoność obliczeniowa/Test 10: Algorytmy probabilistyczne: Różnice pomiędzy wersjami
Nie podano opisu zmian |
m Zastępowanie tekstu - "\cc{" na "\mathrm{" |
||
| Linia 1: | Linia 1: | ||
<quiz> | <quiz> | ||
Algorytmy dla języków z klasy <math>\ | Algorytmy dla języków z klasy <math>\mathrm{RP}</math>: | ||
<rightoption>mają ograniczone prawdopodobieństwo błędu</rightoption> | <rightoption>mają ograniczone prawdopodobieństwo błędu</rightoption> | ||
<wrongoption>działają w czasie oczekiwanym wielomianowym</wrongoption> | <wrongoption>działają w czasie oczekiwanym wielomianowym</wrongoption> | ||
| Linia 11: | Linia 11: | ||
<quiz> | <quiz> | ||
Klasa <math>\ | Klasa <math>\mathrm{ZPP}</math> to: | ||
<rightoption>klasa języków posiadających algorytm typu Las Vegas</rightoption> | <rightoption>klasa języków posiadających algorytm typu Las Vegas</rightoption> | ||
<wrongoption>suma klas <math>\ | <wrongoption>suma klas <math>\mathrm{RP}</math> oraz <math>\mathrm{coRP}</math></wrongoption> | ||
<wrongoption>klasa języków posiadających algorytm typu Monte Carlo</wrongoption> | <wrongoption>klasa języków posiadających algorytm typu Monte Carlo</wrongoption> | ||
<rightoption>część wspólna klas <math>\ | <rightoption>część wspólna klas <math>\mathrm{RP}</math> oraz <math>\mathrm{coRP}</math></rightoption> | ||
</quiz> | </quiz> | ||
<quiz> | <quiz> | ||
Klasa <math>\ | Klasa <math>\mathrm{PP}</math>: | ||
<wrongoption>jest przydatna z punktu widzenia praktycznego</wrongoption> | <wrongoption>jest przydatna z punktu widzenia praktycznego</wrongoption> | ||
<rightoption>zawiera w sobie klasę <math>\ | <rightoption>zawiera w sobie klasę <math>\mathrm{NP.}</math></rightoption> | ||
<rightoption>jest nieprzydatna z punktu widzenia praktycznego</rightoption> | <rightoption>jest nieprzydatna z punktu widzenia praktycznego</rightoption> | ||
<wrongoption>jest zawarta w klasie <math>\ | <wrongoption>jest zawarta w klasie <math>\mathrm{NP.}</math></wrongoption> | ||
</quiz> | </quiz> | ||
<quiz> | <quiz> | ||
Klasa <math>\ | Klasa <math>\mathrm{BPP}</math>: | ||
<wrongoption>zawiera w sobie klasę <math>\ | <wrongoption>zawiera w sobie klasę <math>\mathrm{NP.}</math></wrongoption> | ||
<rightoption>jest przydatna z punktu widzenia praktycznego</rightoption> | <rightoption>jest przydatna z punktu widzenia praktycznego</rightoption> | ||
<wrongoption>zawiera w sobie klasę <math>\ | <wrongoption>zawiera w sobie klasę <math>\mathrm{PP}</math></wrongoption> | ||
<wrongoption>jest nieprzydatna z punktu widzenia praktycznego</wrongoption> | <wrongoption>jest nieprzydatna z punktu widzenia praktycznego</wrongoption> | ||
<rightoption>jest zawarta w klasie <math>\ | <rightoption>jest zawarta w klasie <math>\mathrm{PP}</math></rightoption> | ||
<wrongoption>jest zawarta w klasie <math>\ | <wrongoption>jest zawarta w klasie <math>\mathrm{NP.}</math></wrongoption> | ||
</quiz> | </quiz> | ||
| Linia 41: | Linia 41: | ||
<quiz> | <quiz> | ||
Problem MAJSAT | Problem MAJSAT | ||
<wrongoption>jest problemem z klasy <math>\ | <wrongoption>jest problemem z klasy <math>\mathrm{NP.}</math></wrongoption> | ||
<rightoption>polega na stwierdzeniu czy większość możliwych wartościowań formuły jest spełniająca</rightoption> | <rightoption>polega na stwierdzeniu czy większość możliwych wartościowań formuły jest spełniająca</rightoption> | ||
<rightoption>jest problemem z klasy <math>\ | <rightoption>jest problemem z klasy <math>\mathrm{PP}</math></rightoption> | ||
<wrongoption>polega na znalezieniu największego leksykograficznie wartościowania spełniającego</wrongoption> | <wrongoption>polega na znalezieniu największego leksykograficznie wartościowania spełniającego</wrongoption> | ||
<rightoption>jest problemem zupełnym z klasy <math>\ | <rightoption>jest problemem zupełnym z klasy <math>\mathrm{PP}</math></rightoption> | ||
</quiz> | </quiz> | ||
| Linia 51: | Linia 51: | ||
<quiz> | <quiz> | ||
Rozpoznawanie liczb pierwszych przy pomocy testu Millera-Rabina jest algorytmem z klasy: | Rozpoznawanie liczb pierwszych przy pomocy testu Millera-Rabina jest algorytmem z klasy: | ||
<wrongoption><math>\ | <wrongoption><math>\mathrm{RP}</math></wrongoption> | ||
<rightoption><math>\ | <rightoption><math>\mathrm{coRP}</math></rightoption> | ||
<wrongoption><math>\ | <wrongoption><math>\mathrm{ZPP}</math></wrongoption> | ||
<rightoption><math>\ | <rightoption><math>\mathrm{BPP}</math></rightoption> | ||
<rightoption><math>\ | <rightoption><math>\mathrm{PP}</math></rightoption> | ||
</quiz> | </quiz> | ||
Aktualna wersja na dzień 23:29, 11 cze 2020
Algorytmy dla języków z klasy :
mają ograniczone prawdopodobieństwo błędu
działają w czasie oczekiwanym wielomianowym
mogą dawać fałszywe odpowiedzi pozytywne
mogą popełniać błąd dwustronny
mogą dawać fałszywe odpowiedzi negatywne
działają w czasie wielomianowym
Klasa to:
klasa języków posiadających algorytm typu Las Vegas
suma klas oraz
klasa języków posiadających algorytm typu Monte Carlo
część wspólna klas oraz
Klasa :
jest przydatna z punktu widzenia praktycznego
zawiera w sobie klasę
jest nieprzydatna z punktu widzenia praktycznego
jest zawarta w klasie
Klasa :
zawiera w sobie klasę
jest przydatna z punktu widzenia praktycznego
zawiera w sobie klasę
jest nieprzydatna z punktu widzenia praktycznego
jest zawarta w klasie
jest zawarta w klasie
Problem MAJSAT
jest problemem z klasy
polega na stwierdzeniu czy większość możliwych wartościowań formuły jest spełniająca
jest problemem z klasy
polega na znalezieniu największego leksykograficznie wartościowania spełniającego
jest problemem zupełnym z klasy
Rozpoznawanie liczb pierwszych przy pomocy testu Millera-Rabina jest algorytmem z klasy:
Prawdopodobieństwo błędu jednej iteracji testu Millera-Rabina wynosi:
