Текст брошюры является переводом статьи «Communication complexity», опубликованной в сборнике «Ап Invitation to Mathematics: From Competitions to Research», D. Schleicher, M. Lackmann (eds.), Springer, 2011, при написании которой использовались материалы курса, прочитанного автором в 2009 году в Летней школе «Современная математика».
В брошюре рассказывается об основных понятиях теории коммуникационной сложности, и приводятся как начальные утверждения этой теории, так и формулировки открытых проблем.
Книга представляет интерес для широкого круга подготовленных читателей, интересующихся математикой.
Первое издание книги вышло в 2012 г.
Вероятностные модели.
Еще более увлекательные и трудные задачи возникают, когда мы переходим к рассмотрению разных вариантов основного определения. Наиболее важный из них и единственный, который мы рассмотрим здесь достаточно подробно, — это модель вероятностной коммуникационной сложности.
Предположим, что Анна и Борис теперь не так требовательны и могут позволить себе ошибиться при вычислении f(х, у) ∈ {0,1} с небольшой вероятностью. Им предоставляется честная монета (выражаясь академическим языком, генератор случайных битов), они могут подбрасывать монету во время исполнения протокола и согласовывать посылаемые друг другу сообщения с результатами подбрасываний. Все остальное остается таким же, как на рис. 1, но теперь необходимо специально объяснить, что значит, что протокол Р корректно вычисляет функцию f.
Бесплатно скачать электронную книгу в удобном формате, смотреть и читать:
Скачать книгу Коммуникационная сложность, Разборов А.А., 2019 - fileskachat.com, быстрое и бесплатное скачивание.
Скачать pdf
Ниже можно купить эту книгу, если она есть в продаже, и похожие книги по лучшей цене со скидкой с доставкой по всей России.Купить книги
Скачать - pdf - Яндекс.Диск.
Дата публикации:
Теги: учебник по математике :: математика :: Разборов
Смотрите также учебники, книги и учебные материалы:
Предыдущие статьи:
