Informatikai és Hírközlési Minisztérium Oktatási Minisztérium Apache Php Mysql Fazekas Mihály Gyakorlóiskola
  Bejelentkezás
Üdvözöljük a Matematika portálon!  
Beharangozó: Simonyi Gábor: Információközlés és gráfelmélet

Simonyi Gábor

Információközlés és gráfelmélet

2009. szeptember 29.



Hogyan kell ügyesen barkochbázni? Legalább hány eldöntendő kérdést kell például ahhoz feltennünk, hogy a válaszokból ki tudjuk találni a 8-szor 8-as sakktábla egyik mezőjét, amire játszótársunk gondolt? Változik-e ez a minimális szám, ha a kérdéseket előre, a válaszok ismerete nélkül kell feltennünk?

A dolog nyitja, ha észrevesszük, hogy a válaszokat megfeleltethetjük kétféle jelből, mondjuk 0-kból és 1-esekből álló sorozatoknak. Az így kapott sorozatok kódolják a gondolt mezőt, minket pedig az érdekel, hogy mennyire hosszú kódra van feltétlenül szükség.

Akkor is kódolunk, ha írunk vagy beszélünk. Egy beszélőtől is elvárjuk, hogy lehetőség szerint röviden fejezze ki magát. De ha a rádióban bemondanak egy telefonszámot, amit föl szeretnénk írni, akkor azért nem bánjuk, ha megismétlik, ez csökkenti az esélyét, hogy rosszul jegyezzük le.

Hogyan lesz mindebből matematikai elmélet, amiben az információ mennyiségét számszerűen is kifejezhetjük? Részben erről szól az előadás. Meg arról is, hogy hogyan kerülhetnek ide a gráfok. Erre nevezetes példa az alábbi.

Tegyük fel, hogy minden közlendőnket a p, n, u, v, b betűkkel, illetve ezek sorozataival kell kódolnunk. Kézírásunk olyan, hogy a fenti felsorolásban minden leírt betűnk nézhető bármelyik szomszédjának is, emellett a szélen álló p akár b-nek, a b pedig p-nek is. Vagyis az öt betűt egy gráf pontjainak tekintve és az összekeverhetőket összekötve egy öt hosszúságú kört kapunk.

Tegyük fel azt is, hogy az összekötetlen párok viszont soha nem téveszthetők össze. Ekkor, ha egyetlen betű használható valamilyen üzenet átadásához, és azt akarjuk, hogy az biztosan helyesen legyen értelmezhető, akkor legfeljebb kétféle üzenetünk lehet, hiszen nincsen három betűnk, amik páronként összekötetlenek volnának a gráfunkban. Hányféle kétbetűs üzenetünk lehet, amik biztosan nem keverhetők össze? Kétszer annyi, mint előbb, azaz négy, vagy akár több is? Igyekszem majd vázolni, milyen messzire vezetett ez az ártatlannak látszó kérdés.


Kiemelt támogatónk 2006-ban:
Tigra Computer
Támogatóink 2003-ban:
Oktatási Minisztérium
Powered by:
Apache + Php + Mysql
Kapcsolat
hraskoa@fazekas.hu
Copyright © 2004-2010 Fazekas Mihály Fővárosi Gyakorló Általános Iskola és Gimnázium. Served by pingvin.