Projekti / Programi
Izbrane teme teoretičnega računalništva in kombinatorične optimizacije
01. januar 2004
- 31. december 2008
| Koda |
Veda |
Področje |
Podpodročje |
| 1.07.00 |
Naravoslovje |
Računalniško intenzivne metode in aplikacije |
|
| 1.01.00 |
Naravoslovje |
Matematika |
|
| Koda |
Veda |
Področje |
| P170 |
Naravoslovno-matematične vede |
Računalništvo, numerična analiza, sistemi, kontrola |
kombinatorična optimizacija, algoritmi na grafih, matematična kemija, podatkovne strukture, analiza omrežij, simbolno računanje.
Raziskovalci (29)
Organizacije (1)
Povzetek
Računsko intenzivne metode in aplikacije najdemo tako v naravoslovju (biologija, kemija, fizika), v tehniki (strojništvo, gradbeništvo, elektrotehnika), ekonomiji (finance), v družboslovju (sociologija, antropologija, heraldika, genealogija, zgodovina, jezikoslovje), kot tudi v umetnosti (film, glasba, slikarstvo, kiparstvo, arhitektura). Skupna vsem naštetim področjem je velika potreba po računski moči in učinkovitih metodah za obdelavo informacij. Naše raziskovalno delo vključuje razvoj metod in tehnik za porazdeljeno računanje, ki tvorijo transparentno okolje za izdelavo aplikacij. Tehnike in metode slonijo na učinkovitih in porazdeljenih algoritmih ter robustnih podatkovnih strukturah. Za dosego robustnosti in učinkovitosti pri načrtovanju algoritmov in podatkovnih struktur uporabljamo matematično teorijo grafov in teorijo grup.
V okviru teorije grafov in incidenčnih struktur se ukvarjamo s problemi na področju kombinatoričnih in geometričnih konfiguracij, regularnih zemljevidov, iskanjem prepovedanih grafov pri vložitvah na torus, upodobitev grafov in različnih tipov eulerjevih sprehodov.
V okviru numeričnih metod študiramo prostor zlepkov nad triangulacijami, geometrijsko interpolacijo s parametričnimi polinomskimi krivuljami in ploskvami ter reševanje polinomskih in večparametričnih problemov lastnih vrednosti.
Kombinatorična optimizacija se še vedno intenzivno razvija. Na tem področju nas zanimajo aplikacije na različnih področjih, od matematike, računalništva prek naravoslovja, npr. kemije, do družboslovja, npr. računalniškega rodoslovja in grboslovja.
S sintezo večjih, geometrijskim telesom podobnih molekul, kakršni so npr. fulereni, sta diskretna matematika in teoretično računalništvo dobila v teoretični kemiji novo, pomembnejšo vlogo. Naša skupina na tem področju že več let sodeluje z vodilnimi kemiki in fiziki pri nas in po svetu.
Pri razvoju programskih orodij za diskretne matematične strukture ter distribuiranem vodenju in izdelovanju projektov prek interneta omenimo programski sistem Vega, ki vključuje že okrog 2500 funkcij za delo z diskretnimi matematičnimi strukturami. Trenutno razvijamo novo verzijo sistema. Poleg številnih algoritmov nameravamo sistemu dodati tudi nekatere nove strukture diskretne matematike, kot so konfiguracije in orientirani matroidi.
Z razvrščanjem v skupine, analizo omrežij in algoritmi teorije grafov se ukvarjamo že več let. Zadnja leta smo začeli posebno pozornost posvečati velikim podatkovjem (na desettisoče enot) in hitrim (subkvadratnim) algoritmom za njihovo analizo. Za nazoren in razumljiv prikaz dobljenih rezultatov razvijamo ustrezne oblike vizualizacije v trirazsežnem prostoru, oprte na jezik za opis prostorskih konstrukcij VRML (Virtual Reality Modeling Language).
Za nekatere probleme ne obstajajo učinkoviti točni algoritmi. Zato si prizadevamo za posamezne izmed njih razviti zelo hitre približne algoritme, ki temeljijo na hevristikah. Taki problemi so na primer: bločno modeliranje v obsežnih omrežjih, nivojski prikaz acikličnih omrežij in problem barvanja točk grafa.
Pri analizi velikih podatkovij in omrežij je pogosto ugodno, če jih znamo razbiti na več manjših, lažje obvladljivih kosov. Posebno pozornost posvečamo problemom razčlembe omrežij na podomrežja iz izbranih družin (poti, drevesa, ravninski grafi, kubični grafi itd.). Pričakujemo, da nam bo na tej osnovi uspelo zgraditi tudi posamezne učinkovite algoritme.
Pri operacionalizaciji pristopov k analizi podatkovij in omrežij imajo velik pomen mere različnosti. Tu nadaljujemo raziskave prijemov, kako z ustreznimi transformacijami izboljšati kakovost posameznih mer različnosti in v posebnem primeru, mer različnosti med mešanicami.
Pri simbolnem računanju se osredotočamo na algoritme za reševanje linearnih diferenčnih enačb v več dimenzijah in algoritme za računanje hipergeometričnih in sorodnih determinant v zaključeni obliki.
Pomen za razvoj znanosti
Iz našega dela v predhodnem raziskovalnem obdobju je mogoče nedvoumno ugotoviti tesno mednarodno vpetost naše raziskovalne skupine. Objavljamo v vodilnih mednarodnih znanstvenih revijah na mnogih raziskovalnih področjih, udeležujemo se najpomembnejših specializiranih mednarodnih srečanj, obiskujemo pomembne tuje univerze in vrhunske znanstvene inštitucije, sodelujemo na mednarodnih znanstvenih projektih in na aplikativnih projektih. Številni mladi raziskovalci naše skupine so vsaj del svojega študija opravili na kvalitetnih univerzah v tujini. Obiskujejo nas vodilni strokovnjaki. Naše delo je odmevno v mednarodni raziskovalni sferi in pogosto citirano. Aktivno sodelujemo z znanstveniki iz ZDA (Carnegie Mellon University, University of Pittsburgh, University of Pennsylvania, University of California Irvine, Temple University, Syracuse University, Colgate University, Drake University), Kanada (University of Waterloo, Simon Fraser University), Francija (Universite de Marne-la-Vallee, INRIA Rocquencourt, INRIA Sophia-Antipoli, Universite Bordeaux I), Švedska (University of Technology, Lulea, Royal Institute of Technology, Stockholm), Avstrija (Montanuiversitaet Leoben, RISC Linz, Univerza na Dunaju, FAS research z Dunaja), Nemčija (FU Berlin, Universität Bielefeld, TU Darmstadt, Universität Lepzig), Rusija (Moskovska državna univerza), Italija (University of Pisa, Univerza Udine, Univerza Genova, Univerza v Padovi), Norveška (CMA, IFI, Univerza v Oslu, Univerza v Trondheimu), Nizozemska (Univerza v Eindhovnu), Hrvaška (Institut Rudjer Bošković, Univerza v Zagrebu, Sveučilište u Splitu), Velika Britanija (Univerza v Edinburghu, Univerza v Birminghamu, Univerza v Sheffieldu). Sodelujemo tudi na različnih interdisciplinarnih projektih: s skupino za analizo socialnih omrežij na FDV, Ljubljana, skupino za računalniški vid na FRI, Ljubljana, Inštitutom za biofiziko na MF, Ljubljana, Kemijskim inštitutom, in Primorskim inštitutom za naravoslovne in tehniške vede Univerze na Primorskem. Člani naše raziskovalne skupine sodelujejo v evropskih raziskovalnih mrežah (npr. PASCAL Network of excellence), na več bilateralnih raziskovalnih projektih (z ZDA, Italijo, Norveško, Hrvaško) in na aplikativnih projektih kot je Računalniška orodja v razvoju proizvodnih procesov. Naše delo daje pomembne rezultate na področjih uporabe računsko intenzivnih metod v teoretičnem računalništvu, analizi velikih omrežij, simbolnem računanju, problemih teorije grafov, numerične analize in linearne algebre, računalniško podprtega geometrijskega načrtovanja, kombinatorični optimizaciji, kemiji in v bioinformatiki. Mnogi rezultati imajo poleg teoretičnega pomena tudi uporabno vrednost. To uporabljamo pri prenosu znanja iz akademske sfere v industrijo. Za uporabnike izven znanstvene sfere so posebno pomembni metodologija reševanja problemov, matematično modeliranje in razvoj programskih rešitev. Pri tehnološkem razvoju sodelujemo z nekaterimi vodilnimi slovenskimi podjetji (Gorenje, Mobitel, Iskratel). Pomemben je tudi razvoj kadrov. Mladim raziskovalcem omogočamo stike z vrhunskimi mednarodnimi raziskovalci in jih vpeljujemo v raziskovalno delo. Empirično preverljiv pomen naših rezultatov je vsekakor število člankov in citatov del članov raziskovalne skupine.
Pomen za razvoj Slovenije
Novi algoritmi in implementacije v simbolnem računanju in na področju diskretne in numerične matematike prispevajo k učinkovitosti in računski moči programskih orodij na skoraj vseh poljih znanosti in tehnologije. Pomen naših raziskav za Slovenijo je mogoče razvrstiti v dva sklopa. Vzgoja in razvoj kadrov: Z vzgojo novih raziskovalcev krepimo bazo znanstvene sfere. Svoje mlade raziskovalce ves čas privajamo na mednarodno konkurenco in jim omogočamo stike s svetovnim raziskovalnim vrhom na tem področju. Nekateri med njimi tudi študirajo v tujini. To bo vsekakor prispevalo k dvigu kvalitete in povečanju mednarodnega sodelovanja. Uporaba in sodelovanje z uporabniki izven znanstvene sfere: Člani programske skupine sodelujemo tudi na različnih aplikativnih projektih, kjer v praksi uporabimo znanja, pridobljena preko temeljnih raziskav na programu. Nekateri naši raziskovalci nadaljujejo svojo kariero tudi zunaj akademskih inštitucij in pridobljeno znanje (metodologija reševanja problemov, programiranje) neposredno prenašajo v svoje delovno okolje, s čimer krepijo vezi med znanstveno sfero in ostalo družbo. Primeri sodelovanja so podjetja Mobitel, Seaway - Elan, AMBIENT d.o.o., Ultra, XLab, RTV Slovenija, MZZ RS, MO RS idr. V skupino poskušamo zajeti kljub birokratskim oviram tudi vrhunske raziskovalce iz industrije. Člani skupine so prispevali nove pristope k analizi velikih omrežij, ki s neposredno uporabni v upravi in na drugih področjih. Vodimo tudi ciljne raziskovalne projekte, ki so v podporo Slovenski vojski in MORS, predvsem na logističnem področju in na področju e-izobraževanja. S projekti iz področja e-izobraževanja razvijamo tehnologije za enostavno pripravo programov za celostno učenje z vključevanjem informacijsko-komunikacijske tehnologije in medijev. S tem bomo prispevali tudi k izboljševanju informacijske pismenosti in dostopnosti do novih tehnologij širši javnosti. V okviru projekta "L1-7230 - Računalniška orodja v razvoju proizvodnih programov - 2. del" razvijamo CAD orodja nove generacije, ki bodo pripomogla k učinkovitejšemu in gospodarnejšemu oblikovanju stavb pri moderni urbanizaciji. V okviru projekta "L1-0696 - Digitalni arhiv naravne in kulturne dediščine" bomo poskrbeli za pregledno kategorizacijo naravne in kulturne dediščine ter ji povečali dostopnost. Omenimo naj še vodenje projekta "M6-0046 - Podpolkovnik Jurij Vega - vojak in balistik", v okviru katerega smo preučili in promovirali enega naših največjih in prvih matematikov. Znanja, pridobljena v programski skupini, so danes visoko cenjena v svetovnem gospodarstvu. Ob vključenosti slovenskega gospodarstva v svetovne tokove je tako tudi zelo pomembno, da so takšna znanja prisotna v Sloveniji in na voljo našemu gospodarstvu. Slednje se lahko na ta način veliko uspešneje in hitreje razvija.
Najpomembnejši znanstveni rezultati
Zaključno poročilo,
celotno poročilo na dLib.si
Najpomembnejši družbeno–ekonomsko in kulturno relevantni rezultati
Zaključno poročilo,
celotno poročilo na dLib.si
