border=0

Foarbyld 2.7

Op guon plakken binne der twa tichtneistige doarpen: A en B. It is bekend dat ynwenners fan A altyd de wierheid fertelle, en bewenners fan B altyd lizze. It is ek bekend dat de bewenners fan beide doarpen leaf hawwe om elkoar te besykjen, dus yn elk fan 'e doarpen kinne jo in bewenner fan in buorjend doarp treffen. De reizger, dy't yn 'e nacht fan in paad omkeard wie, fûn him yn ien fan beide doarpen en spruts mei de earste persoan dy't hy moete hie, wist te finen yn hokker doarp hy wie en wêr't syn interlocutor kaam. Wat is it minimum tal fragen mei binêre antwurden dat in reizger freget?

It oantal mooglike kombinaasjes is fansels lykwols lykas 4 (reizger nei A, interlocutor fan A; reizger nei A, interlocutor fan B, ensf.), I. n = 2 2 en dus k = 2. In seleksje fan fragen sels meitsje.

Lit ús besykje de betsjutting fan 'e útkomsten yn dit seksje te begripen. It is nedich om in tal punten te markearjen.

1. Ekspresje (2.14) is in statistyske definysje fan it begryp "ynformaasje", om't it de probaasjes fan mooglik mooglike resultaten fan ûnderfining opnimme. Yn essinsje is in operative definysje fan in nije wearde jûn, d. Set in proseduere (metoade) fan it mjitten fan 'e wearde. As earder oanjûn, is it yn 'e wittenskip (wittenskiplike kennis) dizze metoade om nije termen te yntrodearjen dy't as preferearre beskôge wurdt, om't wat net gemocht wurde kin net ferifiearre wurde en dêrom minder fertrouwen fertsjinnet.

De útdrukking (2.13) kin as folgjende ynterpretearre wurde: as de earste entropy fan it eksperimint H 1 is , en as gefolch fan 'e kommunikaasje fan ynformaasje / entropy wurdt lyk oan H 2 (fansels H 1 ≥ H 2 ) , dan

i.e. Ynformaasje is lyk oan it ferlies fan entropy. Yn it bepaalde saak, as yn earste ynstânsje ekwikbere resultaten n 1 binne , en as gefolch fan ynformaasjeferfanging / ûnwissichheid fermindere, en it oantal resultaten waard n 2 (fansels n 2 ≤ n 1 ), dan fan (2.15) it maklik te krijen:

Sa kinne wy ​​de folgjende definysje jaan:

Ynformaasje is de ynhâld fan in berjocht dat de ûnwissigens fan in soad ûnderfining mei in ungebrûklike útkomst slaan; ferlies fan entropy dy't dêrby ferbûn is in kwantitatyf mjittingen fan ynformaasje.

Yn it gefal fan útwikkelbere resultaten is de ynformaasje lyk oan de logaritme fan 'e ferhâlding fan it oantal mooglike resultaten foar en nei (it ûntfangen fan it berjocht).

2 As al neamde, yn 'e statistyske meganyske entropy karakterisearret ûnwissichheid ferbûn mei in gebrek oan ynformaasje oer de steat fan it systeem. De entropy is de grutste yn in lykwichtigens folslein ungebrûkte system - ús steat fan bewustwêzen is minimaal oer syn state. De opsetting fan it systeem (de yndeksje fan guon oarder) is ferbûn mei it krijen fan in oantal ekstra ynformaasje en in ôfwiking fan entropy. Yn 'e ynformative teory is entropy ek de ûnwissigheid, mar it is in oare soarte fan ûnwissichheid - it is ferbûn mei net te witten fan' e útkomst fan in eksperimint mei in set fan willekeurige resultaten. Sa wurdt, hoewol der in protte yn 'e mienskip is tusken entropy yn natuerkunde en kompjûterwittenskip, is it needsaaklik om it ferskil tusken dizze begripen te erkennen. It is dúdlik dat yn 'e takomst it begryp fan entropy brûkt wurde sil yn' e aspekt fan ynformaasjeynology.

3. De tafoeging fan 'e entropy fan ûnôfhinklike eksperiminten (2.5) is de tafoeging fan ynformaasje. Lit de keuze fan ien fan 'e eleminten (x A ) fan' e set A, dy't n A fan eleminten befettet, is ferbûn mei / A = log 2 n A ynformaasje, en mei de kar fan B fan B mei n B- ynformaasjeelementen binne ferbûn I B = log 2 n B en de twadde Omdat de keuze yn gjinien ferbûn is mei de earste, by it kombinearjen fan sets, sil it oantal mooglike steat (eleminten) n = n A ∙ n B wêze en in kombinaasje selektearje x A x B jo hawwe in kwantiteit fan ynformaasje nedich:

4. Lit ús weromkomme op 'e ferklearring dat it bedrach fan ynformaasje troch it tal fragen meimakke wurde mei twa lykwols probabele antwurden. Is dit betsjutte dat ik altyd in yntegerwearde wêze moat? Fan 'e Hartley-formule (2.15), sa't it te sjen is, I = k bits (dus it ynteger nûmer fan bits) allinich yn it gefal n = 2 k . En yn oare situaasjes? Bygelyks as jo "Guess - 7" spielje (tinke in nûmer fan 0 oant 6), moatte jo m ≥ log 2 7 = 2.807 ynstelle yn 'e selektive cascade, d. Trije fragen moatte frege wurde, om't it tal fragen in inkel is.

Tink derom dat wy tagelyk seis fan deselde wedstriden spielje. Dan moatte jo ien fan 'e mooglike kombinaasjes besjen, dy't binne

Dêrom moat de folsleine sechs-karakter-kombinaasje tocht wurde, I = 17 bit fan ynformaasje is fereaske, i. moatte 17 fragen stelle. Yn trochsneed is ien elemint (ien spul) 17/3 = 2.833 fragen, dy't tichtby de wearde fan log 2 7. Sa,

De wearde fan I , bepaald yn de hjirboppe beskreaune manier, lit sjen hoe folle yn 'e gemiddelde it nedich is om pearde kiezen te meitsjen om it resultaat te fêstjen (folsleine eliminaasje fan ûnwissigens), as it eksperimint in protte kearen werhelle ( n ).

5. It is ek nedich om te begripen dat net altyd mei elk fan 'e antwurden op in fraach dy't allinich twa antwurden hat (wy sille hjirûnder fragen binär betelje ), krekt 1 bit fan ynformaasje is ferbûn. Bysûndere de ûnderfining realisearre troch twa willekeurige eveneminten; want der binne mar twa fan har, fansels, se binne komplemintêre foar elkoar. As dizze eveneminten lykwols wierskynlik binne, p 1 = p 2 = 1/2 , en I = 1 bit, as folget út de Hartley-formule en (2.14). As de wjerringen lykwols oars binne: p 1 = p, dan, neffens (A.8)

p 2 = 1 - p, en fan (2.14) krije wy de funksje:

It is maklik om sjen te litten dat as p → 0 en as p → 1 de funksje I (p) → 0. De situaasje kin yllustrearre wurde troch in grafyk, wêrby't benammen it kin sjoen wurde dat de krom symmetrysk is foar p = 0,5 en makket in maksimum te berikken op dizze wearde . As wy no feroarje, is it evenemint 1 in bejierlik antwurd op in binêre fraach, en evenemint 2 is negatyf, dan slute wy:





Sjoch ek:

Algoritmyske Turing Machine

Algemiene oanpak fan 'e beskriuwing fan apparaten foar it ferwurkjen fan diskrete ynformaasje

Formale systeem

Algoritme performer

Klassifikaasje fan modellen

Gean werom nei Tafel Ynhâld: Teoretyske Stiftingen fan Computer Science

2019 @ bibinar.info