Изворни код странице Теорија информације

'''Теорија информације''' је математичка дисциплина настала у 20. веку. Логаритамски израз за количину информације је предложио [[Ралф Хартли|Хартли]] 1928. године, у свом раду „Пренос информације“. Затим ју је 1948. поопштио амерички инжењер и математичар [[Клод Елвуд Шенон|Клод Шенон]], и нешто раније, руски математичар [[Андреј Колмогоров|Андреј Николајевич Колмогоров]]. Исте 1948. године је амерички математичар [[Норберт Винер]] у свом раду „[[Кибернетика]]“ изнео свој приступ количини информације система. Десило се да је математичка теорија информације настала „одједном“, малтене у неколико радова зачетника и да је у тим радовима „нацртан“ оквир за целу будућу дисциплину. Покретачко место целог тог развоја је откриће, математичка дефиниција појма „количина података“. И данас се сматра да је идеју за мерење количине информације први добио управо амерички инжењер Хартли 1928. године, али му историја математике не придаје велики значај можда због нејасноћа и (математички) непрецизних објашњења.<ref>[[Klod Elvud Šenon|Shannon, C.E.]] (1948), "[[A Mathematical Theory of Communication]]", ''Bell System Technical Journal'', 27, pp. 379–423 & 623–656, July & October, 1948. [http://math.harvard.edu/~ctm/home/text/others/shannon/entropy/entropy.pdf PDF.]</ref><ref>R.V.L. Hartley, [http://www.dotrose.com/etext/90_Miscellaneous/transmission_of_information_1928b.pdf "Transmission of Information"] {{Wayback|url=http://www.dotrose.com/etext/90_Miscellaneous/transmission_of_information_1928b.pdf |date=20111004200852 }}, ''Bell System Technical Journal'', July 1928</ref>

== Информација ==
Математичко тврђење, односно [[математички исказ]] је израз, који може бити Тачан, или Нетачан. То је основа тзв. бинарне логике, дела [[Математичка логика|математичке логике]]. Помоћу [[Бинарна логика|бинарне логике]] је могуће дефинисати сваки исказ [[Поливалентна логика|поливалентне логике]]. Ове посљедње математичке логике, поред бинарних вредности: <math>\top, \bot</math>, тј. тачно, нетачно, укључују читав спектар одговора „можда“.

=== Хартлијева дефиниција ===
Када желимо једноставан одговор ''да'' или ''не'' постављамо питања која почињу са: „Да ли је ...“. На пример питање „Да ли је ова подлога бела?“ тражи једноставнији одговор од питања: „Какве је боје ова подлога?“. У првом случају имамо само дилему да-не, у другом случају имамо спектар боја. Када имамо спектар боја имамо већу дилему, па ћемо рећи да је тада неизвесност већа. 

На пример, када постоји 8 једнако могућих избора за боју подлоге, а није унапред познат следећи избор, мора се постављати више од једног бинарног питања да би се дошло до одговора. Зато је неодређеност избора већа. Тачније:

: '''Неодређеност''' је најмања количина података потребних за препознавање датог елемента.

Неодређеност исказа се може дефинисати као најмањи број питања чији је једини допустив одговор да-не, потребних да се дође до одговора. Свако тако постављено питање дефинишемо као један бит. Дакле број бита је број бинарних питања. 

Колико бинарних питања треба поставити, да би се сазнао један од 8 бројева? Одговор је 3. 
На пример, замислили сте број 6. 

1. питање: Да ли је то један од бројева 1, 2, 3, 4?
Одговор: Не.

2. питање: Да ли је то један од бројева 5, 6?
Одговор: Да.

3. питање: Да ли је то број 5?
Одговор: Не.

Решење: Замишљени број је био 6.

Број (бинарних) питања је 3. Неодређеност замишљеног броја била је 3. Информација коју добијамо сазнањем замишљеног броја је 3.

Колико бинарних питања треба поставити да би се сазнао један од 16 бројева? Одговор је 4.
Уопште, колико бинарних питања треба поставити да би се сазнао један од <math>2^n</math> бројева? Одговор је ''n''.

Амерички инжењер Р. В. Л. [[Ралф Хартли|Хартли]] је у свом раду „Пренос информације“, 1928. године предложио да се количина информације дефинише помоћу логаритма броја једнако вероватних могућности избора. То је наставак претходних примера.

Када имамо <math>n=1,2,3,...</math> једнако вероватних елемената, тада је вероватноћа избора једног од њих <math>p=P(n)=\frac{1}{n}</math>. Информација, тј. количина информације коју добијамо сазнањем једне од ''n'' једнако вероватних вести, према Хартлију је:

: <math>I(p)=-log_2P(n)=log_2n</math>.

На пример, логаритам по бази два од 1 је 0, од 2 је 1, од 4 је 2, од 8 је 3, од 16 је 4, итд. 

Количина информације, зовемо је кратко информација, коју добијамо након случајног опита са једнаковероватним исходима, је логаритам по бази 2 вероватноће тог опита.

=== Шенонова дефиниција ===

Хартлијева информација, формула, служи само у случају мерења једнако вероватних исхода. Бар тако се чини на први поглед. Међутим, шта да радимо ако је случај сложенији. Када имамо различито вероватне исходе и хоћемо да меримо информацију за сваки од случајева. Показаћемо да се полазећи од Хартлијеве може доћи до дефиниције информације за сложеније случајеве, користећи већ познати појам математичке средње вредности. То је открио [[Klod Elvud Šenon|Клод Шенон]] у знаменитом раду „Математичка теорија комуникације“, који је написао заједно са В. Вивером 1949. године.

Ако имамо шест куглица, по две у бојама: црвеној, плавој и белој. Рецимо да бирамо једну од шест, једнако вероватних, али тражен је један од одговора:
# извучена куглица је бела - вероватноћа је 2/6;
# извучена куглица није бела - вероватноћа је 4/6.

Хартлијева информација за први и други случај била би: <math>I_1=-log_2\frac{2}{6}</math>, односно <math>I_2=-log_2\frac{4}{6}</math>. Средња вредност, тј. математичко очекивање за ова два броја је: <math>I=-p_1I_1-p_2I_2</math>. Логаритми вероватноћа су негативни бројеви! Дакле 

: <math>I=- \frac{2}{6}log_2 \frac{2}{6}- \frac{4}{6}log_2 \frac{4}{6}</math>.

Општије, када имамо два исхода, вероватноћа <math>p_1</math> и <math>p_2</math>, тада нам резултат случајног бирања доноси информацију:

: <math>I=-p_1log_2p_1-p_2log_2p_2</math>.

Уопште, када имамо низ <math>n=2,3,4,...</math> исхода, истих или различитих вероватноћа <math>p_1,p_2,...,p_n</math>, тада нам резултат случајног догађаја доноси информацију ''I'' која је средња вредност, тј. математичко очекивање, позитивних вредности логаритама вероватноћа. Према томе,

: <math>I=-p_1log_2p_1-p_2log_2p_2-...-p_nlog_2p_n</math>.

То је Шенонова дефиниција информације. Откриће да се информација може мерити, колико једноставно, толико је било невероватно за математичаре. Била је веома изненађујућа чињеница да можемо (математички прецизно) рећи „има толико и толико бита информације у датој новинској вести“, баш као када кажемо „овај бурек је тежак 300 грама“. Математичари су били у шоку и неверици, али техника није чекала. У другој половини 20. века је наступила револуција информатике. За то време је математичка теорија информације полако, полако напредовала.

=== Неодређеност ===

[[Норберт Винер]] је 1948. године у свом делу [[Кибернетика]] дефинисао информацију у систему као меру његове организованости, док је неодређеност система мера његове неорганизованости. По Винеру је неодређеност само негација информације као одраз у огледалу. Количински су оне једнаке. Колико имате неодређености у опиту пре, толико имате информације у опиту након реализације случајног догађаја. Другим речима, када говоримо о количинама, у истим системима јединица, морало би бити:

: (информација) = (неодређеност).

У једнакости лево и десно, имамо исте количине нечега после и пре сазнања. Он није знао за радове Шенона који су објављени тек следеће године. Решење је пронашао у термодинамици! 

Аустријски физичар [[Лудвиг Болцман]] је још далеке 1872. године изучавао, тада нову науку, [[Термодинамика|термодинамику]] и открио [[Ентропија|ентропију]] гаса. Болцман је уочио да је ентропија мера нереда у термодинамичком систему и да систем временом тежи већој ентропији. Меру нереда система са вероватноћама исхода <math>p_1, p_2, p_3, ...</math>, где је <math>p_1+p_2+p_3+... =1</math>, означио је са ''H'' и извео је свој чувени израз за неред термодинамичког система:

: <math>H(p_1,p_2,p_3,...)=-p_1log_2p_1-p_2log_2p_2-p_3log_2p_3-...</math>.

Обзиром на претходну формулу Винера, добијамо да је информација ''I'' = ''H'', тј. да је Винер-Болцманова формула за количину информације тачно иста као Шенонова. 

Болцман је своју ентропију појаснио на примеру чаше чисте воде у коју би сипао мастило. Временом сва вода постаје обојена, јер се у свом хаотичном кретању честице воде мешају са честицама мастила, правећи све слабију разлику између границе ових двеју течности. Тако се повећава неред, односно ентропија система у чаши. Систем тежи стању у којем сви догађаји имају једнаке вероватноће. Обрнут процес се практично не догађа и зато су термодинамички процеси иреверзибилни (неповратни).

Данас можемо рећи да је Болцман описивао тзв. [[Ергодичка теорија|ергодичке процесе]], код којих се ентропија спонтано повећава до своје максималне вредности. Пример са уљем, уместо мастила у Болцмановој чаши био би супротан, тзв. неергодички процес.

=== Основна теорема ===
Питање математичке истинитости није ствар провере у лабораторији, експеримента, или веровања у сопствена чула. Математичка истина се не доказује провером у пракси.

Овде се бавимо питањем може ли се Хартлијева дефиниција информације, заснована на целим бројевима (навели смо само примере за 8 и 16) могућности поопштити на све целе бројеве, и даље на све позитивне реалне бројеве? 

1. '''Пример''':
: Фабрика производи 16 врста кошуља за чију израду користи 64 врсте дезена. Претпоставка је да је сваки модел произведен у истом броју комада. Колико бита има неодређеност једне кошуље?

Број свих модела које производи фабрика је 16х64=1024.

: (неодређеност) = <math>log_2 1024</math> = 10 бита, 
:: <math>= log_2 16 + log_2 64 = 4 + 6 </math> бита.

Количина неодређености је увек позитиван број. Када нема неизвесности, неодређеност је нула, и кажемо да нема информације. Када расте неизвесност, расте и неодређеност, тачније расте реципрочна вредност вероватноће.

2. '''Пример''': 

: Када имамо ''n'' = 1, 2, 3, ... једнако вероватних елемената тада је вероватноћа избора једног од њих <math>p=P(n)=\frac{1}{n}</math>, а информација према Хартлију је <math>I(p)=-log_2P(n)=log_2 n</math>. 

Са само једним елементом ''n'' = 1 је случај без неизвесности избора, па је и информација нула (логаритам јединице је нула), тј. нема информације. Међутим, информација је позитивна, растућа функција броја ''n'' могућих исхода. Такође важи да је адитивна функција, у смислу: 

: логаритам производа једнак је збиру логаритама, тј.

: <math> log_2 mn=log_2 m + log_2 n </math>, па је

: <math> I(mn)=I(m)+I(n)</math>.

Дакле Хартлијева информација производа једнака је збиру Хартлијевих информација. Сада постављамо питање да ли је тачно и обрнуто.

; Теорема : Нека је ''f''(''x'') непрекидна функција дефинисана на скупу реалних бројева ''x'' > 1. Ако је ''f''(''x''):

: (i) позитивна, тј. за свако ''x'' > 1 је ''f''(''x'') > 0,
: (ii) растућа, тј. за ''x'' < ''y'' је ''f''(''x'') < ''f''(''y''),
: (iii) ''f''(''xy'') = ''f''(''x'') + ''f''(''y'') за свако ''x'', ''y'' из скупа реалних бројева и ''x'', ''y'' > 1 

: тада је <math>f(x)=C \cdot log_bx</math>, где су ''C'' > 0, ''b'' > 1 произвољни реални бројеви.

'''Доказ'''. За свако ''x'' > 1 и за свако ''r'' > 0 постоји број ''k'' = 0, 1, 2, ... такав да је 

: <math>x^k \le 2^r < x^{k+1}</math>. 

На основу овога и особине (ii) је 

: <math>f(x^k) \le f(2^r) < f(x^{k+1})</math>, одакле се због (iii) добија 

: <math>k \cdot f(x) \le r \cdot f(2) < (k+1) \cdot f(x) </math>. Како према (i) је ''f''(''x'')> 0, дељењем ових неједнакости са 

: <math>r \cdot f(x)</math> имамо 

: <math>\frac{k}{r} \le \frac{f(2)}{f(x)} < \frac{k}{r}+ \frac{1}{r}</math>.

Функција <math>f(x)=log_b x</math>, ''b'' > 1 има особине (i)-(iii) па горње неједнакости важе и за њу, тј. 

: <math>\frac{k}{r} \le \frac{log_2b}{log_bx}<\frac{k}{r}+\frac{1}{r}</math>. На основу тога је 

: <math>\left| \frac{log_b2}{log_bx} - \frac{f(x)}{f(2)} \right|<\frac{1}{r}</math>, за свако ''r'' > 0 па и за произвољно велико ''r'', због чега је израз у апослутној загради последње неједнакости нула, тј. 

: <math>f(x)=\frac{f(2)}{log_b2} \cdot log_bx</math>, односно 

: <math>f(x)=C \cdot log_bx</math>. '''Крај доказа'''.

Дакле, Хартлијеву информацију је могуће само толико поопштити да уместо логаритамске базе 2 узмемо неки други број, дозвољен за базу логаритма. 

На пример, ако за јединицу информације узмемо децит, један од 10 једнако вероватних догађаја, тада радимо са декадним логаритмима па је <math>-I_{10}(x)=log_{10}x=log_{10}2 \cdot log_2x</math>, те добијамо 1 децит = 0,30103... бита.

На пример, природна јединица информације, скраћено „нат“ или „нит“ користи базу природног логаритма ''е'' = 2,71828.... Тада је <math>ln N = ln 2 \cdot log_2 N</math>, па је 1 нат = 0,69315... бита.

== Теорија информације у психологији ==
{{Детаљније|Теорија информације у психологији}}
Појавом [[Макроприступ|макроприступа]] долази до промене приласка у испитивању [[Феноменализам|феномена]]. Један од психолошких праваца, [[Гешталт|гешталт психологија]], почиње уместо лабораторијског и класичног [[Психофизика|психофизичког]] приступа, да се бави макроприступом у испитивању когнитивних феномена уводећи феноменолошки поступак. То би била идеја да се приступи истраживању психолошких феномена у целини, не разбијајући њихову структуру. Појава феноменолошког метода у гешталт психологији је први доследан макроприступ у овој науци. Велика разлика је у схватању објекта, где је код гешталтиста слика у целини независна од природе елемената који је граде.<ref>Огњеновић, П. (2002). ''Псхологија опажања.'' Београд: Завод за уџбенике и наставна средства.</ref>

== Референце ==
{{Reflist}}

== Literatura ==
{{Литература|30em}}
* [[Андреј Колмогоров|Andrey Kolmogorov]] (1968), "{{cite journal |last1= |first1= |date= |title=Three approaches to the quantitative definition of information |url= |journal= |volume= |issue= |pages= |doi=10.1080/00207166808803030 }}" in International Journal of Computer Mathematics.
* J. L. Kelly, Jr., [http://betbubbles.com/wp-content/uploads/2017/07/kelly.pdf Betbubbles.com]{{Мртва веза|date=04. 2020 |bot=InternetArchiveBot |fix-attempted=yes }}, "A New Interpretation of Information Rate" ''Bell System Technical Journal'', Vol. 35, July 1956, pp. 917–26.
* R. Landauer, [http://ieeexplore.ieee.org/search/wrapper.jsp?arnumber=615478 IEEE.org], "Information is Physical" ''Proc. Workshop on Physics and Computation PhysComp'92'' (IEEE Comp. Sci.Press, Los Alamitos, 1993) pp. 1–4.
* R. Landauer, [http://www.research.ibm.com/journal/rd/441/landauerii.pdf IBM.com], "Irreversibility and Heat Generation in the Computing Process" ''IBM J. Res. Dev.'' {{cite journal|url=http://www.research.ibm.com/journal/rd/441/landauerii.pdf|volume=5|issue=3|pages=|title=IBM Research Publications &#124; IBM Research|date=9 February 2021}}, 1961
* {{cite arXiv |last1=Timme|first1=Nicholas|last2=Alford |first2=Wesley|last3=Flecker |first3=Benjamin|last4=Beggs |first4=John M.|date=2012 |title=Multivariate information measures: an experimentalist's perspective |eprint=1111.6857|class=cs.IT}}
* {{Cite book|last=Arndt|first=C|title=Information Measures, Information and its Description in Science and Engineering|location=Springer Series|publisher=Signals and Communication Technology|year=2004|isbn=978-3-540-40855-0|pages=}}
* Ash, RB. ''Information Theory''. New York: Interscience, 1965. {{ISBN|0-470-03445-9}}. {{page1|location=New York|publisher=Dover|year=1990|isbn=0-486-66521-6|pages=}}
* {{Cite book|last=Gallager|first=R|authorlink=Gallager, R|title=Information Theory and Reliable Communication.|url=https://archive.org/details/informationtheor0000gall|location=New York|publisher=John Wiley and Sons|year=1968|isbn=0-471-29048-3|pages=}}
* Goldman, S. ''Information Theory''. New York: Prentice Hall, 1953. New York: Dover 1968 {{ISBN|0-486-62209-6}}. {{page|year=2005|isbn=0-486-44271-3|pages=}}
* {{Cite book |last1=Cover |first1=Thomas |author-link1=Thomas M. Cover |last2=Thomas |first2=Joy A. |title=Elements of information theory |url=https://archive.org/details/elementsofinform0000cove_m4w2 |edition=2nd |location=New York |publisher=[[John Wiley & Sons|Wiley-Interscience]] |year=2006|isbn=0-471-24195-4}}
* [[Csiszar, I]], Korner, J. ''Information Theory: Coding Theorems for Discrete Memoryless Systems''  Akademiai Kiado:. {{page1|edition=2nd|year=1997|isbn=963-05-7440-3|pages=}}
* {{Cite book|author=MacKay, David J. C|authorlink=David J. C. MacKay|title=Information Theory, Inference, and Learning Algorithms|url=http://www.inference.phy.cam.ac.uk/mackay/itila/book.html|location=Cambridge|publisher=Cambridge University Press|year=2003|isbn=0-521-64298-1|pages=}}
* {{Cite book|last=Mansuripur|first=M|title=Introduction to Information Theory| url=https://archive.org/details/introductiontoin0000masu|location=New York|publisher=Prentice Hall|year=1987|isbn=0-13-484668-0|pages=}}
* [[Robert McEliece|McEliece, R]]. ''The Theory of Information and Coding". Cambridge. {{page|year=2002|isbn=978-0521831857|pages=}}
* Pierce, JR.  "An introduction to information theory: symbols, signals and noise".  Dover (2nd Edition). 1961 (reprinted by Dover 1980).
* [[Reza, F]]. ''An Introduction to Information Theory''. New York: McGraw-Hill 1961. {{page1|location=New York|publisher=Dover|year=1994|isbn=0-486-68210-2|pages=}}
* {{Cite book |last1=Shannon |first1=Claude |author-link1=Claude Shannon |last2=Weaver |first2=Warren |author-link2=Warren Weaver |year=1949|title=The Mathematical Theory of Communication |url=http://monoskop.org/images/b/be/Shannon_Claude_E_Weaver_Warren_The_Mathematical_Theory_of_Communication_1963.pdf |location=[[Урбана (Илиноис)|Urbana, Illinois]] |publisher=[[University of Illinois Press]] |lccn=49-11922 |isbn=0-252-72548-4}}
* Stone, JV.  Chapter 1 of book [http://jim-stone.staff.shef.ac.uk/BookInfoTheory/InfoTheoryBookMain.html "Information Theory: A Tutorial Introduction"], University of Sheffield, England. {{page|year=2014|isbn=978-0956372857|pages=}}
* Yeung, RW.  ''[http://iest2.ie.cuhk.edu.hk/~whyeung/book/ A First Course in Information Theory]'' Kluwer Academic/Plenum Publishers, . {{cite book|title= A First Course in Information Theory|location= |publisher= Springer|year=2002|pages= |isbn=0-306-46791-7|last1= Yeung|first1= Raymond W.}}.
* Yeung, RW.  ''[http://iest2.ie.cuhk.edu.hk/~whyeung/book2/ Information Theory and Network Coding]'' Springe{{page|year=2002|isbn=978-0-387-79233-0|pages=2008}}
* Leon Brillouin, ''Science and Information Theory'', Mineola, N.Y.: Dover, [1956, 1962]. {{page|year=2004|isbn=0-486-43918-6|pages=}}
* {{Cite book|last=Gleick|first=James|authorlink=James Gleick|title=[[The Information: A History, a Theory, a Flood]]|location=New York|publisher=Pantheon|year=2011|isbn=978-0-375-42372-7|pages=}}
* {{Cite book|last=Khinchin|first=A. I.|title=Mathematical Foundations of Information Theory| url=https://archive.org/details/mathematicalfoun0000khin|location=New York|publisher=Dover|year=1957|isbn=0-486-60434-9|pages=}}
* H. S. Leff and A. F. Rex, Editors, ''Maxwell's Demon: Entropy, Information, Computing'', Princeton University Press, Princeton, New Jersey. {{page|year=1990|isbn=0-691-08727-X|pages=}}
* [[Robert K. Logan]]. ''What is Information? - Propagating Organization in the Biosphere, the Symbolosphere, the Technosphere and the Econosphere'', Toronto: DEMO Publishing.
* {{Cite book|last=Siegfried|first=Tom|title=The Bit and the Pendulum|publisher=Wiley|year=2000|isbn=0-471-32174-5|pages=}}
* {{Cite book|last=Seife|first=Charles|title=[[Decoding the Universe]]|publisher=Viking|year=2006|isbn=0-670-03441-X|pages=}}
* Jeremy Campbell, ''[[Grammatical Man]]'', Touchstone/Simon & Schuster. {{page|year=1982|isbn=0-671-44062-4|pages=}}
* Henri Theil, ''Economics and Information Theory'', Rand McNally & Company - Chicago, 1967.
* {{Cite book|author=Escolano, Suau, Bonev|title=Information Theory in Computer Vision and Pattern Recognition|url=https://www.springer.com/computer/image+processing/book/978-1-84882-296-2|publisher=Springer|year=2009|isbn=978-1-84882-296-2|pages=}}
* {{Cite book|last=Vedral|first=Vlatko|title=Decoding Reality: The Universe as Quantum Information|publisher=Oxford University Press|year=2010|isbn=978-0-19-923769-2|pages=}}
* Raymond W. Yeung, "[http://www.inc.cuhk.edu.hk/InformationTheory/index.html Information Theory] {{Wayback|url=http://www.inc.cuhk.edu.hk/InformationTheory/index.html |date=20191020035535 }}" ([[The Chinese University of Hong Kong]])
{{Литература крај}}

== Спољашње везе ==
{{Commons category-lat|Information theory}}
* {{SpringerEOM |title=Information |id=p/i051040}}
* Lambert F. L. (1999), "[http://jchemed.chem.wisc.edu/Journal/Issues/1999/Oct/abs1385.html Shuffled Cards, Messy Desks, and Disorderly Dorm Rooms - Examples of Entropy Increase? Nonsense!]", ''Journal of Chemical Education''
* [http://www.itsoc.org/ IEEE Information Theory Society] and [https://www.itsoc.org/resources/surveys ITSOC Monographs, Surveys, and Reviews] {{Wayback|url=https://www.itsoc.org/resources/surveys |date=20180612144016 }}

{{подножје|Информатика и рачунарство}}

[[Категорија:Математика]]
[[Категорија:Примењена математика]]
[[Категорија:Информатика]]
[[Категорија:Рачунарство]]
[[Категорија:Теорија информације|*]]
[[Категорија:Формалне науке]]