Az informatika részterületei • Információelmélet – információ, inf. tartalom mérése, inf. mennyiség
• Információ továbbítás (hírközlés) – jel, kódoláselmélet, hírközlőrendszerek, információ továbbítás sebessége
• Információ feldolgozás
Dr. Bacsó Zsolt
– logika, Boole-algebra
• Irányításelmélet (kibernetika) – szabályozás, vezérlés , automaták elmélete
• Alkalmazott informatika – játékelmélet, számítástechnika, telekomunikáció, biokibernetika, bioinformatika
Az információ • Norbert Wiener, 1948 • „kübernetész”, (κυβερνετησ, görög) hajókormányos – gépekben, élőlényekben, társadalomban megvalósuló vezérlési és kommunikációs folyamatokkal foglalkozó tudomány
• informatio, latin - képzés, felvilágosítás, kioktatás • mindennapi életben – tudásnyereség – ismeretanyag növekedése, bizonytalanság csökkenése
• filozófiai értelemben – az információ, az anyag és az energia mellett a világ harmadik alapvető eleme (fogalma, mennyisége)
1960-tól inkább: Informatika - (computer science) –az információ (főleg számítógépekkel és mobil telefonokkal történő) feldolgozásával és továbbításával foglalkozó tudomány
információ forrás
üzenet
információ vevő
Információtartalom Az információ és a véletlen kapcsolata • Az információ mennyiségének a számítása – üzenet célja: bizonytalanság eloszlatása – információtartalom: azon határozatlanság mértéke amit az üzenet megszüntet – véletlen eseményeken végzett kísérletek eredményének megjóslásában rejlő határozatlanság • kísérletek k számú egyenlően valószínű kimenetellel (pl. érmefeldobás, lottóhúzás) • α - az adott kísérlet • k - a kísérlet kimeneteleinek száma • H(α) - a határozatlanság mennyisége
Információelmélet Az információ és a véletlen kapcsolata • A kódelem (pl. betű) előfordulásának valószínűsége az üzenetben: – Annak a valószínűsége, hogy egy n elemű kódkészlet (ábécé) egy eleme (betűje) az üzenetben megjelenjen: p = 1/n (pl. bináris kód: 1/2 ; angol ábécé: 1/26) – Egy k hosszú kódelem sorozat (pl. k db betűből álló szó) valószínűsége az egyes elemek előfordulási valószínűségének szorzata: p = p1 p2 …pk
Információelmélet Az információ információ forrás
üzenet
információ vevő
• Az üzenet információt közvetít a forrástól a vevőhöz • Az üzenet kódjelek sorozataként szállítja az információt • A kódjelek a kódkészlet elemei (pl. latin ábécé, morzejelek, ASCII kód, zászlójel-ábécé)
Az információ és a véletlen kapcsolata • A kódelem (pl. betű) információtartalma az üzenetben: – Egy n elemű kódkészlet (ábécé) egy elemének (betűjének) a információtartalma: I = lb n = - lb p (Mely az adott betűnek az ábécén belül való megtalálásához szükséges bináris döntések számával egyenlő. Bináris kód esetén pl.: lb 2 = 1 ; angol ábécé esetén: lb 26 = 4.70) – Egy k hosszú kódelem sorozat (pl. k db betűből álló szó) információtartalma az egyes elemek információtartalmának az össze: I = I1 +I2 +…+Ik
A sakktáblán elhelyezett bábu helyzetének megkeresése eldöntendő kérdésekre adott igen-nem válaszok alapján (bináris döntés) 1: 1-4 sorokban van? nem → 5-8 sorban. 2: A-D oszlopokban van? nem → E-H oszlopokban. 3: E-F oszlopokban van? nem → G-H oszlopokban. 4: 7-8 sorban van? nem → 5-6 sorban.
•Kockánként kérdezve: 64 •Sorokra és oszlopokra egyenként kérdezve 16 kérdésre lett volna szükségünk! •26 = 64
log2 64 = 6 bit
5: H oszlopokban van? nem → a G oszlopban.
Információtartalom • k számú egyenlően valószínű kimenetellel rendelkező α kísérlet bekövetkezésével kapcsolatos határozatlanság mértéke definíció szerint:
H ( α ) = loga k a kísérlet kimenetelei számának logaritmusa
6: 5. sorban van? igen → a G5-ön van.
Az információtartalom tulajdonságai mely tulajdonságokkal a logaritmus függvény rendelkezik •
Biztos vagy determinisztikus esemény (I) határozatlansága, k=1
•
Információ mennyiség mértékegysége a bit:
H ( I )= 0 f( 1 ) = 0
Kísérletek kimenetelének a H( α ) < H( β ) számával arányosan növekszik a határozatlanság, - monoton növekvő f ( n ) < f ( m) k1=n < k2=m log a ( x ) Két kísérlet együttes bekövetkezésésének a határozatlansága
Információtartalom
f ( x ) = log a ( x )
loga ( 1 ) = 0 •
• α - az adott kísérlet • k - a kísérlet kimeneteleinek száma • H(α) - a határozatlanság mennyisége • az a alap megválasztása megállapodás kérdése
H ( α ) + H( β ) f (n) + f(m) = f (n ⋅ m)
log a ( n ⋅ m) = log a n + log a m
– Két egyenlően valószínű kimenetellel rendelkező esemény egy kimenetelének a megadásához rendelhető információ tartalom 1 bit. – Egy kételemű ábécé azonos kiválasztási valószínűséggel rendelkező elemei közül az egyik kibocsátása hordoz 1 bit információt. – Egy eldöntendő kérdésre adott válasz hírértéke 1 bit, ha mind az igen mind a nem válasznak azonos a valószínűsége.
H=
2
k=
2
=
=
binary unit or basic information unit
Információtartalom és a valószínűség
Minden kísérlet közül, amelynek k számú kimenetele van, a leghatározatlanabb az, amelynél a lehetséges kimenetelek egyenlő valószínűek.
Azaz:
I
p
I (α ) = −
k i =1
pi log pi
(Boltzmann: S = k lnw )
H (α ) = − log p
Az információ a valószínűség negatív logaritmusa. Claud Elwood Shannon (1916)
•
Tekintsünk egy k = 2 kétkimenetelű (Bernoulli) α eseményt, ahol P(k1) = p, P(k2) = q, és p+q=1, ekkor I(α) = - p lb p - q lb q, azaz I(α) = p lb (1/p) + (1-p) lb (1/(1-p))
Kísérlet entrópiája (forrásentrópia,átlagos információtartam), mely egyenlő a kísérlet kimenetelének a határozatlanságával.
1.0
átlagos információ tartalom (H)
H (α ) = log k , ahol k = 1/p = p-1
0.8
0.6
0.4
0.2
0.0 0.0
0.2
0.4
0.6
0.8
1.0
valószínűség (p)
Shannon-függvény
Információtartalom számítása
I • Kétkimenetelű, egyformán valószínű Bernoulli-esemény bekövetkezését jelző hír információtartalma: • A sakkbábú pozícióját jellemző információtartalom:
DNS információ tartalma
p 1 k = 2 ; p1 = p 2 = 2 I = −lb2 = 1 bit
k = 64 ;
p1 = p 2 = ... = p 64 =
I = −lb64 = −lb2 6 = 6 bit
• Weber-Fechner pszichofizikai törvény:
S = konstans × log
I I0
1 64
• Számítsuk ki egy 105 bp-ból álló DNS lánc információ tartalmát: • k = 4 féle bázis n=100 000 helyen, így az összes lehetséges egyenlő valószínűségű sorrend V=kn (ismétléses variáció), V=4100000 • I = logV = log 4100000 = 105 log 4 = 105 lb22 bit = 2 × 105 bit • 500 000 Å x 20 Å térben
• 1 kromoszóma 5 x 109 bázispárja 10 x 109 bit • humán genom (23 krom. pár) 5 x 1011 bit (~60 Gbyte)
Információ továbbítás (hírközlés)
Fehérjék információ tartalma • Hírközlő renszerek felépítése
• Számítsuk ki egy 103 aminosavból álló átlagos fehérje információ tartalmát: • k = 20 féle aminosav n=1000 helyen, így az összes lehetséges egyenlő valószínűségű sorrend V=kn (ismétléses variáció), V=201000 ≅ 101300 • I = lbV = lb 201000 ≅ lb 101300 ≅ 4 × 103 bit
Az emberi érzékszervek információ feldolgozó kapacitása
Információ továbbítás (hírközlés)
Érzékszerv Stimulus Hely
Receptorszám
Látás
Hallás
Tapintás
Hőérzés
Szaglás
Ízlelés
elektromágneses
mechanikus
mechanikus
hőmérséklet különbség
kémiai
kémiai
retina
membrana basilaris
bőr
bőr
orrüreg
nyelv szájpadlás
107 csap 108 pálcika
1-3×104
5×105 nyomás 3×105 fájdalom
1×104
1×107
1×107
• emberi beszéd • rádió
meleg
3×105 hideg
• fehérje szintézis
Idegrostok száma
1-2×106
1-2×104
1×104
1×104
2×103
2×103
Információ kapacitás (bit)
3×106
2-5×104
2×105
2×103
10-100
10
– sejtmagban a transzkripció: kódolás, mRNS: információ szállítás, citoplazmában a riboszómán: dekódolás
Információ továbbítás (hírközlés) • kódolás
• A jelek és az irányított rendszer kapcsolata
– információ átalakítása fizikailag továbbítható jelekké, jelsorozatokká (pl. kodon Î aminosav)
• jelek – információ megjelenítésére szolgáló jelkészlet elemei (pl. betűk, purin és pirimidin bázisok, aminosavak) • analóg – térben és időben, alsó és felső érték között folytonosak (pl. hang)
• digitális – jelek nagysága csak adott véges számú értéket vehet fel (pl. betűk, számok)
Fehérjeszintézis kódolása – n = 4 bázis (4-es számrendszer jegyei) k=20 aminosav (20 jelszint) I = log420 ≅ 2.161 db jel szükséges felfelé kerekítve triplet, így viszont I = 43 = 64 aminosav kódolható, azaz
• Redundáns (bőbeszédű) a kód • Mértéke:
- H R = H max H max
R=
3 - 2,161 = 28 % 3
információvesztés csökkenését eredményezi
• Nyílt hatáslánc
Szabályozás • Zárt hatáslánc
– Hiba Jel = Ki Jel - Be Jel – Jelvisszacsatolás - feedback
• Visszacsatolás – negatív – pozitív