Projekti / Programi
Aproksimacijski algoritmi na skupini delovnih postaj: učinkovito in ceneno računanje
| Koda |
Veda |
Področje |
Podpodročje |
| 2.07.01 |
Tehnika |
Računalništvo in informatika |
Računalniške strukture, sistemi in mreže - programska oprema |
| Koda |
Veda |
Področje |
| T170 |
Tehnološke vede |
Elektronika |
algoritem, zahtevnost, NP-polnost, aproksimacijski algoritem, paralelno raeunanje, skupina, gruea, problemi razdelitve
Raziskovalci (5)
Organizacije (2)
Povzetek
Uporabnik je mnogokrat zadovoljen že s približno rešitvijo svojega problema, če pri tem ve, da ta rešitev ne odstopa pretirano od natančne, optimalne rešitve. Zato smatramo konstrukcijo aproksimacijskega algoritma s polinomsko časovno odvisnostjo od razsežnosti problema za uspešen korak pri spopadanju z računsko zahtevnim problemom. Pri takšnih algoritmih pa je pomembna tudi odvisnost računskega časa od zahtevane natančnosti, saj večja natančnost terja več računskih korakov. Zaželena je polinomska odvisnost, vendar pa je včasih dosegljiva oz. poznana le eksponentna. Slednje v praksi pomeni, da zaradi dolgotrajnosti računanja nadaljnje izboljševanje natančnosti približnih rešitev zelo hitro postane nesmiselno. Izboljšanje natančnosti je do neke mere še možno na visoko zmogljivih računalniških sistemih
(tj. superračunalnikih ali masovno paralelnih računalnikih), ki pa so zaradi svoje cene težko dostopni. Cenejšo rešitev nudi računanje v skupini oz. gruči (angl. cluster), kjer se problem rešuje sočasno s pomočjo več delovnih postaj, povezanih v mrežo. V raziskovalnem projektu bomo iskali ter ocenjevali možnosti za prilagoditev in uporabo znanih ali novih aproksimacijskih algoritmov pri računanju v skupini oz. gruči.
