Методы алгоритмов: углубление
Разбирать динамическое программирование, автоматные и вероятностные методы с проверкой ограничений.
Объяснения и разобранные примеры
Что сравнивает порядок роста алгоритма без обещания секунд
Что сравнивает порядок роста алгоритма без обещания секунд. O(g(n)) ограничивает рост выбранной стоимости сверху постоянным множителем при достаточно больших n.
Как искать минимально допустимый ответ по монотонной проверке
искать минимально допустимый ответ по монотонной проверке. Бинарный поиск по ответу применяют, когда проверка выполнимости монотонна: все значения меньше порога не подходят, а начиная с порога подходят.
Как дерево выражения сохраняет приоритет без выполнения кода
дерево выражения сохраняет приоритет без выполнения кода. В дереве выражения внутренний узел обозначает операцию, а его дети — операнды.
Как конечный автомат хранит только нужное состояние истории
конечный автомат хранит только нужное состояние истории. Конечный автомат читает строку по символу и сохраняет одно из конечного числа состояний.
Почему в задаче о рюкзаке предмет нельзя использовать дважды незаметно
Почему в задаче о рюкзаке предмет нельзя использовать дважды незаметно. В рюкзаке 0/1 каждый предмет разрешено взять не более одного раза.
Чем общая подпоследовательность отличается от общего подотрезка строки
Чем общая подпоследовательность отличается от общего подотрезка строки. Общая подпоследовательность получается удалением символов из обеих строк без перестановки оставшихся.
Как свойство и контрпример дополняют отдельные тестовые примеры
свойство и контрпример дополняют отдельные тестовые примеры. Тестирование свойств проверяет общее требование на множестве сгенерированных входов.
Сортировка подсчётом: диапазон значений важнее числа разрядов
Сортировка подсчётом: диапазон значений важнее числа разрядов. Сортировка подсчётом использует небольшую таблицу возможных целых ключей.
Расстояние редактирования: вставить, удалить или заменить символ
Расстояние редактирования: вставить, удалить или заменить символ. Расстояние Левенштейна — минимальное число вставок, удалений и замен символов, превращающих одну строку в другую, когда каждая правка стоит единицу.
Fisher—Yates: почему случайный обмен требует правильной границы
Fisher—Yates: почему случайный обмен требует правильной границы. В варианте Fisher—Yates слева направо на шаге i выбирают позицию j равномерно среди ещё не закреплённых i…n−1 и меняют элементы i и j.
Префикс-функция: как искать границу совпавшего фрагмента
Префикс-функция: как искать границу совпавшего фрагмента. Префикс-функция π[i] хранит длину наибольшего собственного префикса строки s[0…i], который одновременно является её суффиксом.
Порядковая статистика: найти k-й элемент без полной сортировки
Порядковая статистика: найти k-й элемент без полной сортировки. Чтобы найти k-й элемент по возрастанию, не обязательно полностью сортировать список.
Поразрядная сортировка: зачем каждому проходу стабильность
Поразрядная сортировка: зачем каждому проходу стабильность. В поразрядной LSD-сортировке неотрицательных целых начинают с младшей цифры.
Резервуарная выборка: как один слот остаётся равномерным
Резервуарная выборка: как один слот остаётся равномерным. Чтобы равномерно выбрать одну позицию из потока неизвестной длины, сохраняют первый элемент, а элемент с номером i принимает его место с вероятностью 1/i.
Скользящий хеш: быстро сравнить кандидатов и проверить совпадение
Скользящий хеш: быстро сравнить кандидатов и проверить совпадение. Полиномиальный хеш заменяет строку числом по выбранному основанию и модулю.
Онлайновая дисперсия: обновляем среднее без разности больших квадратов
Онлайновая дисперсия: обновляем среднее без разности больших квадратов. В онлайновом обновлении хранят число наблюдений n, среднее m и сумму квадратов отклонений M2.
Z-функция строки: длины совпадения с её началом
Z-функция строки: длины совпадения с её началом. Значение Z[i] равно длине совпадения начала строки с фрагментом, начинающимся в позиции i.
Как вычислить ДПФ и проверить обратное восстановление
Вычислить комплексные спектральные коэффициенты конечного вещественного сигнала с явной нормировкой и проверить Parseval и обратное ДПФ.
Как получить полный отклик конечного фильтра свёрткой
Вычислить линейную свёртку конечного сигнала с конечным импульсным откликом, сохранить края и отличить её от круговой.
Расписание с ценностью задач: почему раннее окончание уже не гарантирует оптимум
Выбрать совместимые полуоткрытые интервалы максимального суммарного веса и восстановить выбранные исходные задачи из динамики.
Один шаг ДКА хранит сразу все возможные состояния НКА
Детерминизировать двоичный недетерминированный автомат с ε-переходами, строя только достижимые подмножества и проверяя принадлежность слова.
Короткая рекурсия объясняет префикс, но не доказывает неизвестное продолжение
Найти минимальную линейную рекурсию конечной последовательности над малым простым полем, проверить знаки коэффициентов и границу прогноза.
Теорема Райса относится к смыслу программы: синтаксический тест остаётся другой задачей
Распознать нетривиальное семантическое свойство вычислимой частичной функции и правильно применить неразрешимость, не распространяя её на свойства текста программы.
Лемма о накачке: разбиение выбирает противник, а степень выбираете вы
Построить корректное доказательство нерегулярности языка по лемме о накачке, сохраняя порядок кванторов и охватывая все допустимые разбиения.
Проверить на своих данных
Откройте подходящий инструмент и попробуйте свои данные.
Расстояние редактирования с выравниванием
Минимальное число вставок, удалений и замен между двумя короткими строками и один оптимальный путь выравнивания.
Открыть инструментДискретное преобразование Фурье короткого сигнала
Вычислить комплексные коэффициенты ДПФ, восстановить вещественную последовательность и проверить равенство энергий.
Открыть инструментЛинейная свёртка двух конечных сигналов
Получить полный отклик конечного фильтра, со всеми краевыми отсчётами и точными рациональными коэффициентами.
Открыть инструментМаксимальный вес совместимых временных интервалов
Выбрать непересекающиеся полуоткрытые интервалы с максимальной суммой весов и показать динамическое сравнение включения и пропуска.
Открыть инструментДетерминизация НКА с ε-переходами
Построить достижимые состояния ДКА как множества состояний НКА и проверить короткое двоичное слово с учётом ε-замыканий.
Открыть инструментКратчайшая линейная рекурсия конечного префикса над GF(p)
Восстановить минимальную длину линейной рекурсии для заданного конечного набора остатков по одному из малых простых модулей.
Открыть инструментЧастые вопросы
Как работать с темой «Методы алгоритмов: углубление»?
Выберите объяснение из списка, восстановите ход примера своими словами и ответьте на проверочный вопрос. Если к теме подключён инструмент, им можно проверить свои данные.
Можно ли вернуться к более простой теме?
Да. Откройте учебную карту или ссылки на необходимые основы перед списком материалов. Уровень по классу помогает выбрать сложность и не ограничивает доступ.