Ðåôåðàò: Ðàñïðåäåëåííûå àëãîðèòìû
Ðàçäåë 5.1 149
Ðàçäåë 5.2 149
Ðàçäåë 5.3 149
6 Âîëíîâûå àëãîðèòìû è àëãîðèòìû îáõîäà 149
6.1 Îïðåäåëåíèå è èñïîëüçîâàíèå âîëíîâûõ àëãîðèòìîâ 150
6.1.1 Îïðåäåëåíèå âîëíîâûõ àëãîðèòìîâ 151
6.1.2 Ýëåìåíòàðíûå ðåçóëüòàòû î âîëíîâûõ àëãîðèòìàõ 153
6.1.3 Ðàñïðîñòðàíåíèå èíôîðìàöèè ñ îáðàòíîé ñâÿçüþ 155
6.1.4 Ñèíõðîíèçàöèÿ 156
6.1.5 Âû÷èñëåíèå ôóíêöèé èíôèìóìà 156
6.2 Âîëíîâûå àëãîðèòìû 158
6.2.1 Êîëüöåâîé àëãîðèòì 158
6.2.2 Äðåâîâèäíûé àëãîðèòì 159
6.2.3 Ýõî-àëãîðèòì 161
6.2.4 Àëãîðèòì îïðîñà 163
6.2.5 Ôàçîâûé àëãîðèòì 164
6.2.6 Àëãîðèòì Ôèííà 167
6.3 Àëãîðèòìû îáõîäà 169
6.3.1 Îáõîä êëèê 170
6.3.2 Îáõîä òîðîâ 171
6.3.3 Îáõîä ãèïåðêóáîâ 172
6.3.4 Îáõîä ñâÿçíûõ ñåòåé 173
6.4 Âðåìåííàÿ ñëîæíîñòü: ïîèñê â ãëóáèíó 175
6.4.1 Ðàñïðåäåëåííûé ïîèñê â ãëóáèíó 176
6.4.2 Àëãîðèòìû ïîèñêà â ãëóáèíó çà ëèíåéíîå âðåìÿ 177
6.4.3 Ïîèñê â ãëóáèíó ñî çíàíèåì ñîñåäåé 182
6.5 Îñòàëüíûå âîïðîñû 182
6.5.1 Îáçîð âîëíîâûõ àëãîðèòìîâ 182
6.5.2 Âû÷èñëåíèå ñóìì 184
6.5.3 Àëüòåðíàòèâíûå îïðåäåëåíèÿ âðåìåííîé ñëîæíîñòè 186
Óïðàæíåíèÿ ê Ãëàâå 6 188
Ðàçäåë 6.1 188
Ðàçäåë 6.2 189
Ðàçäåë 6.3 190
Ðàçäåë 6.4 190
Ðàçäåë 6.5 190
7 Àëãîðèòìû âûáîðà 190
7.1 Ââåäåíèå 191
7.1.1 Ïðåäïîëîæåíèÿ, èñïîëüçóåìûå â ýòîé ãëàâå 192
7.1.2 Âûáîð è âîëíû 193
7.2 Êîëüöåâûå ñåòè 196
7.2.1 Àëãîðèòìû ËåËàííà è ×àíãà-Ðîáåðòñà 196
7.2.2 Àëãîðèòì Petersen / Dolev-Klawe-Rodeh 200
7.2.3 Âûâîä íèæíåé ãðàíèöû 203
7.3 Ïðîèçâîëüíûå Ñåòè 207
7.3.1 Âûðîæäåíèå è Áûñòðûé Àëãîðèòì 208
7.3.2 Àëãîðèòì Gallager-Humblet-Spira 210
7.3.3 Ãëîáàëüíîå Îïèñàíèå GHS Àëãîðèòìà. 212
7.3.4 Äåòàëüíîå îïèñàíèÿ GHS àëãîðèòìà 215
7.3.5 Îáñóæäåíèÿ è Âàðèàíòû GHS Àëãîðèòìà 219
7.4 Àëãîðèòì Korach-Kutten-Moran 220
7.4.1 Ìîäóëüíîå Ñòðîèòåëüñòâî 221
7.4.2 Ïðèìåíåíèÿ Àëãîðèòìà KKM 225
Óïðàæíåíèÿ ê Ãëàâå 7 225
Ðàçäåë 7.1 225
Ðàçäåë 7.2 226
Ðàçäåë 7.3 226
Ðàçäåë 7.4 226
8 Îáíàðóæåíèå çàâåðøåíèÿ 227
8.1 Ïðåäâàðèòåëüíûå çàìå÷àíèÿ 228
8.1.1 Îïðåäåëåíèÿ 228
8.1.2 Äâå íèæíèõ ãðàíèöû 231
8.1.3 Çàâåðøåíèå Ïðîöåññîâ 233
8.2.2 Àëãîðèòì Shavit-Francez 237
8.3 Ðåøåíèÿ, îñíîâàííûå íà âîëíàõ 241
8.3.1 Àëãîðèòì Dijkstra-Feijen-Van Gasteren 242
8.3.2 Ïîäñ÷åò Îñíîâíûõ Ñîîáùåíèé: Àëãîðèòì Ñàôðà 245
8.3.3 Èñïîëüçîâàíèå Ïîäòâåðæäåíèé 249
8.3.4 Îáíàðóæåíèå çàâåðøåíèÿ ñ ïîìîùüþ âîëí 252
8.4 Äðóãèå Ðåøåíèÿ 254
8.4.1 Àëãîðèòì âîññòàíîâëåíèÿ êðåäèòà 254
8.4.2 Ðåøåíèÿ, èñïîëüçóþùèå âðåìåííûå ïîìåòêè 256
Óïðàæíåíèÿ ê Ãëàâå 8 259
Ðàçäåë 8.1 259
Ðàçäåë 8.2 259
Ðàçäåë 8.3 259
Ðàçäåë 8.4 260
13 Îòêàçîóñòîé÷èâîñòü â Àñèíõðîííûõ Ñèñòåìàõ 260
13.1 Íåâîçìîæíîñòü ñîãëàñèÿ 260
13.1.1 Îáîçíà÷åíèÿ, Îïðåäåëåíèÿ, Ýëåìåíòàðíûå Ðåçóëüòàòû 260
13.1.2 Äîêàçàòåëüñòâî íåâîçìîæíîñòè 262
13.1.3 Îáñóæäåíèå 264
13.2 Èçíà÷àëüíî-ìåðòâûå Ïðîöåññû 265
Ñòðàíèöû: 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31, 32, 33, 34, 35, 36, 37, 38, 39, 40, 41, 42, 43, 44, 45, 46, 47, 48, 49, 50, 51, 52, 53, 54, 55, 56, 57, 58, 59, 60, 61, 62, 63, 64, 65, 66, 67, 68, 69, 70, 71, 72, 73, 74, 75, 76, 77, 78, 79, 80, 81, 82, 83, 84, 85, 86, 87, 88, 89, 90, 91, 92, 93, 94, 95, 96, 97, 98, 99, 100, 101, 102, 103, 104, 105
