Išplėstinė paieška
 
 
 
Pradžia>Informatika>Programavimas>Lygiagretieji algoritmai
   
   
   
naudingas 0 / nenaudingas 0

Lygiagretieji algoritmai

  
 
 
12345678
Aprašymas

Grafų teorija. Minimalaus dengiančio medžio radimas. Algoritmų sudarymo taisyklės. Primo algoritmas. Formulavimas. Primo algoritmas. Nuosekliojo algoritmo sudėtingumas. Lygiagrečiojo algoritmo sudėtingumas. Analizė. Bandymai ir jų rezultatai. Duomenys. Grafikai. Išvados.

Ištrauka

Tegul turime viršūnių aibę } ir briaunų aibę , briauna yra viršūnių pora . Paprasčiausias grafo pavyzdys: žemėlapis.
Grafų teorijoje briaunoms gali būti priskirti skaičiai, įvertinantys atstumą, laiką, svorį ir panašius požymius. Toks grafas yra vadinamas svertiniu. Briaunos įvertį žymėsime ( svoris).
Viršūnių seka yra vadinama k – keliu, jei sekos visos gretimos viršūnės yra sujungtos briaunomis. Ciklu vadiname k – kelią, kuriame pradinė viršūnė sutampa su , o kitos viršūnės kelyje nesikartoja.
Kelio p ilgiu vadinsime skaičių .
Grafas, vadinamas jungiu, jei tarp bet kurių jo viršūnių egzistuoja kelias.
Grafų teorijoje yra sprendžiami 5 pagrindiniai uždaviniai. Tačiau neminint kitų uždavinių, mes paminėsime tik tą kurį mums reikia išspręsti. Tas uždavinys vadinamas minimaliuoju dengiančiuoju medžiu. Jo esmė: šis uždavinys dažnai sutinkamas planuojant komunikacinius tinklus( kompiuterinis tinklas, jungiantis visus įmonės kompiuterius). Tokį tinklą vaizduojame grafu, kurio viršūnių aibę V sudaro asmeniniai kompiuteriai, darbo stotys ir serveriai, o briaunų aibę E sudaro jungtys, jungiančios šiuos kompiuterius. Aišku, gautasis grafas turi būti jungiu, tik tada visi darbuotojai galės keistis informacija. Taip pat siekiame, kad komunikacinių linijų kaina būtų minimali, todėl reikia mažinti briaunų.

Tegul G = (V,E) yra jungusis svertinis grafas. Medis yra jungusis grafas, kuriame nėra ciklų. Grafo G dengiančiuoju medžiu vadinsime medį , kurios briauna yra grafo G briaunų aibės poaibis. Aišku, kad grafo dengiantysis medis nebūtinai yra vienintelis.
Uždavinys pasunkėja, kai grafas G yra įvertintasis. Tada reikia rasti minimalų dengiantįjį medį T, kurio briaunų svoris yra mažiausias. ...

Rašto darbo duomenys
Tinklalapyje paskelbta2007-02-06
DalykasProgramavimo namų darbas
KategorijaInformatika >  Programavimas
TipasNamų darbai
Apimtis7 puslapiai 
Literatūros šaltiniai3
Dydis60.93 KB
AutoriusVitalijus
Viso autoriaus darbų1 darbas
Metai2007 m
Klasė/kursas3
Failo pavadinimasMicrosoft Word Lygiagretieji algoritmai [speros.lt].doc
 

Panašūs darbai

Komentarai

Komentuoti

 

 
[El. paštas nebus skelbiamas]

 
 
Ar šis darbas buvo naudingas?
Taip
Ne
0
0
Pasidalink su draugais
Pranešk apie klaidą