Universitatea Babeş-Bolyai Cluj-Napoca
Facultatea de Matematică şi Informatică
Ciclul de studii: Licenţă
Domeniul: Matematică
Programul de studii: Matematică informatică - linia de studiu maghiară
Limba de predare: Maghiară

SYLLABUS

I. Általános adatok
Kód	Tantárgy neve	
MMP0006	Információelmélet	

Félév	Órák: C+S+L+P	Kategória	Típus	
5	2+2+0+0	szaktárgy	választható	

II. Foállásban az  Egyetem  oktatói
Név	Tudományos	Oktatói	Tanszék	Tevékenység	
	fokozat	státus		E	Sz	L	
BODÓ Zalán Péter	Dr. 	Lect.	Magyar Matematika és Informatika	*	*		
CSATÓ Lehel	Dr.	Conf.	Magyar Matematika és Informatika	*			

Társult oktatók
Név	Tudományos	Intézmény	Állás	Tevékenység 	
	fokozat		típusa	E	Sz	L	

III. A tantárgy célkitűzései
A tantárgy célja a bevezetés a modern információelméletbe, a fontosabb információ-elméleti fogalmak elsajátítása. A cél az entrópia, a mutuális információ a csatornakapacitás fogalmainak használata a komplexitás, az adattömörítés fogalmainak a leírásakor. Az előadások során a hangsúly a lehetséges gyakorlati alkalmazásokon lesz, valamint bemutatjuk az információelmélet kapcsolatát a statisztikával és a valószínség-számítással. A gyakorlati részekben bemutatjuk az információelmélet alkalmazásait a sűrítési és tömörítési feladatoknál, a hibajavító kódoknál, illetve bemutatjuk a CDMA-típusú kódokat. Alkalmazzuk a maximum entrópia elvét feladatok megoldásánál. Bemutatjuk a Kolmogorov-féle programkomplexitást, illetve a komplexitás mérésének különböző módjait.	

IV. A tantárgy tartalma
A félév során megismerkedünk az információelmélet történeti hátterével, Shannon munkásságával. Példákon keresztül illusztráljuk az információelmélet mint tantárgy illetve az információelméleti fogalmak ismeretének a fontosságát.
Az előadások során kapcsolatokat teremtünk a valószínűség-számítás és statisztika valamint az információelmélet diszciplínái között, röviden ismételjük a fontosabb valószínűségszámitási alapfogalmakat.
Bemutatjuk a Shannon által bevezetett entrópia-fogalmat, annak a tulajdonságait, a relatív entrópiát és annak mérését. Az entrópia-egyenlőtlenségek tanulmányozása által betekintést nyerünk az entrópiával rendelkező rendszerek dinamikájába. 
Definiáljuk az információt, mint matematikai mennyiséget, az információ-forrást, illetve osztályozzuk a jellemzők szerint. 
A modern információelmélet egyik legismertebb alkalmazását, a csatornakódolást definiáljuk, alsó korlátot adunk a kód hosszára, majd különböző kódokat mutatunk be, azok jellemzőivel: Huffman-kód, Shannon-kód, univerzális kódok.
Bemutatjuk a veszteséges tömörítést és alkalmazzuk azt képekben használt információk tömörítésére. A modern információelmélet fontos alkalmazását, a hibajavító kódolást is bemutatjuk, tanulmányozva annak tulajdonságait.
A maximum-entrópia elvének alkalmazása után a Kolmogorov-féle komplexitást definiáljuk, majd a különböző alkalmazási területek bemutatása után ismétléssel zárjuk a félévet.	

V. Könyvészet
[1] Blaga, P. Calculul probabilităţilor şi statistică matematică. Vol. II. Curs şi culegere de probleme, UBB, Cluj-Napoca, 1994.
[2] Cover T.M, Thomas J.A. Elements of Information Theory. 2nd edition, Wiley-Interscience, 2006.
[3] Györfi L., Győri S., Vajda I. Információ- és kódelmélet, Typotex Kiadó, 2002.
[4] MacKay D. Information Theory, Inference and Learning Algorithms. Cambridge University Press, 2003.
[5] Murgan A. T. Principiile teoriei Informaţiei în ingineria informaţiei şi a comunicaţiilor. Editura Academiei Române, Bucureşti, 1998.	

VI. Az oktatói tevékenység heti tematikája
Előadások (E)
1.	Történeti háttér
Bemutatjuk az információelmélet kialakulásának a folyamatát, a Shannon által bevezetett fogalmak alapjaira épülő tudomány- és iparágakat. Hangsúlyt fektetünk a különböző alkalmazási területekre.
2.	Bevezető fogalmak, ismétlés
Halmazelméleti alapfogalmak. A valószínűségi változók, változó-vektorok. Eloszlás- és sűrűségfüggvények. Feltételes eloszlások fogalma. Valószínűségi változók és feltételes valószínűségi változók jellemzői: átlag, szórás, deviancia, korreláció, korrelációs együttható.
3.	Entrópia
Entrópia és annak tulajdonságai. Relatív entrópia. Példák és gyakorlatok az entrópia mérésére.
Példák a relatív entrópia mérésére.
4.	Entrópia-egyenlőtlenségek
Jensen egyenlőtlenség, következmények. Log-szum egyenlőtlenség. Fano-egyenlőtlenség.
5.	Információ fogalma
Információ mérése, Shannon-féle információ-mérték. Diszkrét információ-források, ergodikus és nem-ergodikus források.
6.	Veszteségmentes adattömörítések
Példák kódokra, Kraft-egyenlőtlenség. Optimális kódok, optimális kódhossz korlátai, híres egyenlőtlenségek
7.	Huffman és Shannon-kódok
Huffman kódok. Huffman kódok optimalitása, a Shannon-Fano kódolás.
8.	Aritmetikai és univerzális kódolás
Az aritmetikai kódolás illetve az univerzális kódolási algoritmusok (LZ77, LZ78 és LZW) bemutatása. Feladatok az algoritmusokkal.
9.	Hibajavító kódolás
A különböző hibajavító kódolási algoritmusok bemutatása alkalmazásokon keresztül: alapfogalmak, Hamming-távolság, kódtávolság, hibajelzés, hibajavítás, törléses hiba, Singleton-korlát, lineáris kódok, bináris lineáris kódok, generátor és paritásmátrix, szindróma-dekódolás
10.	Hibajavító kódolás II. 
Reed-Solomon-kódok, hibajavító kódok a gépi tanulásban
11.	Veszteséges tömörítési algoritmusok
Kvantálás, prediktív kódolás, Jayant-kvantáló. 
12.	Képek tömörítése
SVD alapú képtömörítés, fraktál alapú képtömörítés, JPEG
13.	Maximum-entrópia elve
A maximum-entrópia elve. Gyakorlatok oldása a max-ent princípium alapján.
14.	Összefoglalás, ismétlés

Szemináriumok (Sz)
1-2. Valószínűségszámítási feladatok, feladatok az entrópiával 
3-4. Kölcsönös (mutuális) információ
5-6. Veszteségmentes adattömörítések: Huffman, Shannon-Fano, aritmetikai, univerzális kódolás
7-8. Hibajavító kódolás: generátor és paritásmátrixok, kódtávolságok
9-10. Hibajavító kódolás: szindróma dekódolás
11-12. Veszteséges tömörítések: prediktív kódolás, Jayant-kvantáló
13-14. Maximum-entrópia feladatok	

VII. Alkalmazott didaktikai módszerek
Kifejtés módszere, a problematizálás módszere, rákérdezés és rávezetés, egyéni feladatok megoldására való ösztönzés. Használunk a megfelelő programnyelvekkel felszerelt számítógépeket gyakorlásra; vetítőt az előadásokhoz kivetítéséhez. Az előadások tematikája, a laborfeladatok és a kötelező olvasmányok letölthető anyaga közös gyűjtőhelye:
http://canvas.infooktatas.ro/courses/24	

VIII. Értékelés
A félév végi jegy írásbeli vizsga eredménye.
A félév során lehetőség van egyéni, illetve legtöbb két-három főt tartalmazó projektek bemutatására, valamint (gyakorlati) pluszfeladatok bemutatására; ezek képezik az évközi tevékenységet.
Az évközi tevékenység a vizsgapontok 40%-át teszi ki, az írásbeli a maradék 60%-ot.	

IX. Kiegészítő könyvészet
[6] Gray R.M. Entropy and Information Theory. Springer, 1999.
[7] Chen P., Alajajiz F. Lecture Notes on Information Theory. Department of Mathematics & Statistics, Queen’s University, Kingston, Canada.
[8] Yeung R.W. A First Course in Information Theory. Springer 2002.	

	Dékán,						Tanszékvezető,

	Dátum,						Előadás felelőse,
	2011.12.17.						Lect. Dr.  BODÓ Zalán Péter