Algoritmning murakkablik sinflari p masalalar sinfi np masalalar sinfi


Download 19.63 Kb.
bet1/2
Sana08.03.2022
Hajmi19.63 Kb.
#600576
  1   2
Bog'liq
13-m
3-m, t ish 1 var12 (1), t ish 2 var 12-variant, 2-lab (1), 4-5-6, ApplicationFile-14, matam5, slayd 4, Slayd 3

13-ma’ruza.
Mavzu: NP- to’liq masalalar. Hisoblashda yechilmaslik hollari
Reja

  1. Algoritmning murakkablik sinflari

  2. P masalalar sinfi

  3. NP masalalar sinfi

  4. NP- to’liq masalalar sinfi

Kalit so’zlar: polynomial, eksponensial, superpolinomial, P masalalar, NP masalalar,
Algortmlar murakkabligini baxolash uchun O-simvolika dan foydalaniladi.
Ushbu baxolash asosida algoritmlarni kuyidagi sinflarga bulish mumkin (kiruvchi ma’lumotla n ga teng bulganda) :

  • Doimiy – murakkablik n ga boglik emas: O(1);

  • Chizikli – murakkablik: O(n);

  • polinomial – murakkablik: O(nm), bu yerda m - konstanta;

  • eksponensial – murakkablik: O(tf(n)), bu yerda t – konstanta > 1, f(n)polinomial funksiya;

  • superpolinomial – murakkablik: O(sf(n)), bu yerda s – konstanta, f(n) – doimiydan tezrok lekin chiziklidan sekinrok usadigan funksiya. Oddiy masalalar (yechib buladigan) –polinomial vaktda yechish mumkin bulan masalalar.

Kiyin yechiladigan masalalar– bu masalalar polinomial vaktda yechilmaydi yoki polinomial vaktda yechish algoritmi topilmaydi.
Sinflarga ajratish
1. P-masalalar (polinomial masalalar) - polinomial vaktda yechish mumkin bulgan masalalar.
2. NP-masalalar (determinirlanmagan polinomial masalalar) fakatgina determinirlanmagan Tyuring mashinasida yechish mumkin bulgan masala. Bu masalalarning javoblari mavjud, ularni topish kiyin lekin polinomial vaktda tekshirish mumkin.
3. NP-tulik masalalar deb, unga NP sinfidan boshqa har qanday masalani polinom vaqtida kamaytirish mumkin. Shunday kilib, tulik masalalar kandaydir ma’noda NP sinfidagi «eng kiyin» masalalar kism tuplamini ifodalaydi.
Agar ularning birontasini yechishning «tez» algoritmi topilsa, u xolda NP sinfdagi ixtiyoriy masala xam shunday «tez» yechish mumkin.
Ixtiyoriy NP – tulik masalani polinomial vaktda yechish algoritmi topilsa NP – masalani xam polinomial vaktda yechish mumkin buladi, ya’ni ularni R-masala deb xisoblash mumkin buladi.
4. EXPTIME sinfi–eksponensial vaktda yechiladigan masalalar sinfi.
5. EXPTIME-tulik masalalar sinfi–determinirlangan polinomial vaktda yechilmaydigan masalalar sinfi.
NP-tulik masalalarga misol

  • Kommivoyajyor masalasi

Grafni buyash masalasi va x.k.

Download 19.63 Kb.

Do'stlaringiz bilan baham:
  1   2




Ma'lumotlar bazasi mualliflik huquqi bilan himoyalangan ©fayllar.org 2022
ma'muriyatiga murojaat qiling