Muhammad al-xorazmiy nomidagi toshkent axborot texnologiyalari universiteti urganch filiali



Yüklə 81,97 Kb.
səhifə16/19
tarix12.05.2023
ölçüsü81,97 Kb.
#112452
1   ...   11   12   13   14   15   16   17   18   19
1 Algoritm murakkabligini statik va dinamik o‘lchovlari. Vaqt va

Algoritm murakkabligi sinflari
Aniq qiyinchilik sinflari: Bular xuddi shunday qiyinchilikka ega toifalar.
Quyidagi asosiy qiyinchilik sinflari ajratiladi:
DTIME Tyuring mashinasi muammoning yechimini cheklangan vaqt ichida (qadamlar soni) topadi. Algoritmning asimptotikasi ko'pincha belgilanadi, shuning uchun aytaylik, agar ish vaqtining o'sish tartibi \ (T (n) = \ mathcal (O) (f (n)) \), keyin \ (DTIME (f) bo'lsa. (n)) \) ko'rsatilgan. P Turing mashinasi muammoning yechimini polinom vaqtida (qadamlar soni) topadi, ya'ni. \ (T (n) = \ matematik (O) (n ^ k) \), bu erda \ (k \ in \ mathbb (N) \). \ (P = DTIME (n ^ k) \) EXPTIME Tyuring mashinasi muammoning yechimini eksponensial vaqtda (qadamlar soni) topadi, ya'ni. \ (T (n) = \ matematik (O) (2 ^ (n ^ k)) \), bu erda \ (k \ in \ mathbb (N) \). \ (EXPTIME = DTIME (2 ^ (n ^ k)) \). DSPACE Turing mashinasi cheklangan miqdordagi qo'shimcha xotira (hujayralar) yordamida muammoning yechimini topadi. Algoritmning asimptotikasi ko'pincha belgilanadi, shuning uchun aytaylik, agar xotira iste'molining o'sish tartibi \ (S (n) = \ mathcal (O) (f (n)) \), keyin \ (DSPACE (f ()) n)) \) ko'rsatilgan. L Tyuring mashinasi logarifmik fazoviy murakkablikdagi muammoning yechimini topadi, ya'ni. \ (S (n) = \ matematik (O) (\ log n) \)... \ (L = DSPACE (\ log n) \). PSPACE Tyuring mashinasi polinom fazoviy murakkablikdagi masalaning yechimini topadi, ya'ni \ (S (n) = \ mathcal (O) (n ^ k) \), bu erda \ (k \ in \ mathbb (N) \ ). \ (PSPACE = DSPACE (n ^ k) \). EXPSPACE Turing mashinasi eksponensial fazoviy murakkablikdagi muammoning yechimini topadi, ya'ni. \ (S (n) = \ matematik (O) (2 ^ (n ^ k)) \), bu erda \ (k \ in \ mathbb (N) \). \ (EXPSPACE = DSPACE (2 ^ (n ^ k)) \).
Bundan tashqari, kontseptsiyada ishlaydigan nazariy murakkablik sinflari mavjud aniqlanmagan Tyuring mashinalari (TMT). Ularning ta'riflari yuqoridagilarga to'g'ri keladi, Tyuring mashinasini NMT bilan almashtirish va nomlar N prefiksiga ega (masalan, NP), NTIME va NSPACE bundan mustasno, bu erda D N bilan almashtiriladi.
NMT - bu sof nazariy konstruktsiya bo'lib, u o'zining ishlash tamoyillari bo'yicha MTga o'xshaydi, farqi bilan har bir shtat uchun mavjud bo'lishi mumkin. bir nechta mumkin bo'lgan harakatlar. Shu bilan birga, NMT har doim mumkin bo'lgan harakatlardan minimal mumkin bo'lgan qadamlar sonida yechimga olib keladiganini tanlaydi. Xuddi shunday, HMT hisoblaydi hammasidan novdalar va minimal mumkin bo'lgan qadamlar sonida yechimga olib keladigan filialni tanlaydi.
Ba'zida kvant kompyuterlari HMT ning qo'llanilishi deb eshitiladi. Ba'zi hollarda bu to'g'ri ko'rinishi mumkin bo'lsa-da, umuman olganda, HMT kvant kompyuteriga qaraganda kuchliroq tizimdir.
Ma'lumki \ (P \ subseteq NP \ subseteq PSPACE \ subseteq EXPTIME \ subseteq NEXPTIME \ subseteq EXPSPACE \)
Shuningdek, \ (P \ subsetneq EXPTIME \), \ (NP \ subsetneq NEXPTIME \), \ (PSPACE \ subsetneq EXPSPACE \)
Bundan tashqari, ma'lumki, agar \ (P = NP \), keyin \ (EXPTIME = NEXPTIME \).
P va NP tengligi masalasi zamonaviy kompyuter fanining hal qilinmagan asosiy savollaridan biridir.

Yüklə 81,97 Kb.

Dostları ilə paylaş:
1   ...   11   12   13   14   15   16   17   18   19




Verilənlər bazası müəlliflik hüququ ilə müdafiə olunur ©azkurs.org 2024
rəhbərliyinə müraciət

gir | qeydiyyatdan keç
    Ana səhifə


yükləyin