(+36) 88 424 483

   8200 Veszprém, Egyetem utca 10. I. épület 9. emelet

   info@dcs.uni-pannon.hu

Témakiírások

A feladat leírása:
Egy n-ed rendű cirkuláris hármasrendszer egy olyan, 3-elemű halmazokból álló halmazrendszer, aminek az alaphalmaza (0,1,...,n-1), és ha egy (a,b,c) hármas benne van, akkor az összes (a+i,b+i,c+i) (modulo n) alakú hármas is benne van, ahol i=1,...,n-1. Pl. n=5-re egy ilyen az, amiben a halmazok (0,1,2), (1,2,3), (2,3,4), (3,4,0), (4,0,1). Az elforgatási invariancia miatt c=0 választásával egy ilyen rendszer a hozzá tartozó (a,b) párokkal is leírható, példánkban (a,b)=(3,4). Olyan programot kell elkészíteni, ami támogatja az alábbi műveleteket az ilyen rendszerekre:

  • beolvasás küldő fájlból
  • adott n és k számokhoz egy pontosan k darab (a,b) párral leírható rendszer véletlen generálása
  • adott n és k számokhoz a pontosan k darab (a,b) párral leírható rendszerek szisztematikus és redundanciamentes generálása
  • adott n-ed rendű és m-ed rendű (m<n) rendszerekhez annak eldöntése, hogy a kisebb beágyazható-e a nagyobb rendszerbe
  • feltételes generálás: olyan rendszerek előállítása, amikbe nem ágyazható be egy vagy több megadott kisebb részrendszer
  • adott rendszernek GUI-n keresztüli bővítése egy újabb (a,b) pár hozzáadásával; az így kapott rendszerbe történő beágyazhatóság eldöntése
  • adott rendszer vizuális megjelenítése
  • két rendszer egymás melletti megjelenítése
  • egy vagy több meghatározott elem törlése, az így kapott rendszer megjelenítése
  • a legkisebb olyan t érték meghatározása, amire létezik t szám (x(0),x(1),...,x(t-1) -- feltehető hogy x(0)=0) amik a rendszernek minden hármasából legalább egy elemet tartalmaznak
  • a legnagyobb olyan p érték meghatározása, amire létezik a (0,1,...,n-1) alaphalmaznak olyan partíciója, amelyben a rendszer minden hármasa vagy egyetlen osztályon belül, vagy két osztály egyesítésében helyezkedik el
  • a fenti t és p paraméterek összehasonlítása, törléssel módosított rendszerekben is

Témavezető: Tuza Zsolt

Elérhetőség: Ez az e-mail-cím a szpemrobotok elleni védelem alatt áll. Megtekintéséhez engedélyeznie kell a JavaScript használatát.