Złożoność obliczeniowa/Test 3: Klasy złożoności obliczeniowej: Różnice pomiędzy wersjami

Z Studia Informatyczne
Przejdź do nawigacjiPrzejdź do wyszukiwania
WizualnieWikikod
Rogoda (dyskusja | edycje)
1875 edycji
Nie podano opisu zmian
 
m Zastępowanie tekstu - "\cc{" na "\mathrm{"
 
(Nie pokazano 5 wersji utworzonych przez 2 użytkowników)
Linia 10: Linia 10:


<quiz>
<quiz>
<math>\cc{NL</quiz></math> jest klasą języków, które mogą być akceptowane:  
<math>\mathrm{NL}</math> jest klasą języków, które mogą być akceptowane:  
<wrongoption>w niedeterministycznym czasie liniowym</wrongoption>
<wrongoption>w niedeterministycznym czasie liniowym</wrongoption>
<wrongoption>w deterministycznej pamięci logarytmicznej</wrongoption>
<wrongoption>w deterministycznej pamięci logarytmicznej</wrongoption>
Linia 29: Linia 29:
<quiz>
<quiz>
Tezą twierdzenia Savitcha jest:  
Tezą twierdzenia Savitcha jest:  
<rightoption><math>\cc{NSPACE</quiz>(f(n))\subseteq\cc{SPACE}(f^2(n))</math></rightoption>
<rightoption><math>\mathrm{NSPACE}(f(n))\subseteq\mathrm{SPACE}(f^2(n))</math></rightoption>
<wrongoption><math>\cc{NSPACE</quiz>(f(n))\subseteq\cc{SPACE}(\textnormal{log</quiz>(n))</math></wrongoption>
<wrongoption><math>\mathrm{NSPACE}(f(n))\subseteq\mathrm{SPACE}(\text{log}(n))</math></wrongoption>
<wrongoption><math>\cc{SPACE</quiz>(f(n))\subseteq\cc{NSPACE}(f^2(n))</math></wrongoption>
<wrongoption><math>\mathrm{SPACE}(f(n))\subseteq\mathrm{NSPACE}(f^2(n))</math></wrongoption>
<wrongoption><math>\cc{SPACE</quiz>(f^2(n))\subseteq\cc{NSPACE}(f(n))</math></wrongoption>
<wrongoption><math>\mathrm{SPACE}(f^2(n))\subseteq\mathrm{NSPACE}(f(n))</math></wrongoption>
</quiz>
</quiz>


Linia 53: Linia 53:




<quiz>Zawieranie klas<quiz>
<quiz>
Jak klasa <math>\cc{L}</math> ma się do <math>\cc{PSPACE}</math>? {
Jak klasa <math>\mathrm{L}</math> ma się do <math>\mathrm{PSPACE}</math>?  
<rightoption></rightoption><math>\cc{L}</math> zawiera się ściśle w <math>\cc{PSPACE}</math>
<rightoption><math>\mathrm{L}</math> zawiera się ściśle w <math>\mathrm{PSPACE}</math></rightoption>
<wrongoption>nie wiadomo nic na ten temat</wrongoption>
<wrongoption>nie wiadomo nic na ten temat</wrongoption>
<wrongoption><math>\cc{L}</math> zawiera się w <math>\cc{PSPACE}</math>, ale nie wiemy czy ściśle</wrongoption>
<wrongoption><math>\mathrm{L}</math> zawiera się w <math>\mathrm{PSPACE}</math>, ale nie wiemy czy ściśle</wrongoption>
<wrongoption><math>\cc{PSPACE}</math> zawiera się ściśle w <math>\cc{L}</math></wrongoption>
<wrongoption><math>\mathrm{PSPACE}</math> zawiera się ściśle w <math>\mathrm{L}</math></wrongoption>
<wrongoption><math>\cc{PSPACE}</math> zawiera się w <math>\cc{L}</math>, ale nie wiemy czy ściśle</wrongoption>
<wrongoption><math>\mathrm{PSPACE}</math> zawiera się w <math>\mathrm{L}</math>, ale nie wiemy czy ściśle</wrongoption>
</quiz>
</quiz>

Aktualna wersja na dzień 23:29, 11 cze 2020

Liniowe przyspieszanie działania maszyny uzyskujemy poprzez:

zwiększenie liczby stanów

zmniejszenie alfabetu maszyny

zwiększenie alfabetu maszyny

wstępne przetworzenie danych

zmniejszenie liczby stanów


NL jest klasą języków, które mogą być akceptowane:

w niedeterministycznym czasie liniowym

w deterministycznej pamięci logarytmicznej

w niedeterministycznej pamięci logarytmicznej

w deterministycznym czasie liniowym


W jak wielu konfiguracjach może znaleźć się maszyna Turinga o złożoności pamięciowej f(n) (asymptotycznie)?

cf(n)

f(n)c

f(n)

cf(n)


Tezą twierdzenia Savitcha jest:

NSPACE(f(n))⊆SPACE(f2(n))

NSPACE(f(n))⊆SPACE(log(n))

SPACE(f(n))⊆NSPACE(f2(n))

SPACE(f2(n))⊆NSPACE(f(n))


Klasy zamknięte na operację dopełnienia to:

klasy deterministyczne

klasy niedeterministyczne czasowe

klasy niedeterministyczne pamięciowe


Która rodzina klas podlega hierarchii?

tylko złożoności czasowej

tylko złożoności pamięciowej

zarówno złożoności czasowej jak i pamięciowej

żadne z powyższych


Jak klasa L ma się do PSPACE?

L zawiera się ściśle w PSPACE

nie wiadomo nic na ten temat

L zawiera się w PSPACE, ale nie wiemy czy ściśle

PSPACE zawiera się ściśle w L

PSPACE zawiera się w L, ale nie wiemy czy ściśle

Źródło: „https://wazniak.mimuw.edu.pl/index.php?title=Złożoność_obliczeniowa/Test_3:_Klasy_złożoności_obliczeniowej&oldid=77675”