Algoritmai2

Konspektas
 5
Microsoft Word 106 KB
13 puslapiai

Informacija
Informacija – žinios, vienų asmenų perduodamos kitiems raštu, žodžiu, masinės komunikacijos priemonėmis. Informacijos klasifikacija: elementarioji, genetinė, biologinė, semantinė, kompiuterinė (semantinės dalis skaitmeniniu pavidalu). Dėsniai: pokyčiai laike, nėra adityvumo (A+A= A), nėra komutatyvumo, turinys nepriklauso nuo saugojimo ir pateikimo (nebent skirsis suvokimo greitis).
Informacijos kiekis auga eksponentiškai lyginant su gamybos apimtimi. Informacija perduodama pranešimu, pranešimas siunčiamas signalu (kalba, raštas, šviesa, srovė, …). Signalas turės prasmę tik tada, jei jį sugeba priimti gavėjas. Signalas – priemonė pranešimams perduoti. Tokiu atveju priimantysis ką nors sužino. Vadinasi, informacija yra nežinojimo priešingybė. Informatyvumo daugiaprasmybės (mat. analizė). Nevienoda žmogaus jutimo organų priėmimo galia.
Kadangi informacija – neapibrėžtumo priešingybė, apie jos dydį būtų galima spręsti iš neapibrėžtumo sumažėjimo. Tarkime, informacijos šaltinis gali siųsti vieną iš vienodai svarbių ir vienodai tikėtinų pranešimų. Žinoma pranešimų aibė (gyvenimiškai – bus suprastas), bei žinoma, kad pranešimas siunčiamas. Tada neapibrėžtumo funkcija E (ji priklauso tik nuo N) yra monotoniškai didėjanti. Imtuvas priims pranešimą, neapibrėžtumas išnyks. Gauta informacija gali būti prilyginta buvusiam neapibrėžtumui. Jei galimas tik vienas pranešimas, tai jo turinys žinomas iki atsiuntimo ir nieko naujo neatneša. E(1) = 0.
Tegul siunčia du šaltiniai, kiekvienas turi po N skirtingų. Galimų porų skaičius N2. Du vienodi šaltiniai turi sukurti dvigubai didesnį neapibrėžtumą, tada E(N2) = 2E(N). Sprendinys – log. Jei pagrindas 2, gausime neapibrėžtumo matą log2N bitais. Natūriniu logaritmu išreikštas matas yra natas. Logaritminį matą nagrinėjo Hartley 19a trečiam dešimtmetyje, vėliau, po II pasaulinio karo bendresnį, entropiją, nagrinėjo Shanon savo ryšio teorijoje.
Gautų žinių kiekis priklauso nuo skaitytojo (patirtis, suvokimas), informacijos matas turi būti objektyvus. Pradinis matas – raidė, jos kodavimas kompiuteriu. Baitas, 2 baitai (Unicode). Analoginė ir diskrečioji informacija (8000*8000 taškų – žmogaus akis). Laidais efektyviau perduodama analoginė informaciją.
Entropija
Vienodai tikėtinų pranešimų atveju neapibrėžtumas buvo nusakytas E(N). Priimtas pranešimas panaikina neapibrėžtumą I(p) = E (1/p) = -log(p), (1)
čia p=1/n yra pranešimo tikimybė. Kuo mažiau tikėtinas pranešimas, tuo didesnė informacija.
Tarkime, vieno pranešimo tikimybė p, kito – q. tikimybė juos gauti paeiliui lygi pq, informacijos kiekis:
I(pq) = - log(pq) =...