COIN-OR::LEMON - Graph Library

Changes between Version 1 and Version 2 of Temak


Ignore:
Timestamp:
03/17/09 14:08:12 (11 years ago)
Author:
Peter Kovacs
Comment:

--

Legend:

Unmodified
Added
Removed
Modified
  • Temak

    v1 v2  
    1 = Nagyprogram, TDK és diplomamunka témák =
     1= Szakdolgozat-, nagyprogram- és TDK-témák =
    22
    3 = Gráfok ábrázolása =
     3== Gráfok ábrázolása ==
    44
    55Gráfok vizualizációja, azaz egy adott gráf pontjainak elhelyezése a síkon minél esztétikusabb, átláthatóbb formában.
    66
    7 == Háttér ==
     7=== Háttér ===
    88
    99Grá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.
     
    1111E 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.
    1212
    13 == Feladat ==
     13=== Feladat ===
    1414
    1515A 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ípusa
    1716
    18 A feledatkör mind nagyprogram, TDK és diplomamunka alapjául is szolgálhat, több jelentkező számára is.
     17A feladatkör szakdolgozat, nagyprogram és TDK alapjául is szolgálhat, akár több jelentkező számára is.
    1918
    20 == Előfeltételek ==
     19=== Előfeltételek ===
    2120
    2221 - C++ programozási nyelv ismerete
     
    2423 - angol nyelvismeret
    2524
    26 = Többtermékes folyam-algoritmusok =
     25
     26== Többtermékes folyam-algoritmusok ==
    2727
    2828Többtermékes folyam-algoritmusok implementálása és összehasonlítása.
    2929
    30 == Háttér ==
     30=== Háttér ===
    3131
    3232A 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.
     
    3636Elmé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.
    3737
    38 == Feladat ==
     38=== Feladat ===
    3939
    4040A 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ípusa
    4241
    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
     42A 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 ===
    4545
    4646 - C++ programozási nyelv ismerete
     
    4848 - angol nyelvismeret
    4949
    50 = Fák pakolása, fedés fákkal =
     50
     51== Fák pakolása, fedés fákkal ==
    5152
    5253Irányítatlan gráfban éldiszjunkt fák keresése (pakolás), gráf éleinek fedése fákkal (fedés)
    5354
    54 == Háttér ==
     55=== Háttér ===
    5556
    56 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.
     57A ''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.
    5758
    5859A ''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 Feladat
    6060
    61 == Feladat ==
     61=== Feladat ===
    6262
    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.
     63A 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.
    6464
    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ő.
     65A feladatkör szakdolgozat, nagyprogram és TDK alapjául is szolgálhat, akár több jelentkező számára is.
     66Az is elképzelhető, hogy a két feladat közül csak az egyiket dolgozza fel a jelentkező.
    6667
    67 == Előfeltételek ==
     68=== Előfeltételek ===
    6869
    6970 - C++ programozási nyelv ismerete