Changes between Version 1 and Version 2 of Temak
- Timestamp:
- 03/17/09 13:08:12 (16 years ago)
Legend:
- Unmodified
- Added
- Removed
- Modified
-
Temak
v1 v2 1 = Nagyprogram, TDK és diplomamunkatémák =1 = Szakdolgozat-, nagyprogram- és TDK-témák = 2 2 3 = Gráfok ábrázolása=3 == Gráfok ábrázolása == 4 4 5 5 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. 6 6 7 == Háttér==7 === Háttér === 8 8 9 9 Gráfok (hálózatok) reprezentálása a síkban egy mind elméletileg, mind a gyakorlatban fontos és érdekes problémakör. A legalapvetőbb kerdés annak (algoritmikus) megválaszolása, hogy egy gráf síkgráf-e, azaz lerajzolható-e úgy a síkban, hogy az élei ne messék egymást. Ha a válasz igen, akkor természetes feladat megadni egy "minél tetszetősebb", minél áttekinthetőbb ilyen reprezentációt. Hasonlóan, feladat lehet nem síkbarajzolható gráfok megjelenítése is. Ezek a problémák tovább ágaztathatók aszerint, hogy az éleket egyenessel, egyszeresen tört vonallal, esetleg tetszöleges görbével kívánjuk reprezentálni, esetleg aszerint, hogy a reprezentálandó gráf rendelkezik-e valamilyen speciális tulajdonsággal. … … 11 11 E feledatkör fontos szerephez jut minden olyan döntéstámogató rendszerben, ahol valamilyen gráffal reprezentálható struktúrát (pl. egy kommunikációs hálózatot, UML diagrammot, egymással összefüggö entitások kapcsolati hálóját stb.) kell a felhasználó számára áttekinthető módon megjeleníteni. A terület gyakorlati fontosságnak megfelelően az elmúlt évtizedekben gráf-ábrázoló algoritmusok sokaságát fejlesztették ki. 12 12 13 == Feladat==13 === Feladat === 14 14 15 15 A jelentkezők feladata az irodalomban fellelhető gráf reprezentáló algoritmusok áttekintése, a gyakorlatban alkalmazható algoritmusok közül néhány implementálása, összehasonlítása esetleg továbbfejlesztése. Cél, hogy a minél több alfeladatra hatékony megoldás szülessen és a letisztázott implementáció bekerüljön a LEMON programkönyvtárba. 16 A feladat típusa17 16 18 A fel edatkör mind nagyprogram, TDK és diplomamunka alapjául is szolgálhat,több jelentkező számára is.17 A feladatkör szakdolgozat, nagyprogram és TDK alapjául is szolgálhat, akár több jelentkező számára is. 19 18 20 == Előfeltételek==19 === Előfeltételek === 21 20 22 21 - C++ programozási nyelv ismerete … … 24 23 - angol nyelvismeret 25 24 26 = Többtermékes folyam-algoritmusok = 25 26 == Többtermékes folyam-algoritmusok == 27 27 28 28 Többtermékes folyam-algoritmusok implementálása és összehasonlítása. 29 29 30 == Háttér==30 === Háttér === 31 31 32 32 A többtermékes folyamok a hagyományos folyam-feladatok általánosításai több forrás-cél pár esetére. A különböző forrás-cél párok közötti forgalmak ("termékek") együttesen használják az éleken levő kapacitásokat. … … 36 36 Elméleti szempontból ez a problémaosztály könnyen kezelhető - azaz létezik polinomiális futásidejű algoritmus - azonban alkalmazásokban gyakran felmerülnek olyan méretű feladatok, amiket ezek az algoritmusok már nem képesek elfogadható időn belül megoldani. Ezért az egzakt megoldó algorimusok mellett hatékony közelítő eljárásokat és heurisztikus módszereket is kifejlesztettek. 37 37 38 == Feladat==38 === Feladat === 39 39 40 40 A jelentkezők feladata az irodalomban fellelhető többtermékes folyam-algoritmusok áttekintése, a gyakorlatban alkalmazhatók közül néhány implementálása, összehasonlítása esetleg továbbfejlesztése. Cél, hogy a minél több alfeladatra hatékony megoldás szülessen és a letisztázott implementáció bekerüljön a LEMON programkönyvtárba. 41 A feladat típusa42 41 43 A feledatkör mind nagyprogram, TDK és diplomamunka alapjául is szolgálhat, akár több jelentkező számára is. 44 Előfeltételek 42 A feladatkör szakdolgozat, nagyprogram és TDK alapjául is szolgálhat, akár több jelentkező számára is. 43 44 === Előfeltételek === 45 45 46 46 - C++ programozási nyelv ismerete … … 48 48 - angol nyelvismeret 49 49 50 = Fák pakolása, fedés fákkal = 50 51 == Fák pakolása, fedés fákkal == 51 52 52 53 Irányítatlan gráfban éldiszjunkt fák keresése (pakolás), gráf éleinek fedése fákkal (fedés) 53 54 54 == Háttér==55 === Háttér === 55 56 56 A ''pakolási feladat'' így hangzik: adott egy összefüggő irányítatlan gráf és egy kpozitív egész, döntsük el, hogy létezik e a gráfban ''k'' darab páronként éldiszjunkt feszítőfa. A szükséges és elégséges feltételt Tutte egy tétele szolgáltatja. A kérdés a matroid-partíciós feladat speciális esete.57 A ''pakolási feladat'' így hangzik: adott egy összefüggő irányítatlan gráf és egy ''k'' pozitív egész, döntsük el, hogy létezik e a gráfban ''k'' darab páronként éldiszjunkt feszítőfa. A szükséges és elégséges feltételt Tutte egy tétele szolgáltatja. A kérdés a matroid-partíciós feladat speciális esete. 57 58 58 59 A ''fedési feladat'' bemenete ugyanaz, mint a pakolási feladaté, de a kérdés az, hogy a gráf élei lefedhetők e ''k'' feszítőfával (illetve mondhatnánk erdőt is, a többszörösen fedett élek kihagyásával). Az elméleti választ Nash-Williams tétele adja meg nekünk egy ritkasági feltétel formájában. 59 Feladat60 60 61 == Feladat==61 === Feladat === 62 62 63 A pakolási -és a fedési feladat elméletének és a megoldó algoritmusoknak a megismerése, majd ezek némelyikének az implementálása, hatékonyságuk összehasonlítása, heurisztikus javítások keresése.63 A pakolási és a fedési feladat elméletének és a megoldó algoritmusoknak a megismerése, majd ezek némelyikének az implementálása, hatékonyságuk összehasonlítása, heurisztikus javítások keresése. 64 64 65 A feladatkör mind nagyprogram, TDK és diplomamunka alapjául is szolgálhat, akár több jelentkező számára is. Az is elképzelhető, hogy a két feladatkör közül csak az egyiket dolgozza fel a jelentkező. 65 A feladatkör szakdolgozat, nagyprogram és TDK alapjául is szolgálhat, akár több jelentkező számára is. 66 Az is elképzelhető, hogy a két feladat közül csak az egyiket dolgozza fel a jelentkező. 66 67 67 == Előfeltételek==68 === Előfeltételek === 68 69 69 70 - C++ programozási nyelv ismerete
