Nalaganje ...
Projekti / Programi vir: ARIS

Aproksimacijski algoritmi na skupini delovnih postaj: učinkovito in ceneno računanje

Raziskovalna dejavnost

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 
Ključne besede
algoritem, zahtevnost, NP-polnost, aproksimacijski algoritem, paralelno raeunanje, skupina, gruea, problemi razdelitve
Vrednotenje (pravilnik)
vir: COBISS
Raziskovalci (5)
št. Evidenčna št. Ime in priimek Razisk. področje Vloga Obdobje Štev. publikacijŠtev. publikacij
1.  10581  dr. Polonca Blaznik  Računalništvo in informatika  Raziskovalec  1998 - 1999  23 
2.  08724  dr. Aleksandar Jurišić  Matematika  Raziskovalec  1997 - 1999  209 
3.  10824  dr. Barbara Koroušić Seljak  Računalništvo in informatika  Raziskovalec  1999  335 
4.  04646  dr. Borut Robič  Računalništvo in informatika  Vodja  1997 - 1999  292 
5.  03430  dr. Janez Žerovnik  Matematika  Raziskovalec  1997 - 1999  805 
Organizacije (2)
št. Evidenčna št. Razisk. organizacija Kraj Matična številka Štev. publikacijŠtev. publikacij
1.  0101  Inštitut za matematiko, fiziko in mehaniko  Ljubljana  5055598000  19.652 
2.  0106  Institut "Jožef Stefan"  Ljubljana  5051606000  90.046 
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.
Zgodovina ogledov
Priljubljeno