Ma'lumotlarni siqish muammosi, eng oddiy ko'rinishida, raqamlar va ularning yozuvlari bilan bog'liq bo'lishi mumkin. Raqamlar raqamlar bilan belgilanishi mumkin ("o'n bir" 11 raqami uchun), matematik ifodalar ("yigirmanchida ikki" 1048576 uchun), qatorli ifodalar ("besh to'qqiz" 99999 uchun), tegishli ismlar ("hayvonning soni" 666 uchun, "Tyuring vafot etgan yili" 1954 yil uchun) yoki ularning ixtiyoriy birikmalari. Suhbatdoshimiz qaysi raqam haqida gapirayotganimizni aniq aniqlashi mumkin bo'lgan har qanday belgi mos keladi. Shubhasiz, suhbatdoshingizga ayting "sakkizlik faktorial" ekvivalent yozuvdan ko'ra samaraliroq "qirq ming uch yuz yigirma". Bu erda mantiqiy savol tug'iladi: berilgan raqam uchun eng qisqa yozuv nima?
Faylasuf Bertran Rassell 1908 yilda nashr etgan , bu qarama-qarshi tomondan raqamlarni belgilash masalasiga to'xtalib o'tadi: Sakson harf talab qilmaydigan eng kichik raqam qaysi?
Bunday raqam mavjud bo'lishi kerak: sakson rus harflari va bo'shliqlaridan siz atigi 3480 belgini yaratishingiz mumkin, ya'ni sakson harfdan foydalanib, siz 3480 dan ortiq raqamni belgilashingiz mumkin emas. Bu shuni anglatadiki, ma'lum bir raqamni 3480 dan ortiq bo'lmagan tarzda belgilash mumkin emas.
Bu shuni anglatadiki, bu raqam belgiga mos keladi "sakson harf etarli bo'lmagan eng kichik raqam", unda atigi 78 ta harf bor! Bir tomondan, bu raqam mavjud bo'lishi kerak; boshqa tomondan, agar bu raqam mavjud bo'lsa, unda uning belgilanishi unga mos kelmaydi. Paradoks!
Ushbu paradoksni yo'q qilishning eng oson yo'li og'zaki belgilarning norasmiyligiga murojaat qilishdir. Masalan, agar yozuvda faqat aniq belgilangan ifodalar to'plamiga ruxsat berilgan bo'lsa, unda "sakson harf etarli bo'lmagan eng kichik raqam" kabi amalda foydali yozuvlar haqiqiy belgi bo'lmaydi "sakkizlik faktorial" maqbul bo'lib qoladi.
Raqamlar ustidagi harakatlar ketma-ketligini (algoritmini) tasvirlashning rasmiy usullari bormi? Mavjud va juda ko'p - ular dasturlash tillari deb ataladi. Og'zaki belgilar o'rniga biz kerakli raqamlarni ko'rsatadigan dasturlardan (masalan, Pythonda) foydalanamiz. Masalan, besh to'qqiz uchun dastur mos keladi print("9"*5). Biz berilgan raqam uchun eng qisqa dasturga qiziqishni davom ettiramiz. Bunday dasturning uzunligi deyiladi raqamlar; bu berilgan sonni siqish mumkin bo'lgan nazariy chegaradir.
Berrining paradoksi o'rniga, biz shunga o'xshash narsani ko'rib chiqishimiz mumkin: Kilobaytli dasturni chiqarish uchun yetarli bo'lmagan eng kichik raqam qaysi?
Biz avvalgidek fikr yuritamiz: 2561024 kilobaytli matnlar mavjud, ya'ni kilobaytli dasturlarda 2561024 dan ortiq raqam chiqarilishi mumkin emas. Bu shuni anglatadiki, 2561024 dan katta bo'lmagan ma'lum bir raqamni shu tarzda chiqarib bo'lmaydi.
Ammo keling, Python-da barcha mumkin bo'lgan kilobaytli matnlarni yaratadigan, ularni bajarish uchun ishga tushiradigan va agar ular raqam chiqarsa, bu raqamni kirish mumkin bo'lganlar lug'atiga qo'shadigan dastur yozaylik. Barcha 2561024 XNUMX XNUMX imkoniyatni tekshirgandan so'ng, qancha vaqt ketishidan qat'i nazar, dastur lug'atda etishmayotgan eng kichik raqamni qidiradi va bu raqamni chop etadi. Ko'rinib turibdiki, bunday dastur bir kilobayt kodga to'g'ri keladi - va kilobayt dastur tomonidan chiqarilmaydigan raqamni chiqaradi!
Endi ov nima? Endi buni notaning norasmiyligi bilan bog'lab bo'lmaydi!
Agar bizning dasturimiz ishlashi uchun astronomik hajmdagi xotirani talab qilishi sizni chalkashtirib yuborsa - 2561024 elementdan iborat lug'at (yoki bit massivi) - u holda siz xuddi shu narsani qilishingiz mumkin: o'z navbatida 2561024 raqamlarning har biri uchun , mos keladigan dastur bo'lmaguncha barcha 2561024 mumkin bo'lgan dasturlarni ko'rib chiqing. Bunday qidiruv juda uzoq davom etishi muhim emas: raqam va dasturdan (2561024) 2 juftdan kamroqni tekshirgandan so'ng, u tugaydi va o'sha juda qadrli raqamni topadi.
Yoki u tugamaydimi? Haqiqatan ham, sinab ko'riladigan barcha dasturlar orasida bo'ladi while True: pass (va uning funktsional analoglari) - va masala bunday dasturni sinab ko'rishdan uzoqqa bormaydi!
Berrining paradoksidan farqli o'laroq, bu erda ushlash notaning norasmiyligida bo'lgan, ikkinchi holatda bizda yaxshi yashirilgan islohot mavjud. . Gap shundaki, dasturdan uning chiqishini cheklangan vaqt ichida aniqlash mumkin emas. Xususan, Kolmogorov murakkabligi : berilgan raqam uchun ushbu raqamni chop etadigan eng qisqa dastur uzunligini topishga imkon beradigan algoritm yo'q; ya'ni Berri muammosiga yechim yo'q - berilgan raqam uchun eng qisqa og'zaki belgi uzunligini topish.
Manba: www.habr.com