6- ma'ruza. To'liq va qisman tanlash algoritmlari reja

Looplar yordamida to'liq sanab o'tish . Dasturlashda to'liq ro'yxatga olishni tashkil qilish vazifasi ko'pincha paydo bo'ladi, masalan, optimal holatni topish yoki barcha mumkin bo'lgan kombinatsiyalarni sanash.
Agar faqat ikkita yoki to'rtta qiymat takrorlangan bo'lsa, o'rnatilgan tsikllardan foydalanish mumkin. Masalan, ikkita raqam bilan yozilgan barcha uchlik raqamlarni, shu jumladan ahamiyatsiz nolga ega raqamlarni ko'rsatamiz:
Qiymatdagi ikkita eng yaqin elementni topish. Minimal qidiruv algoritmi va ichki o'rnatilgan halqalardan foydalangan holda qiymati eng yaqin bo'lgan ikkita elementni topish kerak . Buning uchun barcha mumkin bo'lgan qiymatlar juftligini hisobga olish kerak.


2.Qisman sanash algoritmlari
Aksariyat real muammolarda u ancha katta hajmga ega, shuning uchun ularni hal qilishda faqat qisman sanab o'tishga ruxsat beriladi.
Biz tub sonlarni topish misolida qisman sanash algoritmlarini ko'rib chiqamiz.
Hozirgi matematikaning asosiy tarmoqlaridan biri diskret matematika yo`nalishidir. Ushbu intizom oldida turgan muammolar eng hal etilmaydigan muammolardan biridir. Siz omillar muammosini echishga misol keltirishingiz mumkin, unga ko'ra sonni tub omillarga ajratish kerak. Lekin aslida bu muammo tug'ilgan tub sonlarni topishdan iborat. Asosiy ta'riflar quyidagilar. Tut son - bu faqat 1 ga va o'ziga bo'linadigan musbat butun son n. Qo'shma son - bu tub bo'lmagan musbat butun son n.
Birlamchilik testi - bu algoritm bo'lib, unga ko'ra berilgan N natural son tub sonlar toifasiga tegishli yoki yo'qligini aniq yoki taxminan aniqlash mumkin.
Kriptografiya deganda maxfiylikni, ma'lumotlar xavfsizligini, shuningdek mualliflik huquqidan voz kechishni ta'minlovchi usullar haqidagi ilmiy yo'nalish tushuniladi.
Muammoni shakllantirish. Ilm-fan nuqtai nazaridan, sonning tub ekanligini tashxislash vazifasi qiziqish uyg'otadi, chunki bugungi kunda tub sonni yozishning yagona rasmiylashtirilgan shakli mavjud emas. Lekin muhim o'lchamdagi tub sonlar ochiq kalitli kriptografik tizimlarda qo'llaniladi va tub sonni aniqlash muammosi noan'anaviy muammo hisoblanadi. Oddiy usullar, masalan, o'zaro bog'liqlik usuli, sezilarli resurslarni talab qiladiganligi sababli amaliy foydalanish uchun mos emas. Ya'ni, sonning soddaligi uchun optimal usuldan foydalanish kriptografik tizimlarda algoritmlarning tezligini oshirish va ishonchliligini oshirish imkonini beradi.
Oddiylik testlari. Shuni ta'kidlash kerakki, raqamlarning birlamchiligini aniqlash uchun ma'lum bo'lgan barcha algoritmlarni guruhlarga bo'lish mumkin: Haqiqiy natija berish (deterministik). Sonning tub bo'lish ehtimolini aniqlash uchun testlar. Algoritmlarning birinchi guruhi tub son yoki kompozit sonni aytish imkonini beradi. Algoritmlarning ikkinchi guruhi faqat tub sonlar guruhiga raqam berish ehtimolini aniqlaydi. Ammo har xil parametrik xususiyatlarga ega bo'lgan bir xil raqam uchun ehtimollik algoritmining ko'p takrorlanishi, qoida tariqasida, xatoni juda kichik qiladi. Bo'luvchini qidirish Bu algoritm birinchi guruhga tegishli bo'lib, har qanday potentsial bo'luvchi bo'luvchilarni to'liq izlash orqali sonning tubligini aniqlaydi. Ushbu sinov usulining tuzilishi 6.1-rasmda ko'rsatilgan.



6.1-rasm. To'siqlarni ajratuvchi qismlar.


Amalda, bu algoritm original versiyada qo'llanilmaydi, chunki u nisbatan katta hisoblash quvvatini talab qiladi. Ammo kichik tub sonlarga bo'lish ba'zi testlarda amallardan biri sifatida ishlatiladi.



6.2-rasm. Uilson usuli.
Vilson usuli Bu algoritm ham birinchi guruhga kiradi. Birdan katta n natural son faqat ma'lum hollarda tub bo'ladi. Algoritmning tuzilishi 6.2-rasmda ko'rsatilgan.
Bu algoritm ham kam qo'llaniladi, chunki n soni katta bo'lganda muammolar paydo bo'ladi.