Продвинутые алгоритмы и вычисления
Продвинутые алгоритмы строятся не только на последовательном переборе. В этой теме используются повторяющиеся подзадачи, инварианты, выигрышные стратегии, разбиение вычислений между исполнителями и свойства целых чисел. Такой подход помогает получать решения, которые быстрее, короче и надёжнее полного перебора.
Динамическое программирование
Рекуррентное соотношение задаёт значение через уже известные значения, например \(F_n=F_{n-1}+F_{n-2}\). В динамическом программировании задача разбивается на подзадачи, ответы которых сохраняются и используются повторно. Это особенно полезно, когда разные ветви рекурсии обращаются к одним и тем же состояниям.
Метод решения задачи через описание состояний, переходов между ними, начальных значений и порядка вычисления. Состояние должно содержать всю информацию, необходимую для продолжения решения.
Обычно алгоритм проектируют в четыре шага: определить состояние, записать переход, задать базовые случаи и выбрать порядок заполнения таблицы. В основах динамического программирования подробно рассматриваются мемоизация и табличный метод.
В этой схеме \(p\) — предыдущее состояние, \(s\) — текущее, а оптимум может быть минимумом, максимумом или логической операцией. Для восстановления ответа часто хранят не только значение \(dp[s]\), но и предка, из которого был выполнен лучший переход.
Если оптимальное решение содержит подрешение, то это подрешение должно быть оптимальным для соответствующей подзадачи. Иначе его можно заменить лучшим и улучшить всё решение.
Оптимизация и пример
Наивная рекурсия может иметь экспоненциальное число вызовов. Оптимизация динамического программирования уменьшает время за счёт устранения повторов, сокращения состояний, монотонности переходов или правильного выбора структуры данных.
Лестница имеет \(n\) ступеней. На ступень \(i\) можно попасть с \(i-1\) или \(i-2\), заплатив \(a_i\). Найдём минимальную стоимость достижения ступени \(n\).
Если \(a=(3,7,2,4,1)\), получаем \(dp[0]=0\), \(dp[1]=3\), \(dp[2]=7\), \(dp[3]=9\), \(dp[4]=11\), \(dp[5]=10\). Значит, минимальная стоимость равна \(10\). Память можно сократить до двух последних значений, потому что более старые состояния больше не нужны.
Что нужно изменить, если требуется не минимальная, а максимальная стоимость?
Игры, инварианты и стратегии
В задачах на игры важно определить состояние позиции и множество ходов. Позиция называется выигрышной, если существует ход в проигрышную позицию; проигрышной — если все допустимые ходы ведут в выигрышные позиции. Эта классификация превращает поиск стратегии в рекуррентное рассуждение.
Комбинаторные игры обычно имеют двух игроков, конечное число ходов и противоположные цели. Стратегия в игре может быть явной: указать ход для любой ситуации, или симметричной: после хода соперника возвращать позицию к удобному виду.
Инвариант — свойство состояния, сохраняющееся после каждого допустимого шага. Инварианты в алгоритмах помогают доказывать корректность, потому что проверяют не отдельный пример, а весь процесс.
Если величина строго уменьшается и ограничена снизу, процесс завершится. Такая величина называется моновариантом. Если сама величина меняется, но сохраняет, например, чётность или знак, используют полуинвариант. В играх моновариант часто доказывает конечность партии, а инвариант — невозможность достичь некоторой позиции.
Терминальная позиция, в которой ходить нельзя, проигрышна для игрока, которому передан ход. Позиция с ходом в проигрышную позицию выигрышна; позиция, все ходы из которой ведут в выигрышные, проигрышна.
Параллельные вычисления
Основы параллельных вычислений рассматривают выполнение частей алгоритма одновременно на нескольких процессорах или ядрах. Параллелить можно только независимые действия либо действия, синхронизированные барьерами и обменом данными.
Здесь \(T_1\) — время последовательного алгоритма, \(p\) — число исполнителей, \(T_{overhead}\) — цена распределения и обмена, а \(T_{critical}\) — время самой длинной последовательной цепочки. Ускорение \(S_p=T_1/T_p\), эффективность \(E_p=S_p/p\).
Если доля \(f\) программы неизбежно выполняется последовательно, то при неограниченном числе процессоров ускорение не превосходит \(1/f\): \(S_{\max}=1/f\). Поэтому увеличение числа исполнителей не устраняет последовательное узкое место.
Оптимизация параллельных вычислений включает равномерное распределение работы, уменьшение обменов, объединение мелких задач и выбор подходящего размера блока. Например, сумму массива можно считать параллельно по блокам, а затем сложить частичные суммы. Но операции должны быть безопасны при одновременном доступе: общий счётчик требует блокировки или другой формы синхронизации.
Теория чисел в алгоритмах
Основы теории чисел дают свойства делимости, простых чисел, остатков и наибольшего общего делителя. Алгоритмы теории чисел превращают эти свойства в быстрые процедуры: алгоритм Евклида, решето Эратосфена, быстрое возведение в степень и вычисления по модулю.
Алгоритм Евклида повторяет замену \((a,b)\) на \((b,a\bmod b)\), пока второй аргумент не станет нулём. Последний ненулевой остаток и есть НОД. Его время работы — \(O(\log\min(a,b))\).
Найдём \(\gcd(252,105)\): \(252=2\cdot105+42\); \(105=2\cdot42+21\); \(42=2\cdot21+0\). Последний ненулевой остаток равен \(21\), поэтому \(\gcd(252,105)=21\).
При работе с большими степенями используют двоичное возведение: показатель последовательно делят на два, а основание возводят в квадрат. По модулю каждое действие заменяют остатком, чтобы числа не росли без необходимости.
Не путайте число состояний со временем одного перехода: сложность равна их произведению. В играх нельзя объявлять позицию выигрышной только потому, что один ход кажется хорошим, — нужно доказать ответ на любой ход соперника. В параллельных алгоритмах забывают стоимость синхронизации и гонки данных. В теории чисел ошибаются, считая \(a\bmod b\) обычным делением, или теряют знак при вычислении отрицательных остатков.
Проверьте базовые случаи на маленьких входах, выпишите первые несколько состояний таблицы, оцените границы переменных и отдельно докажите завершение цикла. Для параллельного алгоритма сравните результат с последовательной версией.
Быстрая проверка
Главное
- Динамическое программирование требует состояний, переходов, базовых случаев и порядка вычисления.
- В играх выигрышные позиции имеют ход в проигрышные, а инварианты и моноварианты доказывают свойства процесса.
- Параллелить можно независимые части, но ускорение ограничивают последовательность, обмены и синхронизация.
- В теории чисел особенно важны остатки, делимость, НОД и вычисления по модулю.
- Корректность проверяют инвариантами, тестами на малых случаях и оценкой сложности.