Yakuniy nazorat Savollar
Download 24.6 Kb.
|
Muxamadaliyev Murodjon CAL013 gr
- Bu sahifa navigatsiya:
- Yakuniy nazorat Savollar 31-variant 1.Cheksiz bajariladigan algoritmlar
- Noaniqlik bo’lmasligi
- Algoritmning tasvirlash usullari
- 1.Algoritmning so‘zlar orqali ifodalanishi
- 2.Kantorning dioganal usuli
- 3.Nima sababdan algoritmlarning samaradorligini baholash amalga oshiriladi
Yakuniy nazorat Savollar 31-variant 1.Cheksiz bajariladigan algoritmlar 2.Kantorning dioganal usuli 3.Nima sababdan algoritmlarning samaradorligini baholash amalga oshiriladi? 1.Cheksiz bajariladigan algoritmlar Cheksiz bajariladigan algoritmlar Algoritm - bu muayyan maqsadga erishishga qaratilgan muayyan ijrochiga tegishli amallar ketma-ketligi. Algoritmning aniqligi, shuningdek, amalda ishlatiladigan barcha algoritmlarga xos bo'lmagan xususiyatdir. Real vaqt rejimida ob'ektlarni boshqarish uchun ishlatiladigan deyarli barcha algoritmlar cheksiz emas: kosmik stantsiyaning parvozini yoki yadroviy reaktorning ishlashini kompyuter tomonidan boshqarishning cheklangan algoritmini (ya'ni, sonli qadamlardan keyin ishni to'xtatish) tasavvur qilish qiyin. Albatta, bunday algoritmlar, qoida tariqasida, inson aralashuvi uchun kutish rejimini o'z ichiga oladi (ma'lum bir tugmachani bosish, sichqonchani bosish va boshqalar), ammo bunday algoritm o'z qurilmalarida cheklangan emas. Ammo cheksiz bajariladigan algoritmlar algoritmlarning umumiy nazariyasida muhim rol o'ynaydi. Mana bunday algoritmga misol. Rassom ikki harfning alfavitida yozilgan so'zlarni qayta ishlaydi - a va b. Ijrochining maqbul xatti-harakatlari ikkita so'zning birida X so'zidan Y so'ziga o'tishdir: a) agar X aP shakliga ega bo'lsa, unda P - harflardagi harflar, keyin Y = Pb; b) agar X da b shakli bo'lsa, R bu alifbo ustidagi har qanday so'z bo'lsa, Y = Paba. Algoritmning o'zi quyidagicha ko'rinadi: alg so'zlar (arg sim X, res Y Y) tilanchilik kiritish X; Y: = X;
Y so'zini olganingizcha, bb harfi bilan boshlanadi, harakatni Y so'ziga qo'llang qo'llanilishi mumkin natijani yana Y tomonidan belgilang; Chiqish Y End. 2-qarash: Bilamizki, dasturchining ishi kompyuterga biror vazifani bajarishni buyurishdan iborat. Masalan, kichkina ukangizga yoki singlingizga: “Kelgunimcha barcha darslaringi qilib qo’y” deysiz. U sizni tushunadi va bajaradi. Kompyuter bilan ham shunga o’xshash. Farqi kompyuterning ukangizdek “tushunishi” yoki “farosati” yuqori emas. Uning o’z tili bor (alifbosi faqat 0 va 1 dan iborat: nega?). U bizni tushunishi uchun dasturlash tillari mavjud lekin shunda ham u biz gaplashadigan tildan ancha cheklangan va qat’iy qoidalarga asoslanadi. Unga eng yosh bolaga tushuntirganday tushuntirish kerak. Masalan, 3 yashar bolayam 1 dan 5 gacha sana desangiz, sanab beroladi. Lekin kompyuterda bu quyidagicha bosqichda buyurilishi kerak: 1. x nomli butun sonli o’zgaruvchi yarat va unga 0 ni o’zlashtir (x=0). 2. x 5 dan kichik bo’lganda: 3. unga 1 ni qo’shib ekranda yangi qatorda ko’rsat.
int x=0; while (x < 5) { x = x + 1; System.out.println(x); } Buni umumlashtirib, 1 dan n gacha sanash algoritmini yaratish ham mumkin (n ni foydalanuvchi kiritadi). Demak algoritm (odatda, kompyuterda) biror ishni amalga oshirish uchun yaratilgan qoidalar ketma-ketligi ekan. Qolaversa, algoritm 3 ta asosiy talabga javob berishi kerak: 1. Noaniqlik bo’lmasligi. Har bir qadam kompyuter tushunadigan aniq qilib ko’rsatilishi shart. 2. Foydalanuvchi tomonidan kiritiladigan barcha ma’lumotlar uchun to’g’ri ishlashi kerak. 3. Algoritm doim ma’lum vaqtdan keyin ishni tugallashi kerak, cheksiz davom etmasligi kerak (yuqoridagi misolimizda takrorlanish shartini 5*5 25 bo’lsa deb kiritsangiz cheksiz sanayveradi).
Cantor diagonal usuli, shuningdek Cantor diagonali argumenti yoki Cantorning diagonal chizig'i deb ham ataladi, Georg Cantor tomonidan ishlatilgan aqlli usul, bu butun sonlar va reallarni bir-biriga yozishmalarga (ya'ni, son-sanoqsiz cheksiz to'plamga) qo'yish mumkin emasligini ko'rsatish uchun. Haqiqiy sonlar cheksiz butun sonlardan "kattaroq").Biroq, Cantorning diagonali usuli butunlay umumiydir va quyida tavsiflangan har qanday to'plam uchun amal qiladi. Kantor teoremasiga muvofiq, tabiiy seriyalarning barcha to'plamlari 0-dan kattaroq kardiologiyaga ega va shuning uchun ularni sanab bo'lmaydi. Bu holda dalilning tagida diagonalizatsiya g'oyasini ta'kidlash uchun biz bu dalilni (ozgina o'zgartirishlar bilan) takrorlaymiz. Biz har N to'plam bilan uning nol va ularning xarakterli ketma-ketligini bog'laymiz: a 0 , a 1 , a 2 , ...
Shunday qilib, nollarning ketma-ketligi va N to'plamining pastki qatorlari o'rtasida birma-bir yozishmalar o'rnatiladi . Bo'lsin A 0 , A 1 , A 2 , ... - pastki kümelerini bir o'zboshimchalik ro'yxati N . Biz N- da ushbu ro'yxatda ko'rinmaydigan pastki qism mavjudligini ko'rsatamiz. A 0 , A 1 , A 2 , ... to'plamlarini ularning xarakterli ketma-ketliklari bilan birga ko'rib chiqing : A 0 = a 00 , a 01 , a 02 , a 03 , ...; A 1 = a 10 , a 11 , a 12 , a 13 , ...; A 2 = a 20 , a 21 , a 22 , a 23 , ...; A 3 = a 30 , a 31 , a 32 , a 33 , ...; …………………. “Diagonallarga qarshi” ketma-ketlikni yarataylik 1 00α 00 , 1 11a 11 , 1 22a 22 , 1 33a 33 , .... Ushbu ketma-ketlik hech bo'lmaganda birinchi elementning ro'yxatning birinchi ketma-ketligidan, ikkinchi element ikkinchi darajali, uchinchi element uchinchi va boshqalardan farq qiladi. Shuning uchun “diagonal” ketma-ketligi, u bilan birga va tegishli to'plam mavjud emas ro'yxati. Yuqoridagi dalillar shuni ko'rsatadiki, N to'plamning barcha kichik to'plamlarini o'z ichiga olgan ro'yxatni tuzish mumkin emas va shuning uchun N to'plamning barcha pastki to'plamini hisoblash mumkin emas. Diagonal usuldan foydalanib, [0; 1] intervalning haqiqiy sonlari to'plamini sanab bo'lmasligini ko'rsatamiz. Dalillar. [0; 1] intervaldan har qanday haqiqiy son cheksiz kasr kasr sifatida yozilishi mumkin a = 0, a 0 a 1 a 2 …. Cheklangan o'nlik kasrlar bilan ifodalangan sonlar uchun bunday belgi noaniqdir. Masalan, 0.1000 ... va 0.0999 ... yozuvlari bir xil raqamni anglatadi. Ikkinchi turdagi yozuvlardan foydalanmaslikka rozilik beramiz, unda bir joydan boshlab faqat to'qqiztasi mavjud. Shunda sonlarni kasr kasrlarida ifodalash bir ma'noga ega bo'ladi. Bo'lsin bir 0 , a 1 , a 2 ,... oralig'ida haqiqiy sonlar ixtiyoriy ro'yxati bo'lishi [0; 1]. Biz [0; 1] segmentida ushbu ro'yxatga kirmaydigan raqam borligini ko'rsatamiz. Raqamlar ro'yxatini ko'rib chiqaylik bir 0 , a 1 , a 2 , ..., ularning o'nlik vakolatxonalari bilan birga: a 0 = 0, a 00 α 01 α 02 α 03 ...; a 1 = 0, a 10 α 11 α 12 α 13 ...; a 2 = 0, a 20 α 21 α 22 α 23 ...; a 3 = 0, a 30 a 31 a 32 a 33 33 ...; …………………
Biz o'rnatish β i , 1, agar = α i , i 2 = va β i bo'lsa, 2 = α II ≠ 2. soni β = 0, β 0 β 1 β 2 β 3 .... [0; 1] intervalida yotadi va hech bo'lmaganda birinchi raqamli raqamlar ro'yxatdagi birinchi raqamdan, ikkinchi raqamdan ikkinchi raqam, uchinchi raqamdan uchinchi raqam va boshqalarga farq qiladi. Shuning uchun β raqami ro'yxatda yo'q. Shunday qilib, [0; 1] segmentning barcha raqamlarini o'z ichiga olgan ro'yxat tuzish mumkin emas va shuning uchun [0; 1] segmentning barcha haqiqiy raqamlari to'plamini hisoblab bo'lmaydi. [0; 1] segment raqamlari to'plamining kuchi doimiy deb nomlanadi ; Shu ahamiyat ega silsilasini deyiladi muntazamligini . Kontinentallar quyidagilar: barcha haqiqiy sonlar to'plami, chiziqning nuqtalari to'plami, tekislikning nuqtalari to'plami, haqiqiy sonlar ketma-ketligi to'plami va matematik amaliyotda topilgan boshqa ko'plab to'plamlar. Kontrumdan kichikroq kuchga ega bo'lgan cheksiz to'plamlarning mavjudligi muammosi ( doimiy gipoteza deb ataladigan narsa ) ushbu toriyada deyarli ushbu nazariya paydo bo'lgan paytdan boshlab paydo bo'ldi. Godel, uzluksiz gipotezaning manfiy echimi taxmin qilingan to'plamning aksiomatikasiga zid kelmasligini isbotladi. Keyinchalik, Koen, doimiy gipotezaga ijobiy echim topilishi bu aksiomatikaga zid kelmasligini aniqladi. Ko'rinishi kerak bo'lgan muammolar nazariyasining mavjudligi «ha» yoki «yo'q» turidagi qarorga ega bo'lish, ammo bunday qaror mavjud emasligi avvalgi ma'ruzada aytib o'tilgan matematikani rasmiylashtirishni rag'batlantirgan. Cantorning diagonali usuli Cantorning son-sanoqsiz haqiqiy sonlari to'plami: natural sonlar to'plami va [0, 1] segmentning haqiqiy raqamlari to'plami har xil kuchlarga ega. misol. Rasmiy arifmetikaning to'liq emasligi haqidagi Godel teoremasi. Har qanday izchil aksiomalar to'plamiga asoslanib isbotlab bo'lmaydigan va rad etilmaydigan ba'zi bayonotlar mavjud (bunday bayonotlar qaytarib bo'lmaydigan deb nomlanadi). Isbot (qarama-qarshi). [0, 1] segmentining haqiqiy raqamlari cheksiz o'nlik kasr bilan ifodalanadi, birinchi navbatda 0, undan keyin vergul bilan cheksiz sonlar ketma-ketligi keladi: masalan, 0.31415926536 ... Bunday yozishmalar o'rnatilgan deb taxmin qilamiz (ya'ni, ruxsat bering). biz intervalning barcha raqamlarini sanab chiqdik [0, 1].) 1 0, a1,1a1,2a1,3a1,4a1,5a1,6a1,7 ... 2 0, a2,1a2,2a2,3a2,4a2,5a2,6a2,7 ... 3 0, a3,1a3,2a3,3a3,4a3,5a3,6a3,3 ... 4 0, a4,1a4,2a4,3,4,4,4a4,5a4,6a4,7 ... 5 0, a5.1a5.2a5.3a5.4a5.5a5.6a5.7 .... b 0, a6.1a6.2a6.3a6.4a6.5a6.6a6.7 .... n 0, an, 1an, 2an, 3an, 4an, 5an, 6an, 7 ... a, 1 - 0 dan 9 gacha bo'lgan raqam, i - bu yozuvda qatnashgan raqamning raqami, j - bu raqamdagi pozitsiyasining soni. Bu raqamlashga kiritilmagan raqam borligini isbotlaymiz. 0, b1b2b3b4b5 ... sonini tuzamiz va bn raqamini bn ≠ an, n soniga qo'yamiz. Shunday qilib, n sonidan farq qiluvchi sonni olamiz. Buni har qanday raqam uchun qilish mumkin bo'lganligi sababli, biz barcha haqiqiy raqamlarni raqamlash mumkin degan taxminga qarama-qarshi bo'lib qolamiz. Teorema: n-o'zgaruvchilarning arifmetik funktsiyalari to'plami cheksizdir. Isbot (diagonal usuldan foydalangan holda): To'plamning son-sanoqsizligini isbotlash uchun, uning ba'zi bir qismining hisobsizligini isbotlash uchun etarli. Fi (x) shaklidagi bitta o'zgaruvchining funktsiyalarini ko'rib chiqamiz. Bitta o'zgaruvchining funktsiyalarining sanab bo'ladigan to'plami bo'lsin, ya'ni. ularni qayta nomlash mumkin. FO (x), E1 (x), F2 (x), ... b (x) = E (x) +1 funktsiyasini tuzamiz. Bu diagonali deb ataladigan funktsiya G (0) = Eo (0) +1, G (1) = X1 (1) +1, b (2) = E2 (2) +1 va boshqalar. 6-sanab o'tilgan barcha funktsiyalardan farq qiladi, chunki u har bir funktsiyadan kamida bitta nuqtada farq qiladi. U E0 (x) funktsiyadan x = 0 nuqtada, F1 (x) funktsiyadan x = 1 nuqtada va hokazo bilan farq qiladi. Biroq, qurilish bo'yicha G (x) bitta o'zgaruvchining arifmetik funktsiyalari to'plamiga tegishli, shuning uchun u ro'yxatda bo'lishi kerak, ya'ni. ushbu funktsiyalardan biriga mos Bizda qarama-qarshilik bor, shuning uchun boshlang'ich taxmin noto'g'ri va bitta o'zgaruvchining son-sanoqsiz funktsiyalari mavjud. Shunday qilib, n o'zgaruvchilarning barcha funktsiyalari son-sanoqsizdir. 3.Nima sababdan algoritmlarning samaradorligini baholash amalga oshiriladi? Algoritmlarni tahlil qilishning asosiy vazifasi kirish ma'lumotlari hajmining oshib borishi bilan resurslarga bo'lgan talabni (vaqt va xotira xarajatlari) o'lchash usullarini aniqlashdir. Shundan so'ng, o'sish sur'ati qonuniyatlarini tavsiflash uchun zarur bo'lgan matematik mexanizm ishlab chiqiladi. Kirish ma'lumotlari hajmini oshirish bilan turli xil funktsiyalar; "bitta funktsiya boshqasiga qaraganda tezroq o'sadi" iborasi nimani anglatishini aniqlab olishga yordam beradi. Ba'zi hollarda, yaxshi bajarilish vaqtiga erishish yanada murakkab ma'lumotlar tuzilmalaridan foydalanishga bog'liq va bo'lim oxirida biz bunday ma'lumotlar strukturasining juda foydali misolini ko'rib chiqamiz: ustuvor navbatlar va ularni uyum(kucha, heap) asosida amalga oshirish. Asosiy mavzu - hisoblash muammolarining samarali algoritmlarini izlash. Ushbu umumiylik darajasida kompyuterni hisoblashning butun sohasi ushbu mavzu bilan bog'liq bo'lib tuyuladi; bizning yondashuvimiz boshqalardan qanday farq qiladi? Algoritmlarni ishlab chiqishda umumiy mavzular va loyihalash tamoyillarini aniqlashga harakat qilamiz. Bizni samarali algoritmlarni loyihalashning asosiy usullarini minimal ma'lumot bilan namoyish etuvchi paradigmatik masalalar va usullar qiziqtiradi. Algoritm samaradorligi. (1)T: algoritm samarali deb ataladi agar real kirish ma'lumotlari uchun u tezkor amalga oshirilsa. (2)T: algoritm samarali deb ataladi agar u sifatli bajarilishni “to’liq qidirish”(полнiy перебор)ga nisbatan tezroq ta'minlasa. "To'liq qidirish" usuliga qaraganda ancha yaxshi ishlashni ta'minlaydigan algoritmlar, deyarli har doim qimmatli evristik g'oyani o'z ichiga oladi, buning natijasida ushbu yaxshilanishga erishiladi; Bundan tashqari, ular ko'rib chiqilayotgan masalaning ichki tuzilishi va hisoblash qobiliyati haqida foydali ma'lumotlarni taqdim etadilar. Algoritmning samaradorligi bu algoritmni qo’llash uchun qancha kuch talab qilinishini yoki uning qiymati qanchaligini bildiradi. Bunday qiymat har xil mezonlar bilan o’lchanishi mumkin. Bu erda ulardan ikkitasini: vaqt va fazo miqdorinini samaradorlik mezonlari sifatida olinadi. Bunda vaqt mezoni fazodan muhimroq hisoblanadi, shuning uchun samaradorlik asosan ma’lumotlarnu qayta ishlashga ketgan vaqtga nisbatan olinadi. Samaradorlikni baholash uchun mantiqiy birliklar, ya’ni fayl yoki massivning o’lchami n va qayta ishlash uchun ketgan vaqt miqdori t olinadi. Agar n o’lchov va t vaqt orasida t1=c*n chiziqli bog’liqlik bo’lsa, u holda xajmni bir necha marta, hususan 5 marta, oshirish natijasida, ularni qayta ishlashga ketgan vaqt ham 5 marta oshadi ya’ni n2=5*n bo’lsa, t2=5*t o’rinli bo’ladi. Yoki, agar bog’liqlik t1=logn bo’lsa, u holda n 2 marta oshirilsa vaqt sarfi bor yo’g’i bir birlikka ortadi, ya’ni t2=log2*n=t1+1 bo’ladi. n va t ni bog’liqligini ifodalovchi funksiya odatda murakkab bo’ladi va bunday funksiyani hisoblash katta hajmdagi ma’lumotlarni qayta ishlashda juda muhim hisoblanadi. Hosil qilingan f-ya berilgan funksiyaning tarkibiy samaradorligini bildiradi.Shunga qaramay bu yaqinlashish funksiyaga yaqin hisoblanadi, va katta hajmdagi ma’lumotlar uchun originalga juda yaqin bo’ladi. Samaradorlikning bu o’lchovi assimtotik yaqinlashuvchi o’lchov deyiladi va u samaradorlikni aniqlovchi funksiya ma’lum xadlarini hisobga olganda yoki samaradorlikni aniq hisoblas qiyin, yoki mumkin bo’lmaganda qo’llaniladi. Javob berilishi kerak bo'lgan birinchi jiddiy savol: qanday qilib “samarali algoritm” tushunarsiz kontseptsiyasini aniqroq biror narsaga yaratish uchunmi? Bir qarashda samaradorlikning ishchi ta'rifi quyidagicha ko'rinishi mumkin. Taklif qilinayotgan samaradorlik (1) ta'rifi: algoritm samaradorlik deb ataladi agar uni amalga oshirish tezda real ma'lumotlarni kiritish bo'yicha amalga oshirilsa. Keling, bu ta'rif haqida bir oz o'ylab ko'raylik. U bilan ma'lum darajada Munozara qilish qiyin: algoritmni o'rganishimizning asoslaridan biri bu haqiqiy muammolarni tezda hal qilish qobiliyatidir. Bundan tashqari, qaysi ma'lumotni "haqiqiy" deb hisoblash mumkin? To'liq amalda yuzaga kelishi mumkin bo'lgan kirish oralig'i noma'lum, va ba'zi ma'lumotlar to'plamlari ishlov berish paytida ancha murakkab bo'lishi mumkin. Va nihoyat, taklif qilingan ta'rif qancha ekanligini hisobga olmaydi yaxshi (yoki yomon) algoritm shkalasi, vazifa kutilmagan holga kelganda darajalari. Oddiy vaziyat: ikkita butunlay boshqacha algoritmlar100 o'lchamdagi kirish ma'lumotlarida bir xil ishlaydi; 10 baravar ko'payishi bilan ma'lumotlar hajmi jihatidan bitta algoritm tezkor ishlashni davom ettiradi,boshqasi keskin sekinlashadi. Shunday qilib, biz samaradorlikning aniq ta'rifiga ega bo'lishni xohlaymiz - yo'q platformaga xos va kirishga xos va bashoratli kirish ma'lumotlari hajmining oshishi bilan bog'liq qiymat. Qayta ishlatishdan oldin ushbu bayonotdan amaliy xulosalarni ko'rib chiqishga o'tishingiz mumkin hech bo'lmaganda yuqori darajadagi yashirin taxminni tahlil qiling. Qo'llanma sifatida biz barqaror moslashish muammosini olamiz. Kirish joyida ma'lumotlar tabiiy parametr mavjud - "hajmi" N; uning uchun olinishi mumkin barcha afzalliklar ro'yxatlari taqdimotining umumiy hajmi, chunki ular muammoni hal qilish uchun har qanday algoritm kirishiga uzatiladi. N ning qiymati yaqin ammo bu ushbu vazifaning boshqa tabiiy parametrlari bilan bog'liq: n, erkaklar soni va ayollar soni. Hammasi bo'lib 2n imtiyozli ro'yxatlar mavjud, ularning har biri uning uzunligi n ga teng, shuning uchun N = 2n2 ni, ikkinchi sonni e'tiborsiz qoldiramiz ma'lumotlar taqdimotini amalga oshirish tafsilotlari. Qayta ko'rib chiqish orqali vazifalar, biz algoritmlarni yuqori darajada tasvirlashga harakat qilamiz.Qisqacha qilib aytganda algoritmlarni samadorligini baxolanish sababi, biz ishlatgan algoritm biz uchun qanchalik yengillik beradi, tezlik qay darajada oshadi va xotiradan qancha kam joy oladi. Shu sababli ham har bir algoritmni o`z ishlatiladigan joyi bor. Negaki har qanday murakkablikdagi savolga yechim bo`la oladigan algoritm mavjud emas. Shuning uchun har bir masala uchun eng yaxshi yechimni qidirish kerak bo`ladi. Download 24.6 Kb. Do'stlaringiz bilan baham: 
|