Лекция 10. Задача избрания лидера. Нижние оценки. Оптимальные выборы. Алгоритм GHS и Корача-Каттена-Морана (1185660), страница 5
Текст из файла (страница 5)
Ìàðêåð äîñòèã ïðîöåññà, â êîòîðîì õðàíèòñÿ ìàðêåð òîãîæå óðîâíÿ, ïðåáûâàþùèé â ðåæèìå îæèäàíèÿ; òîãäà îáàìàðêåðà èçûìàþòñÿ è â ýòîì ïðîöåññå íà÷èíàåòñÿ íîâûéîáõîä.3. Ìàðêåð äîñòèã ïðîöåññà òîãî æå óðîâíÿ, è ïðè ýòîìïîñëåäíèé èç ïîñåòèâøèõ ýòîò ïðîöåññ ìàðêåðîâ ïðåáûâàëâ ðåæèìå ïîãîíè; òîãäà íàø ìàðêåð ïåðåõîäèò â ðåæèìîæèäàíèÿ.Àëãîðèòì Êîðà÷àÊàòòåíàÌîðàíàÏðèíöèï 5.Ìàðêåð â ðåæèìå îæèäàíèÿ îñòàåòñÿ â òîì ïðîöåññå, êîòîðîãîîí äîñòèã, äî òåõ ïîð ïîêà íå ñëîæèòñÿ îäíà èç ñëåäóþùèõñèòóàöèé.Àëãîðèòì Êîðà÷àÊàòòåíàÌîðàíàÏðèíöèï 5.Ìàðêåð â ðåæèìå îæèäàíèÿ îñòàåòñÿ â òîì ïðîöåññå, êîòîðîãîîí äîñòèã, äî òåõ ïîð ïîêà íå ñëîæèòñÿ îäíà èç ñëåäóþùèõñèòóàöèé.1. Ìàðêåð áîëåå âûñîêîãî óðîâíÿ äîñòèãíåò òîãî æå ñàìîãîïðîöåññà; òîãäà îæèäàþùèé ìàðêåð áóäåò ïîäàâëåí.Àëãîðèòì Êîðà÷àÊàòòåíàÌîðàíàÏðèíöèï 5.Ìàðêåð â ðåæèìå îæèäàíèÿ îñòàåòñÿ â òîì ïðîöåññå, êîòîðîãîîí äîñòèã, äî òåõ ïîð ïîêà íå ñëîæèòñÿ îäíà èç ñëåäóþùèõñèòóàöèé.1. Ìàðêåð áîëåå âûñîêîãî óðîâíÿ äîñòèãíåò òîãî æå ñàìîãîïðîöåññà; òîãäà îæèäàþùèé ìàðêåð áóäåò ïîäàâëåí.2.
Ìàðêåð òîãî æå ñàìîãî óðîâíÿ äîñòèã òîãî æå ñàìîãîïðîöåññà; òîãäà îáà ìàðêåðà èçûìàþòñÿ, è â äàííîìïðîöåññå íà÷èíàåòñÿ íîâûé îáõîä áîëåå âûñîêîãî óðîâíÿ.Àëãîðèòì Êîðà÷àÊàòòåíàÌîðàíàÇàäà÷à.IÄîêàçàòü, ÷òî àëãîðèòìÊîðà÷àÊàòòåíàÌîðàíà ÿâëÿåòñÿàëãîðèòìîì èçáðàíèÿ ëèäåðà.Àëãîðèòì Êîðà÷àÊàòòåíàÌîðàíàÇàäà÷à.IIÄîêàçàòü, ÷òî àëãîðèòìÊîðà÷àÊàòòåíàÌîðàíà ÿâëÿåòñÿàëãîðèòìîì èçáðàíèÿ ëèäåðà.Îöåíèòü êîììóíèêàöèîííóþ ñëîæíîñòüàëãîðèòì Êîðà÷àÊàòòåíàÌîðàíà ïðèóñëîâèè, ÷òî â êà÷åñòâå ïðîöåäóðû îáõîäàèñïîëüçóåòñÿ àëãîðèòì Òàððè.ÊÎÍÅÖ ËÅÊÖÈÈ 9..
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
