O‘zbekiston respublikasi raqamli texnologiyalar vazirligi

O‘ZBEKISTON RESPUBLIKASI RAQAMLI TEXNOLOGIYALAR VAZIRLIGI

MUHAMMAD AL-XORAZMIY NOMIDAGI TOSHKENT AXBOROT TEXNOLOGIYALARI UNIVERSITETI QARSHI FILIALI

“TELEKOMMUNIKATSIYA TEXNALOGIYALARI VA KASBIY TA'LIM"FAKULTETI

TT-11-21 guruh 2-bosqich talabasining

“ALGORITMNI LOYIHALASH" fanidan tayyorlagan

 MUSTAQIL ISH - 3

 BAJARDI: Ismoilova.M

TEKSHIRDI: Abdullayev. R

MAVZU:

P va NP sinflar, NP-to‘liq masalalar tushunchasi. Algoritmlarni baholash mezonlari. Vaqt va hajim bo’yicha baholshga misollar. Integrallarni taqribiy hisoblashda Nyuton-Kotes formulalari. G’oyalari va hatolik tartibi. Integrallarni taqribiy hisoblashda Gauss formulalari. G’oyasi va hatolik tartibi. Samaradorligi To’plamlarda qisqartma akslantirishlar. Ularga va amaliy tadbiqlarga misollar. Algebraik va transsendent tenglamalarni taqribiy yechishda oraliqni teng ikkiga bo’lish va vatarlar usullarini samaradorlik bo’yicha taqqoslash. Algebraik va transsendent tenglamalarni taqribiy yechishda vatarlar va Nyuton usullarini samaradorlik bo’yicha taqqoslash.

1.P va NP sinflar, NP-to‘liq masalalar tushunchasi. Algoritmlarni baholash mezonlari. Vaqt va hajm bo’yicha baholashga misollar. Vaqt va hajim bo’yicha baholashga misollar.

 P va NP muammosi bu katta kompyuter fanida hal qilinmagan muammo. Yechimi tezda tekshirilishi mumkin bo'lgan har qanday muammoni ham tezda hal qilish mumkinmi, deb so'raydi.

Bu yettitadan biri Ming yillik mukofoti muammolari tomonidan tanlangan Gil Matematika Instituti, ularning har biri birinchi to'g'ri echim uchun 1 000 000 AQSh dollari miqdoridagi mukofotga ega.

Norasmiy atama tez, yuqorida ishlatilgan, an mavjudligini anglatadi algoritm ishlaydigan vazifani hal qilish polinom vaqti, vazifani bajarish vaqti a sifatida o'zgarib turadi polinom funktsiyasi algoritmga kiritish hajmi bo'yicha (masalan, aksincha) eksponent vaqt ). Ba'zi algoritmlar polinom vaqtida javob bera oladigan umumiy savollar klassi "sinf" deb nomlanadi P"yoki shunchaki"P". Ba'zi savollarga javobni tezda topishning ma'lum bir usuli yo'q, ammo agar unga javob nima ekanligini ko'rsatadigan ma'lumot berilsa, javobni tezda tekshirish mumkin. Javob bo'lishi mumkin bo'lgan savollar sinfi tasdiqlangan polinom vaqtiga deyiladi NP, bu "noan'anaviy polinom vaqt" degan ma'noni anglatadi.