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!  
Simonyi Gábor, Információközlés és gráfelmélet Előadások, 2007/2008. tanév

Simonyi Gábor

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

című 2009. szeptember 29-ei előadását lejegyezte Lovas Lia Izabella



Bevezető feladat: Valaki kiválasztja egy sakktábla egy tetszőleges mezőjét. Legalább hány eldöntendő kérdésre van szükségünk ahhoz, hogy biztosan kitalálhassuk a gondolt mezőt?
A feladat megoldása igen egyszerű: 6 kérdés elég, ugyanis minden lépésben feloszthatjuk 2 egyenlő részre a még szóba jöhető mezőket, és rákérdezhetünk, hogy a keresett mező melyik csoportban található. Ilyen módon a 6. kérdés után egyetlen mező marad. Másrészt 6-nál kevesebb kérdés nem lehet elég: ha a még ki nem zárt mezőket következő kérdésünk két nem egyenlő csoportra bontja, akkor mindig lehetséges, hogy a kiválasztott mező a nagyobb elemszámú halmazba kerül.
Felvetődik: vajon akkor is 6-e a fenti feladat megoldása, ha előre meg kell adnunk az összes kérdésünket, és csak ezután kapjuk meg a válaszokat?
Megoldás: Igen. Képzeljük el, hogy minden mezőhöz hozzárendelünk egy 6 karakterből álló 0-1 sorozatot. Ezekből éppen különböző létezik, így a sakktábla minden mezejéhez különböző sorozatot rendelhetünk. Első kérdésünk az lehet, 1-es-e a mezőhöz tartozó sorozat első eleme, majd ugyanígy végigmehetünk a sorozat összes bitjén. A 6. kérdés után ismerni fogjuk a mezőhöz rendelt teljes sorozatot, tehát magát a mezőt is kitaláltuk.

A fenti egyszerű példában a sakktábla mezőihez 0-1 sorozatokat rendeltünk, lényegében kódoltuk őket. Egy-egy ilyen 0-kból és 1-esekből álló sorozatot a későbbiekben bináris kódszónak fogunk nevezni.

Az információelmélet születése Claude Shannon nevéhez fűződik, aki 1948-ban megjelent A Mathematical Theory of Communication című munkájában lefektette a matematika ezen új területének alapjait. A későbbi évek jelentős eredményei közül is számos az ő nevéhez fűződik. Ezen cikk keretein belül csak arra van lehetőségünk, hogy rövid ízelítőt adjunk az információelmélet alapfogalmaiból, illetve vázlatosan rávilágítsunk egy érdekes kapcsolatra a gráfelmélettel.

Folytatás a PDF fájlban:



Előadások, 2007/2008. tanév
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.