Definitsioon – mis on kombinatoorika. Arvutiteadus
Teabe hulk teadmiste ebakindluse vähendamise mõõdupuuna
Teave ja teadmised. Inimene saab oma meelte abil informatsiooni ümbritsevast maailmast, analüüsib seda ja tuvastab mõtlemise abil olulisi mustreid ning salvestab saadud informatsiooni mällu. Süstemaatilise teadusliku teadmise protsess meid ümbritseva maailma kohta viib teabe kogumiseni teadmiste kujul (faktid, teaduslikud teooriad jne). Seega võib tunnetusprotsessi seisukohalt informatsiooni käsitleda kui teadmisi.
Tunnetusprotsessi saab visuaalselt kujutada laieneva teadmiste ringi kujul (selle meetodi leiutasid vanad kreeklased). Väljaspool seda ringi asub teadmatuse ala ja ring on piir teadmiste ja teadmatuse vahel. Paradoks seisneb selles, et mida rohkem teadmisi inimesel on (mida laiem on teadmiste ring), seda rohkem tunneb ta teadmiste puudust (seda suurem on meie teadmatuse piir, mille mõõdupuuks antud mudelis on ümbermõõt) – joon. 1.1.
 |
| Riis. 1.1 Teadmised ja teadmatus |
Seega on koolilõpetaja teadmiste maht palju suurem kui esimesse klassi astuja teadmiste maht, samas on tema teadmatuse piir oluliselt suurem. Tõepoolest, esimesse klassi astuja ei tea füüsikaseadustest midagi ega mõista seetõttu oma teadmiste ebapiisavust, samas kui koolilõpetaja võib füüsikaeksamiteks valmistudes avastada, et on füüsikaseadusi, mida ta ei tea või ei tunne. ei saa aru.
Informatsiooni, mida inimene saab, võib pidada teadmiste ebakindluse vähendamise meetmeks. Kui mõni sõnum viib meie teadmiste ebakindluse vähenemiseni, siis võime öelda, et selline sõnum sisaldab informatsiooni.
Näiteks pärast arvutiteaduse eksami sooritamist piinab sind ebakindlus, sa ei tea, mis hinde sa said. Lõpuks teatab eksamikomisjon eksamitulemused ja saate teate, mis toob täieliku kindluse, nüüd teate oma hinnet. Toimub üleminek teadmatusest täielikele teadmistele, mis tähendab, et eksamikomisjoni sõnum sisaldab infot.
Teadmiste ebakindluse vähendamine. Lähenemine teabele kui teadmiste ebakindluse vähendamise mõõdupuule võimaldab kvantitatiivselt mõõta infot, mis on arvutiteaduse jaoks äärmiselt väärtuslik. Vaatleme konkreetsete näidete abil teabehulga määramise küsimust üksikasjalikumalt.
Oletame, et meil on münt, mille me peale viskame tasane pind. Võrdse tõenäosusega juhtub üks kahest võimalikust sündmusest – münt jõuab ühte kahest positsioonist: “pead” või “sabad”.
Võime öelda, et sündmused on võrdselt tõenäolised, kui katsete arvu suurenemisega hakkab peade ja sabade arv järk-järgult lähenema. Näiteks kui viskame münti 10 korda, võivad "pead" ilmuda 7 korda ja sabad - 3 korda, kui viskame münti 100 korda, siis "pead" võivad ilmuda 60 korda ja "sabad" - 40 korda. , kui me viskame münti 1000 korda, siis “pead” võivad kukkuda 520 korda ja “sabad” 480 korda jne.
Selle tulemusel on väga suure katseseeriaga peade ja sabade arv peaaegu võrdne.
Enne viskamist valitseb meie teadmistes ebakindlus (võimalik on kaks sündmust) ja on võimatu ennustada, kuidas münt maandub. Pärast viset on täielik kindlus, sest näeme (saame visuaalse sõnumi), et münt on sees Sel hetkel on teatud asendis (näiteks "pead"). See sõnum vähendab meie teadmiste ebakindlust poole võrra, kuna enne viset oli meil kaks tõenäolist sündmust ja pärast viset ainult üks, see tähendab poole vähem (joonis 1.2).
 |
| Riis. 1.2 Võimalikud ja tegelikud sündmused |
Ümbritsevas reaalsuses tuleb üsna sageli ette olukordi, kus võib toimuda teatud arv võrdselt tõenäolisi sündmusi. Seega on võrdkülgse tetraeedrilise püramiidi viskamisel 4 võrdselt tõenäolist sündmust ja kuuepoolse täringu viskamisel 6 võrdselt tõenäolist sündmust.
Mida suurem on võimalike sündmuste arv, seda suurem on esialgne määramatus ja vastavalt suur kogus teave sisaldab teadet katse tulemuste kohta.
Teabehulga mõõtmise ühikud. Mis tahes suuruse kvantifitseerimiseks on vaja määrata mõõtühik. Nii et pikkuse mõõtmiseks valitakse ühikuks meeter, massi mõõtmiseks - kilogramm ja nii edasi. Samamoodi tuleb teabe hulga määramiseks sisestada mõõtühik.
Taga teabe koguse ühik saadakse selline hulk infot, mis sisaldab teadet, mis vähendab ebakindlust poole võrra. Seda üksust nimetatakse "natuke".
Kui pöördume tagasi mündiviskamise katse juurde, siis siin väheneb määramatus poole võrra ja seetõttu on saadava teabe hulk võrdne 1 bitiga.
Väikseim teabehulga mõõtmise ühik on bitt ja suuruselt järgmine ühik on bait ja
1 bait = 2 3 bitti = 8 bitti
Arvutiteaduses on teabehulga mõõtmise mitmeühiku moodustamise süsteem mõnevõrra erinev enamikus teadustes aktsepteeritud süsteemist. Traditsioonilised mõõtühikute süsteemid, nt. Rahvusvaheline süsteem SI ühikut, koefitsienti 10n kasutatakse mitmikühikute kordajatena, kus n = 3, 6, 9 ja nii edasi, mis vastab kümnendkoha eesliidetele Kilo (10 3), Mega (10 6), Giga (10 9) ja nii edasi.
Arvuti töötab numbritega mitte kümnendsüsteemis, vaid kahendarvusüsteemis, seetõttu kasutatakse teabehulga mõõtmisühikutes koefitsienti 2 n.
Seega sisestatakse baidi mitmekordsed teabehulga mõõtühikud järgmiselt:
1 KB = 2 10 baiti = 1024 baiti;
1 MB = 2 10 KB = 1024 KB;
1 GB = 2 10 MB = 1024 MB.
Võimalike sündmuste arv ja teabe hulk. On olemas valem, mis seob võimalike sündmuste arvu N ja teabe hulga I:
| N = 2 I | (2.1) |
Selle valemi abil saate hõlpsasti määrata võimalike sündmuste arvu, kui teabe hulk on teada. Näiteks kui saime 4 bitti teavet, siis oli võimalike sündmuste arv:
Vastupidi, teabe hulga määramiseks, kui sündmuste arv on teada, on vaja lahendada / eksponentsiaalvõrrand. Näiteks mängus "Tic Tac Toe" on 8x8 väljal enne esimest käiku 64 võimalikku sündmust (64 erinevat varianti "risti" asukohaks), siis võrrandiks saab:
Kuna 64 = 2 6, saame:
Seega I = 6 bitti, see tähendab, et teise mängija poolt pärast esimese mängija esimest käiku saabunud teabe hulk on 6 bitti.
Küsimused, mida kaaluda
1. Tooge näiteid teadmiste ebakindluse vähendamisest pärast sündmuse kohta teabe saamist.
2. Milline on teadmiste määramatus mündiviskamise katses?
3. Kuidas sõltub info hulk võimalike sündmuste arvust?
Ülesanded
1.1. Kui palju teavet saab teine mängija pärast esimese mängija esimest käiku Tic Tac Toe mängus 4x4 laual?
1.2. Kui palju oli võimalikke sündmusi, kui pärast ühe neist realiseerimist saime 3 biti suuruse teabe? 7 bitti?
Teave on teave või andmed, mis ei sisalda adressaadi jaoks ebakindlust. Kui aga teave sisaldab teatud ebakindlust, siis on seda võimalik tajuda vaid teatud tõenäosusega. Seetõttu püüab teabe saaja ebakindluse olemasolul kuidagi ebakindlust ennast minimeerida. Kui teabe saajal õnnestub ebakindlus täielikult kõrvaldada, siis on tal täielik teave teabe kohta. Selle peatüki teemaks on küsimused selle kohta, kuidas seda praktikas teha.
MÄÄRAMATUSE KVANTITATIIVNE MÕÕT
Määramatuste võrdlemiseks kaaluge järgmisi näiteid või katseid a, b ja g , mis sisaldavad vastavalt määramatust H(a), H(b) ja H(g):
1. Määrake järgmine male maailmameister (katse a).
2. Määrake selle loteriipileti number, millel on eelseisval loteriil suurimad võidud (katse b).
3. Määrake Vene Föderatsiooni järgmine president (kogemus g).
Ilmselgelt erineb iga katse määramatuse aste kahest teisest ja tõenäoliselt esineb ebavõrdsust
H(b) > H(a) > H(g),
kus H(a), H(b) ja H(g) on vastavalt katsete a, b ja g määramatuse (või entroopia) kvantitatiivsed mõõdud. Konkreetsel juhul, kui mõne kogemuse d puhul kehtib võrdus H(d) = 0, siis ütleme, et kogemus d on usaldusväärne, s.t. see ei sisalda ebakindlust. Teisisõnu, kogemuste ebakindlus pole midagi muud kui teabe puudumine või negatiivne teave.
I. Hartley valem. Olgu a suvaline katse k võrdse tõenäosusega A k
Sündmused A 1 A 2. . . A k
Tõenäosused 1/ k 1/ k . . . 1/ k .
Kui k= 1, siis H(a) = 0 ja kui k suureneb, suureneb ka H(a), s.t.
kus f on mingi k funktsioon. Teisest küljest, kui b on teine a-st sõltumatu katse, mille l on võrdselt tõenäolised tulemused Bl, siis komplekskatse ab puhul, mis koosneb katsete a ja b samaaegsest sooritamisest, on loomulik eeldada, et kogemuse ebakindluse aste ab on võrdne katseid a ja b iseloomustavate määramatuste summaga.
H(ab) = H(a) + H(b).
Seega saame funktsioonina f valida logaritmilise funktsiooni ja eeldada, et
H(a) = log 2 k.
See on Hartley valem ja see näitab ebakindlust seoses kogemusega a, mis sisaldub kogemuses a ja millel on kaks võrdselt tõenäolist tulemust (näiteks "jah" või "ei"). Teisisõnu, H(a) on teabe hulk (infohulga mõõtühikuks on bitt), mille abil kogemuse määramatus a teisendatakse kindluseks.
Seega on näiteks kavandatava arvu äraarvamiseks vahemikus 1 kuni 8 vaja maksimaalselt 3 bitti informatsiooni, s.t. Esitada tuleb kolm küsimust.
II. Shannoni valem. Olgu a suvaline katse k ebavõrdselt tõenäolise tulemusega A k:
Sündmused A 1 A 2. . . A k
Tõenäosused P(A 1) P(A 2). . . P(A k) .
H(a) = - å P(A i)log 2 P(A i)
Shannoni sõnul on kogemuste ebakindlus a. Täpsemalt, kui P(A i) = 1/k, tuleneb Hartley valem Shannoni valemist.
3.1.1. Tõesta, et H(ab) = H(a) + H(b).
3.1.2. Kui palju küsimusi peavad akadeemilise rühma õpilased esitama õpetajale, et määrata selle rühma juht (vastus õpetaja küsimustele võib olla kas "jah" või "ei").
3.1.3. Mõelge probleemile 3.1.2. ühe küsimuse korral.
3.1.4. Olgu x kardinaalsuse m hulga M element. Mis kogus
elemendi x määramiseks vajalik teave?
3.1.5. Olgu x 1 ja x 2 vastavalt kardinaalsuse m 1 ja m 2 hulkade M 1 ja M 2 suvalist elementi. Kui palju teavet on vaja elementide x 1 ja x 2 üheaegseks määramiseks?
3.1.6. Olgu siis 27 kuldmünti, millest üks on võltsitud (päristest kergem), ja tassidega kaalud. Mitu kaalu on vaja võltsitud mündi tuvastamiseks?
3.1.7. Tõesta, et iga katse puhul on H(a) ³ 0 ja H(a) = 0 siis ja ainult siis, kui üks tõenäosustest on võrdne 1-ga ja teised on 0.
3.1.8. Tõesta, et H(a) ≤ log 2 k, kus k on katse a tulemuste arv ja võrdsus saavutatakse ainult juhul, kui tulemused on võrdselt tõenäolised.
3.1.9. Millised omadused on H(a)-l, kui a-l on kaks tulemust?
TINGIMUSLIK MÄÄRATLUS.
TEABE KOGUS
Olgu a ja b kaks suvalist katset k ja l tulemustega vastavalt A k, B l. Siis kui a ja b on sõltumatud, siis
H(ab) = H(a) + H(b) ,
ja kui a ja b on sõltuvad, siis
H(ab) = H(a) + H a (b) ,
kus H a (b) on katse b tinglik määramatus, mis on seotud katse a sooritamisega ja määratakse võrrandiga k
H a (b) = å P(A i)H A i (b) .
Siin H A i (b) on katse b tingimuslik määramatus, mis sõltub tulemusest A i ja määratakse järgmise valemiga: l
H A i (b) = - å P A i (B j) log 2 P A i (B j) , i = 1 , k .
Ilmselgelt, kui a ja b on sõltumatud, siis H a (b) = H(b) ja H a (b) ≤ H(b), kui a ja b on sõltuvad.
Samuti on võrdsus
Mõelgem erinevusele
I (a, b) = H(b) - H a (b),
mis näitab, kui palju kogemuse tulemus a vähendab kogemuse ebakindlust b. Arvu I (a, b) nimetatakse kogemuses a sisalduva kogemuse b kohta teabe hulgaks.
Täpsemalt, kui a = b, on meil I (a, a) = 0, mida saab tõlgendada kui informatsiooni hulka endas sisalduva kogemuse a kohta. Kui a ja b on sõltumatud, siis
need. üldiselt
I (a, b) ≥ 0,
mida võib tõlgendada ligikaudu nii: kõik, mida ülikoolis õpetatakse, ei too kahju ja halvimal juhul pole sellest lihtsalt kasu.
I (a , b) = I (b, a) ,
siis I (a, b) võib nimetada ka kahe katse a ja b vastastikuseks informatsiooniks
H(ab) = H(a) + H a (b) ,
I (a , b) = H(a) + H(b) - H(ab) ,
seetõttu k l
I (a , b) = Σ Σ P(A i B j) log 2 P(A i B j) /(P(A i) P(B j)) .
Seega oleme saanud lõpliku valemi infohulga I (a, b) kohta.
3.2.1. Tõesta, et kui a ja b on suvalised katsed, siis;
A) H(ab) = H(a) + H a(b) ;
b) H(ab) ≤ H(a) + H(b) ;
V) 0 ≤ Ha (b) ≤ H(b) ;
G) I (a, b) = I (b, a);
d) I (a, b) ≤ H(a);
3.2.2. Tuletage I (a, b) valem.
3.2.3. Katse b seisneb ühe palli eemaldamises urnist, mis sisaldab m musta ja n valget palli, katse a k - eelnevalt k palli eemaldamist samast urnist (tagastamata). Milline on katse b määramatus ja katsetes a sisalduv kogemusteave 6,
3.2.4. Olgu selektiivseks juhtimiseks konveieril toodetud n osast koosnevatest partiidest eemaldada m osa. Tähistame a-ga defektide protsenti kogu partiis ja b-ga proovis esinevate defektide protsenti. Määrake I (a, b).
3.2.5. (Valetajate ja ausate inimeste linnadest). Anna teada, et teatud linna A elanikud räägivad alati tõtt ja naaberlinna B elanikud valetavad alati. Vaatleja H teab, et ta on ühes neist kahest linnast, kuid ei tea, millises. Küsitledes inimest, kellega ta kohtub, peab ta kindlaks tegema, millises linnas ta asub või millises linnas tema vestluskaaslane elab (A elanikud saavad minna B-sse ja tagasi) või mõlemas. Iseasi, kuidas see on väikseim number küsimused, mida N peaks esitama (kõigile küsimustele N vastab vastasisik ainult "jah" või "ei").
TEABE EDASTAMINE
Tuleme veel kord tagasi üldise infoedastuse skeemi juurde, vaadeldes reaalseid sõnumeid kui mõningaid katseid, kus on vastavad tõenäosusjaotuse tabelid üksikute tähtede või tähekombinatsioonide jaoks.
Täpsemalt, kui x ja x" on vastavalt edastatud ja moonutatud sõnumid, siis määrame teabe koguse I(x" , x) - kanali väljundi selle sisendi suhtes järgmiselt:
I(x" , x) = Н(х) - Н x " (x) ,
kus H(x), H(x") on vastavalt teadete x ja x" entroopiad.
Tähendus
C = max I(x" , x)
nimetatakse kanali läbilaskevõimeks, s.o. see iseloomustab maksimaalset infohulka, mida saab kanali kaudu ühes ajaetapis edastada. Aga tegelikult on kanali läbilaskevõime usaldusväärse infoedastuse kiiruse R ülempiir ja sellele piirile võib läheneda nii lähedale kui soovitakse.
1. teoreem.(kodeerimise kohta). Iga arvu R jaoks, mis on väiksemad kui kanali läbilaskevõime C, ja mis tahes e>0 jaoks, on olemas plokk-edastusmeetod, mille kiirus ei ole väiksem kui R ja vea tõenäosus P(e) ei ületa e.
Samal ajal viib igasugune teabe edastamise meetod läbilaskevõimest suurema kiirusega selleni, et vea tõenäosus on suurem kui teatud fikseeritud väärtus.
2. teoreem.(kodeerimise teoreemi ümberpööramine). Kui R väärtus ületab kanali C läbilaskevõimet, siis on konstant e 0 (olenevalt R-st ja C-st), nii et mis tahes teabe plokkide edastamise meetodi puhul kiirusega, mis ei ole väiksem kui R, on ebavõrdsus täidetud
Р(е)³ e 0 .
Tähistame sümboliga I(a i) sümbolis a i sisalduva informatsiooni hulka ja defineerime seda järgmiselt:
I(a i) = - log 2 P(a i) ,
kus P(a i) on sümboli a i esinemise tõenäosus sõnumi tekstis endas.
Kui sõnumite tekst on kirjutatud mingis loomulikus keeles
(ja seda võib pidada loomulikuks koodiks, mis tuvastab ja parandab vigu), siis on selle keele igal tähel tekstis oma esinemissagedus (näiteks vene keeles on tähed o, e, ё palju rohkem tavalisem (P o = 0,09, P e, е = 0,07) kui tähed e ja f (P e = 0,003, P f = 0,002)) ning seetõttu ka määramatus H L loomulik keel määratletud kui m
H L = - å P(a i) log 2 P(a i) ,
ja koondamine C L vastavalt kui
Kui L = 1 - H L / log 2 m,
kus m on tähtede arv loomulikus keeles.
On ilmne, et 0 ≤ С L ≤ 1, seetõttu võib optimaalse kodeerimise korral osa tekstist arusaamist kahjustamata välja jätta.
Näiteks kirjanduse jaoks on С L = 0,5 inglise keeles ja teiste keelte liiasus on mõnevõrra väiksem.
Pange tähele, et keele liiasus ei ole miinus, vaid pigem eelis, kuna näiteks kui C L = 50%, siis see tähendab, et kasutades poolt moonutatud tekstist, saab kogu teksti taastada.
3.3.1. Määrake DSC võimsus.
3.3.2. Leidke DSC jaoks I(x", x).
3.3.3. Määrake vene keele liiasus ja ebamäärasus.
3.3.4. Määrake ingliskeelsete tähtede teabe hulk.
3.3.5. Tõesta Shannoni teoreemid plokkkoodide jaoks.
3.3.6. Taasta tekst:
A) S??zd ts?li??m? p?ln???yu od??ri? m??opr??t?i c? aur??? ?o??ribi? ? ?a?o?om;
b)?ka?ae kohta? ka?av?n???et.
Sissejuhatus. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .3
1. Diskreetsete seadmete tähestik. Lõpetage väljad. . . . . . . . . . 4
1.1. Lihtne Galois' väli GF(P) . . . . . . . . . . . . . . . . . . . . . 4
1.2. Galois' liitväli GF(P n) . . . . . . . . . . . . . . . . . . . 6
2. Teabe kodeerimine. . . . . . . . . . . . . . . . . . . . . . .9
2.1. Põhimõisted. Koodi näited. . . . . . . . . . . . . . . 9
2.2. Lineaarsed koodid. Nende seadistamise meetodid. . . . . . . . . . . . 15
2.3. Lineaarse koodi omadused. Hammingu koodid. . . . . . . . . . 22
2.4. Tsüklilised koodid. . . . . . . . . . . . . . . . . . . . . . . . 27
2.5. BCH koodid parandavad kaks viga. . . . . . . . . . . . .32
2.6. Mittelineaarsed koodid. Hadamardi koodid. . . . . . . . . . . . . . . .36
2.7. Koodide võimsuse piirid. . . . . . . . . . . . . . . . . . . . 40
3. Teave ja ebakindlus. . . . . . . . . . . . . . . . . . 44
3.1. Määramatuse kvantitatiivne mõõt. . . . . . . . . . . .45
3.2. Tingimuslik ebakindlus. Teabe hulk. . . . .47
3.3. Teabe edastamine. . . . . . . . . . . . . . . . . . . . . .50
Osipjan Valeri Osipovitš
INFO EDASTUSE TEOORIA ELEMENTID
Toimetaja T.V. Shilova
Tehniline toimetaja I.A. Zinovskaja
Korrektor M.E. Šulepova
LR nr 200378 22.01.97
Allkirjastatud avaldamiseks 29. jaanuaril 1997. aastal.
Formaat 60´84 1/16. Paberi tüüp nr 3.
Siiditrükk. Tingimuslik ahju l. 2.75.
Akadeemiline toim. l. 2.7. Tiraaž 300 eksemplari. Tellimuse nr.
Kubani Riiklik Ülikool
Juhuslikkus ja ebakindlus
Kombinatoorika on matemaatika haru, mis uurib hulga elementide kombinatsioone, permutatsioone, paigutust ja loetlemist.
Mis on ebakindlus?
Ebakindlus on teabe puudumine või puudumine millegi kohta.
Juhuslikkus on kategooria selliste nähtuste vaheliste seoste määramiseks päris maailm, mida saab mõnel juhul realiseerida, teistel aga mitte. Sündmuse juhuslikkus tähendab, et konkreetse tulemuse realiseerimisel on teatav ebakindlus.
Juhuslikkus avaldub peaaegu kõigis inimtegevuse valdkondades.
Sündmus on nähtus, mis ilmneb tegevuse tulemusena. Sündmused on tavaliselt tähistatud suurelt ladina tähtedega: A, B, C jne.
Juhuslik sündmus on sündmus, mis võib juhtuda või mitte.
Sündmuste Ai B summat nimetatakse sündmuseks C, mis koosneb sündmuse A või B või mõlema sündmuse toimumisest korraga:
Sündmuste A ja B korrutist nimetatakse sündmuseks C, mis koosneb sündmuste A ja B ühisest toimumisest (nende kombinatsioon):
Sündmuse tõenäosus on sündmuse toimumise objektiivse võimalikkuse mõõt.
Sündmust A nimetatakse sündmusest B sõltumatuks, kui sündmuse A tõenäosus ei sõltu sellest, kas sündmus B toimub või mitte. Vastasel juhul nimetatakse sündmust A sõltuvaks sündmusest B.
Kokkusobimatud sündmused on need, mis ei saa toimuda üheaegselt: ühe toimumine välistab teise toimumise.
Pseudojuhuslikud numbrid on arvud, mida kasutatakse programmeerimisel juhuslike arvude simuleerimiseks.
Pseudojuhuslike arvude generaator on algoritm, mis loob arvude jada, mille elemendid on üksteisest peaaegu sõltumatud ja järgivad kindlat jaotust.
Pseudojuhuslike jadade generaator on algoritm pseudojuhuslike arvude jada koostamiseks, mis on määratud mõne välise juhuslike väärtuste allika (näiteks müra) poolt. Teades i-e number järjestuses saate valemite abil määrata selle (r + 1) elemendi.
Pseudojuhuslike jadade genereerimise algoritmid on perioodilised.
Näited. 1. Määrake numbriga 6 matriitsi näo ilmumise tõenäosus.
Sel juhul on tulemuste koguarv 6, kuna stantsil on 6 külge. Siiski on ainult üks soodne tulemus, kuna stantsil on ainult üks pool numbriga 6, seega
Näide 2. Looge juhuslikus järjekorras järjestatud numbrite loend vahemikus 1 kuni N.
1- viis
Kui elemendi asukoht sisaldab "O", saab elemendi paigutada.
Kui positsioon ei ole “O”, genereeritakse elemendi jaoks juhuslik arv.
2- viis
Määrame loendi elementidele nullväärtused.
Asetage element jadasse.
Kui positsioon ei ole "0", kontrollime kõiki järgnevaid, kuni leiame "0".
3- viis
Määrame loendi elementidele nullväärtused.
Asetage element jadasse.
Kui elemendi asukoht sisaldab "0", saab elemendi paigutada.
Sündmuse kohta teadmiste ebakindlus on sündmuse võimalike tulemuste arv.
Tuleme tagasi mündi näite juurde. Pärast seda, kui viskasite mündi ja vaatasite seda, saite visuaalse sõnumi, et see tuli näiteks pähe. Üks kahest võimalikust sündmusest on aset leidnud. Teadmiste ebakindlus on poole võrra vähenenud: oli kaks varianti, jäänud on vaid üks. See tähendab, et olles saanud teada mündi viskamise tulemuse, saite 1 biti teavet.
Teade, et üks kahest võrdselt tõenäolisest sündmusest on aset leidnud, sisaldab ühte informatsiooni.
Sisaldagu mõni teade teavet selle kohta, et toimus üks N võrdselt tõenäolisest (võrdväärselt võimalikust) sündmusest. Seejärel on selles sõnumis sisalduva teabe hulk i ja sündmuste arv N seotud valemiga:
2 i = N.
Kui N on võrdne täisarvuga kahe (2, 4, 8, 16 jne), siis on arvutusi lihtne teha "peas". Vastasel juhul muutub teabe hulk mittetäisarvuks ja ülesande lahendamiseks peate kasutama logaritmide tabelit või määrama logaritmi väärtuse ligikaudu (lähim täisarv, suurem).
Näiteks kui 256 identse, kuid erinevat värvi palli seast valiti juhuslikult üks, siis teade, et valiti punane pall, kannab 8 bitti informatsiooni (2 8 = 256).
Arvu (kindlasti) arvamiseks vahemikus 0 kuni 100, kui teil on lubatud esitada ainult binaarseid küsimusi (vastustega "jah" või "ei"), peate esitama 7 küsimust, kuna teabe hulk umbes arvatav arv on suurem kui 6 ja väiksem kui 7 (2 6 2 7)
Teatises sisalduva informatsiooni hulk i ühe N võrdselt tõenäolise sündmuse toimumise kohta määratakse eksponentsiaalvõrrandi lahendamisega: 2 i =N
Tähestikuline lähenemine teabe mõõtmiseks
Tähestikuline lähenemine põhineb asjaolul, et mis tahes sõnumit saab kodeerida, kasutades mõne tähestiku lõplikku märgijada.
Tähestik- järjestatud tähemärkide komplekt, mida kasutatakse sõnumite kodeerimiseks keeles.
Tähestiku jõud- tähestiku märkide arv.
Kahendtähestik sisaldab 2 tähemärki, selle võimsus on kaks.
ASCII-märkidega kirjutatud sõnumid kasutavad 256-kohalist tähestikku. UNICODE'is kirjutatud sõnumid kasutavad 65 536 tähemärgist koosnevat tähestikku.
Sõnumi teabe hulga määramiseks tähestikulise lähenemisviisi abil peate järjestikku lahendama järgmised probleemid:
Määrake teabe hulk (i) ühes sümbolis valemiga 2 i = N, kus N on tähestiku aste
Määrake sõnumis olevate märkide arv (m)
Arvutage teabe hulk valemiga: I = i * K.
Infohulk kogu K tähemärgist koosnevas tekstis (I) võrdub tähemärgi infokaalu korrutisega SAADA:
I = i * TO.
See väärtus on teksti teabemaht.
Näiteks kui ASCII-süsteemiga kodeeritud tekstsõnum sisaldab 100 tähemärki, siis on selle teabemaht 800 bitti.
I = 8 * 100 = 800
Sama pikkusega binaarsõnumi puhul on infomaht 100 bitti.
Samuti on vaja teada teabe mõõtühikuid ja nendevahelisi seoseid.
Teabeühikud
Nagu juba öeldud, põhiüksus mõõteinfo - bitt.
8 bitti teeb 1 bait.
Koos baitidega kasutatakse teabehulga mõõtmiseks suuremaid ühikuid:
1 KB (üks kilobait) = 1024 baiti;
1 MB (üks megabait) = 1024 KB;
1 GB (üks gigabait) = 1024 MB.
IN Hiljuti Seoses töödeldava teabe mahu suurenemisega on kasutusele võetud sellised tuletatud ühikud nagu:
1 terabait (TB) = 1024 GB,
1 petabait (PB) = 1024 TB.
Pileti number 3
1. Teabe diskreetne esitus: kahendarvud; arvutimälus oleva teksti binaarne kodeerimine. Teksti teabemaht.
2. Graafiliste piltide loomine ja töötlemine graafilise redaktori abil.
1. Teabe diskreetne esitus: kahendarvud; arvutimälus oleva teksti binaarne kodeerimine. Teksti teabemaht.
Inimene tajub teavet meeli kasutades. Samas püüab ta seda jäädvustada ja teistele kättesaadaval kujul esitada. Teabe esitamise vorm võib erineda. Sama objekti, näiteks maja, saab kujutada graafiliselt joonise kujul või teha joonise kolmes projektsioonis. Seda saab kirjeldada luules või kasutades matemaatilisi valemeid.
Teabe esitamise vorm sõltub eesmärgist, milleks seda kasutatakse. Näiteks. Ruutvõrrandi lahenduse kirjutamine algoritmilises või programmeerimiskeeles erineb põhimõtteliselt algebratundides kasutatavast kirjutamisvormist.
Vaatame arvude esitusi.
Numbrite kirjutamisel kasutatakse spetsiaalseid märgisüsteeme, mida nimetatakse numbrisüsteemideks. Kõik arvusüsteemid jagunevad positsioonilisteks ja mittepositsioonilisteks.
Märge on salvestamise viis numbrid kasutades erimärke - numbrid.
Numbrid:
123, 45678, 1010011, CXL
Numbrid:
0, 1, 2, … I, V, X, L, …
Tähestik– see on komplekt numbrid. {0, 1, 2, 3, 4, 5, 6, 7, 8, 9}
Numbrisüsteemide tüübid:
mittepositsiooniline– numbri tähendus ei sõltu selle kohast (positsioonid) numbrite kirjutamisel;
positsiooniline- oleneb selle asukohast (positsioonid) numbrit kirjutades.
Mittepositsioonilised süsteemid
Unaarne– üks number tähistab ühikut (1 päev, 1 kivi, 1 jäär, ...)
Roman:
I– 1 (sõrm), V– 5 (avatud peopesa, 5 sõrme), X- 10 (kaks peopesa), L –
50, C – 100 (Centum),
D – 500 (Demimille),
M – 1000 (Mille)
Positsioonisüsteem: numbri tähenduse määrab selle asukoht numbrimärgistuses.
Kümnendsüsteem:
algselt - sõrmedel loendamine leiutati Indias, laenasid araablased ja toodi Euroopasse
Tähestik: 0, 1, 2, 3, 4, 5, 6, 7, 8, 9
Alus(numbrite arv): 10
auastmed
3 7 8 = 3 102 + 7 101 + 8 100
300 70 8
Muud positsioneerimissüsteemid:
kahend, kaheksand, kuueteistkümnend (arvutiteadus)
kaksteistkümnendsüsteem (1 jalg = 12 tolli, 1 šilling = 12 penni)
koma (1 frank = 20 sous)
seksagesimaalne (1 minut = 60 sekundit, 1 tund = 60 minutit)
Numbrisüsteemid arvutites
17. sajandil pakkus saksa teadlane Gottfried Leibniz välja ainulaadse süsteemi numbrite esitamiseks, kasutades vaid kahte sümbolit – 0 ja 1. Tänapäeval kasutatakse seda meetodit laialdaselt tehnikas, sealhulgas arvutites, ja seda nimetatakse diskreetseks.
Arvuti on võimeline salvestama ainult diskreetselt esitatud teave. Selle mälu, olenemata sellest, kui suur see on, koosneb üksikutest bittidest, mis tähendab, et see on oma olemuselt diskreetne.
Arvutikeel on kahendarvude keel - binaarne tähestik, millel on kaks märki, 1 ja 0. Loogikas ja tehnoloogias on need märgid seotud mõistetega – jah ja ei, tõene ja vale, sisse ja välja lülitatud. Seda tähestikku nimetatakse ka binaarne. Vastavalt sellele võeti kasutusele väikseim teabeühik - natuke (Inglise bitt, kahendarvust - binaarne ja numbriline - märk). Sõna “jah” või “ei” edastamiseks piisab ühest infobitist, et kodeerida näiteks lambipirni olek. Muide, mõnel lülitil kirjutatakse "1 - sees" ja "0 - väljas". Pilk lülitile lööb meie jaoks välja ebakindlus tema seisundis. Sel juhul saame ühe bitiga võrduva hulga teavet.
BIT on väikseim teabeühik, mis vastab masina binaarkoodi ühele bitile.
Binaarne kodeering (binaarne märge) on teiste kodeerimissüsteemide ees mitmeid eeliseid:
Selle rakendamiseks on vaja tehniliselt lihtsaid elemente, millel on kaks võimalikku olekut (on vool - voolu puudub, magnetiseeritud - magnetiseerimata jne).
Teabe esitamine ainult kahe oleku kaudu on usaldusväärne ja mürakindel.
Info loogiliste teisenduste tegemiseks on võimalik kasutada spetsiaalset loogikaalgebrat (Boole'i algebra).
Binaararitmeetika on palju lihtsam kui kümnendaritmeetika. Binaarsed liitmis- ja korrutustabelid on äärmiselt lihtsad.
Infotöötlus arvutis põhineb elektriliste signaalide vahetamisel masina erinevate seadmete vahel. Signaali olemasolu märki saab tähistada numbriga 1, puudumise märki numbriga 0.
BINAARTEKSTI KODERIMINE
Teksti esitamiseks arvutis kasutatakse 256 erinevat märki. 1 märgi kodeerimiseks eraldatakse 8 bitti.
Kodeerimine– määrates igale märgile kümnendkoodi vahemikus 0 kuni 255 või vastava kahendkoodi vahemikus 00000000 kuni 11111111
Konkreetse koodi määramine sümbolile on kokkuleppe küsimus, mis märgitakse kooditabelisse.
Nagu rahvusvaheline standard kood võeti vastu ASCII tabel(Ameerika standardne teabevahetuse kood):
Koodid 0 kuni 32 (esimesed 33 koodi) - operatsioonikoodid (reavahetus, tühiku sisestus, s.t. vastavad funktsiooniklahvidele);
Koodid 33 kuni 127 – rahvusvaheline, vastavad sümbolitele Ladina tähestik, numbrid, aritmeetilised sümbolid, kirjavahemärgid;
Koodid 128 kuni 255 – rahvuslik, s.o. rahvusliku tähestiku kodeering.
peal 1 märk antakse 1 bait(8 bitti), kokku saab kodeerida 2 8 = 256 tähemärki
Alates 1997. aastast on ilmunud uus rahvusvaheline standard Unicode, mis eraldab kodeerimiseks ühe märgi 2 baiti(16 bitti) ja 65 536 erinevat märki saab kodeerida (Unicode sisaldab kõiki olemasolevaid, väljasurnud ja kunstlikult loodud tähestikke maailmas, palju matemaatilisi, muusikalisi, keemilisi ja muid sümboleid)
Praegu on neid viis Kirillitsa kodeeringud: KOI-8, CP1251, CP866, ISO, Mac. Tekstidokumentide teisendamiseks ühest kodeeringust teise on olemas programmid nimega Konverterid
I = i * K
Pileti number 4
1. Teabe diskreetne esitus: värvilise kujutise kodeerimine arvutis (raster-lähenemine). Heli- ja videopiltide esitamine ja töötlemine. Multimeedia kontseptsioon.
2. Töö failisüsteemiga, graafilise liidesega (tavapäraste toimingute tegemine failidega: loomine, kopeerimine, ümbernimetamine, kustutamine). Individuaalse inforuumi korraldamine (töölaua elementide seadistamine, viiruste kontrollimine, arhiivi kasutamine).
1. Teabe diskreetne esitus: värvilise kujutise kodeerimine arvutis (raster-lähenemine). Heli- ja videopiltide esitamine ja töötlemine. Multimeedia kontseptsioon.
Teavet, sealhulgas graafilist ja heli, saab esitada analoog- või diskreetsel kujul. Arvutis salvestatakse teave diskreetsel kujul. Graafiline ja heliteave analoogvormist diskreetseks teisendatakse diskreetsuse teel, st pideva graafilise kujutise ja pideva helisignaali jagamisega eraldi elementideks.
Graafilise teabe kodeerimine
Ruumiline valim– graafilise kujutise ülekandmine analoogvormist digitaalsesse arvutivormingusse, purustades pildi eraldi väikesteks fragmentideks (punktideks), kus igale elemendile omistatakse värvikood.
piksel – pildi minimaalne pindala ekraanil, antud värv
Rasterpilt moodustatakse üksikutest punktidest – pikslitest, millest igaühel võib olla oma värv. Binaarne pildikood, ekraanil kuvatav on salvestatud videomällu. Bitmap graafika kodeerimine meenutab teatud värvi ruutude mosaiiki.
Kujutise kodeerimise kvaliteet sõltub:
1) punkti suurus (mida väiksem on selle suurus, seda suurem on punktide arv pildil);
2) värvide arv (mida suurem on punkti võimalike olekute arv, seda parem pilt) Värvipalett - kasutatud värvide komplekt.
Rasterpildi kvaliteet sõltub sellest:
1) monitori eraldusvõime - punktide arv vertikaalselt ja horisontaalselt.
2) kasutatud värvipalett (16, 256, 65536 värvi)
3) värvisügavus - bittide arv punkti värvi kodeerimiseks
Ladustamiseks must ja valge kasutatud pilte 1 bitt.
Värvilised pildid moodustatakse vastavalt binaarsele värvikoodile, mis salvestatakse videomällu. Värvilistel piltidel on erinev värvisügavus. Värviline pilt ekraanil moodustub kolme põhivärvi – punase, rohelise ja sinise – segamisel. Rikkaliku paleti saamiseks võib baasvärvidele anda erineva intensiivsusega.
BINAARNE AUDIOKODERIMINE
Analoogkujul on heli pidevalt muutuva amplituudi ja sagedusega laine. Inimesed hakkasid arvutis helifailidega töötama 90ndate alguses. Arvuti abil heli kodeerimise aluseks on õhuvibratsiooni muundamine elektrivoolu vibratsioonideks ja sellele järgnev analoogse elektrisignaali diskreetimine. Heliteabe kodeerimine ja reprodutseerimine toimub spetsiaalsete programmide (salvestusredaktor) abil. Kodeeritud heli taasesituse kvaliteet sõltub diskreetimissagedusest ja selle eraldusvõimest (heli kodeerimise sügavus - tasemete arv)
Ajaproovide võtmine- meetod heli digitaalseks muutmiseks, jagades helilaine eraldi väikesteks ajalõikudeks, kus nende lõikude amplituudid kvantitakse (nendele omistatakse teatud väärtus).
Seda tehakse helikaardil asuva analoog-digitaalmuunduri abil. Seega asendatakse signaali amplituudi pidev sõltuvus ajast diskreetse helitugevuse tasemete jadaga. Kaasaegsed 16-bitised helikaardid kodeerivad 65 536 erinevat helitugevust või 16-bitist helisügavust (igale heli amplituudi väärtusele on määratud 16-bitine kood)
Heli kodeeringu kvaliteet sõltub:
1) heli kodeerimise sügavus - helitasemete arv
2) diskreetimissagedused – signaali taseme muutuste arv ühiku kohta
aega (tavaliselt 1 sekund).
Infoteooria rajaja Claude Shannon kindlaks määratud teavet, Kuidas eemaldas ebakindluse. Täpsemalt on teabe hankimine vajalik tingimus ebakindluse kõrvaldamiseks. Ebakindlus tekib valikuolukorras. Ebakindluse kõrvaldamise käigus lahendatav ülesanne on kaalutavate võimaluste arvu vähendamine (mitmekesisuse vähendamine) ning lõppkokkuvõttes ühe olukorrale sobiva variandi valimine võimalike hulgast. Ebakindluse eemaldamine võimaldab teha teadlikke otsuseid ja tegutseda. See on teabe kontrolliv roll.
Kujutage ette, et läksite poodi ja palusite neil teile närimiskummi müüa. Müüja, kellel on näiteks 16 sorti nätsu, on ebakindel. Ta ei saa teie taotlust täita ilma täiendavat teavet hankimata. Kui määrasite näiteks "Orbiit" ja 16 esialgsest variandist kaalub müüja nüüd ainult 8, vähendasite tema ebakindlust poole võrra (tulevikku vaadates oletame, et määramatuse poole võrra vähendamine vastab 1 biti teabe saamisele). Kui osutasite ilma pikema jututa lihtsalt näpuga ekraanile - “see üks!”, siis oli ebakindlus täielikult eemaldatud. Jällegi tulevikku vaadates oletame, et selle näite liigutusega rääkisite müüjannale 4 bitti teavet.
Olukord maksimaalne ebakindlus eeldab mitme olemasolu sama tõenäoline alternatiivid (valikud), s.o. kumbki variant pole eelistatav. Enamgi veel, seda võrdselt tõenäolisemad variandid on täheldatud, mida suurem on ebakindlus, seda raskem on teha üheselt mõistetavat valikut ja seda rohkem teavet on vaja hankige see selle eest. Sest N valikute korral kirjeldab seda olukorda järgmine tõenäosusjaotus: (1/N, 1/N, … 1/N).
Minimaalne määramatus on 0, st. see olukord täielik kindlus, mis tähendab, et valik on tehtud ja kõik vajalikku teavet saanud. Täieliku kindluse olukorra tõenäosusjaotus näeb välja järgmine: {1, 0, …0} .
Informatsiooniteoorias määramatuse suurust iseloomustavat suurust tähistatakse sümboliga H ja tal on nimi entroopia, täpsemalt teabe entroopia.
Entroopia (H) – määramatuse mõõt väljendatud bittides. Entroopiat võib pidada ka jaotuse ühtluse mõõt juhuslik muutuja.
Joonisel 8 on näidatud entroopia käitumine kahe alternatiivi puhul, kui nende tõenäosuste suhe muutub (p, (1-p)).
Entroopia saavutab maksimaalse väärtuse sel juhul, kui mõlemad tõenäosused on üksteisega võrdsed ja võrdsed ½-ga, nullentroopia väärtus vastab juhtudele (p 0 =0, p 1 =1) ja (p 0 =1, p 1) =0).
Teabe hulk I Ja entroopia H iseloomustada sama olukorda, kuid kvalitatiivselt vastandlikest külgedest. I on teabe hulk, mis on vajalik määramatuse H eemaldamiseks. Leon Brillouini definitsiooni järgi teave on negatiivne entroopia (negentroopia).
Kui ebakindlus on täielikult eemaldatud, siis saadud teabe hulk I võrdne esialgse määramatusega H.
Kui määramatus on osaliselt eemaldatud, liidetakse saadud teabe hulk ja ülejäänud määramatus, mis jääb lahendamata, algse määramatuse summa. H t + I t = H.
Sel põhjusel kasutatakse entroopia arvutamiseks allpool esitatud valemeid H on ka valemid infohulga arvutamiseks I, st. kui tegemist on ebakindluse täielik eemaldamine, H neid saab asendada I.
