Lari universiteti "Axborot tizimlarining dasturiy ta’minoti" kafedrasi
Download 234.41 Kb.
|
Yursunov Dadaxon Algoritm.L Qayta topshirish
|
MUHAMMAD AL - XORAZMIY NOMIDAGI TOSHKENT AXBOROT TEXNOLOGIYALARI UNIVERSITETI “Axborot tizimlarining dasturiy ta’minoti” kafedrasi “Algoritmlarni loyihalash” fanidan
Qayta topshirish ishi Variant № 35 Guruh: 315-18 Bajardi: Yursunov Dadaxon Tekshirdi: dots. Ishmuxamedov A.X. Toshkent 2021
Рекуррент алгоритмлар деганда нимани тушунасиз? Даражали қатор деб нимага айтилади? NP-тўликликга мисоллар келтиринг. Javoblar: Rekurrent algoritmlar deganda nimani tushunasiz? Hisoblash jarayonida ba’zi bir algoritmlarning o‘ziga qayta murojaat qilishga to‘g‘ri keladi. O‘ziga–o‘zi murojaat qiladigan algoritmlarga rekkurent algoritmlar yoki rekursiya deb ataladi. Bunday algoritmga misol sifatida Fibonachchi sonlarini keltirish mumkin. Ma’lumki, Fibonachchi sonlari quyidagicha aniqlangan. F0 ; F1 ; … ; Fi = Fi-1 + Fi-2 ; i > 1 Bu rekkurent ifoda algoritmiga mos keluvchi blok-sxema va MathCad dastur kodi #-rasmda keltirilgan. Eslatib o‘tamiz formuladagi i-indeksga hojat yo‘q, agar Fibonachchi sonining tartib raqamini ham aniqlash zarur bo‘lsa, birorta parametr-kalit kiritish kerak bo‘ladi. Rasm. Fibonachchi sonlarining n-hadini hisoblash algoritm blok-sxemasi. Amalda shunday bir masalalar uchraydiki, ularda takrorlanishlar soni oldindan berilmagan-noma’lum bo‘ladi. Ammo, bu jarayonni tugatish uchun biror bir shart berilgan bo‘ladi. Masalan, quyidagi qatorda nechta had bilan chegaralanish berilmagan. Lekin qatorni ε aniqlikda hisoblash zarur bo‘ladi. Buning uchun | 1/i | > ε shartni olish mumkin. 2-Rasm. Takrorlanishlar soni oldindan no’malum bo‘lgan algoritmlarga doir blok-sxema. Darajali qator deb nimaga aytiladi? Darajali qator tushunchasi. Abel teoremasi. Funksional qatorlar orasida, ularning xususiy holi bo‘lgan ushbu yoki, umumiyroq, qatorlar (bunda o‘zgarmas haqiqiy sonlar) matematikada va uning tatbiqlarida muhim rol o‘ynaydi. Bu yerda funksional qatorning umumiy hadi sifatida un(x)=anxn (yoki un(x)=(x–x0)n), ya’ni x (yoki (x–x0)) darajalari qaralayapti, shu sababli (1) va (2) qatorlar darajali qatorlar deb ataladi. Agar (2) qatorda x-x0=t deb olinsa, u holda bu qator t o‘zgaruvchiga nisbatan (1) qator ko‘rinishga keladi. Demak, (1) ko‘rinishdagi qatorlarni o‘rganish yetarli. (1) ifodadagi haqiqiy sonlar darajali qatorning koeffitsientlari deb ataladi. Darajali qatorlar bir-biridan faqat koeffitsientlari bilangina farq qiladi. Demak, darajali qator berilgan deganda uning koeffitsientlari berilgan deganini tushunamiz. Ixtiyoriy (1) darajali qator x=0 nuqtada yaqinlashuvchi bo‘ladi. Darajali qatorning yaqinlashish sohasini aniqlashda quyidagi Abel teoremasi muhim rol o‘ynaydi. 1-teorema. (Abel) Agar (1) qator x ning x=x0 (x00) qiymatida yaqinlashuvchi bo‘lsa, x ning |x |<|x0| (3) tengsizlikni qanoatlantiruvchi barcha qiymatlarida (1) darajali qator absolyut yaqinlashuvchi bo‘ladi. Natija. Agar (1) qator x ning x=x1 (x10) qiymatida uzoqlashuvchi bo‘lsa, x ning |x|>|x1| tengsizlikni qanoatlantiruvchi barcha qiymatlarida uzoqlashuvchi bo‘ladi. 2. Darajali qatorning yaqinlashish sohasi, yaqinlashish radiusi. 2-teorema. Agar (1) darajali qator x ning (x0) ba’zi qiymatlarida yaqinlashuvchi, ba’zi qiymatlarida uzoqlashuvchi bo‘lsa, u holda shunday yagona r>0 son topilib, (1) darajali qator x ning |x|<r tengsizlikni qanoatlantiruvchi qiymatlarida absolyut yaqinlashuvchi, |x|>r tengsizlikni qanoatlantiruvchi qiymatlarida uzoqlashuvchi bo‘ladi. Yuqoridagi teoremada topilgan r soni (1) darajali qatorning yaqinlashish radiusi, (–r;r) interval darajali qatorning yaqinlashish intervali deyiladi. Agar darajali qator faqat x=0 nuqtadagina yaqinlashuvchi bo‘lsa, u holda r=0; agar darajali qator ixtiyoriy x haqiqiy qiymatida yaqinlashuvchi bo‘lsa, u holda r=+ deb qabul qilamiz. r chekli bo‘lgan holda x=r nuqtalarda qatorning yaqinlashish masalasini hal qilish uchun darajali qatorni shu nuqtalarda alohida tekshirish kerak. 6. Darajali qatorlarning xossalari. Bizga darajali qator berilgan bo‘lsin. 1-xossa. Agar (1) qatorning yaqinlashish radiusi r (r>0) bo‘lsa, u holda bu qator [–c;c] (0<c<r) kesmada tekis yaqinlashuvchi bo‘ladi. 2-xossa. Agar darajali qatorning yaqinlashish radiusi r>0 bo‘lsa, u holda bu qatorning S(x)= yig‘indisi (–r;r) intervalda uzluksiz funksiya bo‘ladi. 3-xossa. Agar darajali qatorning yaqinlashish radiusi r>0 bo‘lsa, u holda bu qatorni [a;b] ([a;b](–r;r) ) kesmada hadma-had integrallash mumkin. 4-xossa. Agar darajali qatorning yaqinlashish radiusi r>0 bo‘lsa, u holda bu qatorni (–r;r) da hadma-had differensiallash mumki 3. NP to'liqligiga misollar keltiring Amaliy jihatdan qiziqarli bo'lgan vazifalarning aksariyati polinomial algoritmlardir. Ya'ni n uzunlikdagi kirishda algoritmning ishlash muddati doimiy k (kirish uzunligidan mustaqil) uchun O (nk) dan oshmaydi. Har qanday muammo ham ushbu xususiyatni qondiradigan echim algoritmiga ega emas. Ba'zi muammolarni hech qanday algoritm bilan umuman hal qilib bo'lmaydi. Bunga klassik misol - "to'xtash muammosi" (ma'lum bir dastur ma'lum bir kirish qismida to'xtashini bilish). Bundan tashqari, ularni echadigan algoritm bilan bog'liq muammolar mavjud, har qanday bunday algoritm uzoq vaqt ishlaydi - uning ishlash muddati har qanday sobit k uchun O (nk) bo'la olmaydi. Agar biz amaliy algoritmlar va faqat nazariy qiziqish algoritmlari o'rtasida qo'pol, ammo rasmiy chegara o'tkazmoqchi bo'lsak, unda birinchi bo'lib uzoq vaqt davomida ishlaydigan algoritmlar sinfi keladi. NP -complete deb nomlangan muammolar sinfini ko'rib chiqamiz. Ushbu muammolar uchun polinom algoritmlari topilmadi, ammo bunday algoritmlar mavjud emasligi isbotlanmagan. NP bilan bog'liq muammolarni o'rganish "P = NP" deb nomlangan savol bilan bog'liq. Bu savol 1971 yilda berilgan va hozirda hisoblash nazariyasidagi eng qiyin masalalardan biri hisoblanadi. Nima uchun dasturchi NP muammolari haqida bilishi kerak? Agar biron bir NPning to'liqligini isbotlash mumkin bo'lsa, uni deyarli erimaydi deb hisoblash uchun asos bor. Bunday holda, uni aniq hal qiladigan tezkor algoritm izlashni davom ettirishdan ko'ra, taxminiy algoritmni tuzishga vaqt sarflash yaxshiroqdir. NP to'liqligi masalasining kuchli tomoni Agar masalaning qisman muammolari bo'lsa, u kuchli NP bilan to'ldirilgan muammo deb nomlanadi, bu erda: masalaning sonli parametrlari bo'lmasa (ya'ni, bu masalada uchraydigan kattaliklarning maksimal qiymati yuqoridan chegaralangan bo'lsa) polinom uzunligi). 1. Masalaning sonli parametrlari bo'lmagan taqdirda (ya'ni bu masalada uchraydigan kattaliklarning maksimal qiymati yuqoridan polinom uzunligi bilan chegaralangan). 2. NP-to'liqligi masalasi. Bunday vazifalar sinfi NPCS deb nomlanadi. Agar P ≠ NP gipotezasi to'g'ri bo'lsa, unda NPCS muammosi uchun xayoliy polinom algoritmi mavjud emas. NP bilan to'ldirilgan muammolarga misollar • Mantiqiy formulalarni bajarish • "Spots" n × n o'lchamdagi eng qisqa echimdir • tovar masalasi • Shtayner muammosi • Grafikni bo'yash muammosi • Yuzaki qoplama masalasi • Paket muammosi • Tanlov masalasi • To'plamning mustaqilligi masalasi • Sapper (o'yin) • Tetris
NP-murakkab masalalarni hal qilish usullari quyidagilarga bo'linadi: aniq, evristik metaevristik usullari Aniq usullar barcha mumkin bo'lgan yechimlarni to'liq ko’rib chiqishga (полный перебор) asoslanadi va bu o'z navbatida ularning samadorligini kamaytiradi. Evristik usullar yechimlarni nisbatan cheklangan qidirishga olib keladi va odatda maqbul vaqt ichida juda yaxshi yechimni topadi. Ammo bu usullar ham kamchilikka ega, ya'ni ular taxminiydir. Metaevristik usullar eng samarali hisoblanadi, ammo bu usullarda natijaga bevosita ta'sir qiladigan parametr mavjud, kirish ma'lumotlariga asoslanib, amalda har safar ushbu parametrni qayta hisoblash kerak. Download 234.41 Kb. Do'stlaringiz bilan baham: 
|