szukanie zaawansowane
 [ Posty: 3 ] 
Autor Wiadomość
Mężczyzna Offline
PostNapisane: 12 sty 2018, o 23:59 
Użytkownik

Posty: 322
Lokalizacja: warszawa
Uzupełnij wyrażenie:

Cytuj:
Niedeterministyczna maszyna Turinga w stosunku do maszyny deterministycznej dla tego samego problemu praktycznie (w sensie klasy złożoności) wykonuje ………. kroków, a zużywa ………. komórek taśmy

W polu może być: mniej, więcej, tyle samo
Uniwersytet Wrocławski Instytut Matematyczny - rekrutacja 2018
Góra
Mężczyzna Offline
PostNapisane: 13 sty 2018, o 12:27 
Użytkownik

Posty: 179
więcej kroków, a zużywa mniej komórek taśmy

Zauważ, jaka jest różnica między Maszyną Turingą a DAS(Deterministyczny Automat Skończony).
DAS tylko czyta, a Turing może zmienić wartosc w każdym polu.
Góra
Kobieta Offline
PostNapisane: 15 cze 2018, o 23:11 
Użytkownik

Posty: 8
Lokalizacja: śląsk
Udowodnij, że:

Predykat L należy do klasy BPP wtedy i tylko wtedy, gdy istnieje predykat R \left( \overline{x}, \overline{y}\right) rozstrzygalny deterministycznie w czasie poly \left( \overline{x}+\overline{y}\right) i wielomian p \left( z \right) \in Z \left[ z\right] takie, że
\overline{x} \in L  \Leftarrow proporcja zbioru\left\{ y \in  \left( \overline{x}, \overline{y}\right) \right\} w zbiorze \left\{ \overline{y} : \left| y \right| \right\ < p\left( \left| \overline{x} \right| \right) } jest większa niż 1- \epsilon.

\overline{x}\not \in L  \Leftarrow proporcja zbioru \left\{ y \in  \left( \overline{x}, \overline{y}\right) \right\} w zbiorze \left\{ \overline{y} : \left| y \right| \right\ < p\left( \left| \overline{x} \right| \right) } jest większa niż \epsilon.
Góra
Utwórz nowy temat Odpowiedz w temacie  [ Posty: 3 ] 


 Zobacz podobne tematy
 Tytuł tematu   Autor   Odpowiedzi 
 [Teoria złożoności] Złożoność rekurencyjna - zadanie 2  krystian987  1
 Maszyna Turinga - zadanie 2  Callan-Grey  1
 [Teoria złożoności] Drzewa rozpinające, algorytm tour  buzzek90  0
 [Maszyna Turinga] Problemy decyzyjne, równoważność gramatyk  WojtekF  0
 [Teoria złożoności] Wylicz złożoność algorytmu  pawlo392  1
 
Atom [Regulamin Forum] [Instrukcja LaTeX-a] [Poradnik] [F.A.Q.] [Reklama] [Kontakt]
Copyright (C) Karpatka.pl