1 Algoritm murakkabligini statik va dinamik o‘lchovlari. Vaqt va xotira hajimi bo‘yicha qiyinchiliklar



Download 101,89 Kb.
bet5/19
Sana14.06.2022
Hajmi101,89 Kb.
#672007
1   2   3   4   5   6   7   8   9   ...   19
Bog'liq
1 Algoritm murakkabligini statik va dinamik o‘lchovlari. Vaqt va

Qiyinchilik sinflari
Polinom vaqt tushunchasi hisoblash murakkabligi nazariyasida bir necha murakkablik sinflariga olib keladi. Polinom vaqti yordamida aniqlangan ba'zi muhim sinflar quyida ko'rsatilgan.

  • : Polinom vaqtida deterministik Tyuring mashinasida echilishi mumkin bo'lgan echilishi mumkin bo'lgan muammolarning murakkablik sinfi.

  • : Polinom vaqtida deterministik bo'lmagan Tyuring mashinasida echilishi mumkin bo'lgan echilishi mumkin bo'lgan muammolarning murakkablik sinfi.

  • ZPP: Polinom vaqtida ehtimolli Tyuring mashinasida nol xato bilan echilishi mumkin bo'lgan echilishi mumkin bo'lgan muammolarning murakkablik sinfi.

  • : Polinom vaqtida ehtimolli Tyuring mashinasida bir tomonlama xatolar bilan echilishi mumkin bo'lgan echilishi mumkin bo'lgan muammolarning murakkablik klassi.

  • BPP polinom vaqtidagi ehtimollik Tyuring mashinasi.

  • BQP: Polinom vaqtida kvant Tyuring mashinasida ikki tomonlama xatolar bilan echilishi mumkin bo'lgan echilishi mumkin bo'lgan muammolarning murakkablik klassi.

P - deterministik mashinadagi eng kichik vaqt murakkabligi sinfi, ya'ni barqaror mashina modelini o'zgartirish nuqtai nazaridan. (Masalan, bitta lentali Tyuring mashinasidan ko'p tarmoqli Tyuring mashinasiga o'tish kvadratik tezlikka olib kelishi mumkin, lekin bir modelda polinom vaqtida ishlaydigan har qanday algoritm boshqasida polinom vaqtida ishlaydi.)
Super polinom vaqti
Algoritm ishlashi aytiladi superpolinom vaqti, agar T(n) yuqorida ko‘phad bilan chegaralanmagan. Bu vaqt ō ga teng ( n c) barcha konstantalar uchun c, qayerda n kirish parametri, odatda kirish bitlari soni.
Masalan, 2 ni amalga oshiradigan algoritm n hajmini kiritish uchun qadamlar n superpolinom vaqtni talab qiladi (aniqrog'i, eksponensial vaqt).
Ko'rsatkichli resurslardan foydalanadigan algoritm superpolinom ekanligi aniq, lekin ba'zi algoritmlar juda zaif superpolinomdir. Masalan, Adleman-Pomeranza-Roumeli soddaligi testi * vaqt uchun ishlaydi n O (jurnal jurnali n) ustida n-bit kiritish. U etarlicha katta bo'lgan har qanday polinomdan tezroq o'sadi n, lekin kirishning o'lchami juda katta bo'lishi kerak, shuning uchun u kichik darajadagi polinom tomonidan hukmronlik qilmasligi kerak.
Superpolinom vaqt talab qiladigan algoritm murakkablik sinfidan tashqarida. Kobhamning tezislari bu algoritmlar amaliy emas, deb da'vo qiladi va ko'p hollarda ular. P va NP sinflarining tengligi masalasi hal etilmaganligi sababli, hozirgi vaqtda NP-to'liq masalalarni polinom vaqtida yechish algoritmlari ma'lum emas.

Download 101,89 Kb.

Do'stlaringiz bilan baham:
1   2   3   4   5   6   7   8   9   ...   19




Ma'lumotlar bazasi mualliflik huquqi bilan himoyalangan ©hozir.org 2024
ma'muriyatiga murojaat qiling

kiriting | ro'yxatdan o'tish
    Bosh sahifa
юртда тантана
Боғда битган
Бугун юртда
Эшитганлар жилманглар
Эшитмадим деманглар
битган бодомлар
Yangiariq tumani
qitish marakazi
Raqamli texnologiyalar
ilishida muhokamadan
tasdiqqa tavsiya
tavsiya etilgan
iqtisodiyot kafedrasi
steiermarkischen landesregierung
asarlaringizni yuboring
o'zingizning asarlaringizni
Iltimos faqat
faqat o'zingizning
steierm rkischen
landesregierung fachabteilung
rkischen landesregierung
hamshira loyihasi
loyihasi mavsum
faolyatining oqibatlari
asosiy adabiyotlar
fakulteti ahborot
ahborot havfsizligi
havfsizligi kafedrasi
fanidan bo’yicha
fakulteti iqtisodiyot
boshqaruv fakulteti
chiqarishda boshqaruv
ishlab chiqarishda
iqtisodiyot fakultet
multiservis tarmoqlari
fanidan asosiy
Uzbek fanidan
mavzulari potok
asosidagi multiservis
'aliyyil a'ziym
billahil 'aliyyil
illaa billahil
quvvata illaa
falah' deganida
Kompyuter savodxonligi
bo’yicha mustaqil
'alal falah'
Hayya 'alal
'alas soloh
Hayya 'alas
mavsum boyicha


yuklab olish