решение задач по теории информации

Работа №1
Задача 1. Дано шесть монет разного веса и известно, что первая
монета легче второй, третья легче четвертой и пятой. Имеются весы,
позволяющие сравнить по весу две любые монеты. Доказать, что
для того, чтобы упорядочить по весу все монеты необходимо и достаточно 8 взвешиваний. (Предупреждение: в доказательстве нижней оценки нужен небольшой перебор).
Решение
Обозначим A, B, C, D, E, F веса монет с 1 по 6-ю. Составим схему при-
менения взвешиваний.

Рис. 1
Эта схема содержит 3 взвешивания. Из этой схемы получаем A < C, A < D, A < E, A < F, E < F. По условию A < B, С < D.
Составим другую схему применения взвешиваний.

Рис. 2
Эта схема содержит 2 взвешивания. Из этой схемы получаем
B < D, B < F.
Составим третью схему применения взвешиваний.

Рис. 3
Эта схема содержит 2 взвешивания. Из этой схемы получаем
B < С, B < E, С < E.
Составим четвертую схему применения взвешиваний.

Рис. 4
Эта схема содержит 1 взвешивание. Из этой схемы получаем
D < F.
Кроме того, по условию С < E.
Алгоритм упорядочения монет по весу содержит в сумме 8 взве- шиваний.
A < B < C < D < E < F.
Таким образом, чтобы упорядочить по весу все монеты необходимо и достаточно 8 взвешиваний.

Задача 4. У Алисы имеется подмножество x множества {1,…,n}, а у
Боба подмножество y множества {1,…,n}. Сколько бит необходимо
передать (от Алисы к Бобу и обратно), чтобы найти мощность объединения x и y? (Ответ нужен с точностью o(n)).

Решение
Мощность объединения множеств определяется формулой
|X∪Y|=|X|+|Y|-|X∩Y|.
Количество бит
N = 2 log2 (|X|+|Y|-|X∩Y|).

Задача 5. Построить детерминированный коммуникационный протокол, который вычисляет функцию GTn, передавая в среднем константу битов. Функция GTn(x,y) определена на парах x,y целых чисел в интервале
(1,…,2n) и принимает значение 1, если x > y и значение 0 иначе. Говоря о среднем, мы имеем в виду, что x, y выбираются случайно и независимо
среди всех чисел указанного интервала с равномерным распределением. Решение
Пусть задана некоторая функция f : X × Y → Z (для конечных X и Y ). Коммуникационным протоколом для вычисления некоторой функции из X×Y в Z называется ориентированное двоичное дерево с корнем и со следующей разметкой на вершинах и рёбрах. Каждая внутренняя вершина дерева помечена буквой A или B. Каждой вершине с пометкой A приписана некоторая функция gi: X → {0, 1}, а каждой вершине с пометкой B приписана некоторая функция hj: Y → {0, 1} (разным вершинам соответствуют, вообще говоря, разные функции gi и hj ). Каждому листу дерева сопоставлен некоторый элемент из Z. Каждое ребро в графе помечено нулём или единицей; из каждой вершины, не являющейся листом, выходит по одному ребру с пометкой 0 и одному ребру с пометкой 1.
Данное определение самым общим образом формализует идею “протокола о намерениях”, заранее подготовленного Алисой и Бобом. Выполнение протокола можно представлять себе так. Пусть Алисе задано некоторое значение x ∈ X, а Бобу некоторое значение y ∈ Y . Поместим в вершину дерева (протокола) фишку. Далее будем перемещать эту фишку вниз по дереву, последовательно удаляясь от корня, пока она не попадём в один из листьев. Перемещение фишки выполняется следующим образом. Пусть текущая вершина помечена буквой A. Это значит, что текущий ход делает Алиса. Она применяет функцию gi для текущей вершины к своему значению x. Если gi(x) = 0, то Алиса посылает Бобу по каналу связи бит 0, и фишка перемещается в соседнюю вершину по исходящему ребру с пометкой 0; если же gi(x) = 1, то Алиса посылает Бобу бит 1, и фишка перемещается по исходящему ребру с пометкой 1. Аналогично, для вершин с пометкой B Боб вычисляет hj (y), посылает значение Алисе, и фишка перемешается в соответствующего сына текущей вершины. Когда фишка попадает в лист дерева, записанное там значение z ∈ Z объявляется результатом выполнения протокола.