1. Существует оптимальное решение, соответствующее одному из углов многогранника

Отметим, что в выражении стоимости 1020 − 2 × АЮ − 5 × БЮ в нашем примере оптимальные значения АЮ и БЮ не зависят от слагаемого 1020. Решение будет то же, если мы будем минимизировать −2 × АЮ − 5 × БЮ или максимизировать 2 × АЮ + 5 × БЮ.

Рассмотрим задачу линейного программирования с двумя переменными в общем виде.

Заметьте, что, во-первых, задача максимизации эквивалентна задаче минимизации с коэффициентами −с1 и −с2. Во-вторых, любое неравенство со знаком ≤ можно превратить в эквивалентное неравенство со знаком ≥, умножив обе части неравенства на –1. Поэтому задача выше, для двух переменных и m ограничений, сформулирована действительно в общем виде. Все значения коэффициентов a, b, с – произвольные действительные числа, которые могут быть как положительными, так и отрицательными.

Каждое ограничение задает полуплоскость значений, на которой оно выполняется. Если пересечение всех m полуплоскостей пусто, то допустимого решения просто не существует. Поэтому допустим, что m полуплоскостей содержат общую ограниченную область S допустимых значений. (Мы не будем рассматривать случай, когда область не ограничена.) Очевидно, что S – это многоугольник, поскольку область S ограничена прямыми.

Утверждение. Максимальное значение целевой функции достигается в одном из углов S.

Доказательство. Обозначим оптимальное решение через x*1, x*2. Заметьте, что x*1, x*2 не может быть внутренней точкой S, потому что в этом случае оба значения переменных можно либо увеличить, либо уменьшить, таким образом увеличивая значение целевой функции. Например, в нашей задаче в решение (58,8) является внутренней точкой, поэтому не может быть оптимальным.

Значит, x*1, x*2 лежит на одной из сторон многоугольника S. На каждой из сторон одно из ограничений превращается в равенство. Рассмотрим сторону, которая соответствует первому ограничению: a11x1 + a12x2 = b1. Что происходит, если мы начнем двигаться вдоль этой стороны?

Не уменьшая общности, допустим, a12 ≠ 0. Для начала перепишем равенство в более привычном виде как уравнение прямой:

Допустим, мы начали в точке (x1,x2). Теперь допустим, что мы немного изменили х1 и получили новую координату x1+δ, где δ>0 достаточно мало, чтобы все остальные ограничения, кроме первого, по-прежнему строго выполнялись. Тогда значение х2 изменится на величину

При этом нетрудно проверить, что целевая функция изменится на величину

Заметьте, что это число не зависит от (x1,x2). Значит, в какой бы точке прямой (П.1) мы не начали движение, в результате перемещения по этой прямой, изменение значения целевой функции зависит только от коэффициента

Если он отрицательный, то, увеличивая x1 и двигаясь по прямой, мы можем только уменьшить целевую функцию. Аналогично если коэффициент положительный, то, двигаясь по прямой в сторону увеличения x1, мы можем целевую функцию только увеличить. Наконец, если коэффициент равен нулю, значение целевой функции на всей прямой постоянно.

Стало быть, из любой точки на данной стороне S мы можем двигаться либо в сторону уменьшения, либо в сторону увеличения x1 так, чтобы значение целевой функции не уменьшалось. Таким образом мы можем менять значение x1, пока какое-то другое ограничение не превратится в равенство. В этом случае мы столкнулись с углом многоугольника S, в котором достигается максимальное значение целевой функции на всей рассмотренной нами стороне. Поскольку сторону мы выбрали произвольно, делаем вывод, что максимальное значение целевой функции достигается в одном из углов S и мы можем выбрать этот угол в качестве x*1, x*2.

Очевидно, что это доказательство легко обобщить на любое количество n переменных.

 

2. Пример задачи целочисленного программирования

Допустим, нам нужно отправить грузовики с товаром к двум разным клиентам. Всего у нас в разных точках четыре грузовика. Обозначим через cij цену отправки грузовика i=1,2,3,4 к клиенту j=1,2. На любую доставку требуется полдня. Доставку можно осуществить либо утром (первая половина дня), либо днем (вторая половина дня). Нужно решить, к какому клиенту какой грузовик поедет и в какой момент времени.

Введем переменные x ijt , i =1,2,3,4; j=1,2; t=1,2. Эти переменные могут принимать значение 0 или 1. Например, если грузовик 3 едет к клиенту 2 в первой половине дня, то x321=1. Если этого не происходит (то есть грузовик 3 в первой половине дня никуда не едет или едет к другому клиенту), то x321=0.

В нашей небольшой задаче всего 4×2×2=16 переменных, то есть ее можно решить и вручную.

Целевая функция – это цена доставки, и вычисляется она очень просто:

Например, если грузовик 3 едет к клиенту 2 в первой половине дня, то x321 = 1 и мы прибавим к общей стоимости c32. А если грузовик 3 к клиенту 2 не поедет, тогда x321 = x322 = 0 и c32 не войдет в общую сумму.

Самое интересное – это ограничения. Например, грузовик i не может поехать к двум клиентам в одно и то же время. Это можно записать в виде ограничения:

x i1t + x i2t ≤, i =1,2,3,4; t =1,2.

Тогда для любого i и t только одно (или ни одно) из значений хi1t или хi2t может равняться единице.

Еще одно универсальное ограничение: к клиенту j нужно послать только один грузовик, то есть

Ограничения могут учитывать особенности каждого грузовика, клиента и другие факторы. Например, мы не хотим, чтобы грузовик 3 работал утром (скажем, у этого грузовика запланирован техосмотр). Тогда мы просто включим ограничение:

x 311 + x 321 = 0.

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

c штраф ( x 311 + x 321 ).

Заметьте, что это слагаемое действительно добавится, только если грузовик 3 работал в утреннюю смену. Естественно, оптимальное решение будет зависеть от коэффициента cштраф. Если он больше любого c ij в целевой функции, то оптимальный вариант – не задействовать грузовик 3 с утра. А если коэффициент сштраф маленький, то, возможно, грузовик 3 все равно задействуют, если это обеспечит более низкую цену доставки.

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

x 311 + x 321 = x 312 + x 322 . (П.2)

Это условие можно несколько усложнить. Например, если грузовик 3 в первой половине дня поехал к клиенту 1, то мы хотим, чтобы он работал и во второй половине дня. Как это записать в виде линейного неравенства? Часто используется такой прием. Вводим достаточно большое значение М и записываем:

(x 311 + x 321 ) − ( x 312 + x 322 ) ≤ M (1 − x 311 ).

Если x311=1, то значение справа при любом М равно нулю. Тогда неравенство выполняется (и на самом деле является равенством), только если x312 + x322=1 (вспомните, что x311 + x321=1). Но если x311=0, то М можно выбрать достаточно большим, чтобы ограничение не играло никакой роли. В данном случае, кстати, достаточно, чтобы М=1. Для увеличения скорости решения М стараются выбирать «экономно» – не больше, чем нужно.

Есть еще множество интересных приемов записи обязательных и желательных условий в виде линейных выражений, но их более подробное описание выходит за рамки нашей книги.

 

3. Идея метода ветвей и границ

Допустим, нам нужно послать землекопов на объекты и мы хотим минимизировать стоимость работ. Для начала мы берем совершенно произвольное расписание и получаем стоимость работ, скажем 50 000 рублей. Это наш максимум, и мы постараемся его уменьшить.

Теперь запускаем симплекс-метод и получаем дробное решение. Например, на объект А нужно отправить 2 и 2/3 землекопа. Допустим, общая стоимость работ при этом составит 40 000 рублей. Это пока не дает нам плана работ, потому что решение не в целых числах. Зато мы знаем, что это решение оптимальное, то есть при любом другом (в том числе целочисленном) решении стоимость получится никак не меньше 40 000 рублей. Значит, наша стоимость в результате будет между 40 000 и 50 000 рублей.

Дальше начинаем «разветвлять» решение. У нас есть два варианта: A ≤ 2 и A ≥ 3. Для каждого из них мы снова решаем задачу линейного программирования. Допустим, стоимость получилась 43 000 рублей при A ≥ 3 и 51 000 при A ≤ 2. Отсекаем вариант A ≤ 2, поскольку у нас уже есть более выгодное решение. В результате делаем вывод, что A ≥ 3, а минимальная стоимость теперь 43 000 рублей. Если при этом все переменные получились целочисленные, то мы нашли решение. А если у нас еще остались дробные переменные, то каждую из них разветвляем снова. И так до тех пор, пока не найдем решения в целых числах.

 

1. Число последовательностей из нулей и единиц заданной длины

Для начала рассмотрим последовательности длины 5. Сколькими способами мы можем выбрать первый элемент последовательности? Очевидно, что вариантов 2: ноль или единица. Теперь давайте посмотрим на второй элемент. Для него у нас тоже есть два варианта, причем при любом выборе первого элемента последовательности. Значит, число способов выставить друг за другом первые два элемента равно четырем. Точно так же для каждого из этих четырех вариантов есть два способа выбрать третий элемент последовательности и так далее. В итоге для кодового слова длины 5 получаем

2 × 2 × 2 × 2 × 2 = 2 5 = 32.

Аналогично число разных последовательностей длины 4 равно 24 = 16, а число разных последовательностей длины 8 равно 28 = 256. Для любой заданной длины n получаем 2n разных последовательностей из нулей и единиц.

 

2. Граница Хэмминга

Допустим, мы пользуемся словами длиной n и наш код состоит из N таких слов.

Если код исправляет d ошибок, то шары Хэмминга с центрами в кодовых словах и радиусами d попарно не пересекаются. Объем шара (то есть количество слов в нем) нетрудно вычислить. Сколько слов отстают от центра шара на заданное расстояние k? Разумеется, столько, сколькими способами можно выбрать те k позиций из n возможных, в которых произойдут помехи. Это число способов называется числом сочетаний из п по k и обозначается C k n . Для того чтобы его записать, нам понадобятся произведения вида

k × (k − 1) × … × 2 × 1.

Такое произведение принято обозначать записью

k !

и она читается как k факториал. Легко увидеть, что, конечно, 1! = 1, и принято считать, что 0! = 1. Заметим, что факториал уже встречался нам в главе 2 в разделе . Там мы показали, что факториал растет очень быстро. Например, 25! – это колоссальное число.

Число сочетаний вычисляется по формуле

Мы приводим вывод этой известной формулы ниже, в приложении 3. Легко проверить, скажем, что C¹ n , и действительно мы можем выбрать одну позицию из n ровно n способами.

Значит, всего внутри шара

слов. Здесь слагаемое C0n =1 – это число слов, отстоящих от центра на расстояние 0. Такое слово только одно – сам центр. Поскольку шары с центрами в кодовых словах попарно не пересекаются, то всего в них находится

различных слов. Но это количество заведомо не превосходит числа всех возможных кодовых слов, которое, как мы уже знаем, равно 2n. Таким образом,

Эта формула и есть граница Хэмминга. В нашем примере, когда n = 10, d = 2, получаем

Всего последовательностей длины 10 ровно 210 = 1024. Получается, что максимальное количество кодовых слов не превышает 1024 ÷ 56 ≈ 18,2857. Поскольку число кодовых слов целое, оно не больше 18.

 

3. Число сочетаний из

n

по

k

Мы рассмотрим число сочетаний на примере, связанном с кодированием. Давайте попробуем сосчитать, сколько существует слов длины n и веса k, k ≤ n. Напомним, что слово – это запись из нулей и единиц, а его вес – это количество единиц. Значит, нам нужно выбрать из n позиций k штук для расстановки на этих k выбранных позициях единиц. При этом ясно, что как только позиции будут выбраны, кодовое слово определяется однозначно. Выбрали, скажем, из шести позиций первую, четвертую и пятую – все, появилось кодовое слово 100110.

Хорошо, допустим, есть n позиций. Выбираем из них любую. Это можно сделать n способами. Для каждого из этих n способов выбора первой позиции из оставшихся n − 1 позиций снова выбираем любую. Для этого уже есть только n − 1 вариант. Итого количество способов зафиксировать первую и вторую позиции для единиц равно n (n − 1). Точно так же три позиции можно последовательно выбрать одним из n (n − 1) (n − 2) способов. И так далее. Для данного k будет всего

n (n − 1) (n − 2) × … × (n − k + 1)

вариантов. Это и есть ответ? Не совсем!

Заметим, что в нашем примере, где n = 6 и k = 3, мы могли сначала выбрать, например, первую позицию, затем – четвертую и наконец – пятую, а могли сперва выбрать четвертую позицию, затем – пятую и лишь в конце – первую. И для каждого из подобных вариантов у нас получится одно и то же кодовое слово 100110. Сколько же раз в нашей формуле n (n − 1) (n − 2) × … × (n − k + 1) мы тем самым посчитали одно и то же кодовое слово? Смотрите, получая эту формулу, мы выбирали какие-то последовательности номеров позиций: допустим, это были 1-4-5, 1-5-4, 5-1-4, 5-4-1, 4-1-5, 4-5-1. Видно, что все эти последовательности дают одно и то же слово из нулей и единиц. И видно, что их 6. Чтобы снова прийти к этому выводу не путем унылого перебора (которым мы сейчас занимались), а «весело и с умом», надо рассудить так: из трех чисел 1, 4, 5 мы можем сначала выбрать любое (3 варианта); затем вслед за ним расположить второе уже только одним из двух способов, а третье выбирается однозначно. Рассуждение дает нужный результат: число способов упорядочить числа 1, 4, 5 равно 3 × 2 × 1 = 6. Аналогично для любого k возникает формула k (k − 1) × … × 2 × 1 = k!. Напомним: по принятой в математике конвенции 0! = 1.

Что же мы имеем в итоге? Сначала мы вывели формулу n (n − 1) (n − 2) × … × (n − k + 1), потом сообразили, что в ней каждое множество позиций для единиц учтено k! раз. Это означает, что искомое количество кодовых слов равно

Заметим, что найденное выражение можно переписать в виде

Это так называемое число сочетаний из n по k, или биномиальный коэффициент. В настоящее время для него приняты два обозначения:

 

В качестве дополнительного материала к этой главе рекомендуем книгу Андрея «Модели случайных графов». Там в подробностях приводится доказательство теоремы Эрдеша – Реньи и много других интересных результатов из теории случайных графов.

 

1. Вероятность потери связи в мини-сети

Рассмотрим мини-сеть как в примере, приведенном в главе: три компьютера – 1, 2, 3 и три канала связи: 1–2, 1–3, 2–3. Допустим, что канал связи доступен с вероятностью р и недоступен с вероятностью 1 − p, где 0 < p < 1. Предположим, что каналы независимы друг от друга. Связь между всеми тремя компьютерами сохраняется в двух случаях.

Случай 1. Все три канала связи доступны. Соответствующая вероятность равна

Вероятности перемножаются потому, что каналы независимы друг от друга. Допустим, у нас тысяча мини-сетей и p = 0,6. Тогда примерно в 600 из них будет доступен канал 1–2. Поскольку доступность канала 1–2 никак не влияет на канал 1–3, из нашей 1000 сетей оба канала 1–2 и 1–3 будут доступны в среднем 600 × 0,6 = 360 случаев. Чтобы вычислить среднее количество сетей, в которых доступны все три канала, надо взять долю 0,6 от 360, получаем 360 × 0,6 = 216. В результате вероятность доступности всех трех каналов равна

Случай 2. Два канала связи доступны и один недоступен. Недоступным может быть любой из трех каналов связи, поэтому случай 2 можно получить тремя разными способами. В результате соответствующая вероятность равна

Общая вероятность сохранения связи в сети теперь равна

(П.3) + (П.4) = p ³ + 3p ² (1 − p ) = 3p ² −2p ³.

Потеря связи хотя бы с одним из компьютеров тоже происходит в двух случаях, которые мы назовем случай 3 и случай 4.

Случай 3. Два канала связи недоступны и один доступен. Заметьте, что этот случай совершенно аналогичен случаю 2, только р и (1 − p) поменялись местами. Соответствующая вероятность равна

3 (p − 1)² p . (П.5)

Случай 4. Все три канала связи недоступны. Этот случай опять же аналогичен случаю 1, если поменять местами р и (1 − p). Соответствующая вероятность равна

(1 − p )³. (П.6)

Вероятность, что хотя бы один компьютер окажется отрезанным от сети, равна

(П.5) + (П.6) = 3(1 − p )² − 2(1 − p )³. (П.7)

Естественно, если просуммировать все вероятности, то получится единица. Это очень красиво следует из бинома Ньютона третьей степени:

(П.3) + (П.4) + (П.5) + (П.6) = p ³ + 3p ² (1 − p ) + 3(p − 1)² p + (1 − p )³ = (p + (1 − p ))³ = 1³ = 1

Если провести еще немножко алгебраических манипуляций, то можно переписать вероятность (П.7) по-другому:

3(1 − p )² − 2(1 − p )³ = (1 − p )² (3 − 2(1 − p )) = (1 − p )² (1 + 2p ) = (1 − p ) ((1 − p ) (1 + 2p )) = (1 − p ) (1 + p − 2p ²)

Легко проверить, что если p > ½, то вторая скобка меньше единицы. Получается, что если p > ½, то вероятность потери связи в мини-сети меньше, чем вероятность потери связи в отдельно взятом канале, которая равна (1 − p).

Кроме того, выражение (П.7) всегда меньше, чем 3 (1 − p)². Поэтому если вероятность неисправности канала (1 − p) уменьшается, то вероятность потери связи в сети уменьшается еще быстрее. Когда вероятность (1 − p) очень мала, то термином −2 (1 − p)³ можно пренебречь. Тогда вероятность потери связи в сети приблизительно равна 3 (1 − p)². Если (1 − p) = 0,01 (то есть 1 %), то эта формула верна до третьего знака после запятой, что мы и видим в последней строчке .

 

2. Теорема Эрдеша – Реньи о фазовом переходе

Теорема (Эрдеша – Реньи). Допустим, граф состоит из п вершин. Предположим, что ребра независимы друг от друга и любые две вершины соединены ребром с вероятностью р(п). Обозначим вероятность помехи через q(n) = 1 − p(n) и предположим, что

(i) Если c > 1, то вероятность связности стремится к единице при п, стремящемся к бесконечности, причем скорость стремления к единице тем выше, чем больше число с. Например, при c ≥ 3 скорость стремления к единице не ниже, чем у выражения 1 − 1/n, как в разделе в главе 4.

(ii) Если c < 1, то вероятность связности стремится к нулю при п, стремящемся к бесконечности, причем скорость стремления к нулю тем выше, чем меньше число с.

(iii) При c = 1 вероятность связности стремится не к нулю и не к единице, а к числу e−1 ≈ 0,3679, где e = 2,71828… – основание натурального логарифма.

 

3. Идея доказательства результата Эрдеша – Реньи

Допустим, граф состоит из n вершин. Предположим, что ребра независимы друг от друга и любые две вершины соединены ребром с вероятностью р(п). Обозначим вероятность помехи через q(n) = 1 − p(n). Рассмотрим одну вершину. Вероятность того, что она не соединена ребром ни с одной из оставшихся n − 1 вершин, равна

(q ( n )) n− 1 .

Поскольку всего вершин п, то в среднем число вершин, которые не соединены ребрами ни с одной другой вершиной, составит

n (q (n ))n− 1 .

Возьмем, как и прежде,

Вспомните один известный замечательный предел

где е – основание натурального логарифма. Интуитивно результат следует из похожего предельного перехода:

Давайте посмотрим, о чем нам говорит эта формула.

Если c < 1, то в среднем число вершин, у которых нет ни одного ребра, стремится к бесконечности. В этом случае таких вершин будет очень много, связность сети с большой вероятностью будет потеряна.

Если c > 1, то в среднем число вершин, у которых нет ни одного ребра, стремится к нулю. Значит, с большой вероятностью таких вершин не будет и связность сети сохранится.

Таким образом, мы видим, откуда появляется фазовый переход!

Наконец, если c = 1, то в среднем число вершин, у которых нет ни одного ребра, равно единице. Заметим, что единица – это среднее значение, а в реальности таких вершин может быть 0, 1, 2… Можно доказать, что соответствующее распределение вероятности близко к закону Пуассона с параметром 1:

Соответственно, вероятность того, что таких вершин не будет, то есть связность сети сохранится, равна е–1.

Добавим, что это еще не строгое доказательство, потому что мы проанализировали только среднее количество вершин, у которых нет ни одного ребра. Для завершения доказательства нужно еще показать, что в случае c < 1 и c > 1 число вершин без ребер относительно мало отклоняется от среднего значения. Для этого разработаны стандартные методы, в частности, основанные на неравенствах Маркова и Чебышева. Эти неравенства названы в честь замечательных русских математиков, стоявших у истоков теории вероятностей.

 

Анализ метода выбора из двух

Допустим, у нас n серверов. Заявки (или задания) поступают с интенсивностью λ n в единицу времени, и каждый сервер в среднем обрабатывает одно задание в единицу времени, то есть загрузка системы равна λ < 1 (если λ ≥1, то система перегружена, очередь будет расти до бесконечности). Рассмотрим случай, когда n очень велико и стремится к бесконечности.

Обозначим через f k долю серверов, у которых ровно k заявок (заявка, которая находится на обслуживании в данный момент, тоже учитывается). Обозначим через u k долю серверов, у которых заявок k или больше. Значения u k можно легко получить через f k и наоборот:

Понятно, что u0 = 1.

Представим, что система находится в равновесии. Тогда у нас в среднем

серверов, на которых ровно k заданий. Все эти серверы обрабатывают задания со скоростью одно задание в единицу времени. Другими словами, количество серверов с k заявками или больше уменьшается на n(u k − u k+1 ) в единицу времени.

Теперь давайте посмотрим, на сколько количество серверов с k заявками или больше увеличивается в единицу времени. Чтобы увеличить число таких серверов, заявки должны поступать на серверы, у которых в данный момент k − 1 заявка. При методе выбора из двух вероятность того, что новое задание попадет на сервер с k или больше заявками, равна

потому что в этом случае оба случайно и независимо выбранных сервера должны иметь k или больше заявок, и для каждого из двух серверов эта вероятность и k . Значит, вероятность того, что новая заявка поступит на сервер, у которого ровно k − 1 заявка, равна

Поскольку заявок в единицу времени поступает λп, то получается, что число серверов с k или больше заявками в единицу времени в среднем увеличивается на

Так как система находится в равновесии, число серверов с k или больше заявками должно оставаться неизменным, то есть (П.9) равняется (П.11). Отсюда получаем уравнение баланса:

Результат, приведенный в работе, говорит, что при определенных общепринятых предположениях о законе поступления заданий и времени их выполнения, в пределе для бесконечного количества серверов, уравнение (П.12) действительно описывает равновесное состояние системы. Это достаточно сложный технический результат. Нетрудно проверить или даже догадаться, что решение уравнения (П.12) задается формулами:

Это так называемый двойной экспоненциальный закон. Двойка в формуле, та самая двойка – вторая степень – из выражения (П.10). Точно так же мы могли бы выбирать не из двух, а из r серверов и получили бы

Интересно заметить, что при тех же предположениях, но случайном выборе одного сервера, изменятся выражения (П.10) и, соответственно, (П.11). Действительно, на этот раз заявка выбирает только один сервер и вероятность попасть на сервер с k или больше заявками равна просто и k . Тогда вместо (П.12) получаем классическое уравнение баланса:

решение которого задается известной формулой Эрланга:

Очевидно, что и k в формуле (П.13) убывает гораздо быстрее.

Именно эти формулы мы использовали в . В нашем случае λ = 0,9, и в таблице мы привели значения f k . В первой колонке – значения k, во второй – значения f k , подсчитанные по формуле (П.14), в третьей – значения f k , подсчитанные по формуле (П.13).

 

1. Схема Диффи – Хеллмана

Для начала введем обозначения. Пусть р – заданное простое число, g – заданное натуральное число, g < p. На самом деле g это так называемый первообразный корень числа р. Об этом мы расскажем ниже, в и к главе 6. Цель данного раздела – доказать, что в схеме Диффи – Хеллмана Алиса и Боб действительно получают один и тот же ключ.

Для любых натуральных чисел n и р мы воспользуемся стандартным обозначением для остатка от деления n на р:

n (mod p ) = [остаток от деления n на p ].

(Читается «n по модулю p».)

Итак, Алиса задумала число х, а Боб число у. Схема Диффи – Хеллмана состоит из двух шагов.

Шаг 1. Алиса передает Бобу

a = (g x ) (mod p ).

Боб передает Алисе

b = (g y ) (mod p ).

Шаг 2. Алиса вычисляет ключ

K A = (b x ) (mod p ).

Боб вычисляет ключ

K B = (a y ) (mod p ).

Утверждение. Боб и Алиса получили один и тот же ключ K = K A = K B .

Доказательство. Нам нужно доказать, что K A = K B . Поскольку а и b – это остатки от деления на р, то существуют такие целые числа k и l, при которых

a = g x − kp , b = g y − lp .

Подставив эти выражения в формулы для ключей, получаем:

K A = (g y − lp )x (mod p ),

K B = (g x − kp) y (mod p ).

Заметим, что в выражении для K A можно расписать (g y − lp)x следующим образом:

где А – это целое число, то есть рА делится на р. Таким образом получаем

K A = ((g y − lp )x ) (mod p ) = ((g y )x + pA ) (mod p ) = (g y )x (mod p ).

Совершенно аналогично для какого-то целого числа B получаем

K B = ((g x − kp )y ) (mod p ) = ((g x )y + pB ) (mod p ) = (g x )y (mod p ).

Результат теперь очевиден, поскольку

(g y )x = g yx = g xy = (g x )y .

 

2. Дискретное логарифмирование

Вспомним, что логарифм числа у по основанию g – это такое число х, для которого выполняется

g x = y .

Легко заметить, что очень похожая операция лежит в основе схемы Диффи – Хеллмана.

После возведения в степень мы берем остаток от деления на р. Как мы уже упоминали выше, в математике такая операция обозначается g x (mod p) (читается «g в степени х по модулю р»). При этом, естественно, g и х натуральные числа и у g нет общих делителей с р.

Одна нетривиальная теорема из теории чисел (см., например,) утверждает, что для каждого простого р существует такое число g, что все числа

разные, то есть служат перестановкой множества 1, 2, …, p − 1 (среди них нет нуля, поскольку g < p и, значит, g х не делится на р). Например,

Из этого следует возможность корректного определения дискретного логарифма, который еще называется индексом. А именно: «логарифм» произвольного числа y ∈ {1, 2, …, p − 1} по основанию g – это тот самый, уникальный, x ∈ {1, 2, …, p − 1}, при котором выполняется g x (mod p) = y. Поскольку для всех x < p остатки разные, то х определяется однозначно. Операция нахождения такого х называется операцией дискретного логарифмирования. Она очень сложная, и никто не знает, можно ли придумать способ ее быстрой реализации.

Как определить такое число g, чтобы все остатки в выражении (П.15) были разные? Число g обладает этим свойством, если оно является первообразным корнем числа р. Мы позволим себе рассказать об этом понятии немножко подробнее.

 

3. Первообразные корни

Есть такая теорема Эйлера: если х и m взаимно просты, то gφ (m) ≡ 1. Здесь a ≡ b, если a − b делится на m. Другими словами, у а и b одинаковый остаток от деления на m. А φ(m) это функция Эйлера, равная количеству чисел, не превосходящих m и взаимно простых с ним. Например, если m = p, где р простое, то φ(p) = p − 1 и теорема Эйлера превращается в малую теорему Ферма.

Условие теоремы Эйлера достаточное, но не необходимое. Вполне может случиться и так, что x a ≡ 1 (mod m), хотя a < φ(m). Самый простой пример такой ситуации – это, конечно, x = 1. Действительно, x a ≡ 1 (mod m) для любых натуральных a и m. Но есть и менее тривиальные примеры. Скажем, p = 5, а 4² = 16 ≡ 1(mod 5), хотя 2 < p − 1 = 4.

Формально число g называется первообразным корнем по модулю m, если

g φ (m) ≡ 1 (mod m ), но g a ≢ 1 (mod m ) при всех a < φ (m) и a ≠ 0.

Пример (отсутствие первообразных корней у m = 2k ). Возьмем m = 2k при k ≥ 3. В этом случае можно показать, что для любого натурального х выполняется

При этом φ(m) = 2k −1 , потому что числа, взаимно простые со степенью двойки, – это все нечетные числа, а их ровно 2k −1 . Значит, для любого х нашлось число

a = 2k −2 < 2k −1 = φ(m),

для которого выполняется x a ≡ 1 (mod m). Получается, что у m = 2k при k ≥ 3 первообразных корней нет.

Теперь мы можем объяснить, почему в качестве m удобно брать простое число р. Для простого р всегда существуют первообразные корни. На самом деле мы уже говорили о них выше, в , только не называли этим термином. Это те самые числа g, которые дают разные остатки от деления на p в (П.15). Например, при p = 3 это g = 2, при p = 5 это g = 2, а при p = 7 это g = 3. В нашем примере в тексте главы число g = 2 – это один из первообразных корней числа p = 19.

Итак, если g – первообразный корень p, то все остатки в (П.15) разные и каждому остатку соответствует единственная степень х (дискретный логарифм, он же индекс), при которой такой остаток получается. Ничего подобного мы не можем сделать, если будем брать остаток от деления на число m, для которого первообразного корня нет. Именно поэтому работают с простыми числами.

Заметим, что первообразные корни есть еще для m = 4, m = p k и m = 2p k . Но все равно с простыми числами работать проще.

 

Двойной логарифм в HyperLogLog

Хеш-значения – это последовательности из нулей и единиц одинаковой длины. Обозначим длину хеш-значений через т. Тогда получим 2m разных хеш-значений (см. и к ней).

Теперь допустим, что нам нужно сосчитать n различных объектов. Чтобы присвоить им всем разные хеш-значения, понадобится как минимум n хеш-значений, то есть

2 m > n или m > log 2 ( n ).

Стало быть, m должно быть того же порядка величины, что и log2(n).

Алгоритм К-Minimum Values запоминает К самых маленьких хеш-значений длины m, то есть для этого алгоритма нам нужен объем памяти примерно K log2(n).

HyperLogLog запоминает только максимальное количество нулей в начале хеш-значений. Если сами хеш-значения длины m, то и нулей может быть не больше, чем т. Значит, нам нужно держать в памяти число между 0 и m. Оно тоже записывается с помощью последовательности нулей и единиц. Какой длины должны быть эти последовательности? Если последовательности длины l, то мы можем записать 2l разных чисел. Стало быть, чтобы записать m + 1 разных чисел, должно выполняться

2 l = m + 1 или l = log 2 ( m + 1 ) ≈ log 2 ( m ).

В памяти нам нужно держать только l битов информации (последовательность из нулей и единиц длины l). Из предыдущих формул получается:

l ≈ log 2 ( m ) ≈ log 2 log 2 ( n ).

Для повышения точности хеш-значения разбивают на r регистров и запоминают максимальное число нулей в каждом регистре отдельно. В результате требуется порядка r log2 (log2 (n)) битов памяти. Относительная точность оценки задается формулой 1,04÷ √r.

 

Доказательство совместимости по стимулам аукциона второй цены

Рассмотрим аукцион второй цены, на котором один товар разыгрывается между n участниками. Обозначим v i истинную ценность товара для участника i (от английского слова value – ценность). Далее обозначим через b i ставку участника i (от англ. bid – ставка). Эти обозначения будем использовать для любого i = 1,2, …, n.

Совместимость по стимулам означает, что верна следующая теорема.

Теорема (Викри). Участник i получает максимальную прибыль, если b i = v i .

Доказательство. Если участник i получает товар, следовательно, его ставка b i была самой высокой. Поскольку мы имеем дело с аукционом второй цены, то стоимость товара равна самой высокой из оставшихся ставок:

При этом ценность товара для участника i равна v i . Значит, если участник i получает товар, то его прибыль составит

Если участник i товар не получает, он не приобретает никакой ценности и ничего не платит, то есть его прибыль равна нулю.

Дальше доказательство ведется так же, как в разделе в главе 8, и в качестве иллюстрации мы можем по-прежнему использовать и . Допустим, что ставки всех участников, кроме i, фиксированы. Мы покажем, что при правдивой ставке b i = v i прибыль участника i та же или больше, чем при повышенной ставке b i > v i или пониженной b i < v i . Подчеркнем, что это утверждение верно при любых (фиксированных) ставках других участников.

Предположим, что b i > v i . Рассмотрим три случая относительно ставок bj , j ≠i.

1. Допустим, что b i  – самая высокая ставка и, кроме того, все остальные участники поставили меньше, чем v i ( вверху). Тогда товар по-прежнему достается участнику i по стоимости maxj ≠ i b j , и участник i получает точно такую же прибыль (П.16), что и при правдивой ставке v i .

2. Теперь предположим, что другой участник k сделал ставку b k > b i (см. в середине). Тогда участник i товар не получает, его прибыль равна нулю. Но поскольку b i > v i , то и при честной ставке v i участник i тоже не получил бы товар. Значит, в этом случае прибыль участника i при честной ставке тоже равна нулю.

3. Наконец, допустим, что b i  – самая высокая ставка и v i < maxj ≠ i b j < b i (см. внизу). Так как v i < b i , такая ситуация возможна. Она возникает, когда самая высокая ставка других участников выше v i , но ниже b i . Если бы i поставил v i , то i не получил бы товар, прибыль была бы равна нулю. Но теперь b i  – самая высокая ставка, поэтому товар достается i. Прибыль i по-прежнему вычисляется по формуле (П.16), но только прибыль становится отрицательной, поскольку ценность товара меньше его стоимости. Значит, в этом случае прибыль i меньше, чем при честной ставке.

Во всех трех случаях 1–3 участник i не получил прибыль выше, чем при честной ставке v i .

Теперь предположим, что b i < v i , то есть ставка занижает реальную ценность. Опять рассмотрим три случая относительно ставок других участников b j , j ≠i.

1ʹ. Допустим, b i  – самая высокая ставка ( вверху). Тогда товар по-прежнему достается участнику i по стоимости maxj ≠ i b j . В этом случае прибыль участника i та же, что и прежде (П.16). Она в точности такая же, как и при честной ставке v i .

2ʹ. Теперь предположим, что другой участник l сделал ставку b l > v i (рис. 8.3 в середине). В этом случае при честной ставке v i участник i товар не получает.

Но тогда и при заниженной ставке b i < v i участник i не получит товар. Значит, прибыль i равна нулю и при честной, и при заниженной ставке.

3ʹ. Наконец, допустим, что b i < maxj ≠ i b j < v i ( внизу). Так как b i < v i такая ситуация возможна. Она возникает, когда самая высокая ставка других участников выше b i , но ниже v i . Тогда при честной ставке товар достался бы участнику i, и его прибыль, по формуле (П.16), была бы положительной. Но поскольку b i теперь не самая высокая ставка, товар достанется другому участнику и прибыль участника i равна нулю. Значит, в этом случае прибыль i меньше, чем при честной ставке.

Во всех трех случаях 1ʹ–3ʹ участник i не получил более высокую прибыль, чем при честной ставке v i .

В результате делаем вывод, что и при заниженной, и при завышенной ставке участник i получает не больше, чем при честной ставке b i = v i . Таким образом, мы доказали, что в аукционе второй цены выгоднее всего делать честную ставку.