Экзаменационные задачи (2016) (1185650)
Текст из файла
Çàäà÷à 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.Äîêàçàòü òåîðåìó.Òåîðåìà.
Характеристики
Тип файла PDF
PDF-формат наиболее широко используется для просмотра любого типа файлов на любом устройстве. В него можно сохранить документ, таблицы, презентацию, текст, чертежи, вычисления, графики и всё остальное, что можно показать на экране любого устройства. Именно его лучше всего использовать для печати.
Например, если Вам нужно распечатать чертёж из автокада, Вы сохраните чертёж на флешку, но будет ли автокад в пункте печати? А если будет, то нужная версия с нужными библиотеками? Именно для этого и нужен формат PDF - в нём точно будет показано верно вне зависимости от того, в какой программе создали PDF-файл и есть ли нужная программа для его просмотра.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
