Projektleírás

Célok

A projekt célja 11 dimenzióig meghatározni az összes általánosított bináris számrendszert. Az alábbiakban röviden ismertetjük a kapcsolódó fogalmakat, és néhány lehetséges alkalmazást.

Alapfogalmak

A hagyományos számrendszerfogalom segítségével nemnegatív egész számokra véges felírást adhatunk a következő alakban (n egynél nagyobb egész):

Ha n = 2, akkor bináris számrendszerről beszélünk. Ahhoz, hogy ilyenkor negatív számokat is elő tudjunk állítani, szükségünk van egy előjel használatára. Ha a számrendszer alapja negatív szám is lehet, ez elkerülhető, például minden egész szám felírható véges összegként

alakban. Ez az előjel nélküli változat általánosítható a racionális számoknál bővebb számtestek egész számaira is. Például az x+yi alakú komplex számok (x,y egész), vagyis a Gauss-egészek esetében választhatjuk alapszámnak a (-1+i) számot, és ekkor

minden Gauss-egész felírható

alakban. A legáltalánosabb változatban lineáris algebrai eszközökkel definiálható a számrendszer fogalma. Ekkor alapszám helyett alapmátrixról beszélünk, a számjegyek pedig vektorok. Az előző példa ekvivalens átfogalmazása a következő: minden kétdimenziós egész vektor előállítható véges alakban

összegként, ahol

, és .

Ha az M mátrix determinánsa ±2, akkor bináris rendszerről beszélünk. Ez esetben csak két számjegy van, melyek közül egyik a nullvektor. Ez azt jelenti, hogy számrendszerség esetén minden egész vektor felírásához elegendő véges sok 1 és 0 jegy, vagyis bináris alakban kódolhatjuk a vektortér egészeit.

Mindezidáig nem ismert, hogy mely M mátrixok szolgálnak általánosított bináris számrendszerek alapjául. Ismertek szükséges feltételek, és elégségesek is, de a köztük levő távolság nagy, és a feltételekkel nem jellemezhető mátrixokról nem sokat tudni. Belátható viszont, hogy rögzített dimenzióban lényegében véges sok jó mátrix található.

Várható eredmények

A program célja minél több (bizonyos dimenzióig az összes) bináris számrendszer meghatározása. Ebben a nehézséget az okozza, hogy a szükséges feltételt teljesítő lehetséges számrendszer alapszámok (mátrixok) száma a dimenzió növekedésével robbanásszerűen nő. Jelenleg a matematikai háttér és a számítási sebesség a 11 dimenziós eset vizsgálatát teszi lehetővé, és mivel a feladat CPU igénye nagy (a feltétel ellenőrzése lebegőpontos számítást igényel), valamilyen elosztott architektúra alkalmazása nélkülözhetetlen. A program inputja a hatalmas, de véges állapottér egy darabkája, outputja pedig a bejárt állapottéren talált, bizonyos szükséges feltételeknek eleget tevő mátrixok (egészen pontosan azok karakterisztikus polinomjai) halmaza, amelyeket később tovább rostálva kapjuk az adott dimenzió általánosított bináris számrendszereit.

A számrendszerek listájának ismeretében információelméleti vizsgálatokra kerül sor. A vektortér egy egész vektorát hagyományos módon és az általánosított bináris számrendszerben felírva a két alak nagymértékben különbözhet hosszban, és az egymáshoz közeli vektorok bináris alakja is nagyon eltérő lehet. Ennek fényében a számrendszerek adattömörítésben, kódolásban illetve kriptográfiában történő alkalmazhatóságát fogjuk vizsgálni.

Hasonlóan a hagyományos számrendszerekhez, ahol a törtszámoknak végtelen „tizedes” törtek felelnek meg, itt is felírhatjuk a vektortér nem egész koordinátájú pontjait végtelen alakban. A 0 „egész részű” vektorok H alaphalmazának határa általában tört dimenziós alakzatot, ún. fraktált alkot. A program kimenetét az alaphalmaz vizsgálatára is fel lehet használni. Itt elsősorban H topológiai jellemzőinek (dimenzió, összefüggőség, térlefedés) vizsgálatára gondolunk. Az alábbi kép a fenti M mátrixhoz tartozó H alaphalmazt ábrázolja.

Végül, de nem utolsó sorban, adott dimenziókban az összes bináris számrendszer ismerete a témakör matematikájának mélyebb megértéséhez is hozzájárulhat.

Látogasson el a projekt ELTE által karbantartott honlapjára.