Yaqinda TATU tomonidan o'tkazilgan CTFda qiziq bir holat bo'ldi. Xullas, ma'lum funksiya uchun natijasi ma'lum bir shartni qanoatlantiradigan barcha input parametr qiymatlarining o'rta arifmetigini topish kerak edi. Bruteforce qilib ko'rdik va natija 127.5 chiqdi, lekin bu javob noto'g'ri ekan. Qayta-qayta tekshirib ko'rdik, lekin bir xil natija. Xullas, o'sha savolni yecha olmadik va oxirida 3-o'rinni oldik (yechganimizda 1-o'rinni olardik).
Ertasiga tashkilotchilardan so'rasam yo'nalish to'g'ri ekani, lekin hisob-kitobda xato bo'lishi mumkinligini aytishdi. Oxirida muammo kutilmagan bo'lib chiqdi: ular o'rta arifmetikni hisoblash uchun integer divisiondan foydalangan ekan😂 (lekin bu haqida shartda hech qanday ma'lumot berilmagan). Lekin na natijalar o'zgardi, na bu haqida biror joyda e'lon qilindi.
Xulosa: Agar to'g'ri javobni topa olmasang siqilma, ba'zan savolni tuzganlar ham topa olmagan bo'lishi mumkin.
Tepadagi postdan keyin "lekin sanashni 1 dan boshlaymiz-ku" degan savol chiqishi aniq edi va aynan qiziq joyi ham shunda. O'zi sanash nima?
To'plamlar nazariyasiga ko'ra sanash bu to'plamdagi jami elementlar sonini bildiradigan sonni (ya'ni to'plamning kardinalligini) topish. Gap shundaki, ta'rifga ko'ra o'sha sonni topish muhim, lekin uni qanday topish aniqlashtirilmagan (aniqrog'i, bu muhim emas). To'plamlar nazariyasining eng asosiy aksiomalaridan biriga ko'ra bo'sh to'plamdagi elementlar soni 0 ga teng. Demak, 0 ham sanoqda ishlatiladi va u bo'sh to'plamdagi elementlar sonini bildiradi.
Aslida shu joyda to'xtasak ham bo'lardi, lekin boyagi savol haliyam ochiq qolayapti: nega unda 1 dan boshlab sanaymiz? Javob tepada aytilgan abstrakt tushuncha - to'plamdagi elementlar sonini konkret ketma-ketlik bilan, ya'ni algoritmik usulda qanday topishimizga borib taqaladi. Eng mashhur va "standart" usul bu incremental yoki recursive approach (biz biladigan 1 dan boshlab sanash). Bu usul uchun ishlatiladigan qoidalar: – Bo'sh to'plamdagi elementlar soni 0 ga teng. – Bo'sh bo'lmagan to'plamlar ichida kardinalligi eng kichik to'plamning kardinalligi 1 ga teng ("kardinalligi kichik" nimani bildirishining ham ta'rifi bor). – Umumiy elementga ega bo'lmagan to'plamlar birlashmasining kardinalligi ularning alohida holatdagi kardinalliklari yig'indisiga teng, ya'ni A ∩ B = ∅ bo'lgan A, B to'plamlar uchun |A ∩ B| = |A| + |B|. Bu qoida ham boshqa bir qoidaning xususiy ko'rinishi.
A to'plamning kardinalligini topish uchun: – B bo'sh to'plam olamiz. – A to'plam bo'sh bo'lmagunicha undan kardinalligi 1 ga teng qism to'plamni "ayirib", B to'plamga "qo'shamiz" va B to'plamning kardinalligini qayta hisoblaymiz. Ya'ni A to'plamdan 1 ta element olib B ga qo'shamiz. Bu holatda A to'plamning kardinalligi 1 ga kamayib, B niki 1 ga oshadi. – Oxirgi operatsiyadan keyin B to'plamning kardinalligi eng boshidagi A to'plamning kardinalligiga teng, sababi tepadagi 3-qoidaga ko'ra har bir qadamda ikkala to'plam birlashmasining kardinalligi o'zgarmayapti.
Savatdagi olmalarni sanash analogimiz bo'yicha boshida hamma olmani "sanalmagan" deb olamiz va sanalmagan olmalar tugaginicha ularni bitta-bittadan"sanalgan"larga o'tkazib chiqamiz. Oxiridagi sanalgan olmalar soni boshidagi sanalmagan olmalar soniga (ya'ni savatdagi jami olmalar soniga) teng bo'ladi.
Lekin ko'pchilik sanashning boshlanish nuqtasi deb sanalganlar 0 ta deb olingan vaqtni emas, 1-olma sanalmaganlardan sanalganlarga o'tkazilgan vaqtni qabul qiladi. Aslida esa "uje" 1 ta qadam o'tib bo'lgan bo'ladi. Xuddi shu sabab sanash 1 dan boshlanadi degan fikr shakllanib qolgan.
P.S. Lambda calculusda sonlar xuddi tepada aytilgan usulda tasvirlanadi. Faqat olmani 1 ta savatdan boshqasiga o'tkazish emas, abstrakt successor funksiyasi bilan.
Engineering NotesSavol: 0 natural sonmi yoki yo'q? Nega?
Bizdagi ko'pchilik adabiyotlarda asabimga tegadigan eng oddiy narsalardan biri shu. "0 natural son emas, sababi natural sonlar sanashda ishlatiladigan sonlar" deyiladi. Aslidayam xuddi shunday. Masalan, savatda 3 ta olma bor deyilganida 3 bu olmalar soni (ya'ni olmalarni sanadik). Endi savatni bo'shatib, savatdagi olmalarni qaytadan sanab ko'ring. "Savatda olma yo'q" degani aslida "savatda 0 ta olma bor" degani. Prosto, "olma yo'q" deyish linguistik norma. Demak, 0 niyam sanashda ishlatsak bo'larkan. Demak 0 ham natural son.
P.S. 0 ta narsadan iborat boshqa narsalar ham bor. Masalan, Windowsni yaxshi ko'radigan Linuxchilar soni, NeoVim ishlatishini maqtanmaydigan developerlar soni, PHPda yozilgan xavfsiz dasturlar soni, ... .
Borrowed from @keilambda a while ago. Really liked it so far, except some concepts are so abstract that I have to pause and think about it for a few minutes before continuing.
"Xavfsiz hudud"dagi chodirda tiriklayin yongan ayollar, boshi olingan bolalar, "noma'lum" deb yozilgan qabrga ko'milgan minglab odamlar, qo'rquvdan shol bo'lib qolgan chaqaloqlar, oilasi ochlikdan o'layotganiga ilojsiz qarab turgan erkaklar... Va shu daxshatga kechayu-kunduz o'z ko'zi bilan guvoh bo'layotgan 2 million ilojsiz xalq.
Bu yoqda esa shularning hammasini g'ing demay kuzatayotgan "musulmon"lar. Birodarlaring boshiga shunday kulfat kelib, ular sendan yordam kutayotganda sen hech narsani ko'rmagandek yashashda davom etganingni farzandlaringga qaysi yuz bilan aytib berasan, nomard? Qiyomat kunida birodarlaring yuzga qanday qaraysan? Ibrohim alayhissalom yongan o'tga og'zida suv tashigan chumolichalik bo'lolmading-a. Birodaringlaring boshiga daxshatni solishayotganda qanday luqmangdan lazzat olayapsan? Savol-javobing og'ir bo'lishidan qo'rqmaysanmi?
I wonder if physical CPUs used by large cloud providers for VPS services (AWS EC2, for example) are just very high-performance general-purpose CPUs or there are hardware features specifically designed to help with type 1 virtualization.
