В пятницу, 25 декабря, состоится очереднное заседание.
При решении задач методом динамического программирования важно выделить состояния системы и определить переходы между ними. Как правило, состояния определяются некоторым (небольшим) количеством параметров и изначально основываются на «естественной» интерпретации задачи. Однако в дальнейшем при разработке алгоритма решения может оказаться полезной техника замены одного из параметров состоянием. Классическим примером является задача LIS (о наибольшей возрастающей подпоследовательности).
В «естественной» интерпретации для каждого элемента последовательности отыскивается наиболее длинная возрастающая подпоследовательность, оканчивающаяся этим элементом; так что можно говорить о функции, определяющей длину подпоследовательности по индексу элемента. Однако можно поступить иначе: попробовать определить функцию, которая по длине подпоследовательности определяет индекс элемента, которым такая подпоследовательность заканчивается. Такая замена позволяет улучшить асимптотическую оценку с O(n^2) до O(n log n). Разумеется, это не единственный подобный пример, подобные замены возможны и в многомерных состояниях. Такие задачи планируется обсудить на заключительном семинаре в осеннем семестре.
Следующий семинар состоится после каникул, в начале февраля. О его дате будет сообщено дополнительно.
