2016 Алгоритм Шави-Франчеза_ корректность и сложность (подробное решение) (1185669)

Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла

Новоселов А., гр. 521

Сычева Е., гр. 521

Условие. Теорема 2.

Алгоритм Шави-Франчеза является корректным алгоритмом обнаружения завершения вычисления; в нем используется обменов контрольными сообщениями.

Пояснения.

Теорема 1.

Теорема 3.

Для обнаружения завершения децентрализованного ба­зового вычисления в худшем случае требуется совершить обмен не менее чем контрольными сообщениями, где - коммуникационная сложность волнового алгоритма.

Алгоритм Дейкстры-Шолтена. Теорема 1.

Алгоритм Дейкстры-Шолтена являет­ся корректным алгоритмом обнаружения завершения вычисления; в нем используется обменов контрольными сообщениями.

Алгоритм Шави-Франчеза.

Алгоритм Шави-Франчеза — это обобщенный для случая децентрализованных базовых вычислений алгоритм Дейкстры-Шол­тена.

Алгоритм Шави-Франчеза. Примечания:

1. В приведенном описании волновой алгоритм в явном виде не выделен.

2. Волновой алгоритм запускают только инициаторы базовых вычислений.

3. Все процессы проводят параллельное выполнение волнового алгоритма, причем отправление сообщений или принятие решения разрешается только тем процессам , у которых переменная emptyp имеет значение true.

4. При осуществлении события вызывается процедура .

Алгоритм Шави-Франчеза. Дополнительные обозначения:

Предпосылка Q является инвариантом алгоритма Шави — Франчеза.

Доказательство.

Как при доказательстве Теоремы 1, можно пока­зать, что число сигналов не превосходит числа базовых сообщений . Кроме сиг­налов контрольный алгоритм отправляет только сообщения для одной волны, количество которых равно согласно Теореме 3. Значит, всего будет отправлено не более контрольных сообщений.

Обоснуем необходимое и достаточное условия корректности алгоритма.

Необходимое условие корректности алгоритма

Покажем, что происходит необходимый вызов процедуры оповещения Announce:

• После завершения базового вычисления могут выполняться только действия . А так как уменьшается на единицу при совершении каждого такого перехода, алгоритм достигнет заключительной конфигурации.

• По определению в заключительной конфигурации в множестве отсутствуют сообщения. Кроме того (согласно соотношению (5) предпосылки ) в множестве невожможно наличие пассивных листовые вершины из графа . Следовательно, граф не имеет вообще листовых вершин, а это значит, что граф пуст.

• Так как грав пуст в распространении волны может участвовать каждый процесс. При достижении заключительной конфигурации, все события, присущие этой волне, осуществились, включая хотя бы одно событие принятия решения decide, которое было обязано вызвать процедуру Announce (см. Алгоритм Шави-Франчеза. Примечание 4).

Достаточное условие корректности алгоритма.

Проверка того, что все деревья исчезли, проводится при помощи одной-единственной волны, при этом:

• Процедура оповещения Announce вызывается только при осуществлении события принятия решения decide в волне (см. Алгоритм Шави-Франчеза. Примечание 4).

• Событию принятия решения decide в волне предшествует, по крайней мере, одно событие в каждом процессе: отправления сообщения или принятия решения. При этом каждый процесс принимает участие в распространении волны только тогда, когда его дерево исчезает: отправление сообщений или принятие решения разрешается только тем процессам , у которых переменная имеет значение true (см. Алгоритм Шави-Франчеза. Примечание 3)

• Лес строится так, чтобы всякое дерево , ставшее пустым, оставалось пустым и в дальнейшем: ни один из блоков действий не содержит оператор .

• Во время вызова процедуры оповещения Announce для каждого процесса , переменная имеет значение true, что эквивалентно пустоте (обобщая соотношение (6) предпосылки ). Следовательно, предикат обращается в истину. ◻

Характеристики

Тип файла документ

Документы такого типа открываются такими программами, как Microsoft Office Word на компьютерах Windows, Apple Pages на компьютерах Mac, Open Office - бесплатная альтернатива на различных платформах, в том числе Linux. Наиболее простым и современным решением будут Google документы, так как открываются онлайн без скачивания прямо в браузере на любой платформе. Существуют российские качественные аналоги, например от Яндекса.

Будьте внимательны на мобильных устройствах, так как там используются упрощённый функционал даже в официальном приложении от Microsoft, поэтому для просмотра скачивайте PDF-версию. А если нужно редактировать файл, то используйте оригинальный файл.

Файлы такого типа обычно разбиты на страницы, а текст может быть форматированным (жирный, курсив, выбор шрифта, таблицы и т.п.), а также в него можно добавлять изображения. Формат идеально подходит для рефератов, докладов и РПЗ курсовых проектов, которые необходимо распечатать. Кстати перед печатью также сохраняйте файл в PDF, так как принтер может начудить со шрифтами.

Список файлов курсовой работы