Szakdolgozat- és TDK-témák

Az alábbi témák a LEMON programkönyvtár fejlesztéséhez, illetve alkalmazásához kapcsolódnak. A lista korántsem teljes, az érdeklődőknek személyre szabott feladatokat, témákat tudunk összeállítani BSc/MSc szakdolgozathoz és TDK-hoz egyaránt.

• Heurisztikus útvonalkeresés

Heurisztikus algoritmusok implementálása legrövidebb utak keresésére (kétirányú keresés, A* algoritmus stb.).

• Tranzitív lezárt

Hatékony algoritmus implementálása egy gráf tranzitív lezártjának előállítására.

• Gráfok direkt szorzata

Gráfok direkt szorzatát megvalósító dinamikus adatstruktúra implementálása.

• Élgráf adatstruktúra

Egy irányítatlan gráf élgráfját megvalósító dinamikus adatstruktúra implementálása.

• Különböző gráfformátumok kezelése

Gráfok és hozzájuk kapcsolódó adatok beolvasása és kiírása különböző fájlformátumokban.

• Irányítatlan gráfok k-élösszefüggővé irányítása

Különböző irányítási algoritmusok implementálása és összehasonlítása.

• Irányított gráf erősen összefüggővé tétele

Egy algoritmus implementálása, amely egy irányított gráfot minimális számú él összehúzásával erősen összefüggővé tesz.

• pyLemon modul fejlesztése

A LEMON használatának lehetővé tétele a Python programozási nyelvből.

• Párhuzamos gráfalgoritmusok

Különböző gráfelméleti, hálózattervezési feladatokra párhuzamos (többszálú) algoritmusok implementálása és összehasonlítása.

• Steiner-fa keresése

Hatékony közelítő és heurisztikus algoritmusok implementálása és összehasonlítása a Steiner-fa feladatra.

• Steiner-hálózat keresése

Lineáris programozást használó 2-approximációs algoritmus implementálása irányítatlan gráfban Steiner-hálózat keresésére.

• Fák pakolása, fedés fákkal

Irányítatlan gráfban éldiszjunkt fák keresése (pakolás), gráf éleinek fedése fákkal (fedés).

• Nagy hálózatok vizsgálata

Különböző területekről származó nagyméretű hálózatok vizsgálata és megkülönböztetése.

• Forgalmi mátrix becslése IP hálózatokban

A rendelkezésre álló adatforgalmi adatok alapján a forgalmi mátrix becslése IP hálózatokban.

• Utazóügynök feladat

Approximációs, heurisztikus és exponenciális algoritmusok implementálása és összehasonlítása az utazóügynök problémára.

• Metaheurisztikák implementálása

Különböző metaheurisztikák implementálása, tesztelése és összehasonlítása.

• Többtermékes folyam-algoritmusok

Többtermékes folyam-algoritmusok implementálása és összehasonlítása.

• Gráfok ábrázolása

Gráfok vizualizációja, azaz egy adott gráf pontjainak elhelyezése a síkon minél esztétikusabb, átláthatóbb formában.

• Véletlen gráfok generálása

Adott gráfosztályból egy véletlen elem generálása egyenletes vagy más eloszlás szerint.

• Gráfosztályok előállítása konstruktív karakterizáció segítségével

Algoritmus kifejlesztése bizonyos gráfosztályokba tartozó összes n csúcsú gráf felsorolására (generálására).

• Gráfelméleti sejtés-ellenőrző modul fejlesztése

Egy olyan általános keretrendszer kidolgozása, amely kisméretű példák ellenőrzésével segíti a gráfelméleti kutatók munkáját.