Описание тем задач
Содержание
Деревья поиска
Тема предназначена для знакомства студентов с тестирующей системой и определения уровня последующих задач. Содержательная часть каждой задачи (т. е. всё, кроме построения дерева) должна решаться за линейное от числа вершин время. (Это означает, что во время построения дерева не допускается вычисление каких-либо характеристик.) Исключение составляет задача 24, где допускается нелинейная зависимость от числа вершин. Кроме того, в задачах 23 и 35 допускается линейная зависимость от параметра [math]k[/math] в качестве мультипликативной добавки, т. е. общее время [math]\mathrm{O}(nk)[/math], где [math]n[/math] — число вершин дерева.
Стоит отметить, что при тестировании в системе допускается тривиальное (вообще говоря, квадратичное) построение дерева методом спуска от корня к новой вершине (за исключением задач 0, 36 и 37), несмотря на то, что существуют более эффективные методы. Поэтому из того факта, что решение успешно справляется с предложенными наборами входных данных, никак не следует его эффективность (впрочем, это относится и к другим темам).
Рекуррентные соотношения
Тема предполагает использование метода динамического программирования, т. е. сведение задачи к подзадачам. Приемлемое время работы алгоритма определяется, исходя из ограничений на входные данные в каждой задаче. Эта тема не предполагает использования каких-либо структур данных, кроме массива.
Полученная для алгоритма оценка времени работы должна давать гарантию, что решение уложится в отведённое время на любом наборе входных данных, соответствующем ограничениям, указанным в условии. При отсутствии ограничений допускается только линейное время работы.
Структуры данных
Тема предполагает использование известных структур данных. Приемлемое время работы алгоритма определяется, исходя из ограничений на входные данные в каждой задаче.
Полученная для алгоритма оценка времени работы должна давать гарантию, что решение уложится в отведённое время на любом наборе входных данных, соответствующем ограничениям, указанным в условии. При отсутствии ограничений допускается только линейное время работы.
Алгоритмы на графах
Тема предполагает использование и разработку алгоритмов на графах. Приемлемое время работы алгоритма определяется, исходя из ограничений на входные данные в каждой задаче. Стандартные алгоритмы не следует как-то модифицировать, вместо этого лучше грамотно построить граф, чтобы использовать их без изменений.
Полученная для алгоритма оценка времени работы должна давать гарантию, что решение уложится в отведённое время на любом наборе входных данных, соответствующем ограничениям, указанным в условии. При отсутствии ограничений допускается только линейное время работы.
Перебор
Тема предполагает использование техник эффективного (но никак не полного!) перебора. Во всех задачах необходимо найти «разумный» перебор. Основным критерием «разумности» перебора выступает возможность аналитически оценить качество предложенных отсечений.
Так, во многих задачах, в которых выводится большое множество решений или подсчитывается их число, время работы алгоритма должно линейно зависеть от количества информации на выходе (размера выхода) или же численного ответа задачи и «слабо» зависеть от размера входных данных. Например, в задачах о маршрутах слона, ладьи и ферзя хорошим считается решение со временно́й сложностью [math]\mathrm{O}(k + mn(m+n) + X)[/math], где [math]k[/math] — число чёрных фигур, [math]m[/math] и [math]n[/math] — размеры доски, а [math]X[/math] — сумма длин всех маршрутов.
Под полным перебором, с которым сравнивается предложенный эффективный, подразумевается рассмотрение всех возможных вариантов без каких-либо отсечений. Тем не менее, само множество вариантов не должно быть избыточным. Простым примером избыточных действий может выступать сложение двух положительных целых чисел таким образом: к первому числу добавляется единица, а от второго отнимается до тех пор, пока второе число не обратится в ноль. Способ в определённой степени разумный, и даже не самый медленный из разумных, тем не менее он очевидно избыточный по числу операций. Точно так же возможен избыточный перебор, который, вообще говоря, ещё медленнее полного. Неизбыточный полный перебор, в частности, не должен оперировать множеством всех меньших значений численного параметра (время, расстояние и т. д.), поскольку такой подход может оказаться суперэкспоненциальным по времени.
Касательно ограничений на входные данные, во всех задачах гарантируется то, что времени достаточно для ввода и вывода. В задачах, в которых не требуется вывод множества искомых объектов, также гарантируется, что решение со временем, пропорциональным их числу, будет принято.
Приближённые алгоритмы
Тема предполагает использование и разработку быстрых алгоритмов, гарантирующих не оптимальность, но определённое качество решения. Во всех задачах, даже если этого не требуется явно, необходимо найти расписание, упаковку и т. п., на которых достигается значение целевой функции, не более чем в определённое число раз (своё для каждой задачи) хуже оптимального (больше или меньше, в зависимости от задачи). Большинство задач требуется решать за время сортировки (линейно-логарифмическое), некоторые — за квадратичное время.
Тема, в первую очередь, теоретическая и требует предельно строгого доказательства оценки качества решения, а также демонстрации того, что эта оценка (для данного алгоритма) не может быть улучшена. С практической точки зрения приближённые алгоритмы могут достаточно быстро давать либо решение надлежащего качества, либо решение, служащее отправной точкой для дальнейших эвристических оптимизаций.
