анти. Guide to Competitive

• Название: Guide to Competitive
• Дата: 20.12.2022
• Размер: 2.39 Mb.
• Имя файла: анти.pdf
• Тип: Guide; #854732
• страница: 16 из 26

199
x
1
+ x
2
= 5
x
1
+ x
2
= 7
неразрешима, т. к. уравнения противоречат друг другу. Если у системы нет единственного решения, то алгоритм это обнаружит, потому что на ка- ком-то этапе мы не сможем успешно обработать столбец.
11.4. Вероятность
Вероятностью называется вещественное число от 0 до 1, показывающее, насколько вероятно событие. Если событие произойдет наверняка, то его вероятность равна 1, а вероятность невозможного события равна 0. Веро- ятность события обозначается P(…),где многоточие описывает событие.
Например, бросание игральной кости может завершиться одним из шести исходов: 1, 2, …, 6, и P(«выпало четное число»)=1/2.
Чтобы вычислить вероятность события, мы можем либо воспользовать- ся комбинаторикой, либо смоделировать процесс, порождающий собы- тия. Рассмотрим эксперимент: на стол выкладываются три верхние карты из перетасованной колоды
2
. Какова вероятность, что все три карты будут иметь одинаковое достоинство (например, ♠8, ♣8 и ♦8)?
Можно вычислить вероятность по формуле:
число благоприятных исходов
————————————————————— .
общее число исходов
В нашем примере благоприятными считаются исходы, при которых все три карты имеют одинаковое достоинство. Таких исходов 13(
4 3
), потому что существует 13 способов выбрать достоинство карты и (
4 3
) способов выбрать три масти из четырех. Всего же исходов (
52 3
), поскольку мы выбираем 3 кар- ты из 52. Следовательно, вероятность события равна
4 13 3
1 52 425 3
 
 
 
=
 
 
 
Другой способ вычисления вероятности – смоделировать процесс, по- рождающий события. В нашем случае мы вытаскиваем три карты, поэтому процесс состоит из трех шагов. Требуется, чтобы каждый шаг был успеш- ным.
Вытаскивание первой карты всегда успешно, поскольку нас устраивает любая карта. Второй шаг будет успешным с вероятностью 3/51, потому что осталась 51 карта и 3 из них имеют такое же достоинство, как первая. Точ-
2
В колоде 52 карты. У каждой карты есть масть (пики ♠, бубны ♦, трефы ♣, черви ♥) и достоинство
(целое число от 1 до 13).

200 
Глава 11. Математика но так же третий шаг будет успешным с вероятностью 2/50. Следовательно, вероятность успешного завершения всего процесса равна
3 2
1 1
51 50 425
⋅
⋅
=
11.4.1. Операции с событиями
События удобно представлять с помощью множеств. Например, мно- жество возможных исходов бросания кости {1, 2, 3, 4, 5, 6}, а любое его под- множество является событием. Событию «выпало четное число» соответ- ствует множество {2, 4, 6}.
Каждому исходу x сопоставляется вероятность p(x), а вероятность P(X)
события X вычисляется по формуле:
( )
( ).
x X
P X
p x
∈
=
∑
В случае бросания кости p(x)= 1/6 для любого исхода x, поэтому вероят- ность события «выпало четное число» равна
p(2) + p(4) + p(6) = 1/2.
Поскольку события представлены множествами, мы можем манипули- ровать ими, применяя обычные теоретико-множественные операции.
• Дополнение A означает «A не произошло». Так, при бросании кости дополнение события A = {2, 4, 6} равно Ā = {1, 3, 5}.
• Объединение A ∪ B означает «произошло A или B». Объединением со- бытий A = {2, 5} и B = {4, 5, 6} является A ∪ B = {2, 4, 5, 6}.
• Пересечение A ∩ B означает «произошло A и B». Пересечением собы- тий A = {2, 5} и B = {4, 5, 6} является A ∩ B = {5}.
Дополнение. Вероятность события A вычисляется по формуле
P
( A ) = 1 − P(A).
Иногда дополнения позволяют легко решить задачу, противоположную исходной. Например, вероятность выбросить хотя бы одну шестерку при бросании кости 10 раз равна
1 − (5/6)
10
.
Здесь 5/6 – вероятность выбросить любое число, кроме шести, а (5/6)
10
– вероятность ни разу из десяти не выбросить шестерку. Дополнительная вероятность и есть ответ на исходный вопрос.
Объединение. Вероятность события A ∪ B вычисляется по формуле
P
(A ∪ B) = P(A) + P(B) − P(A ∩ B).

11.4. Вероятность

201
Например, рассмотрим события A = «выпало четное число» и B = «выпа- ло число меньше 4». В этом случае A ∪ B означает «выпавшее число четно или меньше 4», а его вероятность равна
P
(A ∪ B) = P(A) + P(B) − P(A ∩ B) = 1/2 + 1/2 − 1/6 = 5/6.
Если события A и B дизъюнктны, т. е. A ∩ B пусто, то вероятность события
A ∪ B равна просто
P
(A ∪ B) = P(A) + P(B).
Пересечение. Вероятность события A ∩ B вычисляется по формуле
P
(A ∩ B) = P(A)P(B|A),
где P(B|A)– условная вероятность того, что B произойдет, если известно, что A произошло. Так, для событий из предыдущего примера P(B|A)= 1/3, потому что мы знаем, что исход принадлежит множеству, и лишь один из исходов в этом множестве меньше 4. Следовательно,
P
(A ∩ B) = P(A)P(B|A)= 1/2 · 1/3 = 1/6.
События A и B называются независимыми, если
P
(A|B) = P(A) и P(B|A) = P(B),
т. е. тот факт, что B произошло, не изменяет вероятность A, и наоборот.
В этом случае вероятность пересечения равна
P
(A ∩ B) = P(A)P(B).
11.4.2. Случайные величины
Случайной величиной называется значение, порождаемое случайным процессом. Например, в случае бросания двух костей можно определить случайную величину
X = «сумма исходов».
Если имели место исходы [4, 6] (т. е. на первой кости выпала четверка, а на второй шестерка), то значение X равно 10.
Будем обозначать P(X = x)вероятность того, что случайная величина X равна x. Так, при бросании двух костей P(X = 10)= 3/36, поскольку об- щее число исходов равно 36 и существует три способа получить в сумме
10: [4, 6], [5, 5], [6, 4].
Математическое ожидание. Математическое ожидание E[X] описывает среднее значение случайной величины X. Его можно записать в виде суммы
(
) ,
x
P X
x x
=
∑
где x пробегает все возможные значения X.

202 
Глава 11. Математика
Так, при бросании кости математическое ожидание исхода равно
1/
6 · 1 + 1/6 · 2 + 1/6 · 3 + 1/6 · 4 + 1/6 · 5 + 1/6 · 6 = 7/2.
Полезным свойством математического ожидания является линейность.
Это означает, что математическое ожидание суммы E[X
1
+ X
2
+ … + X
n
] рав- но сумме математических ожиданий E[X
1
] + E[X
2
] + … + E[X
n
]. Это верно даже в случае, когда случайные величины зависимы. Например, при бро- сании двух костей математическое ожидание выпавших значений равно
E[X
1
+ X
2
] = E[X
1
] + E[X
2
] = 7/2 + 7/2 = 7.
Теперь рассмотрим задачу о случайном размещении n шаров по n ящи- кам. Пусть требуется найти математическое ожидание количества пустых ящиков. Каждый шар с одинаковой вероятностью может быть помещен в любой ящик.
Рис. 11.17. Возможные способы разместить два шара в трех ящиках
На рис. 11.17 показаны вероятности при n = 2. В этом случае математи- ческое ожидание количества пустых ящиков равно
0 0 1 1 1
4 2
+ + +
=
А в общем случае вероятность того, что один ящик окажется пустым, равна
1
,
n
n
n
−






потому что в нем не должно оказаться ни одного шара. В силу свойства линейности математическое ожидание количества пустых ящиков рав- но
1
n
n
n
n
−


⋅



Распределения. Распределение случайной величины X описывает ве- роятности принимаемых X значений, P(X = x). Например, распределение суммы двух брошенных костей таково:
x
2 3
4 5
6 7
8 9
10 11 12
P
(X
= x) 1/36 2/36 3/36 4/36 5/36 6/36 5/36 4/36 3/36 2/36 1/36

11.4. Вероятность

203
Случайная величина X с равномерным распределением принимает любое из n возможных значений a, a + 1, …, b с вероятностью 1/n. Так, при броса- нии кости a = 1, b = 6 и P(X = x)= 1/6 для каждого значения x.
Математическое ожидание равномерно распределенной величины X
равно
[ ]
2
a
b
E X
+
=
Если производится n испытаний и вероятность успеха в каждом испы- тании равна p, то случайная величина X, равная количеству успешных ис- пытаний, имеет биномиальное распределение:
P
(X = x) = p
x
(1 − p)
n−x
(
n
x
)
,
где p
x
и (1 − p)
n−x
соответствуют успешным и неудачным испытаниям, а (
n
x
) определяет, сколькими способами можно выбрать порядок испытаний.
Например, если бросить кость десять раз, то вероятность ровно три раза выбросить шестерку равна (1/6)
3
(5/6)
7
(
10 3
).
Математическое ожидание биномиально распределенной случайной величины X равно
E[X] = pn.
Пусть вероятность успеха в каждом испытании равна p и испытания продолжаются до первого успеха. Тогда случайная величина X, равная чис- лу проведенных испытаний, имеет геометрическое распределение:
P
(X = x) = (1 − p)
x
−1
p,
где (1 − p)
x
−1
соответствует неудачным испытаниям, а p – первому успеш- ному испытанию.
Например, если бросать кость до первого выпадения шестерки, то веро- ятность, что число бросаний окажется равным в точности 4, равна (5/6)
3 1/6.
Математическое ожидание геометрически распределенной случайной величины X равно
[ ]
1
E X
p
=
11.4.3. Марковские цепи
Марковской цепью называется случайный процесс, состоящий из состоя- ний и переходов между ними. Для каждого состояния известны вероятнос- ти перехода в другие состояния. Марковскую цепь можно представить в виде графа, вершины которого соответствуют состояниям, а ребра описы- вают переходы.

204 
Глава 11. Математика
В качестве примера рассмотрим следующую задачу. Мы находимся на первом этаже n-этажного здания. На каждом шаге мы случайным образом принимаем решение – подняться или спуститься на один этаж – с двумя ис- ключениями: с первого этажа мы всегда поднимаемся, а с последнего всегда спускаемся. Какова вероятность после k шагов оказаться на этаже m?
В этой задаче каждый этаж соответствует состоянию марковской цепи.
На рис. 11.18 показана цепь при n = 5.
1 2
3 4
5 1
1
/2 1
/2 1
/2 1
1
/2 1
/2 1
/2
Рис. 11.18. Марковская цепь для пятиэтажного здания
Распределением вероятности марковской цепи является вектор [p
1
,
p
2
, …, p
n
], в котором p
k
– вероятность нахождения в состоянии k. При этом имеет место равенство p
1
+ p
2
+ … + p
n
= 1.
В данном случае начальное распределение равно [1, 0, 0, 0, 0], поскольку мы находимся на первом этаже. Следующее распределение – [0, 1, 0, 0, 0], поскольку с первого этажа можно попасть только на второй. А затем мы можем либо подняться, либо спуститься на этаж, так что следующее рас- пределение равно [1/2, 0, 1/2, 0, 0]. И так далее.
Для моделирования блуждания, описываемого марковской цепью, эф- фективно будет применить динамическое программирование. Идея за- ключается в том, чтобы запоминать распределение вероятности и на каж- дом шаге перебирать все возможные ходы. С помощью этого метода мы можем смоделировать блуждание с m шагами за время O(n
2
m).
Переходы марковской цепи можно также представить в виде матрицы, которая обновляет распределение вероятности. В рассматриваемом слу- чае матрица имеет вид:
0 1 / 2 0
0 0
1 0
1 / 2 0
0 0 1 / 2 0
1 / 2 0
0 0
1 / 2 0
1 0
0 0
1 / 2 0
















При умножении распределения вероятности на эту матрицу мы полу- чаем новое распределение после выполнения одного шага. Так, переход от распределения [1, 0, 0, 0, 0] к распределению [0, 1, 0, 0, 0] производится следующим образом:

11.4. Вероятность

205
0 1 / 2 0
0 0
1 0
1 0
1 / 2 0
0 0
1 0 1 / 2 0
1 / 2 0
0 0 .
0 0
1 / 2 0
1 0
0 0
0 0
1 / 2 0
0 0

    

    

    

    
=

    

    

    

    
Применяя эффективный алгоритм возведения матрицы в степень, мы сможем вычислить распределение после m шагов за время O(n
3
log m).
11.4.4. Рандомизированные алгоритмы
Иногда при решении задачи можно применить случайный выбор, даже если она не связана с вероятностью. Такие алгоритмы называются рандо-
мизированными. Существует два основных типа рандомизированных алго- ритмов:
• алгоритм типа Монте-Карло иногда может давать неверный ответ.
Чтобы такой алгоритм был полезен, вероятность неверного ответа должна быть мала;
• алгоритм типа Лас-Вегас всегда дает правильный ответ, но время его работы является случайной величиной. Наша цель – спроекти- ровать алгоритм, который с высокой вероятностью будет работать эффективно.
Мы рассмотрим три задачи, которые можно решить с помощью рандо- мизированных алгоритмов.
Порядковые статистики. k-й порядковой статистикой массива являет- ся элемент, который после сортировки в порядке возрастания оказывает- ся на k-м месте. Любую порядковую статистику легко вычислить за время
O(n log n), предварительно отсортировав массив, но так ли необходимо сор тировать весь массив, чтобы найти единственный элемент?
Оказывается, что порядковую статистику можно найти с помощью алго- ритма типа Лас-Вегас со средним временем работы O(n). Алгоритм выби- рает из массива случайный элемент x и перемещает все элементы, мень- шие x, влево от него, а все остальные – вправо. Для массива n элементов это занимает время O(n).
Предположим, что в левой части оказалось a элементов, а в правой –
b элементов. Если a = k, то элемент x является k-й порядковой статистикой.
В противном случае, если a > k, мы рекурсивно находим k-ю порядковую статистику для левой части, а если a < k, то рекурсивно находим r-ю поряд- ковую статистику для правой части, где r = k − a − 1. Поиск продолжается, пока не будет найден нужный элемент.

206 
Глава 11. Математика
Если элемент x всегда выбирается случайно, то размер массива на каж- дом шаге уменьшается примерно вдвое, поэтому временная сложность нахождения k-й порядковой статистики приблизительно равна
n + n/2 + n/4 + n/8 + … = O(n).
Отметим, что в худшем случае временная сложность алгоритма равна
O(n
2
), потому что может случиться так, что x всегда оказывается одним из наименьших или наибольших элементов массива, и тогда потребуется
O(n)шагов. Однако вероятность этого настолько мала, что таким развити- ем событий можно пренебречь.
Проверка произведения матриц. Пусть даны матрицы A, B, C размера
n
×n
. Наша следующая задача заключается в том, чтобы проверить спра- ведливость равенства AB = C. Конечно, ее можно решить за время O(n
3
), просто вычислив произведение AB, но хочется надеяться, что проверить ответ можно и быстрее.
Оказывается, что задачу можно решить с помощью алгоритма типа
Монте-Карло с временной сложностью O(n
2
). Идея проста: случайным об- разом выбрать вектор X, содержащий n элементов, и вычислить матрицы
ABX и CX. Если ABX = CX, то мы считаем, что AB = C, иначе – что AB ≠ C.
Временная сложность этого алгоритма равна O(n
2
), т. к. именно столько времени необходимо для вычисления ABX и CX. Для эффективного вы- числения ABX представим произведение в виде A(BX), тогда потребуется только два умножения матриц размера n×n и n×1.
Недостаток алгоритма заключается в том, что существует небольшая веро- ятность признать равенство AB = C, хотя на самом деле это не так. Например:
6 8 8 7
,
1 3
3 2

 

≠

 


 

но
6 8 3
8 7 3
1 3
6 3 2 6

   
  
=

   
  

   
  
Впрочем, на практике вероятность ошибки мала, и ее можно еще умень- шить, если проверять результат на нескольких случайных векторах, а не на одном.
Раскраска графа. Пусть дан граф с n вер- шинами и m ребрами. Последняя наша зада- ча – раскрасить вершины графа двумя цвета- ми, так чтобы, по крайней мере, для m/2 ребер их концы были разного цвета. На рис. 11.19 показан пример правильной раскраски гра-
Рис. 11.19. Правильная раскраска графа
1 2
3 4
5

11.5. Теория игр

207
фа. В данном случае в графе семь ребер, и концы пяти из них раскрашены в разные цвета.
Задачу можно решить с помощью алгоритма типа Лас-Вегас, который генерирует случайные раскраски до тех пор, пока не будет найдена пра- вильная. При случайном раскрашивании цвет каждой вершины выбира- ется независимо с вероятностью 1/2. Поэтому математическое ожидание числа ребер с концами разного цвета равно m/2. Поскольку можно ожи- дать, что случайная раскраска правильна, то на практике искомая раскрас- ка будет найдена быстро.
11.5. Теория игр
В этом разделе мы будем рассматривать игры с двумя игроками, которые ходят попеременно. Предполагается, что множеств допустимых ходов для обоих игроков одинаково и что в игре нет элементов случайности. Наша цель – найти стратегию, обеспечивающую выигрыш вне зависимости от ходов противника, если такая стратегия существует.
Оказывается, что для таких игр существует общая стратегия, а для ана- лиза игры можно воспользоваться теорией игры ним. Сначала проанализи- руем простые игры, в которых игроки берут палочки из кучки, а затем обобщим найденную стратегию на другие игры.
11.5.1. Состояния игры
Рассмотрим игру, в начале которой имеется кучка из n палочек. Два игрока ходят по очереди, и на каждом ходе игрок может взять из кучки
1, 2 или 3 палочки. Игрок, который забирает последнюю палочку, выиг- рывает.
Например, при n = 10 игра может протекать следующим образом:
• игрок A берет 2 палочки (остается 8 палочек);
• игрок B берет 3 палочки (остается 5 палочек);
• игрок A берет 1 палочку (остается 4 палочки);
• игрок B берет 2 палочки (остается 2 палочки);
• игрок A берет 2 палочки и выигрывает.
Состояния игры 0, 1, 2, …, n соответствуют количеству оставшихся пало- чек.
Выигрышным называется состояние, в котором игрок выигрывает, если применяет оптимальную стратегию, а проигрышным – состояние, в кото- ром игрок проигрывает, если противник применяет оптимальную страте- гию. Оказывается, что любое состояние игры является либо выигрышным, либо проигрышным.
В рассмотренной выше игре состояние 0, очевидно, проигрышное, по- тому что игрок не может сделать ни одного хода. Состояния 1, 2, 3 выиг-

208 
Глава 11. Математика рышные, потому что игрок может забрать 1, 2 или 3 палочки и выиграть.
Состояние 4, напротив, проигрышное, потому что любой ход приводит к состоянию, в котором выигрывает противник.
Вообще, если существует ход, который ведет из текущего состояния в проигрышное, то это выигрышное состояние, в противном случае – проиг- рышное. Пользуясь этим наблюдением, мы можем классифицировать все состояния игры, начав с проигрышных состояний, в которых нет ни од- ного возможного хода. На рис. 11.20 показана классификация состояний
0…15 (W обозначает выигрышное состояние, L – проигрышное).
L
W
W
W
L
W
W
W
L
W
W
W
L
W
W
W
0 1
2 3
4 5
6 7
8 9
10 11 12 13 14 15
Рис. 11.20. Классификация состояний 0−15 в игре в палочки
Эту игру легко проанализировать: состояние k проигрышное, если k де- лится на 4, и выигрышное в противном случае. Оптимальная стратегия – всегда брать столько палочек, чтобы количество оставшихся в кучке дели- лось на 4. В конечном итоге палочек не останется, и противник проиграет.
Разумеется, для применения этой стратегии необходимо, чтобы при своем ходе количество палочек не было кратно 4, иначе мы ничего не сможем сделать, и противник выиграет, если бу- дет играть оптимально.
Рассмотрим другую игру с палочками: в каж- дом состоянии k разрешено брать из кучки лю- бое число палочек x, которое меньше k и делит k.
Например, в состоянии 8 можно взять 1, 2 или 4 палочки, а в состоянии 7 – только одну палоч- ку. На рис. 11.21 состояния 1…9 показаны в виде
графа состояний, вершинами которого явля- ются состояния, а ребрами – переходы между ними.
В этой игре конечным состоянием всегда является 1 – проигрышное, по- тому что в нем нет допустимых ходов. На рис. 11.22 показана классифи- кация состояний 1…9. Оказывается, что в этой игре все четные состояния выигрышные, а все нечетные – проигрышные.
L
W
L
W
L
W
L
W
L
1 2
3 4
5 6
7 8
9
Рис. 11.22. Классификация состояний 0…9 в игре в делимость
1 2
3 4
5 6
7 8
9
Рис. 11.21. Граф состояний в игре в делимость

11.5. Теория игр

209
11.5.2. Игра ним
Ним – простая игра, имеющая большое значение в теории игр, посколь- ку ту же стратегию можно применять и в других играх. Сначала мы рас- смотрим ним, а затем обобщим стратегию на другие игры.
В игре ним есть n кучек, и в каждой из них сколько-то палочек. Игроки ходят попеременно, каждый игрок выбирает кучку, в которой еще оста- лись палочки, и берет из нее любое число палочек. Выигрывает тот, кто забирает последнюю палочку.
Состояния в ним имеют вид [x
1
, x
2
, …, x
n
], где x
i
– количество палочек в i-й кучке. Так, [10, 12, 5] – состояние, в котором есть три кучки, содержащие 10,
12 и 5 палочек. Состояние [0, 0, …, 0] проигрышное, т. к. в нем нет возмож- ных ходов; оно всегда является конечным.
Анализ. Оказывается, что состояние в ним легко классифицировать, вычислив ним-сумму s = x
1
⊕ x
2
⊕ … ⊕ x
n
, где знаком ⊕ обозначена опера- ция ИСКЛЮЧАЮЩЕЕ ИЛИ. Состояния, в которых ним-сумма равна 0, про- игрышные, остальные – выигрышные. Например, ним-сумма состояния
[10, 12, 5] равна 10 ⊕ 12 ⊕ 5 = 3, так что это состояние выигрышное.
Но как ним-сумма связана с игрой ним? Это можно объяснить, глядя на то, как меняется ним-сумма при изменении состояния игры.
Проигрышные состояния. Конечное состояние [0, 0, …, 0] проигрышное, и его ним-сумма, как и следовало ожидать, равна 0. В других проигрышных состояниях любой ход приводит к выигрышному состоянию, потому что при изменении одного значения x
i
ним-сумма также изменяется, поэтому после хода ним-сумма становится отлична от 0.
Выигрышные состояния. Мы можем перейти в проигрышное состояние, если существует кучка i, для которой x
i
⊕ s < x
i
. В таком случае можно за- брать из кучки i столько палочек, чтобы в ней осталось x
i
⊕ s палочек, а это приведет к проигрышному состоянию. Такая кучка существует всегда, для нее x
i
содержит единичный бит в позиции самого левого единичного бита s.
Пример. Рассмотрим состояние [10, 12, 5]. Это выигрышное состояние, поскольку его ним-сумма равна 3. Следовательно, должен существовать ход, приводящий в проигрышное состояние. Найдем такой ход.
Ним-сумма состояния вычисляется следующим образом:
10 1010 12 1100 5
0101 3
0011
В данном случае кучка с 10 палочками – единственная, для которой чис- ло палочек содержит единицу в позиции самого левого единичного бита ним-суммы:

210 
Глава 11. Математика
10 1010 12 1100 5
0101 3
0011
Новый размер кучки должен быть равен 10 ⊕ 3 = 9, так что следует за- брать всего одну палочку. После этого игра переходит в проигрышное со- стояние [9, 12, 5]:
9 1001 12 1100 5
0101 3
0000
Игра мизер. В этом варианте игры ним цель противоположная – игрок, забравший последнюю палочку, проигрывает. Оказывается, что в игре ми- зер оптимальная стратегия почти такая же, как в стандартной игре ним.
Идея в том, чтобы сначала играть в мизер как в стандартную игру, а в конце игры изменить стратегию. Смена стратегии происходит в момент, когда после следующего хода в каждой кучке останется не более одной па- лочки. В стандартной игре мы сделали бы ход, после которого осталось бы четное число кучек с одной палочкой. А в игре мизер мы пойдем так, чтобы число кучек с одной палочкой стало нечетным.
Эта идея работает, потому что в игре обязательно имеется состояние, в котором стратегию можно сменить, и это состояние выигрышное, т. к. со- держит ровно одну кучку с числом палочек больше 1, поэтому его ним-сум- ма не равна 0.
11.5.3. Теорема Шпрага–Гранди
Теорема Шпрага–Гранди обобщает стратегию игры ним на все игры, удовлетворяющие следующим требованиям:
• два игрока ходят попеременно;
• возможные ходы в каждом состоянии игры не зависят от того, чья очередь ходить;
• игра заканчивается, когда игрок не может сделать следующий ход;
• игра гарантированно заканчивается за конечное время;
• игроки обладают полной информацией о состояниях и допустимых ходах, и в игре нет элемента случайности.
Числа Гранди. Идея в том, чтобы для каждого состояния игры вычис- лять число Гранди, являющееся аналогом числа палочек в кучке ним. Зная числа Гранди всех состояний, мы сможем играть так же, как в ним.

11.5. Теория игр

211
Число Гранди состояния игры вычисляется по формуле mex({g
1
, g
2
, …, g
n
}),
где g
1
, g
2
, ..., g
n
– числа Гранди состояний, в которые мы можем перейти из данного, а функция mex возвращает наименьшее неотрицательное чис- ло, не принадлежащее множеству. Например, mex({0, 1, 3}) = 2. Если в со- стоянии нет возможных ходов, то его число Гранди равно 0, потому что mex(∅) = 0.
На рис. 11.23 показан граф состояний, в ко- тором каждому состоянию сопоставлено его число Гранди. Число Гранди проигрышного состояния равно 0, а выигрышного состоя- ния – положительно.
Рассмотрим состояние, для которого число
Гранди равно x. Можно считать, что это соот- ветствует кучке с x палочками в игре ним. В частности, если x > 0, то мы можем перейти в состояния с числами Гранди 0, 1, ..., x − 1, что можно уподобить взятию палочек из кучки. Но есть одно отличие: может оказать- ся возможен переход в состояние с числом Гранди, большим x, что соот- ветствует «добавлению» палочек в кучку. Однако противник всегда может сделать в точности противоположный ход, поэтому на стратегию это не влияет.
В качестве примера рассмотрим игру, в которой игроки двигают фигурку в лабиринте. Каждая клет- ка лабиринта либо доступна, либо нет. Получив ход, игрок должен переместить фигурку на любое число шагов влево или вверх. Выигрывает тот, кто сделает последний ход. На рис. 11.24 показана начальная кон- фигурация, @ обозначает фигурку, а * – квадратики, в которые она может попасть. Состояниями игры яв- ляются все доступные клетки. На рис. 11.25 показаны числа Гранди состояний этой игры.
Согласно теореме Шпрага–Гранди, каждое состоя- ние игры в лабиринт соответствует кучке в ним. На- пример, число Гранди правой нижней клетки равно 2, т. е. это выигрышное состояние. Мы можем перейти в проигрышное состояние и тем самым выиграть игру, передвинув фигурку на четыре клетки влево или на две вверх.
Подыгры. Предположим, что игра состоит из подыгр, и, дождавшись своей очереди, игрок сначала выбирает подыгру, а затем ход в ней. Игра заканчи-
0 1
0 2
0 2
Рис. 11.23. Числа Гранди состояний игры
@
*
*
*
*
*
*
Рис. 11.24. Воз- можные ходы при первом ходе
Рис. 11.25. Числа
Гранди состояний игры
0 1
0 1
0 1
2 0
2 1
0 3
0 4
1 0
4 1
3 2

212 
Глава 11. Математика вается, когда невозможно сделать ход ни в одной подыгре. В таком случае число Гранди игры равно ним-сумме чисел Гранди подыгр. Тогда в игру можно играть, как в ним, вычисляя числа Гранди всех подыгр, а затем их ним-сумму.
В качестве примера рассмотрим игру, состоящую из трех лабиринтов.
На каждом ходе игрок выбирает лабиринт, а затем двигает в нем фигурку.
На рис. 11.26 показана начальная конфигурация игры, а на рис. 11.27 – соответствующие числа Гранди. В этой конфигурации ним-сумма чисел
Гранди равна 2 ⊕ 3 ⊕ 3 = 2, так что выигрывает первый игрок. Один из оптимальных ходов – переместить фигурку на две клетки вверх в первом лабиринте, что дает ним-сумму 0 ⊕ 3 ⊕ 3 = 0.
@
@
@
Рис. 11.26. Игра, состоящая из трех подыгр
0 1
0 1
0 1
2 0
2 1
0 3
0 4
1 0
4 1
3 2
0 1
2 3
1 0
0 1
2 0
1 2
3 1
2 0
4 0
2 5
3 0
1 2
3 4
1 0
2 1
3 2
4 0
1 2
3
Рис. 11.27. Числа Гранди для подыгр
Игра Гранди. Иногда один ход разбивает игру на независимые подыг- ры. В таком случае число Гранди состояния игры равно mex({g
1
, g
2
, …, g
n
}),
где n – число возможных ходов, а
g
k
= a
k,1
⊕ a
k,2
⊕ ... ⊕ a
k,m
,
т. е. ход k разбивает игру на m подыгр с числами Гранди a
k,1
, a
k,2
, ... a
k,m
Примером такой игры является игра Гранди. Первоначально имеется одна кучка с n палочками. На каждом ходе игрок выбирает кучку и разби- вает ее на две непустые кучки разного размера. Игрок, сделавший послед- ний ход, выигрывает.

11.6. Преобразование Фурье

213
Обозначим g(n)число Гранди кучки размера n. Его можно вычислить, перебрав все способы разбиения кучки на две. Так, при n = 8 есть три воз- можности: 1 + 7, 2 + 6 и 3 + 5, поэтому
g
(8) = mex({g(1) ⊕ g(7), g(2) ⊕ g(6), g(3) ⊕ g(5)}).
В этой игре значение g(n)зависит от g(1), ..., g(n − 1). Начальные усло- вия – g(1)= g(2)= 0, потому что кучки с одной и двумя палочками нельзя разбить на меньшие. Вот несколько первых чисел Гранди:
g
(1) = 0
g
(2) = 0
g
(3) = 1
g
(4) = 0
g
(5) = 2
g
(6) = 1
g
(7) = 0
g(8) = 2
Для n = 8 число Гранди равно 2, поэтому игру можно выиграть. К выиг- рышу ведет ход, заключающийся в создании кучек 1 + 7, потому что
g
(1)⊕ g(7) = 0.
11.6. Преобразование Фурье
Пусть даны два полинома f(x) и g(x). В этом разделе наша задача заключа- ется в том, чтобы эффективно вычислить произведение f(x)g(x). Например, если f(x) = 2x + 3 и g(x) = 5x + 1, то искомый результат f(x)g(x) = 10x
2
+ 17x + 3.
Простой способ вычислить произведение – перебрать все пары членов f(x) и g(x) и просуммировать их произведения, как показано ниже:
f
(x)g(x)= 2x · 5x + 2x · 1 + 3 · 5x + 3 · 1 = 10x
2
+ 17x + 3.
Однако этот метод медленный: требуется время O(n
2
),где n – степень по- линомов. По счастью, произведение можно вычислить за время O(n log n), воспользовавшись быстрым преобразованием Фурье (БПФ). Идея этого алгоритма заключается в том, чтобы преобразовать полиномы в специ- альное представление значениями в точках, позволяющее упростить вы- числение.
11.6.1. Работа с полиномами
Рассмотрим полином степени n – 1:
f
(x)= c
0
+ c
1
x + … + c
n
–1
x
n
–1
Существует два стандартных способа его представления.

214 
Глава 11. Математика
• Представление коэффициентами: создается список
[
c
0
, c
1
, …, c
n
–1
],
содержащий коэффициенты полиномов.
• Представление значениями в точках: создается список
[(x
0
, f(x
0
)), (x
1
, f(x
1
)), …, (x
n
–1
, f(x
n
–1
))],
содержащий значения полинома в n различных точках. Это пред- ставление основано на том, что полином степени n − 1 однозначно определен значениями в n различных точках.
Например, рассмотрим полином f(x)= x
3
+ 2x + 5, для которого представ- ление коэффициентами имеет вид [5, 2, 0, 3]. Чтобы создать представление значениями в точках, выберем произвольно n разных точек и вычислим в них полином. Одно из возможных представлений имеет вид [(0, 5), (1, 8),
(2, 17), (3, 38)], т. е. f(0) = 5, f(1) = 8, f(2) = 17 и f(3) = 38.
У обоих способов есть достоинства. Зная представление коэффициен- тами, легко вычислить значение полинома в любой точке. Но для вычис- ления произведения полиномов f(x)и g(x)представление значениями в точках удобнее: если мы знаем, что f (x
i
)= a
i
и g(x
i
)= b
i
в некоторой точке x
i
, то легко вычислить f(x
i
)g(x
i
)= a
i
b
i
. Например, если известно, что f(1)= 5 и
g
(1) = 6, то сразу можно сказать, что f(1)g(1) = 30.
Тем не менее во всех случаях, кроме вычисления произведений, мы обычно предпочитаем использовать представление коэффициентами.
Поэтому для вычисления произведения полиномов f(x)и g(x), заданных своими коэффициентами, можно поступить следующим образом:
1) создать представления f(x)и g(x) значениями в точках;
2) вычислить произведение f(x)g(x) в этом представлении;
3) создать представление f(x)g(x) коэффициентами.
Заметим, что если степени f(x)и g(x)равны n − 1, то степень f(x)g(x)равна
2
n − 2. Следовательно, на шаге 1 нужно вычислить 2n − 1 значений, чтобы на шаге 3 можно было однозначно найти правильный полином.
Для шага 2 нужно время O(n), потому что требуется всего лишь вычис- лить произведение во всех точках. Шаги 1 и 3 труднее, но ниже мы пока- жем, как выполнить их за время O(n log n), применив алгоритм БПФ. Идея в том, чтобы представить полином значениями во вполне определенных точках комплексной плоскости, благодаря чему можно легко переходить от одного представления к другому.
11.6.2. Алгоритм БПФ
Пусть дан вектор a = [c
0
, c
1
, ... , c
n
–1
], представляющий полином

11.6. Преобразование Фурье

215
f
(x)= c
0
+ c
1
x + … + c
n
–1
x
n
–1
Тогда его преобразованием Фурье a называется вектор
t = [f(ω
0
n
), f(ω
1
n
), …, f(ω
n
n
–1
)],
где
ω
n
= e
2
πi/n
= cos(2π/n)+ sin(2π/n)i.
Вектор t соответствует представлению полинома f(x) значениями в точ- ках ω
0
n
, ω
1
n
, …, ω
n
n
–1
. Значение ω
n
– комплексное число, называемое главным
корнем из единицы, это число удовлетворяет равенству ω
n
n
= 1. На рис. 11.28 показано положение чисел ω
4
и ω
8
, а также их степеней на комплексной плос кости.
ω
0 4
1 4
ω
ω
2 4
ω
3 4
ω
0 8
ω
1 8
ω
8 2
ω
3 8
ω
4 8
ω
5 8
ω
8 6
ω
7 8
Рис. 11.28. Степени ω
4
и ω
8
на комплексной плоскости
Алгоритм быстрого преобразования Фурье (БПФ) вычисляет преобразо- вание Фурье за время O(n log n). Для эффективного вычисления исполь- зуются свойства чисел ω
n
. Начиная с этого момента будем предполагать, что n (длина входного вектора a) – степень двойки. Если это не так, можно добавить нули в конец вектора перед началом работы алгоритма.
Идея алгоритма БПФ заключается в том, чтобы разбить вектор a = [c
0
,
c
1
, …, c
n
–1
] на два вектора a
ЧЕТ
= [c
0
, c
2
,..., c
n
–2
] и a
НЕЧЕТ
= [c
1
, c
3
, ..., c
n
–1
]. Оба вектора состоят из n/2 элементов и представляют полиномы c
0
+ c
2
x + c
4
x
2
+
… + c
n
–2
x
n
/2–1
и c
1
+ c
3
x + c
5
x
2
+ … + c
n
–1
x
n
/2–1
соответственно. Затем алгоритм ре- курсивно вычисляет преобразования Фурье a
ЧЕТ
и a
НЕЧЕТ
, получая векторы
t
ЧЕТ
и t
НЕЧЕТ
. Наконец, алгоритм вычисляет преобразование Фурье вектора
a по формуле
t[k] = t
ЧЕТ
[
k mod (n/2)] + t
НЕЧЕТ
[
k mod (n/2)] ω
k
n
.
Эта формула правильна, потому что ω
k
n
/2
= ω
2
n
k
и ω
k
n
= ω
k
n
mod n
(см. рис. 11.28).
Поскольку алгоритм разбивает входной вектор длины n на два вектора длины n/2 и обрабатывает их рекурсивно, время его работы составляет
O(n log n).

216 
Глава 11. Математика
Алгоритм БПФ можно также использовать для вычисления обратного преобразования Фурье, т. е. для преобразования представления значения- ми в точках в представление коэффициентами. Удивительно, что если вы- числить преобразование Фурье вектора
t = [f(ω
0
n
), f(ω
1
n
), …, f(ω
n
n
–1
)],
заменив ω
n
на 1/ω
n
и поделив все выходные значения на n, на выходе полу- чится представление исходного вектора a коэффициентами.
Реализация. Хорошо реализовать алгоритм БПФ не так-то просто.
В частности, не стоит создавать новые векторы и обрабатывать их рекур- сивно, потому что при такой реализации значения постоянных множите- лей будут велики. Часто алгоритм рассматривается как черный ящик, кото- рый умеет эффективно вычислять преобразования Фурье, предпочитая не вдаваться в детали. Показанная ниже реализация основана на псевдокоде, приведенном в CLRS [7]; если вам инте ресно, что именно делает этот код, обратитесь к книге.
Сначала определим тип комплексного числа cd
, вещественная и мнимая части которого имеют тип double
, а также переменную pi
, равную π.
typedef complex<double> cd;
double pi = acos(-1);
Функция fft выполняет алгоритм БПФ. Ей передается вектор a
, содер- жащий коэффициенты полинома, и дополнительный параметр d
. Если d
равен 1 (по умолчанию), то функция вычисляет прямое преобразование
Фурье, а если –1, то обратное. Как уже было сказано, функция предполага- ет, что n – степень двойки.
Сначала функция строит вектор r
, равный поразрядной обратной пере-
становке a
, соответствующей порядку, в котором производится доступ к значениям на нижнем уровне рекурсии. Этот прием позволяет вычислить преобразование без создания дополнительных векторов и рекурсивных вызовов. После этого функция вычисляет преобразования Фурье векторов длины 2, 4, 8, ..., n. Наконец, если требовалось вычислить обратное преоб- разование Фурье, то все выходные значения делятся на n.
vector fft(vector a, int d = 1) {
int n = a.size();
vector r(n);
for (int k = 0; k < n; k++) {
int b = 0;
for (int z = 1; z < n; z *= 2) {
b *= 2;
if (k&z) b++;
}

11.6. Преобразование Фурье

217
r[b] = a[k];
}
for (int m = 2; m <= n; m *= 2) {
cd wm = exp(cd{0,d*2*pi/m});
for (int k = 0; k < n; k += m) {
cd w = 1;
for (int j = 0; j < m/2; j++) {
cd u = r[k+j];
cd t = w*r[k+j+m/2];
r[k+j] = u+t;
r[k+j+m/2] = u-t;
w = w*wm;
}
}
}
if (d == –1) {
for (int i = 0; i < n; i++) r[i] /= n;
}
return r;
}
Ниже показано, как с помощью функции fft вычислить произведение
f
(x)= 2x + 3 и g(x)= 5x + 1. Сначала преобразовываем оба полинома в пред- ставление значениями в точках, затем вычисляем произведение и, нако- нец, выполняем обратное преобразование в представление коэффициен- тами. Получается 10x
2
+ 17x + 3, как и положено.
int n = 4;
vector f = {3,2,0,0};
vector g = {1,5,0,0};
auto tf = fft(f);
auto tg = fft(g);
vector tp(n);
for (int i = 0; i < n; i++) tp[i] = tf[i]*tg[i];
auto p = fft(tp,-1); // [3,17,10,0]
Хотя алгоритм БПФ оперирует комплексными числами, входные и вы- ходные значения часто являются целыми. После вычисления произведе- ния мы можем написать
(int)(p[i].real()+0.5)
, чтобы получить вещест- венную часть комплексного числа p[i]
и преобразовать ее в целое.
11.6.3. Вычисление свертки
В общем случае мы можем использовать алгоритм БПФ для вычисления
свертки двух массивов за время O(n log n). Если даны массивы a и b, то

218 
Глава 11. Математика сверткой c = a ∗ b называется массив, элементы которого вычисляются по формуле
( )
[ ] [ ].
i j k
c t
a i b i
+ =
=
∑
Если a и b – векторы коэффициентов двух полиномов, то свертка представляет коэффициенты произведения этих полиномов, но можно вычислять и свертки без всякой связи с полиномами. Приведем несколько примеров.
Комбинации. Имеются яблоки и бананы, у каждого плода есть вес, рав- ный целому числу от 1 до n. Для каждого веса w ≤ 2n мы хотим узнать, сколькими способами можно выбрать одно яблоко и один банан, совокуп- ный вес которых равен w.
Для решения задачи можно создать массивы a и b, так что a[i] равно чис- лу яблок веса i, а b[i] – число бананов веса i. Тогда свертка этих массивов дает искомый результат.
Обработка сигнала. Можно считать, что массив a – сигнал, а массив b –
маска, модифицирующая этот сигнал. Маска сдвигается вдоль сигнала слева направо, и в каждой позиции вычисляется сумма произведений. Ре- зультат можно вычислить как свертку, если сначала обратить маску, т. е. поменять порядок элементов на противоположный.
Пусть, например, a = [5, 1, 3, 4, 2, 1, 2] и b = [1, 3, 2]. Сначала создадим обра- щенную маску b' = [2, 3, 1], а затем вычислим свертку
c = a ∗ b' = [10, 17, 14, 18, 19, 12, 9, 7, 2].
На рис. 11.29 показана интерпретация значений c[1] и c[5].
5 1
3 4
2 1
2 1
3 2
1 3
2
Рис. 11.29. Обработка сигнала:
c
[1] = 5 · 3 + 1 · 2 = 17 и c[5] = 4 · 1 + 2 · 3 + 1 · 2
Разности. Дана битовая строка s длины n, требуется для каждого k = 1,
2, ..., n − 1 найти, сколькими способами можно выбрать две позиции i и j такие, что s[i] = s[j] = 1 и j − i = k.
Для решения этой задачи вычислим свертку c = s ∗ s', где s' – обраще- ние s. Тогда элемент c[n + k − 1] дает ответ для k (можно также считать, что s одно временно является сигналом и маской).