BinSYS Projekt

 

Eötvös Lóránd Tudományegyetem,

Komputeralgebra Tanszék

 

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.



Home | My Account | Message Boards


Copyright © 2017 SZTAKI Desktop Grid