(+36) 88 424 483

   Egyetem str. 10, Building I, 9th floor, Veszprém H-8200

  

Thesis

A feladat egy elméleti kutatásokat segítő számítógépes program elkészítése Linux vagy Windows operációs rendszerre.

A feladat elvégzéséhez mindkét operációs rendszerre egy-egy csoport jelentkezhet.

Az angol szakirodalomban a "monostar" egy H halmazrendszernek olyan részrendszerét jelenti, amelynek metszete pontosan egy elem, és ha ezeknek a halmazoknak az uniójából az egyetlen közös elemet elhagyjuk, akkor az így kapott halmaz a H-nak egyetlen tagját sem tartalmazza részhalmazként.

Olyan halmazrendszereket vizsgálunk, amelyekben minden halmaznak pontosan 3 eleme van, és cirkuláris szimmetriával rendelkezik. Legyen az alaphalmaz elemeinek száma N. Az elemeket a 0,1,2,...,N-1 számokkal jelöljük. Cirkuláris szimmetria azt jelenti, hogy ha egy {a,b,c} hármas tagja H-nak, akkor minden i-re az {a+i,b+i,c+i} hármas szintén tagja (ahol az összeadást modulo N értjük). Ilyen rendszerek közül azokat kell szisztematikusan előállítani, amelyekben nincs monostar.

A cirkuláris szimmetria miatt egy hármas általában N hármast generál, pl. N=6 esetén a {0,1,3} hármas ugyanakkor van jelen a rendszerben, amikor az {1,2,4}, {2,3,5}, {3,4,0}, {4,5,1}, {5,0,2} hármasok is. Másrészt ha N osztható 3-mal, akkor van egy N/3 méretű csoport is, mégpedig {0,2,4} és {1,3,5} ha N=6. Az első típusú csoportnak 3 tagja tartalmazza a 0 elemet, a második típusúnak 1 tagja. Minden csoportból ki tudunk jelölni egy reprezentáló hármast. Például N=6 esetén -- az összes lehetséges csoportot figyelembe véve -- ezek a következők: {0,1,2}, {0,1,3}, {0,1,4}, {0,2,4}. (Például a {0,1,5} azért nincs itt, mert azt már generálja a {0,1,2}.) Ily módon 15 rendszer állítható elő, bár ezek nem mind tekinthetők lényegesen különbözőnek. (Pl. a {0,1,3} és a {0,1,4} által előállított csoportok egymásnak tükörképei.)

A feladat egy olyan, felhasználóbarát GUI-val rendelkező program elkészítése, amely megvalósítja a következőket:
- adott N-hez felsorolja a generáláshoz tekintetbe vehető hármasokat,
- meghatározza és grafikusan szemlélteti, hogy amennyiben egy hármas monostar-t is tartalmazó csoportot generál, ahhoz melyek azok a hármasok, amelyeket hozzávéve az eredetileg ott lévő monostar megszűnik,
- generáló hármasoknak minden megadott halmazáról el tudja dönteni, hogy a hozzájuk tartozó rendszerben van-e monostar,
- automatizált módon szisztematikusan előállítja azokat a kombinációkat, amelyekben nincs monostar,
- ezeket a kombinációkat megadott formátumú .txt fájlban kiírja,
- futás közben folyamatosan ad információt arról, hogy az eljárás hol tart.