Kombinatorika

A kombinatorika tárgyából bizonyára készségszintű ismeretekkel rendelkeznek a diákok az érettségi-követelmények miatt:

• n elemet hányféleképpen lehet egymás mellé rendezni (permutálni)
• n elemből hányféleképpen lehet kiválasztani k elemet úgy, hogy a sorrend számít (variálni)
• n elemből hányféleképpen lehet kiválasztani k elemet úgy, hogy a sorrend nem számít (kombinálni)

 

A valószínűségszámítás kombinatorikusan megoldható részéhez elengedhetetlen az ismétléses és ismétlés nélküli esetek felismerése, és a binomiális együtthatók gyors kezelése. Az alábbi témák rövid összefoglalója és 8 vegyes feladat megoldása mellékelve van a hátrányok orvoslása céljából.

 

Permutációk

Variációk

Kombinációk

Pascal-háromszög

Kombinatorikai feladatok

Huffman-kódolás

Egyszerű informatikai alkalmazásként nézzük meg az egyik tömörítési eljárást, mely szerint a leggyakrabban előforduló bájtok rövidebb kódsorozatokkal helyettesíthetők.

 

Tömörítendő szöveg: „A KÖNYVEK NÉMA MESTEREK"

 

Állítsuk elő a szöveg karaktereinek gyakoriságát (egyébként rendezzük azokat a relatív gyakoriságuk szerint):

 

E	K	szóköz	M	N	A	Ö	Y	V	É	S	T	R
4	3	3	2	2	2	1	1	1	1	1	1	1

 

A gyakoriságokból -, mint levelekből elindulva- felépítünk egy bináris fát, melyben mindig a 2 legkisebb értékhez rendelünk közös szülőt, akinek a 2 gyerek értékének összege lesz az értéke. Az új szülő helyezkedjen el az ugyanolyan értékű csúcsok csoportjának az elején vagy a végén, de következetesen. Most az első módszert választjuk:

21. ábra

 

Ha odafigyelünk a kialakulás sorrendjére, nem kell minduntalan új fát rajzolnunk azért, hogy a részfák ne keresztezzék egymást az ábrán.

 

A kialakult fa gyökeréből elindulva a levelekig rendeljünk minden élhez 0-t vagy 1-et, attól függően, hogy az aktuális szülőtől az a jobb vagy a bal gyerek felé vezet.

22. ábra

 

Olvassuk ki a gyökértől a levelekig az élek sorozatát, és tegyük meg azt a levélhez tartozó karakter kódjának! Ezzel az egyes karakterek az előfordulásuk valószínűségével ellentett arányban lesznek egyre hosszabb jelsorozattal leírhatók a jelenlegi, azonosan hosszú jelsorozat helyett.

 

E	K	space	M	N	A	Ö	Y	V	É	S	T	R
000	010	100	0010	0011	0110	0111	1010	1011	1100	1101	1110	1111

 

Az eredeti szöveg 23x1 bájt = 23 bájt méretű,

a tömörített szöveg pedig: (4+3+3)x3 bit + (2+2+2)x4 bit + 7x4 bit = 82 bit méretű.

 

A tömörítés akkor is 82 bit méretűre hozná a szöveget, ha az összegzéskor kapott számérték az ugyanakkora értékek sorának nem a legelejére, hanem a legvégére kerülne. Abban az esetben előfordulhatnak 5-hosszú jelsorozatok is a kódtáblában -, a kódtábla elemei nagyobb szórással rendelkeznének - de annak a verziónak is megvan az előnye az információelmélet szerint.