Entropiya tushunchasi. Kompyuter fanlari. Tasodifiylik va noaniqlik. Ta'rif - kombinatorika nima Axborot o'lchov birliklari
Axborot - bu qabul qiluvchi uchun noaniqlikni o'z ichiga olmaydigan ma'lumotlar yoki ma'lumotlar. Agar, shunga qaramay, ma'lumot qandaydir noaniqlikni o'z ichiga olsa, uni faqat ma'lum bir ehtimollik bilan qabul qilish mumkin. Shuning uchun, noaniqlik mavjud bo'lganda, ma'lumotni qabul qiluvchi qandaydir tarzda noaniqlikni minimallashtirishga intiladi. Agar bir vaqtning o'zida ma'lumot oluvchi noaniqlikni to'liq bartaraf etishga muvaffaq bo'lsa, demak u ma'lumotga to'liq egalik qiladi. Buni amalda qanday amalga oshirish mumkinligi - bu bobning mavzusi.
NOANIQLIKNING MAQOMIY O'LCHASI
Noaniqliklarni solishtirish uchun quyidagi misollar yoki tajribalarni ko'rib chiqing a, b va g , mos ravishda H(a), H(b) va H(g) noaniqliklarini o'z ichiga olgan:
1. Shaxmat bo‘yicha navbatdagi jahon chempionini aniqlang (a tajriba).
2. Bo'lajak lotereya o'yinida eng katta yutuqni oladigan lotereya chiptasining raqamini aniqlang (b eksperimenti).
3. Rossiya Federatsiyasining keyingi prezidentini aniqlang (tajriba g).
Shubhasiz, har bir tajribaning noaniqlik darajasi boshqa ikkitadan farq qiladi va katta ehtimollik bilan tengsizliklar mavjud.
H(b) > H(a) > H(g),
bu yerda H(a), H(b) va H(g) mos ravishda a, b va g tajribalari noaniqliklarining (yoki entropiyalarining) miqdoriy oʻlchovlari. Maxsus holatda, agar ba'zi tajriba d uchun H(d) = 0 tengligi sodir bo'lsa, u holda biz d tajribani ishonchli deb aytamiz, ya'ni. unda noaniqlik mavjud emas. Boshqacha qilib aytganda, tajribaning noaniqligi ma'lumot etishmasligi yoki salbiy ma'lumotdan boshqa narsa emas.
I. Xartli formulasi. A k teng ehtimolli natijalar bilan ixtiyoriy tajriba bo'lsin
A 1 A 2 hodisalari. . . A k
Ehtimollar 1/ k 1/ k . . . 1/k.
k= 1 H(a) = 0 uchun va k ortishi bilan H(a) ham ortadi, ya’ni.
bu yerda f k ning qandaydir funksiyasi. Boshqa tomondan, agar b l teng ehtimolli natijalarga ega bo'lgan a dan mustaqil boshqa tajriba bo'lsa B l , u holda a va b tajribalarni bir vaqtda bajarishdan iborat bo'lgan murakkab ab tajriba uchun noaniqlik darajasini taxmin qilish tabiiydir. tajriba ab a va b tajribalarni tavsiflovchi noaniqliklar yig'indisiga teng, ular.
H(ab) = H(a) + H(b).
Shunday qilib, f funktsiya sifatida biz logarifmik funktsiyani tanlab, uni qabul qilishimiz mumkin
H(a) = log 2 k .
Bu Xartli formulasi bo'lib, a tajribasida mavjud bo'lgan tajribaga nisbatan noaniqlik o'lchovidir va ikkita bir xil ehtimolli natijalarga ega (masalan, "ha" yoki "yo'q"). Boshqacha qilib aytadigan bo'lsak, H(a) - bu ma'lumot miqdori (bit ma'lumot miqdorini o'lchash birligi sifatida qabul qilinadi), uning yordamida a tajribasining noaniqligi ishonchlilikka aylanadi.
Shunday qilib, masalan, 1 dan 8 gacha bo'lgan oraliqda mo'ljallangan raqamni taxmin qilish uchun sizga maksimal 3 bit ma'lumot kerak, ya'ni. uchta savol berish kerak.
II. Shennon formulasi. A k teng bo'lmagan natijaga ega bo'lgan ixtiyoriy tajriba bo'lsin:
A 1 A 2 hodisalari. . . A k
Ehtimollar P(A 1) P(A 2) . . . P(A k) .
H(a) = - å P(A i)log 2 P(A i)
Shennonga ko'ra, tajriba noaniqligining o'lchovi mavjud. Xususan, R(A i) = 1/ k bo‘lganda, Shennon formulasidan Xartli formulasi kelib chiqadi.
3.1.1. H(ab) = H(a) + H(b) ekanligini isbotlang.
3.1.2. Ushbu guruh rahbarini aniqlash uchun akademik guruh talabalaridan o'qituvchiga qancha savol berish kerak (o'qituvchining savollariga javoblar "ha" yoki "yo'q" bo'lishi mumkin).
3.1.3. Muammoni ko'rib chiqing 3.1.2. bitta savol bo'lsa.
3.1.4. x m kardinallik M to'plamining elementi bo'lsin. Necha
x elementini aniqlash uchun zarur bo'lgan ma'lumotlar?
3.1.5. X 1 va x 2 mos ravishda m 1 va m 2 kardinallik M 1 va M 2 toʻplamlarning ikkita ixtiyoriy elementi boʻlsin. Bir vaqtning o'zida x 1 va x 2 elementlarini aniqlash uchun qancha ma'lumot kerak?
3.1.6. 27 ta oltin tanga bo'lsin, ulardan biri soxta (haqiqiydan engilroq) va tarozilar stakan bilan. Soxta tangani aniqlash uchun qancha tortish kerak?
3.1.7. Har qanday tajriba a H(a) ³ 0 va H(a) = 0 bo‘lishini isbotlang, agar ehtimollardan biri 1 ga, qolganlari esa 0 ga teng bo‘lsa.
3.1.8. H(a) ≤ log 2 k ekanligini isbotlang, bu erda k - tajriba natijalari soni a , va natijalar teng ehtimolli bo'lgandagina tenglikka erishiladi.
3.1.9. Agar a ikkita natijaga ega bo'lsa, H(a) qanday xususiyatlarga ega?
SHARTLI NOANIQLIK.
Axborot miqdori
a va b ikkita ixtiyoriy tajriba bo'lsin, mos ravishda k va l natijalari A k, B l. Agar a va b mustaqil bo'lsa, u holda
H(ab) = H(a) + H(b) ,
va agar a va b bog'liq bo'lsa, u holda
H(ab) = H(a) + H a (b) ,
Bu yerda H a (b) tajriba a bajarilgan va k tengligi bilan aniqlangan shartda b tajribaning shartli noaniqligi.
H a (b) = å P(A i)H A i (b) .
Bu yerda H A i (b) A i natijasi sharti ostida b tajribaning shartli noaniqligi va quyidagi formula bilan aniqlanadi: l.
H A i (b) = - å P A i (B j) log 2 P A i (B j) , i = 1 , k.
Shubhasiz, agar a va b mustaqil bo'lsa, u holda H a (b) = H (b) va H a (b) ≤ H (b) agar a va b bog'liq bo'lsa.
Tenglik ham bor
Farqni ko'rib chiqing
I (a , b) \u003d H (b) - H a (b) ,
bu tajriba a natijasi tajribaning noaniqligini qanchalik kamaytirishini ko'rsatadi b. I soni (a, b) a tajribasida mavjud b tajribasi haqidagi ma'lumotlarning miqdori deb ataladi.
Xususan, a =b uchun bizda I (a , a) = 0 bor, uni o'zida mavjud bo'lgan a tajribasi haqidagi ma'lumotlar miqdori sifatida talqin qilish mumkin. Agar a va b mustaqil bo'lsa, u holda
bular. umuman
I (a, b) ≥ 0,
buni shunday talqin qilish mumkin: universitetda o'qitiladigan hamma narsadan hech qanday zarar bo'lmaydi va eng yomon holatda, shunchaki foyda bo'lmaydi.
I (a, b) = I (b, a) ,
u holda I (a , b) ni a va b ikkita tajribaning o'zaro ma'lumoti deb ham atash mumkin
H(ab) = H(a) + H a (b) ,
I (a , b) = H(a) + H(b) - H(ab) ,
shuning uchun kl
I (a , b) = S S P(A i B j) log 2 P(A i B j) /(P(A i) P(B j)) .
Shunday qilib, biz ma'lumot miqdori uchun yakuniy formulani oldik I (a, b).
3.2.1. isbotlang, agar a va b ixtiyoriy tajriba bo'lsa, u holda;
A) H(ab) = H(a) + H a (b) ;
b) H(ab) ≤ H(a) + H(b) ;
V) 0 ≤ H a (b) ≤ H (b) ;
G) I (a, b) = I (b, a) ;
e) I (a , b) ≤ H(a) ;
3.2.2. I (a, b) uchun formulani chiqaring.
3.2.3. Tajriba b m qora va n ta oq shar bo'lgan urnadan bitta sharni olishdan iborat bo'lsin, k - bir xil idishdan dastlabki ajratib olishda (orqaga qaytmasdan) k sharni olishdan iborat bo'lsin. Tajribaning noaniqligi nima b va tajribalarda mavjud bo'lgan tajriba haqidagi ma'lumotlar a 6,
3.2.4. Konveyerda selektiv nazorat qilish uchun ishlab chiqarilgan n ta qism partiyasidan m ta qism olib tashlansin. Butun partiyadagi nuqsonlar foizini a bilan va namunadagi nuqsonlar foizini b bilan belgilang. I (a, b) ni aniqlang.
3.2.5. (Yolg'onchi va halol odamlar shaharlari haqida). Ma’lum bo‘lsinki, qaysidir A shahrining aholisi doim haqiqatni aytadi, qo‘shni B shahrining aholisi esa doim yolg‘on gapiradi. Kuzatuvchi H bu ikki shahardan birida ekanligini biladi, lekin qaysi birini bilmaydi. U uchrashgan odamni so'roq qilish orqali u qaysi shaharda joylashganligini yoki suhbatdoshi qaysi shaharda yashashini (A aholisi B ga va orqaga borishi mumkin) yoki ikkalasini ham aniqlashi kerak. Savol shundaki, H eng kam savol berishi kerak (barcha savollar H faqat "ha" yoki "yo'q" deb javob berishi kerak).
MA'LUMOTLARNI UZATISH
Haqiqiy xabarlarni alohida harflar yoki harflar birikmalarining ehtimollik taqsimotining tegishli jadvallari bilan ba'zi tajribalar sifatida ko'rib, yana bir bor ma'lumot uzatishning umumiy sxemasiga qaytaylik.
Xususan, agar x va x" mos ravishda uzatilgan va buzilgan xabarlar bo'lsa, biz ma'lumot miqdori I(x", x) - kanalning kirishiga nisbatan chiqishini quyidagicha aniqlaymiz:
I (x ", x) \u003d H (x) - H x "(x),
Bu yerda H(x), H(x") mos ravishda x va x" xabar entropiyalari.
Ma'nosi
C = maksimal I(x, x)
kanal sig'imi deb ataladi, ya'ni. u bir takt siklida kanal orqali uzatilishi mumkin bo'lgan maksimal axborot miqdorini tavsiflaydi. Aslida, kanal sig'imi ishonchli ma'lumot uzatish tezligining R yuqori chegarasi bo'lib, bu chegaraga o'zboshimchalik bilan yaqinlashish mumkin.
Teorema 1.(kodlash haqida). Kanalning o'tkazish qobiliyati C dan kam bo'lgan har qanday R soni va har qanday e>0 uchun R dan kam bo'lmagan tezligi va e dan oshmaydigan xatolik ehtimoli P(e) bo'lgan blokli uzatish usuli mavjud.
Shu bilan birga, ma'lumotni tarmoqli kengligidan yuqori tezlikda uzatishning har qanday usuli xato ehtimoli qandaydir sobit qiymatdan kattaroq bo'lishiga olib keladi.
Teorema 2.(kodlash teoremasining konvertatsiyasi). Agar R ning qiymati C kanalining sig'imidan oshsa, u holda doimiy e 0 (R va C ga qarab) mavjud bo'lib, ma'lumotni R dan kam bo'lmagan tezlikda blokirovka qilishning har qanday usuli uchun tengsizlik.
R(e)³ e 0 .
a i belgisidagi axborot miqdorini I(a i) bilan belgilang va uni quyidagicha belgilang:
I(a i) = - log 2 P(a i) ,
Bu erda P(a i) - a i belgisining xabar matnida paydo bo'lish ehtimoli.
Agar xabar matni qandaydir tabiiy tilda yozilgan bo'lsa
(va uni xatolarni aniqlaydigan va tuzatuvchi tabiiy kod deb hisoblash mumkin), keyin bu tilning har bir harfi matnda o'ziga xos chastotaga ega (masalan, rus tilida o, e, e harflari ancha keng tarqalgan. (P o \u003d 0,09, P e, e = 0,07) e va f harflaridan (P e = 0,003, P f = 0,002)) va shuning uchun tabiiy tilning noaniqligi H L m sifatida aniqlanadi.
H L = - å P(a i) log 2 P(a i) ,
va ortiqcha ~ L, mos ravishda, kabi
C L \u003d 1 - H L / log 2 m,
bu yerda m - tabiiy tildagi harflar soni.
Shubhasiz, 0 ≤ S L ≤ 1, shuning uchun optimal kodlash bilan matnning bir qismini tushunishga putur etkazmasdan olib tashlash mumkin.
Masalan, adabiyot uchun S L = 0,5 inglizchada, va boshqa tillarning ortiqchaligi biroz kamroq.
E'tibor bering, tilning ortiqchaligi kamchilik emas, balki afzallikdir, chunki, masalan, S L = 50% bo'lsa, bu buzilgan matnning yarmidan butun matnni tiklash uchun ishlatilishi mumkinligini anglatadi.
3.3.1. DSC ning tarmoqli kengligini aniqlang.
3.3.2. DSC uchun I(x" , x) toping.
3.3.3. Rus tilining ortiqcha va noaniqligini aniqlang.
3.3.4. Ingliz tilidagi harflarning ma'lumotlar miqdorini aniqlang.
3.3.5. Blok kodlari uchun Shennon teoremalarini isbotlang.
3.3.6. Matnni tiklash:
A) C??zd q?li??m? p?ln???yu od??ri? m??opr??t?i c? bug ??? ?o??rb? ? ?a?o?om;
b)?haqida?ka?ae? ka?av?n???ay.
Kirish. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .3
1. Diskret qurilmalar alifbosi. Yakuniy maydonlar. . . . . . . . . . 4
1.1. Oddiy Galois maydoni GF(P) . . . . . . . . . . . . . . . . . . . . . 4
1.2. Kompozit Galois maydoni GF(P n) . . . . . . . . . . . . . . . . . . . 6
2. Axborotni kodlash. . . . . . . . . . . . . . . . . . . . . . .9
2.1. Asosiy tushunchalar. Kod misollari. . . . . . . . . . . . . . . 9
2.2. Satr kodlari. Ularni o'rnatish usullari. . . . . . . . . . . . 15
2.3. Chiziqli kod xususiyatlari. Hamming kodlari. . . . . . . . . . 22
2.4. Tsiklik kodlar. . . . . . . . . . . . . . . . . . . . . . . . 27
2.5. BCH kodlari ikkita xatoni tuzatadi. . . . . . . . . . . . .32
2.6. Chiziqsiz kodlar. Hadamard kodlari. . . . . . . . . . . . . . . .36
2.7. Kod quvvat chegaralari. . . . . . . . . . . . . . . . . . . . 40
3. Axborot va noaniqlik. . . . . . . . . . . . . . . . . . 44
3.1. Noaniqlikning miqdoriy o'lchovi. . . . . . . . . . . .45
3.2. Shartli noaniqlik. Ma'lumot miqdori. . . . .47
3.3. Ma'lumot uzatish. . . . . . . . . . . . . . . . . . . . . .50
Osipyan Valeriy Osipovich
AXBOROTNI UZATISH NAZARIYASI ELEMENTLARI
Muharrir T.V.Shilova
Texnik muharrir I.A. Zinovskaya
Korrektor M.E. Shulepova
22.01.97 yildagi 200378-son LR
1997 yil 29 yanvarda nashr etish uchun imzolangan.
Format 60´84 1/16. Qog'oz turi. № 3.
Ekranda chop etish. Konv. pech l. 2.75.
Uch.-tahrir. l. 2.7. 300 nusxada tiraj. Buyurtma raqami
Kuban davlat universiteti
Axborot nazariyasi asoschisi Klod Shennon belgilangan ma `lumot, Qanaqasiga noaniqlikni olib tashladi. Aniqroq aytganda, ma'lumot olish noaniqlikni bartaraf etishning zaruriy shartidir. Noaniqlik tanlangan vaziyatda paydo bo'ladi. Noaniqlikni bartaraf etish jarayonida hal qilinadigan vazifa ko'rib chiqilayotgan variantlar sonini kamaytirish (xilma-xillikni kamaytirish) va natijada mumkin bo'lganlar orasidan vaziyatga mos keladigan variantni tanlashdir. Noaniqlikni bartaraf etish ongli qarorlar qabul qilish va harakat qilish imkoniyatini beradi. Bu axborotning nazorat qiluvchi roli.
Tasavvur qiling-a, siz do'konga kirib, saqich sotishni so'ragansiz. Aytaylik, 16 markali saqichga ega bo‘lgan sotuvchi ayol noaniq holatda. U sizning so'rovingizni qabul qilmasdan bajara olmaydi Qo'shimcha ma'lumot. Agar siz "Orbita" deb aytsangiz va 16 ta boshlang'ich variantdan sotuvchi endi atigi 8 tasini ko'rib chiqsangiz, siz uning noaniqligini ikki baravar kamaytirdingiz (oldinga qarab, aytaylik noaniqlikni yarmiga kamaytirish 1 bit ma'lumotni olishga to'g'ri keladi). Agar siz ortiqcha cho'zmasdan, barmog'ingizni derazaga ishora qilsangiz - "bu!", demak noaniqlik butunlay olib tashlandi. Shunga qaramay, oldinga qarab, aytaylik, ushbu misoldagi ushbu imo-ishora bilan siz sotuvchiga 4 bit ma'lumot berdingiz.
Vaziyat maksimal noaniqlik bir necha borligini ko‘rsatadi teng ehtimolli muqobil variantlar (variantlar), ya'ni. variantlardan hech biri afzal ko'rilmaydi. Bundan tashqari, imkoniyatlar tengroq kuzatilgan, noaniqlik qanchalik katta bo'lsa, aniq tanlov qilish shunchalik qiyin bo'ladi va mavzular qo'shimcha ma'lumot talab qilinadi uni olish uchun. Uchun N variantlarda bu holat quyidagi ehtimollik taqsimoti bilan tavsiflanadi: (1/N, 1/N, ... 1/N).
Minimal noaniqlik 0 ga teng, ya'ni. bu holat to'liq ishonch, ya'ni tanlov qilingan va barcha kerakli ma'lumotlar olingan. To'liq aniq vaziyat uchun ehtimollik taqsimoti quyidagicha ko'rinadi: {1, 0, …0} .
Axborot nazariyasidagi noaniqlik miqdorini tavsiflovchi miqdor belgi bilan belgilanadi H va nomi bor entropiya, aniqroq axborot entropiyasi.
Entropiya (H) – noaniqlik o'lchovi bitlarda ifodalanadi. Entropiya sifatida ham ko'rish mumkin taqsimotning bir xilligi o'lchovi tasodifiy o'zgaruvchi.
Shakl 8. ikkita muqobil holatlar uchun entropiyaning xatti-harakatlari, ularning ehtimollik nisbati o'zgarishi bilan (p , (1-p )) ko'rsatilgan.
Entropiya o'zining maksimal qiymatiga etadi, bunda ikkala ehtimollik ham bir-biriga teng va ½ ga teng bo'lsa, nol entropiya qiymati (p 0 =0, p 1 =1) va (p 0 =1, p 1) holatlarga mos keladi. =0).
Ma'lumotlar miqdori I Va entropiya H bir xil vaziyatni xarakterlaydi, lekin sifat jihatidan qarama-qarshi tomonlardan. I - noaniqlikni bartaraf etish uchun zarur bo'lgan ma'lumotlar miqdori H. Léon Brillouinga ko'ra ma'lumot salbiy entropiya (negentropiya).
Noaniqlik to'liq bartaraf etilganda, olingan ma'lumotlar miqdori I xos noaniqlikka teng H.
Noaniqlikning qisman olib tashlanishi bilan olingan ma'lumotlarning miqdori va qolgan hal qilinmagan noaniqlik dastlabki noaniqlikka qo'shiladi. H t + I t = H.
Shu sababli, entropiyani hisoblash uchun quyida taqdim etiladigan formulalar H axborot miqdorini hisoblash uchun formulalar hamdir I, ya'ni. Qachon gaplashamiz O noaniqlikni to'liq bartaraf etish, H bilan almashtirilishi mumkin I.
Axborot miqdori bilimlarning noaniqligini kamaytirish o'lchovi sifatida
Axborot va bilim. Inson o'z atrofidagi dunyodan ma'lumotni hislar yordamida oladi, uni tahlil qiladi va fikrlash yordamida muhim naqshlarni aniqlaydi, olingan ma'lumotlarni xotirada saqlaydi. Atrofdagi dunyoni tizimli ilmiy bilish jarayoni bilim (faktlar, ilmiy nazariyalar va boshqalar) shaklida ma'lumotlarning to'planishiga olib keladi. Shunday qilib, bilish jarayoni nuqtai nazaridan axborotni shunday deb hisoblash mumkin bilim.
Bilish jarayonini vizual ravishda kengayib borayotgan bilim doirasi sifatida tasvirlash mumkin (bu usul qadimgi yunonlar tomonidan ixtiro qilingan). Bu doiradan tashqarida jaholat maydoni yotadi va doira bilim va jaholat o'rtasidagi chegaradir. Paradoks shundaki, inson qanchalik ko'p bilimga ega bo'lsa (bilim doirasi qanchalik keng bo'lsa), u shunchalik ko'p bilim etishmasligini his qiladi (bizning jaholat chegaramiz qanchalik katta, bu modelda uning o'lchovi aylanadir) - rasm. 1.1.
 |
| Guruch. 1.1 Bilim va jaholat |
Shunday qilib, maktab bitiruvchisining bilim hajmi birinchi sinf o'quvchisining bilim hajmidan ancha katta, ammo uning nodonligining chegarasi ancha katta. Darhaqiqat, birinchi sinf o'quvchisi fizika qonunlari haqida hech narsa bilmaydi va shuning uchun o'z bilimi etarli emasligini anglamaydi, maktab bitiruvchisi esa fizika imtihonlariga tayyorgarlik ko'rayotganda o'zi bilmagan yoki tushunmaydigan jismoniy qonunlar mavjudligini bilib olishi mumkin.
Biror kishi olgan ma'lumotni bilim noaniqligini kamaytirish o'lchovi deb hisoblash mumkin. Agar ma'lum bir xabar bizning bilimimizning noaniqligining pasayishiga olib keladigan bo'lsa, unda bunday xabarda ma'lumot mavjud deb aytishimiz mumkin.
Misol uchun, informatika fanidan imtihon topshirganingizdan so'ng, siz noaniqlikdan azob chekasiz, qanday baho olganingizni bilmaysiz. Nihoyat, imtihon komissiyasi imtihon natijalarini e'lon qiladi va siz to'liq aniqlik keltiradigan xabarni olasiz, endi siz o'z bahongizni bilasiz. Jaholatdan to'liq bilimga o'tish mavjud, ya'ni imtihon komissiyasining xabarida ma'lumotlar mavjud.
Bilimlarning noaniqligini kamaytirish. Axborotga bilim noaniqligini kamaytirish chorasi sifatida yondashish informatika uchun nihoyatda muhim bo'lgan axborotni miqdoriy jihatdan aniqlash imkonini beradi. Axborot miqdorini aniqlash masalasini aniq misollar bo'yicha batafsilroq ko'rib chiqing.
Aytaylik, bizda tekis yuzaga tashlaydigan tanga bor. Teng ehtimollik bilan ikkita mumkin bo'lgan hodisadan biri sodir bo'ladi - tanga ikkita pozitsiyadan birida bo'ladi: boshlar yoki dumlar.
Aytishimiz mumkinki, agar tajribalar soni ortib borayotgan bo'lsa, bosh va dumlar soni asta-sekin yaqinlashsa, voqealar bir xil darajada ehtimoli bor. Masalan, agar biz tangani 10 marta tashlasak, boshlar 7 marta, dumlar 3 marta, agar 100 marta tashlasak, boshlar 60 marta, dumlar esa 40 marta yuqoriga chiqishi mumkin. tanga 1000 marta, keyin "burgut" 520 marta tushishi mumkin va "dumlar" - 480 va hokazo.
Natijada, juda katta tajribalar seriyasi bilan bosh va quyruq soni deyarli teng bo'ladi.
Otishdan oldin bizning bilimimizda noaniqlik mavjud (ikkita hodisa bo'lishi mumkin) va tanga qanday tushishini oldindan aytib bo'lmaydi. Otishdan keyin to'liq ishonch bor, chunki biz tanga ichida ekanligini ko'ramiz (vizual xabar olamiz) bu daqiqa ma'lum bir holatda (masalan, "burgut"). Bu xabar bizning bilimlarimiz noaniqligining ikki baravar kamayishiga olib keladi, chunki uloqtirishdan oldin bizda ikkita ehtimoliy hodisa bo'lgan va otishdan keyin - faqat bitta, ya'ni ikki baravar kam (1.2-rasm).
 |
| Guruch. 1.2 Mumkin va o'tmishdagi voqealar |
Atrofdagi voqelikda ma'lum miqdordagi bir xil ehtimoliy hodisalar ro'y berishi mumkin bo'lgan holatlar tez-tez uchraydi. Shunday qilib, teng qirrali tetraedral piramidani uloqtirganda, 4 ta teng ehtimolli hodisa mavjud va olti qirrali zar- 6 ta teng ehtimolli hodisa.
Mumkin bo'lgan hodisalar soni qanchalik ko'p bo'lsa, dastlabki noaniqlik shunchalik ko'p bo'ladi va shunga mos ravishda eksperiment natijalari haqidagi xabar shunchalik ko'p ma'lumotni o'z ichiga oladi.
Axborot miqdorini o'lchash birliklari. Har qanday miqdorni miqdoriy ifodalash uchun o'lchov birligini aniqlash kerak. Shunday qilib, uzunlikni o'lchash uchun birlik sifatida metr, massa, kilogramm va boshqalarni o'lchash uchun tanlanadi. Xuddi shunday, ma'lumot miqdorini aniqlash uchun siz o'lchov birligini kiritishingiz kerak.
Orqada axborot birligi noaniqlikni yarmiga kamaytiradigan xabarni o'z ichiga olgan ma'lumotlarning bunday miqdori olinadi. Bu birlik deyiladi "bit".
Agar biz tanga otish bilan tajribaga qaytsak, bu erda noaniqlik ikki baravar kamayadi va shuning uchun olingan ma'lumot miqdori 1 bitni tashkil qiladi.
Axborot miqdorini o'lchash uchun eng kichik birlik - bit, keyingi eng katta birlik esa baytdir.
1 bayt = 2 3 bit = 8 bit
Informatika fanida ma'lumotlar miqdorini o'lchash uchun bir nechta birliklarning ta'lim tizimi ko'pgina fanlarda qabul qilinganidan biroz farq qiladi. Birliklarning an'anaviy metrik tizimlari, masalan, Xalqaro SI birliklari tizimi, 10n koeffitsientini bir nechta birliklarning ko'paytmalari sifatida ishlatadi, bu erda n = 3, 6, 9 va boshqalar, Kilo (10 3) o'nlik prefikslariga mos keladi, Mega (10 6), Giga (10 9) va boshqalar.
Kompyuter o'nlik kasrda emas, balki ikkilik tizimda raqamlar bilan ishlaydi, shuning uchun ma'lumot miqdorini o'lchashning bir nechta birliklarida 2 n koeffitsienti qo'llaniladi.
Shunday qilib, baytga karrali bo'lgan axborot miqdorining o'lchov birliklari quyidagicha kiritiladi:
1 KB = 2 10 bayt = 1024 bayt;
1 MB = 2 10 KB = 1024 KB;
1 GB = 2 10 MB = 1024 MB.
Mumkin bo'lgan hodisalar soni va ma'lumotlar miqdori. Mumkin bo'lgan hodisalar soni N va ma'lumot miqdori I bilan bog'liq bo'lgan formula mavjud:
| N=2 I | (2.1) |
Ushbu formuladan foydalanib, agar ma'lumot miqdori ma'lum bo'lsa, mumkin bo'lgan hodisalar sonini osongina aniqlashingiz mumkin. Misol uchun, agar biz 4 bit ma'lumot olgan bo'lsak, unda mumkin bo'lgan hodisalar soni:
Aksincha, axborot miqdorini aniqlash uchun, agar hodisalar soni ma'lum bo'lsa, / uchun ko'rsatkichli tenglamani yechish kerak. Masalan, "Tic-Tac-Toe" o'yinida birinchi harakatdan oldin 8x8 maydonda 64 ta mumkin bo'lgan voqea ("X" ning joylashishi uchun 64 xil variant) mavjud, keyin tenglama quyidagicha bo'ladi:
64 \u003d 2 6 dan boshlab biz quyidagilarni olamiz:
Shunday qilib, I = 6 bit, ya'ni birinchi o'yinchining birinchi harakatidan keyin ikkinchi o'yinchi tomonidan qabul qilingan axborot miqdori 6 bit.
Fikrlash uchun savollar
1. Hodisa haqida ma'lumot olgandan keyin bilimlarning noaniqligini kamaytirishga misollar keltiring.
2. Tanga tashlash tajribasida bilimlarning noaniqligi nima?
3. Axborot miqdori mumkin bo'lgan hodisalar soniga qanday bog'liq?
Vazifalar
1.1. 4x4 maydonda tic-tac-toe o'yinida birinchi o'yinchining birinchi harakatidan keyin ikkinchi o'yinchi qancha ma'lumot oladi?
1.2. Agar ulardan birini amalga oshirgandan so'ng biz 3 bitga teng ma'lumotni olgan bo'lsak, mumkin bo'lgan hodisalar soni qancha edi? 7 bit?
Tasodifiylik va noaniqlik
Kombinatorika - bu toʻplam elementlarining birikmalari, oʻrnini almashtirish, joylashtirish va sanab oʻtishni oʻrganuvchi matematikaning boʻlimi.
Noaniqlik nima?
Noaniqlik - biror narsa haqida ma'lumotning etishmasligi yoki yo'qligi.
Tasodifiylik - bu kabi hodisalar o'rtasidagi bog'liqlik kategoriyasi haqiqiy dunyo ba'zi sharoitlarda amalga oshirilishi mumkin, boshqalari ostida emas. Hodisaning tasodifiyligi ma'lum bir natijaning amalga oshirilishi ma'lum darajada noaniqlikka ega bo'lishidan iborat.
Tasodifiylik inson faoliyatining deyarli barcha sohalarida namoyon bo'ladi.
Hodisa - bu harakatlar natijasida yuzaga keladigan hodisa. Voqealar odatda katta lotin harflari bilan belgilanadi: A, B, C va boshqalar.
Tasodifiy hodisa - bu sodir bo'lishi yoki bo'lmasligi mumkin bo'lgan hodisa.
Ai B hodisalari yig'indisi A hodisasi yoki B hodisasi yoki ikkala hodisaning bir vaqtning o'zida paydo bo'lishidan iborat bo'lgan C hodisasidir:
A va B hodisalarning mahsuloti C hodisasi bo'lib, u A va B hodisalarining birgalikda ko'rinishidan iborat (ularning kombinatsiyasi):
Hodisaning yuzaga kelishi ehtimoli - bu hodisaning ob'ektiv imkoniyatining o'lchovidir.
Agar A hodisaning ehtimoli B hodisaning sodir bo'lishi yoki sodir bo'lmasligiga bog'liq bo'lmasa, A hodisasi B hodisasidan mustaqil deyiladi. Aks holda, A hodisasi B hodisasiga bog'liq deyiladi.
Mos kelmaydigan hodisalar bir vaqtning o'zida sodir bo'lolmaydigan hodisalardir: birining paydo bo'lishi ikkinchisining yuzaga kelishini istisno qiladi.
Pseudo-tasodifiy raqamlar - bu tasodifiy sonlarni taqlid qilish uchun dasturlashda qo'llaniladigan raqamlar.
Pseudo-tasodifiy raqamlar generatori - bu elementlari deyarli bir-biridan mustaqil bo'lgan va ma'lum bir taqsimotga bo'ysunadigan raqamlar ketma-ketligini yaratadigan algoritm.
Pseudo-tasodifiy ketma-ketlik generatori tasodifiy qiymatlarning ba'zi tashqi manbalari (masalan, shovqin) tufayli psevdo-tasodifiy raqamlar ketma-ketligini yaratish algoritmidir. Bilish i-son ketma-ketlikda formulalar yordamida uning (r + 1) elementini aniqlash mumkin.
Pseudo-tasodifiy ketma-ketliklarni yaratish algoritmlari davriydir.
Misollar. 1. 6-raqamli zarning yuzining paydo bo'lish ehtimolini aniqlang.
Bunday holda, umumiy natijalar soni 6 tani tashkil qiladi, chunki zarning 6 ta yuzi bor. Biroq, faqat bitta ijobiy natija bor, chunki matritsa 6 raqami bilan faqat bitta yuzga ega
2-misol. 1 dan N gacha bo'lgan raqamlarning tasodifiy ro'yxatini yarating.
1- th yo'l
Agar elementning pozitsiyasida "0" bo'lsa, siz elementni joylashtirishingiz mumkin.
Agar pozitsiya "0" bo'lmasa, element uchun tasodifiy son hosil bo'ladi.
2- th yo'l
Biz ro'yxat elementlariga nol qiymatlarni beramiz.
Elementni ketma-ketlikda joylashtiramiz.
Agar pozitsiya "0" bo'lmasa, biz "0" ni topgunimizcha barcha keyingilarni tekshiramiz.
3- th yo'l
Biz ro'yxat elementlariga nol qiymatlarni beramiz.
Elementni ketma-ketlikda joylashtiramiz.
Agar element pozitsiyasida "0" bo'lsa, siz elementni joylashtirishingiz mumkin.
8 . Axborotni o'lchashga mazmunli yondashuv
Kontent yondashuvidaxabardagi ma'lumotlarning miqdori ushbu xabarni qabul qiluvchi shaxsga beradigan bilim miqdori bilan belgilanadi.
Buni "inson" nuqtai nazaridan eslaylikma `lumot Biz tashqi dunyodan oladigan bilimdir. Xabarda mavjud bo'lgan ma'lumotlar miqdori qanchalik ko'p bo'lsa, u bizning bilimimizga shunchalik ko'p qo'shiladi.
Axborotning o'lchov birligi nima ekanligini allaqachon bilasiz1 bit.
1 bit - axborot miqdorining minimal o'lchov birligi.
Axborotni o'lchash muammosi axborot nazariyasida o'rganiladi, uning asoschisi hisoblanadiKlod Shennon .
Axborot nazariyasida bit quyidagicha ta'riflanadi:
Bilimning noaniqligini yarmiga kamaytiradigan xabar olib keladi 1 bit ma `lumot.
Bilimning noaniqligi nima, biz misollar bilan tushuntiramiz.
Aytaylik, siz tanga tashladingiz, nima tushadi, deb hayron bo'lasiz: boshlar yoki dumlar. Tanga tashlashning faqat ikkita natijasi bor. Bundan tashqari, bu natijalarning hech biri boshqasidan ustunlikka ega emas. Bunday holda, ular aytiladiteng ehtimolli .
Tangani tashlashdan oldin bo'lsa, natijani bilishning noaniqligi ikkitadir.
Olti tomoni bo'lgan zar ularning har qandayiga teng ehtimollik bilan tushishi mumkin. Demak, matritsani tashlash natijasi haqidagi bilimlarning noaniqligi oltiga teng.
Yana bir misol: poyga oldidan chang'ichilar startda o'zlarining seriya raqamlarini qur'a tashlash orqali aniqlaydilar. Keling, bor deb faraz qilaylik100 musobaqa ishtirokchilari, keyin qur'a tashlashdan oldin sportchining uning raqamini bilishining noaniqligi tengdir.100 .
Shuning uchun siz buni aytishingiz mumkin:
Bilimlarning noaniqligi biron bir hodisaning natijasi haqida (tanga yoki zar tashlash, qur'a tashlash va hokazo) - bu mumkin bo'lgan natijalar soni.
Keling, tanga misoliga qaytaylik. Siz tangani tashlab, unga qaraganingizdan so'ng, siz, masalan, boshga tushganligi haqida vizual xabar oldingiz. Ikki mumkin bo'lgan natijadan biri aniqlandi. Bilimning noaniqligi ikki baravar kamaydi: ikkita variant bor edi, faqat bittasi qoldi. Shunday qilib, tanga tashlash natijasini bilib, siz 1 bit ma'lumot oldingiz.
Ba'zi bir hodisaning ikkita bir xil ehtimoliy natijalaridan biri haqidagi xabar1 bitma `lumot.
Ba'zi xabarlardan biri haqida ma'lumot bo'lsinNkutilmagan hodisalar.
Keyin ma'lumot miqdoriidan biri xabarda keltirilganNdan teng ehtimolli hodisalarni aniqlash mumkinHartli formulalari:
N=2 i.
Bu formulaeksponensial tenglamanisbatan noma'lumi. sabab bilan2 .
AgarNikkining butun soniga teng (2,4,8,16 va hokazo), keyin bunday tenglamani "ongda" hal qilish mumkin.
