Párhuzamos algoritmusok

Eloszó......Page 11
1. Bevezetés......Page 14
1.1. Alapfogalmak......Page 18
1.2. Hatékonysági mértékek......Page 20
1.3. Pszeudokód......Page 27
1.4. Számítási modellek......Page 30
1.4.2. Párhuzamos gépek......Page 31
1.4.3. Hálózatok......Page 37
1.5. Rekurzió......Page 45
1.6. Véletlenített algoritmusok ()......Page 49
1.6.1. Egyenlotlenségek......Page 50
1.6.2. Példák......Page 51
1.7. Alsó korlátok......Page 54
1.7.1. Egyszeru számolás......Page 55
1.7.2. Leszámlálás......Page 57
1.7.3. Döntési fák......Page 58
1.7.4. Tanácsadói érvelés......Page 59
1.8. Anomália......Page 60
1.8.1. Lapcsere......Page 61
1.8.2. Ütemezés......Page 63
1.8.3. Párhuzamos feldolgozás átfedéses memóriával......Page 64
1.8.4. Párhuzamos korlátozás és szétválasztás......Page 66
1.8.5. Az anomália elkerülése......Page 68
Prefixszámítás CREW PRAM modellen......Page 73
Prefixszámítás EREW PRAM modellen......Page 76
Prefixszámítás munkaoptimálisan......Page 77
2.1.2. Tömb elemeinek rangsorolása......Page 79
Determinisztikus tömbrangsorolás......Page 81
Véletlenített listarangsorolás ()......Page 83
2.2.1. Logaritmikus ideju algoritmus......Page 87
2.2.2. Páros-páratlan összefésülo algoritmus......Page 88
2.2.3. Munkaoptimális algoritmus......Page 92
2.2.4. Egy O(lglgm) ideju algoritmus......Page 94
2.3.1. Kiválasztás n2 processzoron......Page 96
2.3.2. Kiválasztás p processzoron......Page 97
2.3.3. Kiválasztás egész számok között......Page 99
2.3.4. Az általános kiválasztási feladat......Page 101
2.3.5. Munkaoptimális véletlenített algoritmus ()......Page 102
2.4. Rendezés......Page 104
2.4.1. Páros-páratlan algoritmus......Page 106
2.4.3. Preparata algoritmusa......Page 108
2.4.4. Reischuk véletlenített algoritmusa ()......Page 111
2.5.1. Minmátrix......Page 113
2.5.3. Összefüggo komponensek......Page 115
2.6. Párhuzamos ütemezés......Page 116
2.6.1. A feladat megfogalmazása......Page 118
2.6.2. A feladat értelmezése......Page 120
2.6.4. Elozetes eredmények......Page 121
2.6.5. Fo eredmény......Page 122
3.1. Számítási modellek......Page 125
3.2. Csomagirányítás......Page 127
3.2.1. Csomagirányítás láncon......Page 130
3.2.2. Egy mohó algoritmus a PPR megoldására rácson......Page 135
3.2.3. Véletlenített algoritmus ()......Page 137
3.3. Alapfeladatok......Page 138
3.3.1. Üzenetszórás......Page 139
Prefixszámítás láncon......Page 140
3.3.3. Adatkoncentráció......Page 142
3.3.4. Ritka rendezés......Page 143
3.4. Kiválasztás......Page 144
3.4.1. Véletlenített algoritmus az p = n esetre ()......Page 145
3.4.2. Véletlenített algoritmus a p < n esetre ()......Page 146
3.4.3. Determinisztikus algoritmus a p < n esetre......Page 147
3.5.1. Rangon alapuló összefésülés láncon......Page 150
3.5.3. Páratlan-páros összefésülés négyzeten......Page 151
Páratlan-páros felcserélo rendezés láncon......Page 153
Páratlan-páros összefésülo rendezés láncon......Page 154
Páratlan-páros összefésülo rendezés......Page 155
3.7.1. Kocka......Page 157
3.7.2. Négyzet......Page 158
Legrövidebb utak......Page 159
Konvex burok......Page 160
4.1.1. Hiperkocka......Page 168
4.1.2. Pillangó hálózat......Page 171
Gyuru beágyazása......Page 173
Bináris fa beágyazása......Page 175
4.2.1. Mohó algoritmus......Page 179
4.2.2. Véletlenített algoritmus......Page 180
4.2.3. Az elso fázis elemzése......Page 182
A sorméret elemzése......Page 183
4.3.1. Üzenetszórás fában......Page 184
4.3.2. Prefixszámítás fán......Page 185
4.3.3. Adatkoncentráció......Page 188
4.3.4. Kisszámú elem rendezése hiperkockán......Page 189
4.4.1. Véletlenített algoritmus a p = n esetre (*)......Page 191
4.4.3. Determinisztikus algoritmus a p < n esetre......Page 192
4.5.1. Páratlan-páros összefésülés......Page 194
4.5.2. Biton összefésülés......Page 195
4.6. Rendezés......Page 196
4.6.2. Biton rendezés......Page 197
4.7.1. Minmátrix meghatározása......Page 198
4.7.2. Tranzitív lezárt......Page 199
4.7.5. Konvex burok......Page 200
5.1. Számítási modell......Page 203
5.2. Vezeto választása......Page 204
5.2.1. Vezetoválasztás megoldhatatlansága gyuruben......Page 205
LeLann algoritmusa......Page 206
Chang és Roberts algoritmusa......Page 208
Hirschberg és Sinclair algoritmusa......Page 211
Alsó korlát az üzenetszámra......Page 212
5.2.3. Vezetoválasztás fában......Page 213
Opt-max-terjed algoritmus......Page 214
5.2.5. Alsó korlát az üzenetek számára......Page 215
5.3.1. Megegyezés vonalhibák esetében......Page 216
5.3.3. k-megegyezés......Page 217
5.3.4. Közelíto megegyezés......Page 218
6.1. Megjegyzések az 1. fejezethez......Page 227
6.2. Megjegyzések a 2. fejezethez......Page 232
Magyar szakkifejezések angolul......Page 233
Lelohelyjegyzék......Page 252
Tárgymutató......Page 319
Megoldások......Page 328