ડેટા કમ્પ્રેશન વિશે વિરોધાભાસ

ડેટા કમ્પ્રેશનની સમસ્યા, તેના સરળ સ્વરૂપમાં, સંખ્યાઓ અને તેમના સંકેતો સાથે સંબંધિત હોઈ શકે છે. સંખ્યાઓને અંકો દ્વારા સૂચવી શકાય છે ("અગિયાર" નંબર 11 માટે), ગાણિતિક સમીકરણો ("વીસમાં બે" 1048576 માટે), શબ્દમાળા સમીકરણો ("પાંચ નવ" 99999 માટે), યોગ્ય નામો ("જાનવરની સંખ્યા" 666 માટે, "ટ્યુરિંગના મૃત્યુનું વર્ષ" 1954 માટે), અથવા તેના મનસ્વી સંયોજનો. કોઈપણ હોદ્દો યોગ્ય છે જેના દ્વારા ઇન્ટરલોક્યુટર સ્પષ્ટપણે નિર્ધારિત કરી શકે છે કે આપણે કયા નંબર વિશે વાત કરી રહ્યા છીએ. દેખીતી રીતે, તમારા ઇન્ટરલોક્યુટરને કહો "આઠનો અવયવપૂર્ણ" સમકક્ષ સંકેત કરતાં વધુ કાર્યક્ષમ "ચાલીસ હજાર ત્રણસો વીસ". અહીં એક તાર્કિક પ્રશ્ન ઊભો થાય છે: આપેલ સંખ્યા માટે સૌથી ટૂંકી સંકેત શું છે?

ફિલસૂફ બર્ટ્રાન્ડ રસેલ 1908માં પ્રકાશિત થયા હતા "બેરીનો વિરોધાભાસ", જે વિરુદ્ધ બાજુથી નંબર નોટેશનના મુદ્દાને સ્પર્શે છે: સૌથી નાની એવી કઈ સંખ્યા છે જેને એંસી અક્ષરોની જરૂર નથી?
આવી સંખ્યા અસ્તિત્વમાં હોવી જોઈએ: એંસી રશિયન અક્ષરો અને જગ્યાઓમાંથી તમે ફક્ત 3480 હોદ્દો બનાવી શકો છો, જેનો અર્થ છે કે એંસી અક્ષરોનો ઉપયોગ કરીને તમે 3480 કરતા વધુ નંબરો નિયુક્ત કરી શકતા નથી. આનો અર્થ એ છે કે આ રીતે 3480 થી વધુ કોઈ ચોક્કસ સંખ્યાને નિયુક્ત કરવી અશક્ય છે.

આનો અર્થ એ છે કે આ નંબર હોદ્દાને અનુરૂપ હશે "સૌથી નાની સંખ્યા જેના માટે એંસી અક્ષરો પૂરતા નથી", જેમાં માત્ર 78 અક્ષરો છે! એક તરફ, આ સંખ્યા અસ્તિત્વમાં હોવી જોઈએ; બીજી બાજુ, જો આ સંખ્યા અસ્તિત્વમાં છે, તો તેનું હોદ્દો તેને અનુરૂપ નથી. વિરોધાભાસ!

આ વિરોધાભાસને નકારી કાઢવાનો સૌથી સહેલો રસ્તો એ છે કે મૌખિક સંકેતોની અનૌપચારિકતાનો સંદર્ભ લો. જેમ કે, જો સંકેતમાં અભિવ્યક્તિઓના માત્ર ચોક્કસ વ્યાખ્યાયિત સમૂહને મંજૂરી આપવામાં આવી હોય, તો પછી "સૌથી નાની સંખ્યા જેના માટે એંસી અક્ષરો પૂરતા નથી" માન્ય નોટેશન નહીં હોય, જ્યારે વ્યવહારિક રીતે ઉપયોગી નોટેશન જેમ કે "આઠનો અવયવપૂર્ણ" સ્વીકાર્ય રહેશે.

શું સંખ્યાઓ પરની ક્રિયાઓના ક્રમ (એલ્ગોરિધમ)નું વર્ણન કરવાની ઔપચારિક રીતો છે? ત્યાં છે, અને પુષ્કળ પ્રમાણમાં - તેમને પ્રોગ્રામિંગ ભાષાઓ કહેવામાં આવે છે. મૌખિક સંકેતોને બદલે, અમે પ્રોગ્રામ્સનો ઉપયોગ કરીશું (ઉદાહરણ તરીકે, પાયથોનમાં) જે જરૂરી સંખ્યાઓ દર્શાવે છે. ઉદાહરણ તરીકે, પાંચ નવ માટે પ્રોગ્રામ યોગ્ય છે print("9"*5). અમને આપેલ નંબર માટેના સૌથી ટૂંકા પ્રોગ્રામમાં રસ લેવાનું ચાલુ રાખીશું. આવા પ્રોગ્રામની લંબાઈ કહેવામાં આવે છે કોલમોગોરોવની જટિલતા સંખ્યાઓ; તે સૈદ્ધાંતિક મર્યાદા છે જેમાં આપેલ સંખ્યાને સંકુચિત કરી શકાય છે.

બેરીના વિરોધાભાસને બદલે, હવે આપણે સમાન વિચારણા કરી શકીએ છીએ: સૌથી નાની સંખ્યા કઈ છે જે આઉટપુટ કરવા માટે કિલોબાઈટ પ્રોગ્રામ પર્યાપ્ત નથી?

અમે પહેલાની જેમ જ તર્ક કરીશું: ત્યાં 2561024 કિલોબાઈટ ટેક્સ્ટ્સ છે, જેનો અર્થ છે કે 2561024 થી વધુ નંબરો કિલોબાઈટ પ્રોગ્રામ્સ દ્વારા આઉટપુટ કરી શકાતા નથી. આનો અર્થ એ છે કે 2561024 કરતા મોટી ન હોય તેવી ચોક્કસ સંખ્યા આ રીતે મેળવી શકાતી નથી.

પરંતુ ચાલો Python માં એક પ્રોગ્રામ લખીએ જે તમામ સંભવિત કિલોબાઈટ ટેક્સ્ટ્સ જનરેટ કરે છે, તેને એક્ઝેક્યુશન માટે ચલાવે છે અને જો તેઓ કોઈ નંબર આઉટપુટ કરે છે, તો આ નંબરને પહોંચી શકાય તેવા ડિક્શનરીમાં ઉમેરે છે. બધી 2561024 શક્યતાઓ તપાસ્યા પછી, ભલે તે કેટલો સમય લે, પ્રોગ્રામ ડિક્શનરીમાંથી ગુમ થયેલ સૌથી નાની સંખ્યાને શોધે છે અને તે નંબરને છાપે છે. તે સ્પષ્ટ લાગે છે કે આવો પ્રોગ્રામ કોડના એક કિલોબાઈટમાં ફિટ થશે - અને તે સંખ્યાને આઉટપુટ કરશે જે એક કિલોબાઈટ પ્રોગ્રામ દ્વારા આઉટપુટ કરી શકાતી નથી!

હવે કેચ શું છે? તે હવે નોટેશનની અનૌપચારિકતાને આભારી હોઈ શકે નહીં!

જો તમે એ હકીકતથી મૂંઝવણમાં હોવ કે અમારા પ્રોગ્રામને કામ કરવા માટે મેમરીની ખગોળીય માત્રાની જરૂર પડશે - 2561024 તત્વોનો શબ્દકોશ (અથવા બીટ એરે) - તો તમે તેના વિના પણ તે જ કરી શકો છો: બદલામાં 2561024 નંબરોમાંથી દરેક માટે , બધા 2561024 સંભવિત પ્રોગ્રામ્સમાંથી પસાર થાઓ, જ્યાં સુધી ત્યાં કોઈ યોગ્ય ન હોય. તે કોઈ વાંધો નથી કે આવી શોધ ખૂબ લાંબો સમય ચાલશે: નંબર અને પ્રોગ્રામમાંથી (2561024)2 કરતાં ઓછા જોડીને તપાસ્યા પછી, તે સમાપ્ત થશે અને તે ખૂબ જ પ્રિય નંબર મળશે.

અથવા તે સમાપ્ત થશે નહીં? ખરેખર, પ્રયત્ન કરવામાં આવશે તે તમામ કાર્યક્રમો વચ્ચે, ત્યાં હશે while True: pass (અને તેના કાર્યાત્મક એનાલોગ) - અને આ બાબત આવા પ્રોગ્રામનું પરીક્ષણ કરતાં વધુ આગળ વધશે નહીં!

બેરીના વિરોધાભાસથી વિપરીત, જ્યાં કેચ નોટેશનની અનૌપચારિકતામાં હતો, બીજા કિસ્સામાં અમારી પાસે સારી રીતે છૂપી સુધારણા છે. "સમસ્યાઓ અટકાવવી". હકીકત એ છે કે મર્યાદિત સમયમાં પ્રોગ્રામમાંથી તેનું આઉટપુટ નક્કી કરવું અશક્ય છે. ખાસ કરીને, Kolmogorov જટિલતા અસંગત: ત્યાં કોઈ અલ્ગોરિધમ નથી કે જે આપેલ નંબર માટે, આ નંબરને છાપતા ટૂંકા પ્રોગ્રામની લંબાઈ શોધવાની મંજૂરી આપે; જેનો અર્થ છે કે બેરીની સમસ્યાનો કોઈ ઉકેલ નથી - આપેલ સંખ્યા માટે સૌથી ટૂંકા મૌખિક હોદ્દાની લંબાઈ શોધવા માટે.

સોર્સ: www.habr.com