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) = I(p) + I(q), o tai atitinka intuityvų reikalavimą, kad nepriklausomų šaltinių informaciją reikia sumuoti.
Kadangi pranešimas priėmėjo požiūriu atsitiktinai išrinktas, tai gaunamos informacijos kiekis taip pat atsitiktinis, su tikimybe pi gaunam –log(pi) informacijos. Gaunamos informacijos kiekis, išreiškiantis šaltinio neapibrėžtumą (vadinamą entropija) išreiškiamas formule
E(P) = , P = (p1, … pN)
Panašiai ir statistinėje fizikoje. Yra ir kitų apibrėžimų. Atskiru atveju, kai visos tikimybės 1/N, gauname entropiją išreiškiamą log(N). Intuityviai didžiausia – kai tikimybės lygios – entropija maksimali. Vadinasi, entropija intuityviai sutampa su neapibrėžtumu.
Dviejų pranešimų su tikimybe ½ entropija lygi 1. Vadinasi, vienas bitas – iš semaforo. Šviesoforo (049 002 049) lygus 1,12 bito (skaičiuojama dvejetainių logaritmų suma) – įrodykite.
Max = 3, kai tikimybės vienodos.
Perdavimo trikdžiai. Statistinis nagrinėjimas. Iš statistikos – informacijos suspaudimo būdai.
Algoritmai
783-850 metais (dabartinė Chiva Uzbekijoje) gyveno Abu Jafar Mohamed ibn Musa al Chorezmi (Iš Chorezmo). Jis parašė veikalą Kitab Al Džebr val Mukabala – atstatymų ir perstatymų knyga, iš čia algebra.
O dar parašė traktatą apie indiškąją (arabiškąją) skaičiavimo sistemą, veiksmus stulpeliu.
Al Chorizmi – algorism – algoritmas. Pradžioje – veiksmai su dešimtainiais skaičiais, vėliau ir bet kurie.
Grįžkim prie informatikos problemų. Apytiksliai kalbant, spręsti tokias problemas mes pradedame nuo duotos informacijos, duomenų (duotų ar įvestų) ir stengiamės iš jų sukurti rezultatą, kuris pageidaujamu būdu susijęs su pradiniais duomenimis. Panagrinėkime paprastus pavyzdžius:
1. 2 sveikų skaičių daugyba: Duomenys – 2 natūriniai skaičiai, rezultatas sveikas skaičius, šių dviejų sandauga.
2. 2 lygčių sistema. Duomenys 6 realūs, a11, a12, a21, a22, b1, b2, sąlyga– diskriminantas ≠0. Rez 2 skaičiai x1 ir x2 tokie, kad a11x1+ a12x2=b1 ir a21x1+ a22x2=b2 .
3. Rūšiavimas. Duomenys simbolių eilučių masyvas, rezultatas- irgi tik žodyno tvarka.
Matosi, kad iš duomenų gaunam rezultatą. Atidžiau, pastebim, kad sprendžiam ne vieną problemą, o jų klasę, mes ieškom tokių sprendimo metodų, kurie veiks vienodai su visais šios klasės uždaviniais. Yra daugybė atskirų uždavinių, kuriuos galima būtų išspręsti daug gražiau, protingiau, jei nagrinėtume tik specialius duomenų atvejus. Beje, dažnai tokie atvejai būna įdomūs, naudingi mąstymo treniruotei. Tačiau kartu svarbu yra rasti bendrus sisteminius sprendimo metodus, kurie duos pageidaujamą
rezultatą visiems teisingiems duomenims. Tokį bendrą sisteminį metodą dažnai vadiname algoritmu.
Mes (jūs), būdami kompiuterių specialistais algoritmą dažnai tapatiname su programos sąvoka, tačiau terminas plačiau pradėtas naudoti 1930 metais, prieš kompiuterį.
Prieš pradedant nagrinėti kokį nors objektą, jį reikia apibrėžti. Kalbant apie algoritmus, dažnai vartojama artima programos sąvoka. Kai kurie vadovėliai šias sąvokas interpretuoja kaip abstraktaus ir konkretaus priešybę: algoritmas – griežtai ir vienareikšmiškai apibrėžta veiksmų seka, o programa – algoritmo realizavimas kuria nors programavimo kalba. Tačiau toks algoritmo apibrėžimas ne visai korektiškas, kadangi griežtumo ir vienareikšmiškumo reikalavimai patys savaime nėra vienareikšmiai. Kita vertus, programavimo kalba užrašyta ‘programa’ atitinka griežtumo ir vienareikšmiškumo reikalavimus, keliamus algoritmui. Programavimo kalbos – vienas iš būdų algoritmams užrašyti. Nors kai kuriais atvejais algoritmą lengva suformuluoti ir bendrine kalba, tačiau teoriniams tyrimams reikia specialių algoritmų užrašymo formalizmų, kaip pavyzdžiui: RAM, Turing’o ir Post’o mašinos, Markovo algoritmai, lambda skaičiavimas.
Bandykim pradžiai intuityviai aptarti algoritmo sąvoką. Turbūt galvojam, kad algoritmas turėtų būti trumpas ir aiškus problemos sprendimo metodo aprašymas, o pasąmonėje dar jaučiam, kad jis turėtų būti tinkamas mechaniniams įrenginiams (ką reiškia – griežtumas, minimalus pasirinkimų sk.). Tada plačiau galėtume sakyti, kad algoritmas turėtų būti aiškių suprantamai aprašytų žingsnių seka, reikalinga problemai išspręsti, o pasąmonėje vėl jusime, kad ta seka turi būti baigtinė (o dar baigtinė – lyginant su žmogaus gyvenimo trukmės matavimo vienetais). Kadangi įsivaizdavome, kad ta seka galėtų kažkokiu būdu būti vykdoma mechaniškai, galėtume reikalauti, kad nei vienas žingsnis nepriklausytų nuo subjektyvių sprendimų, intuicijos, kūrybiškumo.