• N2-0171 - Teorija grafov in kombinatorično znanstveno računalništvo
Naročnik: Javna agencija za raziskovalno dejavnost RS ( N2-0171 )
Trajanje projekta: 2021 - 2023
  • Opis

Glavni cilj projekta je opredelitev problemov s področja teorije grafov v okviru kombinatoričnega znanstvenega računalništva. Poseben poudarkom bo na povezovanju teoretičnega pristopa in praktične uporabe teoretičnih rešitev iz različnih področij. Slednja vključujejo kombinatorično kemijo, sistemsko biologijo, tržne in portfolio analize, klasične inženirske panoge, družbene vede, biomateriomiko in uporabno matematiko. Iz matematičnega zornega kota bodo uporabljena zaporedja vozlišč z monotono naraščajočimi stopnjami, grafi in drevesa z nizkimi stopnjami vozlišč, klike in neodvisne množice, grafne funkcije (povezljivost, naklonjenost, naključnost), različni tipi barvanja grafov in modelov skupnosti. Naš cilj je načrtovanje (močno vzporednih optimizacijskih) algoritmov na grafih za reševanje omenjenih problemov in njihova implementacija na vzporednih računalniških okoljih. Projekt sestoji iz teoretičnega in praktičnega dela, ki se vzajemno dopolnjujeta: aplikacije definirajo najpomembnejše praktične probleme (ki pa so običajno preprostejši od povsem splošno zastavljenih problemov) in teoretično raziskovanje poskuša poiskati zakonitosti, katere veljajo v posebnem primeru, da lahko na njihovi osnovi razvijemo učinkovite rešitve za super-računalniške (vzporedne) sisteme. Čeprav bo teoretični del projekta v glavnem potekal na Rényijevem inštitutu v Budimpešti, razvoj algoritmov in njihova uporaba pa na univerzah v Ljubljani, Szegedu in Pécsu, bo sodelovanje obeh vej projekta glavni doprinos projekta. Glavni problem je obstoj množice praktičnih problemov, ki so zelo zahtevni za reševanje (NP-težki in NP-polni), za katere so potrebne relativno dobre rešitve, saj ni mogoče poiskati optimalnih rešitev ali pa jih je možno najti samo pod določenimi posebnimi pogoji. Pristop k reševanju ima tri dele. Najprej je potrebno znati praktični problem ustrezno zmodelirati in oceniti računsko zahtevnost reševanja. Nato je v primeru težkih optimizacijskih in odločitvenih problemov potrebno preučiti po eni strani posebne primere in po drugi graf teoretične rezultate, ki bi vodili k razvoju učinkovitih algoritmov. Na koncu pa uporabimo še hevristične pristope za iskanje približnih rešitev s čim boljšo oceno ali dokazom kakovosti rešitve. Predvideni rezultati so pomembni zaradi dveh stvari: najprej pričakujemo, da bodo imeli dejanski vpliv na področju teorije grafov oziroma na splošno na diskretno matematik; poleg tega in morda celo pomembneje, naj bi razviti algoritmi omogočili učinkovito reševanje praktičnih problemov z zgoraj naštetih področij.

  • Logo
Logo