Treść książki
Przejdź do opcji czytnikaPrzejdź do nawigacjiPrzejdź do informacjiPrzejdź do stopki
X
Spisrysunków
3.7.
Algorytmwyznaczaniasumyelementówzapomocąpprocesorów.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
91
3.8.
(a)Złożonośćczasowaalgorytmuzrys.3.7,przyjętoc1l170,c2l10,nl200;(b)osiągane
przyspieszenia(wzór(3.24))dlaróżnychwartościn;(c)osiąganeefektywności(wzór(3.26))
dlaróżnychwartościn.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
93
94
96
3.9.
Symulacjasumowanianl8liczbzapomocąpl3procesorów.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
3.10.Algorytmobliczeńprefiksowych.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
3.11.Ilustracjadziałaniaalgorytmuobliczeńprefiksowych(⊗
j
ioznaczaxi⊗xi+1⊗...⊗xj,dla
i<j).
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.101
96
97
99
3.12.AlgorytmwyznaczaniaelementuminimalnegowczasieO(1).
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
3.13.AlgorytmsortowaniawczasieO(logn).
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
3.14.Algorytmmnożeniamacierzy.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
3.15.Algorytmustalaniaporządkuobiektównaliście;każdemuelementowiilistyLjestprzypo-
rządkowanyprocesorPi,1≤i≤n.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.104
3.16.Ilustracjadziałaniaalgorytmuustalaniaporządkuobiektówna6-elementowejliścieL;szarym
koloremzaznaczonesąwartościw[i]będącewtrakcieobliczania;(a)listapojejzainicjowaniu
wwierszach2–5algorytmuzrys.3.15;(b)–(d)listapokolejnychwykonaniachinstrukcji
iteracyjnejwwierszach6–13.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.105
3.17.)ReprezentacjadrzewawpostacizmodyfikowanychlistsąsiedztwaL;(b)przykładowedrze-
woT;(c)ilustracjagraficznautworzonegocykluEuleradladrzewaT;(d)funkcjanastępnika
sokreślającacyklEulerazapisanawdwuwymiarowejtablicyS.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.107
3.18.Algorytmprzekształcaniadrzewanieukorzenionegowukorzenione.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.108
3.19.(a)Przeszukiwaniewgłąbdrzewaukorzenionego;(b)drogaD,sumyprefiksoweσ[v7u]oraz
znacznikiłukówz[v7u](poznaczałuknwprzód”,t—nwtył”);(c)tablicerodzic[v]orazδ[v]
określające,odpowiednio,rodzicaorazliczbępotomkówwierzchołkav,v∈V.
.
.
.
.
.
.
.
.109
3.20.Algorytmmnożeniamacierzyprzezwektorwjednowymiarowymtorusie.
.
.
.
.
.
.
.
.
.
.
.
.111
3.21.Algorytmmnożeniamacierzywdwuwymiarowymtorusie.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.113
3.22.Dystrybucjaelementówmacierzyaorazbmiędzyprocesoramipopierwszej(a),drugiej(b)
itrzeciej(c)iteracjiinstrukcjiforwwierszach14–24algorytmuzrys.3.21.
.
.
.
.
.
.
.
.
.
.
.114
3.23.Algorytmrozwiązywaniaproblemuredukcjiwkostce.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.116
3.24.Ilustracjarozwiązywaniaproblemuredukcjiwkostcetrójwymiarowej:przykładowewartości
podlegającesumowaniu(wyznaczonewwierszach2–12)(a)orazwartościpopierwszej(b),
drugiej(c)itrzeciej(d)iteracjiwwierszach13–19algorytmuzrys.3.23.
.
.
.
.
.
.
.
.
.
.
.
.117
3.25.Alogrytmwyznaczaniaprefiksówwkostce.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.118
3.26.Wartościzmiennychsibwprocesorachkostkiprzedwykonaniemiteracjiforwwierszach
6–16(a),anastępniepowykonaniupierwszego(b),drugiego(c)itrzeciego(d)przebiegutej
iteracjiwalgorytmiezrys.3.25.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.119
3.27.Algorytmrozwiązywaniaproblemuredukcjiwsiecityputasuj-wymień.
.
.
.
.
.
.
.
.
.
.
.
.
.120
3.28.Wartościzmiennychawprocesorachsiecityputasuj-wymieńprzedwykonaniemiteracjifor
wwierszach2–9(a),anastępniepowykonaniupierwszego(b),drugiego(c)itrzeciego(d)
przebiegutejiteracjiwalgorytmiezrys.3.27(pl8).Redukcjipodlegajądanebędące
numeramiprocesorów.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.120
3.29.RedukcjaproblemuAdoB.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.122
3.30.Przykładukładulogicznego.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.125
3.31.Drzewosortowaniaprzezscalanie;elementysortowanegociąguodługościn,nl2r,znajdują
siępoczątkowowliściachdrzewa.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.126
3.32.Algorytmscalaniaciągów.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.127
3.33.(a)ŁączenieciągówJiKzapomocądobregociągupróbkującegoL;(b)przykładdlaciągów
Jl(273,7,8,10,14,15,17),Kl(174,6,9,11,12,13,16)iLl(5710,13).
.
.
.
.
.
.
.127
3.34.AlgorytmsortowaniaCole’a—operacjerealizowanewnieukończonymwierzchołkuwweta-
piet.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.129
