Экзаменационные задачи (2016)

Çàäà÷à 1.Ïîêàæèòå, ÷òî â ¾íàèâíîì¿ ïðîòîêîëå ïåðåäà÷è äàííûõ ñ 4 ñîîáùåíèÿìè (Ëåêöèÿ1) âîçìîæíî äóáëèðîâàíèå èëè ïîòåðÿ ñîîáùåíèé ââèäó òîãî, ÷òî NCP A âûíóæäåíàñ÷èòàòüñÿ ñ âîçìîæíîñòüþ âûõîäà èç ñòðîÿ NCP B .Çàäà÷à 2.Ïîñòðîéòå ïðîñòîé ïðîòîêîë ñ äâóìÿ îáìåíàìè ñîîáùåíèÿìè, êîòîðûé íèêîãäà íåäîïóñêàåò ïîòåðè ñîîáùåíèé (õîòÿ ìîæåò äóáëèðîâàòü ñîîáùåíèÿ).

Äîêàæèòå êîððåêòíîñòü ýòîãî ïðîòîêîëà (ò.å., ÷òî ïîñòðîåííûé ïðîòîêîë íèêîãäà íå òåðÿåò íèîäíîãî ñîîáùåíèÿ).Çàäà÷à 3.Äîêàæèòå òåîðåìó.Òåîðåìà.Ïóñòü γ êîíôèãóðàöèÿ ðàñïðåäåëåííîé ñèñòåìû (ñ àñèíõðîííûì îáìåíîì ñîîáùåíèÿìè), è ïóñòü ep è eq ñîáûòèÿ, êîòîðûå ïðîèñõîäÿò â ðàçíûõ ïðîöåññàõ pè q , è ïðè ýòîì îáà ñîáûòèÿ äîïóñòèìû â êîíôèãóðàöèè γ . Òîãäà ñîáûòèå ep äîïóñòèìî â êîíôèãóðàöèè eq (γ), à ñîáûòèå eq â êîíôèãóðàöèè ep (γ), è ïðè ýòîìep (eq (γ)) = eq (ep (γ)).Çàäà÷à 4.Äîêàæèòå, ÷òî îòíîøåíèå ïðè÷èííî-ñëåäñòâåííîé çàâèñèìîñòè ìåæäó ñîáûòèÿìèâûïîëíåíèÿ ≺ ÿâëÿåòñÿ îòíîøåíèåì ÷àñòè÷íîãî ïîðÿäêà? Ïðè êàêèõ óñëîâèÿõ ýòîîòíîøåíèå áóäåò ÿâëÿòüñÿ îòíîøåíèåì ïîëíîãî (ëèíåéíîãî) ïîðÿäêà?Çàäà÷à 5.Ïîäáåðèòå ïîäõîäÿùåå îïðåäåëåíèå äëÿ ïðè÷èííî-ñëåäñòâåííîãî ïîðÿäêà ïåðåõîäîâ ñèñòåìû ñ ñèíõðîííûì îáìåíîì ñîîáùåíèÿìè.

Ïðåäëîæèòå îïðåäåëåíèå ÷àñîâäëÿ ñèñòåì òàêîãî ðîäà è ïîñòðîéòå ðàñïðåäåëåííûå àëãîðèòìû äëÿ âû÷èñëåíèÿ ïîêàçàíèé ýòèõ ÷àñîâ.Çàäà÷à 6.Äîêàæèòå, ÷òî ñóùåñòâóþò òàêèå ðàñïðåäåëåííûå ñèñòåìû, êîòîðûå íå ñïîñîáíûâû÷èñëÿòü ôóíêöèþ ãëîáàëüíûõ ÷àñîâ Θg .Çàäà÷à 7.Ïîêàæèòå, ÷òî ôóíêöèÿ Ëýìïîðòà ΘL äåéñòâèòåëüíî ÿâëÿåòñÿ ÷àñàìè.Çàäà÷à 8.Ìîæíî ëè ïîñòðîèòü òàêóþ ôóíêöèþ ÷àñîâ Θ, êîòîðàÿ1. ìîãëà áûòü âû÷èñëåíà ðàñïðåäåëåííûì àëãîðèòìîì;2. äëÿ ëþáîãî âû÷èñëåíèÿ è äëÿ ëþáûõ äâóõ ñîáûòèé a è b â ýòîì âû÷èñëåíèèîáëàäàëà ñâîéñòâîìa ≺ b ⇐⇒ Θ(a) < Θ(b).1Çàäà÷à 9.Âåðíî ëè, ÷òî óòâåðæäåíèå, êîòîðîå ÿâëÿåòñÿ èñòèííûì â êàæäîé êîíôèãóðàöèèëþáîãî âûïîëíåíèÿ, îáÿçàòåëüíî ÿâëÿåòñÿ èíâàðèàíòîì?Çàäà÷à 10.Ïðèâåäèòå ïðèìåð òàêîé ñèñòåìû ïåðåõîäîâ S è òàêîãî óòâåðæäåíèÿ P , ÷òî Pâñåãäà èñòèííî â ñèñòåìå S , íî ïðè ýòîì íå ÿâëÿåòñÿ èíâàðèàíòîì S .Çàäà÷à 11.Ïðåäïîëîæèì, ÷òî P1 è P2 ýòî èíâàðèàíòû ñèñòåìû S .

Äîêàæèòå, ÷òî (P1 ∨ P2 )è (P1 ∧ P2 ) òàêæå ÿâëÿþòñÿ èíâàðèàíòàìè.Çàäà÷à 12.Ïóñòü S ïàðàëëåëüíàÿ êîìïîçèöèÿ ñèñòåì S1 è S2 .Äîêàæèòå, ÷òî âñÿêèé èíâàðèàíò P ñèñòåì S1 è S2 òàêæå ÿâëÿåòñÿ èíâàðèàíòîì ñèñòåìû S .Äîêàæèòå, ÷òî âñÿêàÿ Q-ïðîèçâîäíàÿ P ñèñòåì S1 è S2 òàêæå ÿâëÿåòñÿ Q-ïðîèçâîäíîéñèñòåìû S .Ïðèâåäèòå ïðèìåð óòâåðæäåíèÿ P , êîòîðîå ÿâëÿåòñÿ âñåãäà èñòèííûì â îáåèõ ñèñòåìàõ S1 è S2 , íî íå ÿâëÿåòñÿ òàêîâûì â ñèñòåìå S .Çàäà÷à 13.Ïîêàæèòå, ÷òî ñèììåòðè÷íûé ïðîòîêîë ðàçäâèæíîãî îêíà íå óäîâëåòâîðÿåò òðåáîâàíèþ íåèçáåæíîé äîñòàâêè ñîîáùåíèÿ, åñëè èç äâóõ äîïóùåíèé ñïðàâåäëèâîñòèF1 è F2 âûïîëíÿåòñÿ òîëüêî äîïóùåíèå F2.Çàäà÷à 14.Áóäåò ëè ñèììåòðè÷íûé ïðîòîêîë ðàçäâèæíîãî îêíà óäîâëåòâîðÿòü òðåáîâàíèþíåèçáåæíîé äîñòàâêè ñîîáùåíèÿ, åñëè áóäåò âûïîëíÿòüñÿ òîëüêî äîïóùåíèå F1?Çàäà÷à 15.Äîêàæèòå, ÷òî åñëè â ñèììåòðè÷íîì ïðîòîêîëå ðàçäâèæíîãî îêíà lp + lq = 1 èíà÷àëüíûå çíà÷åíèÿ ïåðåìåííûõ ap è aq ðàâíû −lq è −lp , òî ðàâåíñòâà ap + lq = sp èaq + lp = sq âñåãäà âûïîëíÿþòñÿ.Çàäà÷à 16.Äîêàæèòå ñëåäóþùåå óòâåðæäåíèå.Ëåììà 3.3.Îòïðàâëåíèå ïàêåòà ⟨pack, w, i⟩ ïðîöåññîì p â ïðîòîêîëå ðàçäâèæíîãî îêíà äîïóñòèìî òîëüêî òîãäà, êîãäà i < ap + L.Çàäà÷à 17.Äîêàæèòå ñëåäóþùåå óòâåðæäåíèå.Ëåììà 3.4.Åñëè outp [i] ̸= udef , òî âûïîëíÿåòñÿ íåðàâåíñòâî i < sp + L.Çàäà÷à 18.Äîêàæèòå ñëåäóþùåå óòâåðæäåíèå.Òåîðåìà 3.7.2Óòâåðæäåíèå P ′ , îïðåäåëÿåìîå ñëåäóþùåå ôîðìóëîéP′ ≡∧∧∧∧P⟨pack, w, i⟩ ñëåäóåò çà ⟨pack, w′ , i′ ⟩ â Qp ⇒ i > i′ − L⟨pack, w, i⟩ ñëåäóåò çà ⟨pack, w′ , i′ ⟩ â Qq ⇒ i > i′ − L⟨pack, w, i⟩ ∈ Qp ⇒ i ≥ ap − lp⟨pack, w, i⟩ ∈ Qq ⇒≥ aq − lq(4p)(4q)(5p)(5q)ÿâëÿåòñÿ èíâàðèàíòîì ïðîòîêîëà ðàçäâèæíîãî îêíà ïðè óñëîâèè, ÷òî â êàíàëàõ ñâÿçèïîääåðæèâàåòñÿ î÷åðåäíîñòü ïåðåäàâåìûõ ñîîáùåíèé.Çàäà÷à 19.Ïîêàæèòå, ÷òî â ñëó÷àå L = 1 â ïðîòîêîëå ðàçäâèæíîãî îêíà äîñòàòî÷íî èñïîëüçîâàòü òîëüêî îäíó èç äâóõ ïåðåìåííûõ ap èëè sp (è òîëüêî îäíó èç ïåðåìåííûõ aqèëè sq ).Çàäà÷à 20.Ïî÷åìó íèêàêîé ïðîòîêîë íå ìîæåò ïðåäîñòàâèòü ãàðàíòèè òîãî, ÷òî ñëîâî áóäåòäîñòàâëåíî ïî íàçíà÷åíèþ çà îãðàíè÷åííûé ñðîê âðåìåíè?Çàäà÷à 21.Äîêàæèòå ñëåäóþùåå óòâåðæäåíèå.Òåîðåìà 4.2.Ñëåäóþùåå óòâåðæäåíèå ÿâëÿåòñÿ èíâàðèàíòîì ïðîòîêîëà ñ òàéìåðàìè.P1 ≡∧∧∧∧∧P0¬ cs ⇒ ∀i < B : Ok(i)(9)cs ⇒ ∀i < B + Low : Ok(i)(10)⟨data, true, I, w, ρ⟩ ∈ Mq ⇒ ∀i < B + I : Ok(i) (11)cr ⇒ ∀i < B + Exp : Ok(i)(12)⟨ack, I, ρ⟩ ∈ Mp ⇒ ∀i < B + I : Ok(i)(13)Çàäà÷à 22.Äîêàæèòå ñëåäóþùåå óòâåðæäåíèå.Òåîðåìà 4.4.

Ñëåäóþùåå óòâåðæäåíèå ÿâëÿåòñÿ èíâàðèàíòîì ïðîòîêîëà ñ òàéìåðàìè.P2 ≡∧∧∧∧∧P1⟨data, s, i, w, ρ⟩ ∈ Mq ⇒ U t[B + i] > ρ − µi1 ≤ i2 < B + High ⇒ U t[i1 ] ≤ U t[i2 ]cr ⇒ Rt ≥ U t[pr] + µpr < B + High ∧ (U t[pr] > −µ ⇒ cr)cr ⇒ B + Exp = pr + 1(14)(15)(16)(17)(18)Çàäà÷à 23. ïðîòîêîëå ñ òàéìåðàìè îòïðàâèòåëü ìîæåò çàíåñòè â îò÷åò ñëîâî êàê âîçìîæíîóòðà÷åííîå, â òî âðåìÿ êàê ýòî ñëîâî áûëî áëàãîïîëó÷íî äîñòàâëåíî ïîëó÷àòåëþ.Îïèøèòå âûïîëíåíèå ýòîãî ïðîòîêîëà, â õîäå êîòîðîãî ïðîèñõîäèò ïîäîáíûé ýôôåêò.3Çàäà÷à 24.Ïðåäïîëîæèì, ÷òî â ñâÿçè ñ âûõîäîì èç ñòðîÿ ÷àñîâîãî ìåõàíèçìà, ïîëó÷àòåëü íåìîæåò çàêðûòü ñåàíñ ñâÿçè âîâðåìÿ. Îïèøèòå âû÷èñëåíèå ïðîòîêîëà ñ òàéìåðàìè,â õîäå êîòîðîãî ñëîâî áóäåò óòðà÷åíî, íî îòïðàâèòåëü íå ñìîæåò îòìåòèòü ýòî âîò÷åòå.temÇàäà÷à 25.Îïèøèòå òàêîå âû÷èñëåíèå ïðîòîêîëà ñ òàéìåðàìè, â õîäå êîòîðîãî ïîëó÷àòåëüîòêðûâàåò ñåàíñ ñâÿçè ïîñëå ïîëó÷åíèÿ ïàêåòà ñ ïîðÿäêîâûì íîìåðîì áîëüøèì íóëÿ.Çàäà÷à 26.Ïðîåêòèðîâùèê ñåòè õîòåë áû âîñïîëüçîâàòüñÿ ïðîòîêîëîì ñ òàéìåðàìè, íî ïðèýòîì æåëàåò, ÷òîáû î âîçìîæíî óòðà÷åííûõ ñëîâàõ çàïèñü â îò÷åòå îñóùåñòâëÿëàñüðàíåå.

Äëÿ ýòîãî îí ìîäèôèöèðóåò äåéñòâèå Ep ñëåäóþùèì îáðàçîì:Ep : (* Ñôîðìèðîâàòü îò÷åò îá îøèáêå äëÿ âîçìîæíî óòðà÷åííîãî ñëîâà *){ U t[B + Low] < 0 }begin error[B + Low] := true ; Low := Low + 1 endÁóäåò ëè ìîäèôèöèðîâàííûé òàêèì îáðàçîì ïðîòîêîë óäîâëåòâîðÿòü òðåáîâàíèÿìîòñóòñòâèÿ ïîòåðü è óïîðÿäî÷åíèÿ èëè äëÿ ýòîãî íåîáõîäèìî âíåñòè òàêæå äðóãèåèçìåíåíèÿ?Êàêîâû, ïî Âàøåìó ìíåíèþ, ïðåèìóùåñòâà è íåäîñòàòêè óêàçàííîé ìîäèôèêàöèè?Çàäà÷à 27.Äîïóñòèì, ÷òî òàáëèöû ìàðøðóòèçàöèè òàê îáíîâëÿþòñÿ ïîñëå êàæäîãî èçìåíåíèÿ òîïîëîãè÷åñêîé ñòðóêòóðû ñåòè, ÷òî îíè îñòàþòñÿ àöèêëè÷åñêèìè ïî õîäó îáíîâëåíèÿ.

Ìîæåò ëè ýòî ñëóæèòü ãàðàíòèåé òîãî, ÷òî ïàêåòû âñåãäà äîñòàâëÿþòñÿ ïîàäðåñó äàæå â òîì ñëó÷àå, êîãäà ñåòü ïðåòåðïåâàåò áåñêîíå÷íî áîëüøîå êîëè÷åñòâîòîïîëîãè÷åñêèõ èçìåíåíèé?Çàäà÷à 28.Äîêàæèòå, ÷òî íè îäèí àëãîðèòì ìàðøðóòèçàöèè íå ñïîñîáåí îáåñïå÷èòü äîñòàâêó ïàêåòîâ ïî àäðåñó, åñëè ñåòü èñïûòûâàåò íåïðåðûâíûå èçìåíåíèÿ òîïîëîãèè.Çàäà÷à 29.Çà÷åì â àëãîðèòìå ìàðøðóòèçàöèè Òóýãà íóæíî ïåðåäàâàòü â êàæäîì ñîîáùåíèèèìÿ òåêóùåé îïîðíîé âåðøèíû w?Çàäà÷à 30.Ìîæíî ëè èñêëþ÷èòü èç àëãîðèòìà Òóýãà îòïðàâëåíèå ñîîáùåíèé ⟨nys, w⟩? Áóäåòëè ìîäèôèöèðîâàííûé òàêèì îáðàçîì àëãîðèòì êîððåêòíûì?Çàäà÷à 31.Äîêàæèòå, ÷òî ïðèâåäåííàÿ íèæå ôîðìóëà çàäàåò èíâàðèàíò àëãîðèòìà ×àíäèÌèñðû âû÷èñëåíèÿ ïóòåé, âåäóùèõ â âåðøèíó v0 .∀u, w : ⟨mydist, v0 , d⟩ ∈ Mwu ⇒ d(w, v0 ) ≤ d∧ ∀u : d(u, v0 ) ≤ Du [v0 ]4Çàäà÷à 32. îïèñàíèè àëãîðèòìà ×àíäèÌèñðû íå óêàçûâàåòñÿ, äî êàêèõ ïîð äîëæíî ïðîâîäèòüñÿ âû÷èñëåíèå ìàðøðóòîâ â êàæäîì ïðîöåññå.

Äîêàæèòå, â ëþáîé êîíôèãóðàöèèëþáîãî âûïîëíåíèÿ àëãîðèòìà ×àíäèÌèñðû ïðîìåæóòî÷íûå òàáëèöû ìàðøðóòèçàöèè ÿâëÿþòñÿ àöèêëè÷åñêèìè. ×òî íóæíî äîáàâèòü ê àëãîðèòìó ×àíäèÌèñðû,äëÿ òîãî ÷òîáû êàæäûé ïðîöåññ ìîã óçíàòü, ÷òî ïîñòðîåíèå òàáëèö ìàðøðóòèçàöèèâ ñåòè çàâåðøåíî.Çàäà÷à 33.Âûÿñíèòå, êàêèå çíà÷åíèÿ áóäóò èìåòü âñå ïåðåìåííûå â çàêëþ÷èòåëüíîé êîíôèãóðàöèè àëãîðèòìà Netchange â òîì ñëó÷àå, êîãäà ýòîò àëãîðèòì ïðèìåíÿåòñÿ êñåòè, èìåþùåé ñëåäóþùóþ òîïîëîãè÷åñêóþ ñòðóêòóðó:ABCDEFÏîñëå òîãî êàê áûëà äîñòèãíóòà çàêëþ÷èòåëüíàÿ êîíôèãóðàöèÿ, â ñåòè âîçíèê íîâûéêàíàë ñâÿçè ìåæäó óçëàìè A è F . Êàêîå ñîîáùåíèå óçåë F îòïðàâèò óçëó A ïðèîáðàáîòêå óâåäîìëåíèÿ ⟨repair, A⟩? Êàêîå ïîñëàíèå óçåë A îòïðàâèò óçëó F â îòâåòíà ýòî ñîîáùåíèå?Çàäà÷à 34.Ïîêàæèòå, ÷òî â êàæäîì âû÷èñëåíèè äðåâåñíîãî àëãîðèòìà â òî÷íîñòè äâà ïðîöåññà ïðèíèìàþò ðåøåíèå.Çàäà÷à 35.Ïðèâåñòè ïðèìåð ñåòè, â êîòîðîé ïðîèçâîëüíûé âîëíîâîé àëãîðèòì ïðîèçâåäåòðîâíî N îáìåíîâ ñîîáùåíèÿìè, ãäå N ÷èñëî ïðîöåññîâ â ñåòè.Çàäà÷à 36.Ïðèâåñòè ïðèìåð ñåòè, â êîòîðîé ïðîèçâîëüíûé âîëíîâîé àëãîðèòì ïðîèçâåäåòðîâíî K îáìåíîâ ñîîáùåíèÿìè, ãäå K ÷èñëî êàíàëîâ â ñåòè.Çàäà÷à 37.Ïðèäóìàòü êîëüöåâîé àëãîðèòì ñ äâóìÿ èíèöèàòîðàìè è äîêàçàòü åãî êîððåêòíîñòü.Çàäà÷à 38.Ïðèäóìàòü êîëüöåâîé àëãîðèòì ñ äâóìÿ èíèöèàòîðàìè è äîêàçàòü åãî êîððåêòíîñòü.Çàäà÷à 39. äîêàçàòåëüñòâå ôàçîâîãî àëãîðèòìà äîêàçûâàåòñÿ, ÷òî îòíîøåíèå f ( i)pq ≼ g ( i)pqñîõðàíÿåòñÿ äàæå åñëè êàíàë pq íå ÿâëÿåòñÿ î÷åðåäüþ.Ïîêàçàòü, ÷òî äàííîå îòíîøåíèå ñîõðàíÿåòñÿ äàæå åñëè êàíàë pq ÿâëÿåòñÿ êàíàëîì ñ ïîòåðåé ñîîáùåíèé.5Ïîêàçàòü, ÷òî äàííîå îòíîøåíèå íå ñîõðàíÿåòñÿ åñëè â êàíàëå pq ñîîáùåíèÿ ìîãóòäóáëèðîâàòüñÿ.Çàäà÷à 40.Ïîêàçàòü, ÷òî ìîäèôèöèðîâàííûé ôàçîâûé àëãîðèòì, êîòîðûé âûðàáàòûâàåò ðåøåíèå ïîñëå ïðèíÿòèÿ D − 1 ñîîáùåíèé îò êàæäîãî ñîñåäà íà âõîäå, íå ÿâëÿåòñÿâîëíîâûì àëãîðèòìîì.Çàäà÷à 41.Ïðåäïîëîæèì, ÷òî Âû íàìåðåâàåòåñü èñïîëüçîâàòü âîëíîâûå àëãîðèòìû â ñåòÿõñ äóáëèðîâàíèåì ñîîáùåíèé â êàíàëàõ.• Êàêèå èçìåíåíèÿ íåîáõîäèìî âíåñòè â àëãîðèòì Ýõà.• Êàêèå èçìåíåíèÿ íåîáõîäèìî âíåñòè â àëãîðèòì Ôèííà.Çàäà÷à 42.Ïðèâåñòè âû÷èñëåíèå àëãîðèòìà Òàðè, â ðåçóëüòàòå êîòîðîãî ïîëó÷àåòñÿ äåðåâî,íå ÿâëÿþùååñÿ äåðåâîì ïîèñêà â ãëóáèíó.Çàäà÷à 43.Àäàïòèðóéòå àëãîðèòì ýõà äëÿ âû÷èñëåíèÿ ñóììû âõîäíûõ äàííûõ âñåõ ïðîöåññîâ.Çàäà÷à 44.Äîêàçàòü òåîðåìó.Òåîðåìà.