I-sinf bo`yicha tahdidlar

8.To`liq tekshiruv (to`liq qidiruv)

Tarif:
To`liq qidiruv – matematik muammolarni hal qilishda usuli bo`lib, bunda barcha bo`lishi mumkin bo`lgan variantlar echimlarni ko`rib chiqish yo`li bilan amalga oshriladi. Agar yechim maydoni juda katta bo'lsa, to'liq qidirish bir necha yil yoki hatto asrlar natijalarini bermasligi mumkin.
NP klassidagi har qanday muammo to'liq qidiruv bilan hal etiladi. Shu bilan birga, muammoning har bir muayyan yechimining ob'ektiv funktsiyasini hisoblash , barcha mumkin bo'lgan echimlarning soniga qarab , polinom vaqtida amalga oshirilishi mumkin bo'lsa ham , to'liq qidiruv eksponent ishvaqti talab qilishi mumkin .
Yilda kriptografiya ustida bo'yicha hisoblash murakkabligi batafsil qidiruv asoslangan baholash kriptografik shifrlar . Xususan, shifrlarni kriptografik deb hisoblash, agar barcha kalitlarni to'liq qidirishdan ancha tezroq "buzish" usuli bo'lmasa . Shafqatsiz kuch usuliga asoslangan kriptografik hujumlareng ko'p qirrali, ammo eng uzunidir.
To`liq tejshiruv bir nechta turlari bo`lib bular:
Mukamal qidirsh- Birinchi masala bu zanjirni (matritsa mahsulotini) eng qisqa vaqt ichida hisoblashdir. Istalgan mahsulotni hisoblab chiqadigan arzimas ketma-ketlik algoritmini qo'llashingiz mumkin. Yildan Matritsa mahsulot hisoblanadi Assotsiativ operatsiya , bir tasodifiy zanjir elementlari bir juft tanlashda chainlike mahsulotni hisoblash mumkin{\ displaystyle (A_ {i} A_ {i + 1}), i = 1..n-1} va uni matritsa bilan almashtirish {\ displaystyle A_ {i} {1} \ nuqta A_ {i} {1} = (A_ {i} A_ {i + 1})} Agar tasvirlangan amaliyotni takrorlasangiz qolgan natija matritsasi va javob bo`ladi . Ushbu formulani quyidagicha tasvirlash mumkin. Matris zanjirini ko'rib chiqing: . Ushbu zanjirga mos keladigan mahsulotni hisoblash uchun quyidagi 5 usul mavjud.

Shunday qilib, ushbu muammoni hal etish matris zanjirini hisoblash uchun sarflangan vaqtni ancha qisqartirishi mumkin. Ushbu echim to'liq qidiruv orqali olinishi mumkin: hisoblashning barcha mumkin ketma-ketligini ko'rib chiqish va zanjirni hisoblashda eng kichik miqdordagi skaler mahsulotlarni olganini tanlash kerak. Shu bilan birga, ushbu algoritm eksponent hisoblash vaqtini talab qiladi , shuning uchun uzun matritsali zanjirlar uchun zanjirni eng samarali tarzda (optimal strategiya ) hisoblashdan olingan daromadushbu strategiya topilgan vaqtdan butunlay yo'qoladi.