📄Работа №125355
Тема: О некоторых вопросах полудуплексной коммуникационной сложности булевых функций
Тип работы
Бакалаврская работа
Предмет
Математика
Объем:
17 листов
Год:
2022
Просмотров:
48
4800
руб.
🛒 Купить работу
Не подходит эта работа?
Закажите новую по вашим требованиям
Узнать цену на написание
Закажите новую по вашим требованиям
Представленный материал является образцом учебного исследования, примером структуры и содержания учебного исследования по заявленной теме. Размещён исключительно в информационных и ознакомительных целях.
Workspay.ru оказывает информационные услуги по сбору, обработке и структурированию материалов в соответствии с требованиями заказчика.
Размещение материала не означает публикацию произведения впервые и не предполагает передачу исключительных авторских прав третьим лицам.
Материал не предназначен для дословной сдачи в образовательные организации и требует самостоятельной переработки с соблюдением законодательства Российской Федерации об авторском праве и принципов академической добросовестности.
Авторские права на исходные материалы принадлежат их законным правообладателям. В случае возникновения вопросов, связанных с размещённым материалом, просим направить обращение через форму обратной связи.
Настоящий учебно-методический информационный материал размещён в ознакомительных и исследовательских целях и представляет собой пример учебного исследования. Не является готовым научным трудом и требует самостоятельной переработки.
📋 Содержание
Введение 3
1. Обзорный раздел по предметной области 5
1.1. Используемые определения 5
1.2. Используемые факты 6
2. Верхняя оценка на функцию дизъюнктности 8
3. Другие результаты 12
3.1. Функция рекурсивного голосования 12
3.2. Функция четности 13
Заключение 15
Список литературы 16
1. Обзорный раздел по предметной области 5
1.1. Используемые определения 5
1.2. Используемые факты 6
2. Верхняя оценка на функцию дизъюнктности 8
3. Другие результаты 12
3.1. Функция рекурсивного голосования 12
3.2. Функция четности 13
Заключение 15
Список литературы 16
📖 Введение
В классической модели коммуникационной сложности, предложенной Яо [6], два игрока — Алиса и Боб хотят вычислить значение f (х,у) для некоторой булевой функции f. Изначально Алиса имеет только битовую строчку х, а Боб — у. Они могут общаться, посылая друг другу биты, по одному за раунд. В конце коммуникации игроки должны знать результат f (х, у). Например Алиса может отправить все биты своей строки Бобу, после чего он может посчитать значение функции f (х, у) и отправить результат Алисе. Однако обычно существуют более эффективные с точки зрения количества отправленных друг другу битов коммуникационные протоколы.
Важным ограничением классической модели является то, что за один раунд только один игрок может посылать бит. В статье [2] рассматривается расширение модели, суть которого заключается в том, что игрокам позволяется посылать биты одновременно. Такой канал связи называется полудуплексным. Пример такого канала — общение по рации. Особенность этой модели заключается в том, что в один момент времени игрок может либо только говорить, либо только слушать. То есть если собеседники попытаются говорить одновременно, то оба ничего не услышат.
В такой модели каждый раунд каждый игрок совершает одно из следующих действий: отправить 1, отправить 0 или принимать. Если один игрок посылает, а другой принимает, то такой раунд ничем не отличается от классического, его называют нормальным. Если оба игрока посылают биты, то эти биты теряются, будем называть такие раунды потерянными. Если оба игрока принимают, то такие раунды будем называть тихими. В зависимости от канала связи в тихом раунде могут возникать разные ситуации, в связи с этим определены три модели.
• Модель с нулем: оба игрока в тихом раунде получают 0. В этом случае они не могут отличить ноль, полученный от другого игрока, от нуля, полученного в результате тихого раунда. Сложность функции f в этой модели обозначается как Dgd(f).
• Модель с тишиной: в тихом раунде игроки получают специальный символ тишины, то есть, в отличие от случая с тишиной, игроки различают тихие раунды. Сложность функции f в этой модели обозначается как D^d(f).
• Модель с противником: в тихом раунде каждый игрок получает либо 0, либо 1. Можно представить что есть некий противник, который пытается помешать коммуникации, выбирая какой бит Алиса и Боб услышат в тихом раунде. В такой модели игроки не могут отличить тихий раунд от нормального. Сложность функции f в этой модели обозначается как Ddd(f).
Цель данной работы — исследовать описанные выше модели полудуплексной коммуникационной сложности, сравнить их с классической моделью и между собой. Мы получим верхнюю оценку в модели с нулём для функции дизъюнктности, классическая коммуникационная сложность которой уже известна. Это поможет нам понять то, что модели с нулем и противником не равны.
Важным ограничением классической модели является то, что за один раунд только один игрок может посылать бит. В статье [2] рассматривается расширение модели, суть которого заключается в том, что игрокам позволяется посылать биты одновременно. Такой канал связи называется полудуплексным. Пример такого канала — общение по рации. Особенность этой модели заключается в том, что в один момент времени игрок может либо только говорить, либо только слушать. То есть если собеседники попытаются говорить одновременно, то оба ничего не услышат.
В такой модели каждый раунд каждый игрок совершает одно из следующих действий: отправить 1, отправить 0 или принимать. Если один игрок посылает, а другой принимает, то такой раунд ничем не отличается от классического, его называют нормальным. Если оба игрока посылают биты, то эти биты теряются, будем называть такие раунды потерянными. Если оба игрока принимают, то такие раунды будем называть тихими. В зависимости от канала связи в тихом раунде могут возникать разные ситуации, в связи с этим определены три модели.
• Модель с нулем: оба игрока в тихом раунде получают 0. В этом случае они не могут отличить ноль, полученный от другого игрока, от нуля, полученного в результате тихого раунда. Сложность функции f в этой модели обозначается как Dgd(f).
• Модель с тишиной: в тихом раунде игроки получают специальный символ тишины, то есть, в отличие от случая с тишиной, игроки различают тихие раунды. Сложность функции f в этой модели обозначается как D^d(f).
• Модель с противником: в тихом раунде каждый игрок получает либо 0, либо 1. Можно представить что есть некий противник, который пытается помешать коммуникации, выбирая какой бит Алиса и Боб услышат в тихом раунде. В такой модели игроки не могут отличить тихий раунд от нормального. Сложность функции f в этой модели обозначается как Ddd(f).
Цель данной работы — исследовать описанные выше модели полудуплексной коммуникационной сложности, сравнить их с классической моделью и между собой. Мы получим верхнюю оценку в модели с нулём для функции дизъюнктности, классическая коммуникационная сложность которой уже известна. Это поможет нам понять то, что модели с нулем и противником не равны.
✅ Заключение
На примере функции дизъюнктности мы убедились, что модель с противником и модель с нулём отличаются. Результаты данной работы вошли в публикацию [3]. Оценка на полудуплексную коммуникационную сложность функции дизъюнктности не является точной: во всех трёх полудуплексных моделях между верхней и нижней оценкой есть зазор, а в модели с противником нет верхней оценки лучше тривиальной. Будет интересно получить любое улучшение какой-либо из представленных в таблице 5 оценок.
Также известно [3], что классическая и полудуплексная сложности ведут себя по-разному. Например, для функций равенства и внутреннего произведения сложности в классическом случае совпадают, а в полудуплексном — отличаются. На данный момент нельзя утверждать, что полудуплексные коммуникационные сложности функций внутреннего произведения и дизъюнктности отличаются, но очень похоже, что это действительно так. Мы знаем, что Dq^(IP^) > п/ log2(2/(3 — д/5)) « 0.72п и Dq^(DISJn) < 0.75п + о(п). Зазор между этими оценками небольшой, поэтому вполне возможно, что их получится разъединить.
Также известно [3], что классическая и полудуплексная сложности ведут себя по-разному. Например, для функций равенства и внутреннего произведения сложности в классическом случае совпадают, а в полудуплексном — отличаются. На данный момент нельзя утверждать, что полудуплексные коммуникационные сложности функций внутреннего произведения и дизъюнктности отличаются, но очень похоже, что это действительно так. Мы знаем, что Dq^(IP^) > п/ log2(2/(3 — д/5)) « 0.72п и Dq^(DISJn) < 0.75п + о(п). Зазор между этими оценками небольшой, поэтому вполне возможно, что их получится разъединить.
ИЛИ
Поиск аналога
📕 Список литературы
🖼 Скриншоты
🛒 Оформить заказ
⚡ Работу высылаем в течении 5 минут после оплаты.