Теорија информације

Теорија информације је математичка дисциплина настала у 20. веку. Логаритамски израз за количину информације је предложио Хартли 1928. године, у свом раду "Пренос информације". Затим ју је 1948. поопштио амерички инжењер и математичар Клод Шенон, и нешто раније, руски математичар Андреј Николајевич Колмогоров. Исте 1948. године је амерички математичар Норберт Винер у свом раду "Кибернетика" изнео свој приступ количини информације система. Десило се да је Математичка теорија информације настала "одједном", малтене у неколико радова зачетника и да је у тим радовима "нацртан" оквир за целу будућу дисциплину. Покретачко место целог тог развоја је откриће, математичка дефиниција појма "количина података". И данас се сматра да је идеју за мерење количине информације први добио управо амерички инжењер Хартли 1928. године, али му историја математике не придаје велики значај можда због нејасноћа и (математички) непрецизних објашњења.

Информација

Математичко тврђење, односно математички исказ је израз, питање на које је могућ одговор Тачно, односно Нетачно. То је основа тзв. бинарне логике, дела математичке логике. Помоћу бинарне логике је могуће дефинисати сваки исказ поливалентне логике. Ове посљедње математичке логике, поред бинарних вредности: $\top ,\bot$, тј. тачно, нетачно, укључују читав спектар одговора "можда".

Хартлијева дефиниција

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

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

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

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

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

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

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

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

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

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

Колико бинарних питања треба поставити да би се сазнао један од 16 бројева? Одговор је 4. Уопште, колико бинарних питања треба поставити да би се сазнао један од $2^{n}$ бројева? Одговор је n.

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

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

$I(p)=-log_{2}P(n)=log_{2}n$.

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

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

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

Хартлијева информација, формула, служи само у случају мерења једнако вероватних исхода. Бар тако се чини на први поглед. Међутим, шта да радимо ако је случај сложенији. Када имамо различито вероватне исходе и хоћемо да меримо информацију за сваки од случајева. Показаћемо да се полазећи од Хартлијеве може доћи до дефиниције информације за сложеније случајеве, користећи већ познати појам математичке средње вредности. То је открио Клод Шенон у знаменитом раду "Математичка теорија комуникације", који је написао заједно са В. Вивером 1949. године.

Ако имамо шест куглица, по две у бојама: црвеној, плавој и белој. Рецимо да бирамо једну од шест, једнако вероватних, али тражен је један од одговора:

1. извучена куглица је бела - вероватноћа је 2/6;
2. извучена куглица није бела - вероватноћа је 4/6.

Хартлијева информација за први и други случај била би: $I_{1}=-log_{2}{\frac {2}{6}}$, односно $I_{2}=-log_{2}{\frac {4}{6}}$. Средња вредност, тј. математичко очекивање за ова два броја је: $I=-p_{1}I_{1}-p_{2}I_{2}$. Логаритми вероватноћа су негативни бројеви! Дакле

$I=-{\frac {2}{6}}log_{2}{\frac {2}{6}}-{\frac {4}{6}}log_{2}{\frac {4}{6}}$.

Општије, када имамо два исхода, вероватноћа $p_{1}$ и $p_{2}$, тада нам резултат случајног бирања доноси информацију:

$I=-p_{1}log_{2}p_{1}-p_{2}log_{2}p_{2}$.

Уопште, када имамо низ $n=2,3,4,...$ исхода, истих или различитих вероватноћа $p_{1},p_{2},...,p_{n}$, тада нам резултат случајног догађаја доноси информацију I која је средња вредност, тј. математичко очекивање, позитивних вредности логаритама вероватноћа. Према томе,

$I=-p_{1}log_{2}p_{1}-p_{2}log_{2}p_{2}-...-p_{n}log_{2}p_{n}$.

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

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

Норберт Винер је 1948. године дефинисао информацију у систему као меру његове организованости, док је неодређеност система мера његове неорганизованости.

Основни теорем

Питање математичке истинитости није ствар провере у лабораторији, експеримента, или веровања у сопствена чула. Математичка истина се не може доказивати проверавањем у тзв. пракси, али опет, ствари у математици нису тако мрачне како то може изгледати. Треба само ићи полако. Једном приликом је речено да када идемо полако кроз доказ неке математичке теореме, идемо корацима у које нико нормалан неће посумњати, али када дођемо до коначног теорема доћи ћемо до тврђења у које нико нормалан неће лако поверовати.