анти. Guide to Competitive
 Скачать 2.39 Mb.
|
|
Рис. 11.13. Существует 16 различных помеченных деревьев с 4 вершинами Для доказательства теоремы Кэли можно воспользоваться кодами Прю- фера. Кодом Прюфера называется последовательность n − 2 чисел, описы- вающих помеченное дерево. Код строится путем применения следующего процесса, который удаляет из дерева n − 2 листьев. На каждом шаге уда- ляется лист с наименьшей меткой, а метка его един- ственного соседа добавляется к коду. Дереву, изобра- женному на рис. 11.14, соответствует код Прюфера [4, 4, 2], поскольку мы удаляем листья 1, 3, 4. Код Прюфера можно построить для любого дере- ва, и, что важнее, по коду Прюфера можно реконст- руировать исходное дерево. Следовательно, коли- чество помеченных деревьев с n вершинами равно n n −2 – количеству кодов Прюфера длины n. 1 2 3 4 5 Рис. 11.14. Этому дереву соответствует код Прюфера [4, 4, 2] 190 Глава 11. Математика 11.3. Матрицы Математическому понятию матрицы в программировании соответствует двумерный массив. Например: 6 13 7 4 7 0 8 2 9 5 4 18 A = – матрица размера 3×4, т. е. она состоит из 3 строк и 4 столбцов. Элемент матрицы на пересечении i-й строки и j-го столбца обозначается [i, j]. Так, для показанной выше матрицы A[2, 3] = 8 и A[3, 1] = 9. Частным случаем матрицы является вектор – одномерная матрица раз- мера n×1. Например: 4 7 5 V = – вектор из трех элементов. Транспонированной матрицей A T называется матрица, в которой строки и столбцы матрицы A переставлены местами, т. е. A T [i , j] = A[j, i]: 6 7 9 13 0 5 7 8 4 4 2 18 T A = Матрица называется квадратной, если число строк равно числу столб- цов. Ниже приведен пример квадратной матрицы: 3 12 4 5 9 15 0 2 4 S = 11.3.1. Операции над матрицами Сумма A + B матриц A и B определена, если обе матрицы одного разме- ра. Результатом является матрица, каждый элемент которой равен сумме соответственных элементов A и B. Например: 6 1 4 4 9 3 6 4 1 9 4 3 10 10 7 3 9 2 8 1 3 3 8 9 1 2 3 11 10 5 + + + + = = + + + 11.3. Матрицы 191 Результатом умножения матрицы A на скалярное значение x является матрица, каждый элемент которой равен произведению соответственного элемента A на x. Например: 6 1 4 2 6 2 1 2 4 12 2 8 2 3 9 2 2 3 2 9 2 2 6 18 4 ⋅ ⋅ ⋅ ⋅ = = ⋅ ⋅ ⋅ Произведение AB матриц A и B определено, если A имеет размер a×n, а B имеет размер n×b, т. е. ширина A равна высоте B. Результатом яв- ляется матрица размера a×b, элементы кото- рой вычисляются по формуле: [ ] [ ] [ ] 1 , ( , , ). n k AB i j A i k B k j = = ⋅ ∑ Иначе говоря, каждый элемент AB есть сум- ма произведений элементов A и B, располо- женных, как показано на рис. 11.15. Например: 1 4 1 1 4 2 1 6 4 9 9 42 1 6 3 9 3 1 9 2 3 6 9 9 21 99 . 2 9 8 6 8 1 6 2 8 6 6 9 20 102 ⋅ + ⋅ ⋅ + ⋅ ⋅ = ⋅ + ⋅ ⋅ + ⋅ = ⋅ + ⋅ ⋅ + ⋅ Приведенную выше формулу можно использовать непосредственно для вычисления произведения C двух матриц A и B размера n×n за время O(n 3 ): 1 for (int i = 1; i <= n; i++) { for (int j = 1; j <= n; j++) { for (int k = 1; k <= n; k++) { C[i][j] += A[i][k]*B[k][j]; } } } Умножение матриц ассоциативно, т. е. A(BC)= (AB)C, но не коммутатив- но, т. е. в общем случае AB ≠ BA. Единичной матрицей называется квадратная матрица, в которой эле- менты на диагонали равны 1, а все остальные элементы равны 0. Ниже показана единичная матрица 3×3: 1 Хотя прямолинейного алгоритма сложности O(n 3 ) для олимпиадного программирования доста- точно, существуют теоретически более эффективные алгоритмы. Первый такой алгоритм с вре- менной сложностью O(n 2.81 ) открыл в 1969 году Штрассен [35], теперь он так и называется – алго- ритмом Штрассена. Лучший из известных на сегодняшний день алгоритмов был предложен в работе Le Gall [13] в 2014 году, его временная сложность O(n 2.37 ) A AB B Рис. 11.15. Иллюстрация умножения матриц 192 Глава 11. Математика 1 0 0 0 1 0 0 0 1 I = При умножении на единичную матрицу исходная матрица не изменя- ется, например: 1 0 0 1 4 1 4 0 1 0 3 9 3 9 0 0 1 8 6 8 6 ⋅ = и 1 4 1 4 1 0 3 9 3 9 . 0 1 8 6 8 6 ⋅ = Степень A k определена, если матрица A квадратная: k k A A A A A = ⋅ ⋅ ðàç Например: 3 2 5 2 5 2 5 2 5 48 165 1 4 1 4 1 4 1 4 33 114 = ⋅ ⋅ = По определению, A 0 – единичная матрица: 0 2 5 1 0 1 4 0 1 = Матрицу A k можно эффективно вычислить за время O(n 3 log k) с по- мощью алгоритма из раздела 11.1.4. Например: 8 4 4 2 5 2 5 2 5 1 4 1 4 1 4 = ⋅ 11.3.2. Линейные рекуррентные соотношения Линейным рекуррентным соотношением называется функция f(n), на- чальные значения которой равны f(0), f(1), …, f(k − 1), а следующие вычис- ляются рекурсивно по формуле f (n) = c 1 f (n − 1) + c 2 f (n − 2) + … c k f (n − k), где c 1 , c 2 , … , c k – постоянные коэффициенты. 11.3. Матрицы 193 Для вычисления любого значения f(n)за время O(kn)можно восполь- зоваться динамическим программированием, последовательно вычисляя f (0), f(1), …, f(n). Однако, как мы вскоре увидим, значение f(n)можно вы- числить и за время O(k 3 log n),применяя операции над матрицами. Это существенное улучшение в случае, когда k мало, а n велико. Числа Фибоначчи. Простым примером линейного рекуррентного со- отношения является функция, определяющая последовательность чисел Фибоначчи: f (0) = 0, f (1) = 1, f (n) = f(n − 1) + f(n − 2). В данном случае k = 2, c 1 = c 2 = 1. Для эффективного вычисления чисел Фибоначчи представим эти фор- мулы в виде квадратной матрицы X размера 2×2, для которой справедливо следующее соотношение: ( ) ( 1) ( 1) ( 2) f i f i X f i f i + ⋅ == + + Тогда значения f(i)и f(i + 1)подаются на «вход» X, и X вычисляет по ним f (i + 1) и f(i + 2). Оказывается, что матрица X равна 0 1 1 1 X = Например: 0 1 (5) 0 1 5 8 (6) 1 1 (6) 1 1 8 13 (7) f f f f ⋅ = ⋅ = = Таким образом, f(n) можно вычислить по формуле ( ) (0) 0 1 0 ( 1) (1) 1 1 1 n n f n f X f n f = ⋅ = ⋅ + Значение X n вычисляется за время O(log n), поэтому f(n)тоже можно вы- числить за время O(log n). Общий случай. Рассмотрим теперь произвольное линейное рекуррент- ное соотношение f(n). Наша цель – построить матрицу X, для которой 194 Глава 11. Математика ( ) ( 1) ( 1) ( 2) ( 1) ( ) f i f i f i f i X f i k f i k + + + ⋅ = + − + Такая матрица имеет вид 1 2 1 0 1 0 0 0 0 1 0 0 0 0 1 k k k X c c c c − − = В первых k − 1 строках один элемент равен 1, а все остальные равны нулю. Эти строки заменяют f(i)на f(i + 1), f(i + 1)– на f(i + 2) и так далее. А в последней строке находятся коэффициенты рекуррентного соотношения для вычисления нового значения f(i + k). Теперь f(n)можно вычислить за время O(k 3 log n)по формуле ( ) (0) ( 1) (1) ( 1) ( 1) n f n f f n f X f n k f k + = ⋅ + − − 11.3.3. Графы и матрицы У степеней матриц смежности графов есть ряд интересных свойств. Если M – матрица смежности невзвешенного графа, то M n для каждой пары вершин (a, b) содержит количество путей, которые начинаются в a, заканчиваются в b и состоят ровно из n ребер. Вершина может встречаться в пути несколько раз. Рассмотрим граф на рис. 11.16(a). Вот его матрица смежности: 0 0 0 1 0 0 1 0 0 0 1 1 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 1 0 1 0 M = 11.3. Матрицы 195 1 4 2 3 5 6 (a) 1 4 2 3 5 6 4 1 2 4 1 2 3 2 (b) Рис. 11.16. Примеры графов, соответствующих операциям над матрицами Тогда матрица 4 0 0 1 1 1 0 2 0 0 0 2 2 0 2 0 0 0 0 0 2 0 0 0 0 0 0 0 0 0 0 0 0 1 1 1 0 M = позволяет определить число путей, содержащих ровно 4 ребра. Например, M 4 [2 , 5] = 2, потому что существует два пути с 4 ребрами из вершины 2 в вершину 5: 2 → 1 → 4 → 2 → 5 и 2 → 6 → 3 → 2 → 5. Аналогичная идея в применении к взвешенному графу позволяет для каждой пары вершин (a, b) вычислить длину кратчайшего пути из a в b, содержащего ровно n ребер. Для этого мы определим умножение матриц по-другому, чтобы вычислять не число путей, а их минимальные веса. В качестве примера рассмотрим граф на рис. 11.16 (b). Построим матри- цу смежности, в которой ∞ означает, что ребра не существует, а любое дру- гое значение интерпретируется как вес соответствующего ребра. Матрица графа имеет вид 4 2 1 2 4 1 3 2 M ∞ ∞ ∞ ∞ ∞ ∞ ∞ ∞ ∞ ∞ ∞ ∞ ∞ = ∞ ∞ ∞ ∞ ∞ ∞ ∞ ∞ ∞ ∞ ∞ ∞ ∞ ∞ ∞ При определении матричного умножения мы вместо формулы 196 Глава 11. Математика [ ] [ ] [ ] 1 , ( , , ). n k AB i j A i k B k j = = ⋅ ∑ будем использовать формулу [ ] [ ] [ ] 1 , min( , , ) n k AB i j A i k B k j = = + , т. е. будем вычислять минимумы вместо сумм и суммы вместо произве- дений. При такой модификации операция возведения матрицы в степень дает веса кратчайших путей. Например: 4 10 11 9 9 8 9 11 , 8 12 13 11 M ∞ ∞ ∞ ∞ ∞ ∞ ∞ ∞ ∞ ∞ ∞ = ∞ ∞ ∞ ∞ ∞ ∞ ∞ ∞ ∞ ∞ ∞ ∞ ∞ ∞ и, значит, кратчайший путь с 4 ребрами из вершины 2 в вершину 5 имеет вес 8. Это путь 2 → 1 → 4 → 2 → 5. 11.3.4. Метод Гаусса Метод Гаусса – это способ решения системы линейных уравнений. Идея заключается в том, чтобы представить систему в виде матрицы и приме- нить к ней последовательность простых операций над строками, которые сохраняют существенную информацию о системе и вместе с тем позволя- ют найти значения всех переменных. Пусть дана система n линейных уравнений с n переменными: a 1,1 x 1 + a 1,2 x 2 + ... + a 1,n x n = b 1 a 2,1 x 1 + a 2,2 x 2 + ... + a 2,n x n = b 2 a n ,1 x 1 + a n ,2 x 2 + ... + a n ,n x n = b n Представим ее в виде матрицы: 1,1 1,2 1, 1 2,1 2,2 2, 2 ,1 ,2 , n n n n n n n a a a b a a a b a a a b 11.3. Матрицы 197 Для решения системы мы хотим преобразовать эту матрицу к виду 1 2 1 0 0 0 1 0 , 0 0 1 n c c c откуда сразу находим решение x 1 = c 1 , x 2 = c 2 , …, x n = c n . В процессе преобра- зования мы будем использовать операции трех типов: 1. Перестановка двух строк. 2. Умножение всех элементов одной строки на неотрицательное число. 3. Сложение одной строки, умноженной на скаляр, с другой строкой. После выполнения любой из этих операций множество решений систе- мы не изменяется. Мы можем последовательно обработать все столбцы матрицы таким образом, что временная сложность алгоритма составит O(n 3 ). Рассмотрим следующую систему уравнений: 2x 1 + 4x 2 + x 3 = 16 x 1 + 2x 2 + 5x 3 = 17 3x 1 + x 2 + x 3 = 8 Для нее матрица имеет вид 2 4 1 16 1 2 5 17 3 1 1 8 Будем обрабатывать эту матрицу по столбцам. Наша цель на каждом шаге – сделать так, чтобы в нужной позиции столбца оказалась единица, а во всех остальных – нули. При обработке первого столбца сначала умно- жим первую строку на 1 2 : 1 2 1 2 8 1 2 5 17 3 1 1 8 Затем прибавляем первую строку, умноженную на –1, ко второй и пер- вую строку, умноженную на –3, к третьей: 198 Глава 11. Математика 1 2 9 2 1 2 1 2 8 0 0 9 0 5 16 − − − После этого переходим к обработке второго столбца. Поскольку второй элемент второго столбца равен нулю, мы сначала переставляем вторую и третью строки: 1 2 1 2 9 2 1 2 8 0 5 16 0 0 9 − − − Теперь умножаем вторую строку на 1 5 − и прибавляем ее произведение на скаляр –2 к первой: 3 8 5 10 1 16 5 10 9 2 1 0 0 1 0 0 9 Осталось обработать третий столбец. Сначала умножаем третью строку на 2 9 , а затем прибавляем ее произведение на скаляр 3 10 − ко второй строке и произведение на скаляр 1 10 − к первой строке: 1 0 0 1 0 1 0 3 0 0 1 2 Теперь из последнего столбца матрицы следует, что решение исходной системы уравнений x 1 = 1, x 2 = 3, x 3 = 2. Отметим, что метод Гаусса работает правильно, только если система уравнений имеет единственное решение. Например, у системы x 1 + x 2 = 2 2x 1 + 2x 2 = 4 бесконечно много решений, потому что оба уравнения содержат одну и ту же информацию. С другой стороны, система |