Projekti / Programi
Natančni in približni algoritmi in tehnike
| Koda |
Veda |
Področje |
Podpodročje |
| 2.07.00 |
Tehnika |
Računalništvo in informatika |
|
| Koda |
Veda |
Področje |
| P170 |
Naravoslovno-matematične vede |
Računalništvo, numerična analiza, sistemi, kontrola |
algoritem, aproksimacijski algoritem, verjetnostni/naključni algoritem, optimizacija, računska zahtevnost, programska oprema, porazdeljeni sistem, "grid computing", podvajanje podatkov, usmerjanje podatkov, optimalno dodeljevanje, razmeščanje, prevajalnik, prevajanje programskih jezikov, sintaksna analiza.
Raziskovalci (5)
| št. |
Evidenčna št. |
Ime in priimek |
Razisk. področje |
Vloga |
Obdobje |
Štev. publikacijŠtev. publikacij |
| 1. |
23400 |
dr. Uroš Čibej |
Računalništvo in informatika |
Mladi raziskovalec |
2004 - 2007 |
71 |
| 2. |
18188 |
dr. Tomaž Dobravec |
Računalništvo in informatika |
Raziskovalec |
2004 - 2007 |
135 |
| 3. |
22475 |
dr. Jurij Mihelič |
Računalništvo in informatika |
Raziskovalec |
2004 - 2007 |
143 |
| 4. |
04646 |
dr. Borut Robič |
Računalništvo in informatika |
Vodja |
2004 - 2007 |
292 |
| 5. |
01902 |
dr. Boštjan Vilfan |
Računalniško intenzivne metode in aplikacije |
Raziskovalec |
2004 - 2007 |
189 |
Organizacije (1)
Povzetek
Prvi temeljni cilj projekta je raziskva lastnosti in uporabnosti natančnih in približnih algoritmov pri reševanju zelo zahtevnih računskih problemov, ki jih poraja praksa. Sem sodi tudi raziskava primernosti raznih vrst računskih problemov za natančno in približno reševanje. Za mnogo praktičnih problemov se je namreč izkazalo, da so NP-težki, odkritja novih pa so tako pogosta, da jih poznamo že krepko čez tisoč. Ko se v praksi srečamo s tovrstnim problemom, običajno opustimo iskanje natančnega polinomskega algoritma in se raje posvetimo iskanju algoritmov, ki v korist hitrosti žrtvujejo natančnost. Dva aktualna razreda hevrističnih algoritmov predstavljajo aproksimacijski algoritmi, ki hitro vračajo približne rešitve, obenem pa zagotavljajo določeno kakovost teh rešitev, ter verjetnostni/naključni algorimi, ki hitro vračajo rešitve, hkrati pa podajajo verjetnost, da so te rešitve optimalne. Kljub svoji nenatančnostii pa oboji v praksi največkrat povsem zadoščajo našim potrebam, seveda pod pogojem, da so dobri, kar pomeni, da bodisi zagotavljajo majhna odstopanja od optimalnega rezultata (aproksimacijski) ali pa zagotavljajo majhne verjetnosti, da je rezultat napačen (verjetnostni).
Drugi temeljni cilj predlaganega projekta pa je razvoj in uporaba natančnih in približnih algoritmov in tehnik pri reševanje nekaterih konkretnih NP-težkih problemov, ki se porajajo predvsem na štirih, danes zelo aktualnih področjih: na področju razmeščanja, na področju usmerjanja podatkov, na področju podvajanja podatkov ter na področju sintaksne analize. Pri problemih razmeščanja je trebna razmestiti ponudnike v danem prostoru, toda tako da bo v čim večji meri izpolnjena dana zahteva. Pri usmerjanje podatkov je potrebno razviti učinkovite statične in dinamične usmerjevalne algoritme, ki bodo omogočali hiter prenos podatkov med sodelujočimi računalniki. Z dobrim podvajanjem podatkov skušamo pospešiti izvajanje opravil v porazdeljenem sistemu, ne da bi preveč obremenili pomnilniških in komunikacijskih kapacitet omrežja. Kombinirane metode sintaksne analize skušajo zapolniti vrzel med LL in LR sintaksno analizo in izkoristi čimveč prednosti, ki jih prinaša vsaka od njiju.
