Vidi fonton por Informteorio

'''Informteorio''' aŭ '''informa teorio''', ne aparte specifita, estas la komuna nomo pri la teorio de [[informo]]j de [[Claude Shannon]], kiu estas [[probabloteorio]] por kvantigi la averaĝajn informojn en aro da mesaĝoj, kies komputila kodigo sekvas precizan [[oftecodistribuo|statistikan distribuon]]. Ĉi tiu kampo havas sian sciencan originon kun Claude Shannon, kiu estas la fondinta patro kun sia artikolo ''A Mathematical Theory of Communication'' (Matematika Teorio de Komunikado) eldonita en [[1948]].

Gravaj branĉoj de la informteorio de Shannon inkludas:

:- la kodadon de informoj,
:- la kvantecan mezuron de [[redundo]] de teksto,
:- '''datumkunpremo''' aŭ '''datumdensigo''',
:- [[kriptografio]].
En pli ĝenerala senco, informteorio estas teorio celanta kvantigi kaj kvalifiki la nocion de enhavo pri informoj ĉeestantaj en aro da [[datumo]]j. Kiel tia, ekzistas alia teorio de informoj: la "algoritma teorio de informoj", kreita de [[Andrej Kolmogorov|Kolmogorov]], [[Ray Solomonov|Solomonov]] kaj [[Gregory Chaitin]] komence de la 1960-aj jaroj.

== Disvolviĝo de la matematika informteorio ==
[[Claude Shannon]] kaj [[Warren Weaver]] plifortigis la [[paradigmo]]n. Ili estis telekomunikado-inĝenieroj kaj temis pri mezurado de informojn por dedukto de la fundamentaĵoj pri [[komunikado]] (kaj ne teorio de informoj). En ''A Mathematical Theory of Communication'' (Matematika teorio pri komunikado) <ref>Robert B. Ash. ''Information Theory''. New York: Interscience, 1965. {{ISBN|0-470-03445-9}}. New York: Dover 1990. {{ISBN|0-486-66521-6}}, p. v</ref><ref>{{Citaĵo el libro|aŭtoro= R.W. Yeung | volumo = The Science of Information (La scienco pri informado) | doi = 10.1007/978-0-387-79234-7_1 | titolo = Information Theory and Network Coding (Informteorio kaj [[Kodo|kodado]] | paĝoj = p. 1–01 | jaro = 2008 | isbn = 978-0-387-79233-0 | pmid = | pmc =|lingvo=angle }}</ref> estas artikolo verkita de la [[inĝeniero]] kaj [[matematikisto]] [[Claude Shannon]] eldonita en la ĵurnalo ''Bell System Technical Journal'' en [[1948]]<ref> {{Citaĵo el ĵurnalo |aŭtoro=Claude E. Shannon |titolo=A Mathematical Theory of Communication (Matematika teorio pri komunikado) |gazeto=Bell System Technical Journal |volumo=27 |issue=3 |paĝoj=p. 379–423 |dato=Julio 1948 | url = http://ieeexplore.ieee.org/xpl/articleDetails.jsp?arnumber=6773024 |doi=10.1002/j.1538-7305.1948.tb01338.x|lingvo=angle}}</ref><ref> {{Citaĵo el ĵurnalo |aŭtoro=Claude E. Shannon |titolo=A Mathematical Theory of Communication |gazeto=Bell System Technical Journal |volumo=27 |numero=4 |paĝoj=p. 623–666 |dato=oktobro 1948 | url = http://ieeexplore.ieee.org/xpl/articleDetails.jsp?arnumber=6773067 |doi=10.1002/j.1538-7305.1948.tb00917.x|lingvo=angle}}</ref>. Ili modelis informojn por studi la respondajn leĝojn: [[bruo]]n, [[entropio]]n kaj [[ĥaoso]]n, laŭ ĝenerala analogio al la leĝoj de [[energio]] kaj [[termodinamiko]]. Iliaj verkoj kompletigis tiujn de [[Alan Turing]], [[Norbert Wiener]] kaj [[John von Neumann]] (por nomi nur la ĉefajn fakulojn) kaj konstituas la komencan bazon de la "teorio de signalo"" kaj de la "Sciencoj pri informo".

Estu fonto <math>X</math> kun <math>n</math> simboloj, simbolo <math>i</math> havanta [[probablo]]n <math>p_i</math> aperi, la entropio <math>H</math> de la fonto <math>X</math>, ankaŭ nomata ''Shannon-entropio'', estas difinita laŭ la informteorio tiele:
<center>
<math> H(X)=-\sum_i^n p_i \log_2 (p_i)</math>
</center>
Komence la [[natura logaritmo]] estis uzata. Sed por komforto, ĝi estos anstataŭigata de la logaritmo kun [[duuma nombrosistemo|bazo ''2'']], tielmaniere ke la elementa informo estu la [[bito]].

[[Informadiko]] do estos teĥnika variado aŭtomatanta la prilaboradon (inkluzive de transdono kaj transporto) de informoj.

== Informekzemploj ==
Informo difinas, inter aro da [[evento]]j, unu aŭ plurajn eblajn eventojn.

Teorie, la informo reduktas [[necerteco]]n. En la ''teorio de decido'', oni eĉ konsideras, ke oni devas nomi "informo" nur tion, kio estas "verŝajne havi efikon sur niaj [[decido]]j".

En praktiko, la troo da informo, kiel ĝi aperas en [[retpoŝto|retpoŝtaj]] sistemoj, povas konduki al saturado kaj malhelpi decidon.

=== Unua ekzemplo ===
Estu fonto, kiu povas produkti elektrajn [[tensio]]jn kun [[entjero|entjeraj]] valoroj de 1 ĝis 10 [[volto]]j kaj ricevilo, kiu mezuros ĉi tiun tension. Antaŭ sendi la [[kurento]]n per la fonto, la ricevilo havas neniun ideon pri la elektra fluo, kiu estos transdonita de la fonto. Aliflanke, post la elsendo kaj la ricevo de kurento, la necerteco pri la elsendita fluo malpliiĝas. La informteorio konsideras, ke la ricevilo havas necertecon de 10 [[stato]]j.

=== Dua ekzemplo ===
[[Biblioteko]] havas multajn [[verko]]jn, [[revuo]]jn, [[libro]]jn kaj [[vortaro]]jn. Ni serĉas kompletan [[kurso]]n pri informteorio. Unue, estas logike, ke ni ne trovos ĉi tiun dosieron en verkoj pri arto aŭ literaturo; ni ĵus akiris informojn, kiuj reduktos nian tempon de serĉo. Ni diris, ke ni ankaŭ volis kompletan kurson, do ni ne trovos ĝin en revuo aŭ en vortaro. Ni akiris plian informon, ke ni serĉas libron, kio ankoraŭ malpliigos la daŭron de nia esplorado.

=== Malperfekta informo ===
Estu [[reĝisoro]], pri kiu mi kutime ŝatas du filmojn el tri. Kritikulo, kiun mi bone konas, mallaŭdis sian lastan filmon kaj mi scias, ke mi kunkonsentas la averaĝan analizon de ĉi tiu kritikulo kvar fojojn el kvin. Ĉu ties kritiko malhelpu min iri por vidi la filmon? Ĉi tiu estas la centra demando pri "Bayesia [[inferenco]]", kiu ankaŭ estas kvantigita en [[bito]]j.

== Enhavo de informo kaj kunteksto ==
Bezonas malpli da bitoj por skribi "hundo" ol "mamulo". Tamen la indiko "Medor estas hundo" enhavas multe pli da informoj ol la indiko "Medor estas mamulo": la enhavo de [[semantiko|semantika]] informo de [[mesaĝo]] dependas de la [[kunteksto]]. Fakte, estas la paro ''mesaĝo + kunteksto'', kiu konstituas la veran portanton de informoj, kaj neniam la mesaĝo sole.

== Mezurante la kvanton da informoj ==
=== Kvanto da informo: elementa kazo ===
Konsideru <math>N</math> skatolojn numeritaj de 1 ĝis <math>N</math>. Individuo A kaŝis objekton hazarde en unu el ĉi tiuj skatoloj. Individuo B devas trovi la numeron de la skatolo, en kiu la objekto estas kaŝita. Por ĉi tio, li rajtas demandi la individuon A, al kiu li devas respondi sen mensogi, per JES aŭ NO. Sed por ĉiu demando devas esti pagita de la individua B etan monsumon (ekzemple unu eŭro). Individuo C scias, en kiu skatolo kaŝitas la objekto. Li havas la eblon vendi ĉi tiun informon al la individuo B. B nur akceptos ĉi tiun merkaton se la prezo de C estas malpli ol aŭ egalas al la averaĝa kosto, kiun B devus elspezi por koni la bonan skatolon, per la vico da demandoj al A. La informoj tenataj de C sekve havas certan prezon. Ĉi tiu prezo reprezentas la kvanton da informoj ligitan al la [[scio]] de la serĉata skatolo: ĝi estas la averaĝa nombro da petendaj demandoj por identigi ĉi tiun skatolon. Kompreneble ju pli la nombro de skatoloj estas granda, des pli individuo B akceptos pagi grandmonsumon al individuo C. Notu ni ĝin <math>I</math>.

'''Ekzemploj:'''

Aŭ <math>N = 1</math>, <math>I = 0</math>; estas nur unu skatolo, ne utilas iu ajn demando.

Aŭ <math>N = 2</math>, <math>I = 1</math>; post la demando ĉu la bona skatolo estas la skatolo 1, la respondo JES aŭ NE permesas tiam senambigue koni tiun, kiu estas la serĉita skatolo.

Aŭ <math>N = 4</math>, <math>I = 2</math>; post la du demandoj ĉu la bona skatolo estas unu el la du skatoloj 1 aŭ 2, se estas respondo JES la problemo estas solvita, se NE sufiĉas alia kroma demando, por trovi tiun, kiu estas la bona skatolo el la du restantaj.

Aŭ <math>N=2^k</math>, <math>I = k</math>; oni numeras la skatolojn laŭ la [[bazo (nombrosistemo)|bazo]] ''2''. La numeroj posedas maksimume <math>k</math> duumajn ciferojn, kaj por ĉiu pozicio de tiuj ciferoj, oni demandas ĉu la serĉata skatolo rilatas al la cifero 0 aŭ 1. Per <math>k</math> demandoj, tiel determinitas ĉiuj duumaj ciferoj kaj finfine la pozicio de la bona skatolo. Ĉi tio resumiĝas per <math>k</math> demandoj, ĉiu demando sinsekve dividanta per 2 la nombron de skatoloj konsideritaj ([[Diĥotomio|diĥotomia]] metodo).

Do oni povas skribi la rezulton: <math>I = \log_2(N)</math>, sed ĝi validas nur se la <math>N</math> eventoj estas sam[[probablo|probablaj]].

=== Kvanto da informoj rilate al unu evento ===
Supozu ni nun, ke la skatoloj estu kolorigitaj kaj ke estu <math>n</math> ruĝaj skatoloj. Supozu ankoraŭ, ke la individuo C scias, ke estas ruĝa la skatolo en kiu la objekto estas kaŝita. Kiu estas la prezo de tiu informo? Sen ĝi, la pagenda prezo estus <math>\log_2(N)</math>. Dank' al tiu informo, la pagenda prezo estas nur <math>\log_2(n)</math>. La prezo de la informo «la serĉata skatolo estas ruĝa» estas do <math> \log_2(N) - \log_2(n)  = \log_2(N/n) </math>.

Tial difiniĝas la kvanto da informo, kiel kreska funkcio de <math>\frac{N}{n}</math> kun:
* <math>N</math> nombro de eblaj eventoj,
* <math>n</math> nombro de eventoj de la [[subaro]] difinita per la informo.

Por mezuri tiun infrormkvanton, oni difinas: <math>I = \log_{2}  \left (\frac{N}{n} \right) = - \log_{2}  \left (\frac{n}{N} \right)\ \, ,</math>

kie <math>I</math> esprimatas per [[bito]] .

Tia difino praviĝas, pro la fakto ke la sekvantaj proprecoj nepras:
# informo valoras inter 0 kaj ∞ ;
# evento kun malgranda probablo enhavas grandkvanton da informoj (ekzemple: « Neĝas dum januaro» enhavas multe malpli da informo ol « Neĝas dun aŭgusto » se ni loĝas en la [[norda duonglobo]]);
# informo [[Sigma adicieco|adicias]].

=== Entropio, apliko de Shannon-formulo ===
Supozu ni, ke estas diverskoloraj skatoloj: ''n''<sub>1</sub> skatoloj kun koloro C<sub>1</sub>, ''n''<sub>2</sub> skatoloj kun koloro C<sub>2</sub>…, ''n''<sub>''k''</sub> skatoloj kun koloro C<sub>''k''</sub>, kun ''n''<sub>1</sub> + ''n''<sub>2</sub> + … + ''n''<sub>''k''</sub> = N. La individuo C konas la koloron de la serĉata skatolo. Kiu estas la prezo de tiu informo?

La informo «la koloro de la skatolo estas C<sub>1</sub>» valoras log N/''n''<sub>1</sub>, kaj tiu okazaĵo havas probablon ''n''<sub>1</sub>/N.
La informo «la koloro de la skatolo estas C<sub>2</sub>» valoras log N/''n''<sub>2</sub>, kaj tiu okazaĵo havas probablon ''n''<sub>2</sub>/N...

La averaĝa prezo de la informo estas do ''n''<sub>1</sub>/N log N/''n''<sub>1</sub> + ''n''<sub>2</sub>/N log N/''n''<sub>2</sub> + … + ''n''<sub>''k''</sub>/N log N/''n''<sub>''k''</sub>. Pli ĝenerale, se oni konsideras ''k'' disajn eventojn kun respektivas probabloj ''p''<sub>1</sub>, ''p''<sub>2</sub>…, ''p''<sub>''k''</sub> kaj ''p''<sub>1</sub> + ''p''<sub>2</sub> + … + ''p''<sub>''k''</sub> = 1, tial la informkvanto respondanta al tiu probablodistribuo estas ''p''<sub>1</sub> log 1/''p''<sub>1</sub> + … + ''p''<sub>''k''</sub> log 1/''p''<sub>''k''</sub>. Tiu kvanto nomiĝas entropio de la probablodistribuo

Tiu Shannon-entropio permesas do mezuri la averaĝan informkvanton da eventaro (aparte de mesaĝoj) kaj mezuri ĝian necertecon. Oni notas ĝin <math>H</math>
:<math>H(I) = \log_2(N) - \sum_i p_i \log_2(n_i) = - \sum_{i\in I} p_i \log_2(n_i/N) = -\sum_{i\in I} p_i \log_2(p_i)</math>
kun <math>p_i = \frac{n_i}{N}</math> la probablo asociita al la apero de la evento <math>i</math> kaj sekvas:
:<center><math>H \left (I \right) = - \sum_{i\in I} p_i \log_2\; p_i  \ \, .</math></center>

== Referencoj ==
<big>{{referencoj}}</big>

== Vidu ankaŭ ==
=== Bibliografio ===
* {{en}} {{pdf}} [[Claude Shannon|C. E. Shannon]] {{Citaĵo el la reto|url=http://www-igm.univ-mlv.fr/~beal/Enseignement/TheorieInfo/shannon1948.pdf|titolo=A Mathematical Theory of Communication|eldonejo=L’Institut d’électronique et d’informatique Gaspard-Monge|format=|lingvo=angle}} (Represita kun korektoj el ''Bell System Technical Journal'', Vol. 27, {{p.|379–423}}, 623–656, Julio, oktobro, 1948.)
* https://fr.wikipedia.org/wiki/R%C3%A9f%C3%A9rence:Elements_of_Information_Theory Eldonejo Wiley-Interscience, ISBN 978-0-471-24195-9 ({{en}})
* http://www.inference.org.uk/mackay/itila/ 16 videoj de prelegoj de David MacKay ({{en}})

=== Eksteraj ligiloj ===
{{Projektoj}}
* [https://www.youtube.com/watch?v=nAA7UyiCIOE [[Video]] pri la entropio en la informteorio] ({{fr}})

{{Portalo|Komputiko}}

== Fonto ==
{{Tradukita|fr|Théorie de l'information|Q131222}}

[[Kategorio:Informa teorio| ]]
[[Kategorio:Entropio]]