3-Mustaqil ishi reja: p va np sinflar,np-to`liq masalalar tushunchasi

3-Mustaqil ishi

REJA:

1.P va NP sinflar,NP-to`liq masalalar tushunchasi.

2.Algoritimlarni baholash mezonlari.

3.Vaqt va hajm bo`yicha baholashga misollar.

4.Integrallarni taqribiy hisoblashda Nyuton-Kotes formulalari.

5.G`oyalari va hatolik tartibi.

6.Integrallarni taqribiy hisoblashda Gauss formulalari.G`oyasi va hatolik tartibi.

7.Samaradorligi to`plamlarida qisqartma akslantirishlar. Va ularga amaliy tadbiqlarga misollar.

8.Algebraik va transsedent tenglamalarni taqribiy yechishda oraliqni teng ikkiga bo`lish va vatarlar usullarini samaradorlik bo`yicha taqqoslash.

9.Algebraik va transsedent tenglamalarni taqribiy yechishda vatarlar va Nyuton usullarini samaradorlik bo`yicha taqqoslash.

Polinom – ba’zi kuchlarga va ularning koeffitsientlariga ko’tarilgan o’zgaruvchilardan tashkil topgan ibora. Masalan, ax² + bx + c shaklidagi ikkinchi darajali ko’paytma.Algoritm vaqt murakkabligi – kirishning uzunligi funktsiyasi sifatida bajarilishi uchun algoritm olgan vaqt. Katta O belgi yordamida umumiy ifodalanadi. Masalan, 2n o’lchamdagi barcha elementlarni birma-bir bosib chiqarish uchun algoritm yozsak, uning vaqt murakkabligi O (n) bo’ladi.Polinomial vaqt murakkabligi – algoritmning vaqt murakkabligi n ^ {O (1)}P = Deterministik Turing mashinasi tomonidan ko’paytirilgan vaqt ichida echiladigan muammolar to’plami. NP = noaniq bo’lmagan polinomik vaqt ichida yechilishi mumkin bo’lgan echimlar muammolarining to’plami (javob ha yoki yo’q) i.e ko’p bo’lmagan vaqt ichida noaniqsiz Turing Machine [4] tomonidan hal qilinishi mumkin.Nondeterministic Turing Machine (NTM) – dallanadigan mashina. Agar hisoblashning keyingi bosqichi uchun ko’plab imkoniyatlar mavjud bo’lsa, ushbu mashina ularning barchasini bir vaqtning o’zida o’chirib qo’yishi mumkin. NTM-lar O (1) vaqtda ko’p variantlardan to’g’ri variantni taxmin qilishga qodir.Npga alternativ ta’rif bu mumkin bo’lgan echim taqdim etilsa, DTM polinomik vaqt ichida uning to’g’riligini tekshirishga imkon beradigan qarorlar to’plamidir. Shuni ta’kidlash kerakki, barcha P muammolar NP ga ham tegishli, chunki agar muammo DTM tomonidan ko’p martali hal qilinsa, mumkin bo’lgan echimni tekshirish hal qilishdan osonroq bo’ladi. Shunday qilib, DTM ham ko’plik vaqt ichida ham tekshirishi mumkin edi. Shunday qilib, arzimas, P ⊆ NP i.e P NP ning pastki qismi.Bugungi kunda mavjud bo’lgan barcha kompyuterlar DTM va NTM fikrlash tajribalarida ishlatiladigan sof nazariy kompyuter ekanligini bilish ham muhimdir. Professor Erik Demain aytganidek [1].”Demak, bu (NTM) ancha kuchli model. Albatta, bunday ishlaydigan kompyuterlar yo’q, afsuski, men ko’proq qiziqayapman ”.

• Polinom – ba’zi kuchlarga va ularning koeffitsientlariga ko’tarilgan o’zgaruvchilardan tashkil topgan ibora. Masalan, ax² + bx + c shaklidagi ikkinchi darajali ko’paytma.Algoritm vaqt murakkabligi – kirishning uzunligi funktsiyasi sifatida bajarilishi uchun algoritm olgan vaqt. Katta O belgi yordamida umumiy ifodalanadi. Masalan, 2n o’lchamdagi barcha elementlarni birma-bir bosib chiqarish uchun algoritm yozsak, uning vaqt murakkabligi O (n) bo’ladi.Polinomial vaqt murakkabligi – algoritmning vaqt murakkabligi n ^ {O (1)}P = Deterministik Turing mashinasi tomonidan ko’paytirilgan vaqt ichida echiladigan muammolar to’plami. NP = noaniq bo’lmagan polinomik vaqt ichida yechilishi mumkin bo’lgan echimlar muammolarining to’plami (javob ha yoki yo’q) i.e ko’p bo’lmagan vaqt ichida noaniqsiz Turing Machine [4] tomonidan hal qilinishi mumkin.Nondeterministic Turing Machine (NTM) – dallanadigan mashina. Agar hisoblashning keyingi bosqichi uchun ko’plab imkoniyatlar mavjud bo’lsa, ushbu mashina ularning barchasini bir vaqtning o’zida o’chirib qo’yishi mumkin. NTM-lar O (1) vaqtda ko’p variantlardan to’g’ri variantni taxmin qilishga qodir.Npga alternativ ta’rif bu mumkin bo’lgan echim taqdim etilsa, DTM polinomik vaqt ichida uning to’g’riligini tekshirishga imkon beradigan qarorlar to’plamidir. Shuni ta’kidlash kerakki, barcha P muammolar NP ga ham tegishli, chunki agar muammo DTM tomonidan ko’p martali hal qilinsa, mumkin bo’lgan echimni tekshirish hal qilishdan osonroq bo’ladi. Shunday qilib, DTM ham ko’plik vaqt ichida ham tekshirishi mumkin edi. Shunday qilib, arzimas, P ⊆ NP i.e P NP ning pastki qismi.Bugungi kunda mavjud bo’lgan barcha kompyuterlar DTM va NTM fikrlash tajribalarida ishlatiladigan sof nazariy kompyuter ekanligini bilish ham muhimdir. Professor Erik Demain aytganidek [1].”Demak, bu (NTM) ancha kuchli model. Albatta, bunday ishlaydigan kompyuterlar yo’q, afsuski, men ko’proq qiziqayapman ”.