Экзаменационные задачи (2016) (1185650), страница 2
Текст из файла (страница 2)
Èñïîëüçóÿ ôàçîâûé àëãîðèòì èçáðàíèå ëèäåðà ìîæåò áûòü ïðîèçâåäåíîçà O(D|E|) îáìåíîâ ñîîáùåíèÿìè è èñïîëüçóÿ O(D) åäèíèö âðåìåíè.Çàäà÷à 45.Äîêàæèòå, ÷òî àëãîðèòì èçáðàíèÿ ïóòåì ñðàâíåíèÿ ÿâëÿåòñÿ âîëíîâûì àëãîðèòìîì, åñëè ñîáûòèå èçáðàíèÿ ïðîöåññà ëèäåðîì ðàññìàòðèâàòü êàê ñîáûòèå ðåøåíèÿ.Çàäà÷à 46.Äîêàçàòü òåîðåìó.Òåîðåìà. Àëãîðèòì ×åíÿ-Ðîáåðòñà ðåøàåò çàäà÷ó èçáðàíèÿ ëèäåðà, èñïîëüçóÿìåíåå (N 2 ) ñîîáùåíèé è O(N ) åäèíèö âðåìåíè.Çàäà÷à 47.Ðàññìîòðèì àëãîðèòì ×åíÿÐîáåðòñà, ïîëàãàÿ, ÷òî êàæäûé ïðîöåññ ÿâëÿåòñÿèíèöèàòîðîì. Ïðè êàêîì ðàñïîëîæåíèè îòëè÷èòåëüíûõ ïðèçíàêîâ â êîëüöå ñëîæíîñòü ïî ÷èñëó îáìåíîâ ñîîáùåíèÿìè áóäåò ìèíèìàëüíîé è ñêîëüêî îáìåíîâ ñîîáùåíèÿìè ïîòðåáóåòñÿ â ýòîì ñëó÷àå?Çàäà÷à 48.Ïðèâåñòè íà÷àëüíóþ êîíôèãóðàöèþ ñåòè, â êîòîðîé àëãîðèòì Ïàòåðñîíà-ÄîëåâàÊëåéâà-Ðîäå òðåáóåò (⌊log N ⌋ +1) ðàóíäîâ. Òàêæå ïðèâåñòè íà÷àëüíóþ êîíôèãóðàöèþ, â êîòîðîé àëãîðèòìó äîñòàòî÷íî äâóõ ðàóíäîâ âíå çàâèñèìîñòè îò ÷èñëà èíèöèàòîðîâ. Âîçìîæíî ëè àëãîðèòìó çàâåðøèòüñÿ çà îäèí ðàóíä?6Çàäà÷à 49.Ñðàâíèòü àëãîðèòì óãàñàíèÿ âîëíû äëÿ êîëåö ñ àëãîðèòìîì ×åíÿ-Ðîáåðòñà.
Â÷åì ðàçëè÷èÿ è êàêîé îíè èìåþò ýôôåêò?Çàäà÷à 50.Óñòàíîâèòü äëÿ ñîîáùåíèé âñåõ ñåìè òèïîâ àëãîðèòì Ãàëëàäæåðà-Õàìáëåòà-Ñïèðû,ìîæåò ëè êàæäîå èç íèõ áûòü ïîñëàíî ïðîöåññó, íàõîäÿùåìóñÿ â ñîñòîÿíèè ñíà.Çàäà÷à 51.Àëãîðèòì Ýòüÿ (Attiya) îòëè÷àåòñÿ îò àëãîðèòìà Êîðàõà-Êàòòåíà-Ìîðàíà òîëüêîòåì, ÷òî ôèøêà âìåñòî òîãî, ÷òîáû âïàñòü â ñîñòîÿíèå ïîãîíè, çàìèðàåò è ïîñûëàåòñîîáùåíèå-óáèéöó, êîòîðîå äîãîíÿåò ïðåñëåäóåìóþ ôèøêó, óáèâàåò åå è âîçâðàùàåòñÿ íàçàä. Ïîñëå âîçâðàùåíèÿ óáèéöû âûïîëíåíèå îáõîäà ïðîäîëæàåòñÿ.Ðåàëèçîâàòü àëãîðèòì Attiya è óñòàíîâèòü åãî ñëîæíîñòü.Çàäà÷à 52.Âðåìåííîé ñëîæíîñòü àëãîðèòìà çàâåðøåíèÿ âû÷èñëåíèÿ íàçûâàåòñÿ ÷èñëî åäèíèö âðåìåíè ìåæäó çàâåðøåíèåì áàçîâîãî àëãîðèòìà è çàâåðøåíèåì êîíòðîëüíîãîàëãîðèòìà.Êàêîâà âðåìåííàÿ ñëîæíîñòü àëãîðèòìà Äåéêñòðû-Øîëòåíà?Çàäà÷à 53.Åñëè àëãîðèòì Øàâè-Ôðàí÷åçà ïðèìåíÿåòñÿ ê ïðîèçâîëüíîé ñåòè, ïðîöåññû êîòîðîé èìåþò óíèêàëüíûå èäåíòèôèêàòîðû, è ïðè ýòîì èñïîëüçóåòñÿ âîëíîâîé àëãîðèòì Ãàëëåäæåðà-Õàìáëåòà-Ñïèðû, òî âðåìåííàÿ ñëîæíîñòü òàêîãî êîíòðîëüíîãîàëãîðèòìà áóäåò ñîñòàâëÿòü (N logN ).Ìîæíî ëè óëó÷øèòü âðåìåííóþ ñëîæíîñòü äî O(N ) öåíîé îáìåíà O(N ) äîïîëíèòåëüíûìè ñîîáùåíèÿìè?Çàäà÷à 54.Ïîêàçàòü ñóùåñòâîâàíèå òàêîãî áàçèñíîãî âû÷èñëåíèÿ, â êîòîðîì ïðîèñõîäèò îáìåí m ñîîáùåíèÿìè, ïðè êîíòðîëå êîòîðîãî àëãîðèòì Ñàôðû èñïîëüçóåò m(N − 1)ñîîáùåíèé.Çàäà÷à 55. àëãîðèòìå Ðàíû ïðåäïîëàãàåòñÿ, ÷òî ïðîöåññû íàäåëåíû îòëè÷èòåëüíûìè ïðèçíàêàìè.
Ïðåäïîëîæèì òåïåðü, ÷òî âñå ïðîöåññû àíîíèìíû, íî îáëàäàþò âîçìîæíîñòüþ îòïðàâëÿòü ñîîáùåíèÿ ñâîèì ïîñëåäîâàòåëÿì ïî êîëüöó, è ïðè ýòîì ÷èñëîïðîöåññîâ çàðàíåå èçâåñòíî. Âíåñèòå â àëãîðèòì Ðàíû íåîáõîäèìûå èçìåíåíèÿ, ïîçâîëÿþùèå åìó ðàáîòàòü â ðàìêàõ òàêèõ äîïóùåíèé.Çàäà÷à 56.Îáîñíóéòå êîððåêòíîñòü àëãîðèòìà Ðàíû íà îñíîâå èíâàðèàíòîâ ýòîãî àëãîðèòìà.Çàäà÷à 57.Âíåñèòå èçìåíåíèÿ â àëãîðèòì Ðàíû òàê, ÷òîáû äëÿ ïåðåäà÷è ñîîáùåíèé ìîæíîáûëî èñïîëüçîâàòü ïðîèçâîëüíûé âîëíîâîé àëãîðèòì, à íå òîëüêî êîëüöåâîé àëãîðèòì.7Çàäà÷à 58.Ïðåäïîëîæèì, ÷òî ñíÿòèå ñíèìêà ïðîöåññîì p ÿâëÿåòñÿ äîïîëíèòåëüíûì âíóòðåííèì ñîáûòèåì ap . Ïîêàçàòü, ÷òîS ⋆ çíà÷èìûé ñðåç ⇐⇒ ∀p, q ap ̸≼ aq & aq ̸≼ ap .Çàäà÷à 59.Áóäåì ðàññìàòðèâàòü ðåãèñòðàöèþ ìîìåíòàëüíîãî ëîêàëüíîãî ñîñòîÿíèÿ ïðîöåññà p êàê åùå îäíî âíóòðåííåå ñîáûòèå ap .
Äîêàæèòå, ÷òîS ∗ ÿâëÿåòñÿ çíà÷èìûì ⇐⇒ ∀p, q : ap ∥ aq .Çàäà÷à 60.Ïðîôåññîð Çàõàðîâ óòâåðæäàåò:¾Ïîñëåòîãî êàê ÿ ïðî÷åë ëåêöèþ î ìîìåíòàëüíûõ ñîñòîÿíèÿõ, ÿ ñóìåë ëó÷øå ïî-íÿòü àëãîðèòìû îáíàðóæåíèÿ çàâåðøåíèÿ âû÷èñëåíèé. Íàïðèìåð, â àëãîðèòìå Ñàôðû îáðàáîòêó ìàðêåðîâ ïðîöåññîìñîñòîÿíèÿ ïðîöåññàp íóæíî ïîíèìàòü êàê âû÷èñëåíèå ìîìåíòàëüíîãîp.  ïîñòðîåííîì ìîìåíòàëüíîì ñîñòîÿíèè ñèñòåìû âñå ïðîöåññûÿâëÿþòñÿ ïàññèâíûìè, òàê êàê ìàðêåð îáðàáàòûâàåòñÿ òîëüêî ïàññèâíûìè ïðîöåññàìè.
Ïîýòîìó, ÷òîáû ïðèíÿòü ðåøåíèå î çàâåðøåíèè âû÷èñëåíèÿ òðåáóåòñÿ âñåãîëèøü ïðîâåðèòü, ïóñòû ëè âñå êàíàëû. Äëÿ ýòîãî â ìàðêåðå óêàçûâàåòñÿ ñóììàðíîåçíà÷åíèå ñ÷åò÷èêîâ ñîîáùåíèé.Îäíàêî ìíå íåÿñíà òà ðîëü, êîòîðóþ èãðàþò îêðàñêèwhite è black , à òàêæå êàê óäà¿åòñÿ îáåñïå÷èòü çíà÷èìîñòü ìîìåíòàëüíûõ ñîñòîÿíèé ñèñòåìû.Íå ìîãëè áû Âû ïîìî÷ü ïðîôåññîðó?8.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
