Статьи об алгоритмах

Подберите термин под ограничение

• streaming algorithm — обработка потока без хранения всего входа.
• approximation algorithm — приближённое решение с оценкой качества.
• dynamic graph algorithm — алгоритм для графа, который меняется.
• parameterized algorithm — алгоритм, сложность которого отдельно зависит от выбранного параметра задачи.

Две основные рубрики и готовые запросы

В arXiv cs.DS подходит для проектирования алгоритмов и структур данных. cs.CC полезен, когда вы ищете результаты о вычислительной сложности и нижние оценки.

Эти условия вводятся в «Сложном запросе». Первое ищет алгоритмы приближённого решения задачи, второе — структуры для изменения графа.

(cat:cs.DS AND all:"approximation algorithm")
(cat:cs.DS AND all:"dynamic graph")

Как получать новые результаты

В боте выберите «Добавить тему» → arXiv → «Раздел arXiv» и отправьте cs.DS. Ответ «Добавлено» означает, что подписка сохранена. Если весь раздел не нужен, выберите «Ключевую фразу» и отправьте streaming algorithm.

Через «Последние работы» посмотрите результаты выбранной подписки. Для работ о трудности задач добавьте отдельный раздел cs.CC, а для вероятностного анализа — нужную тему из теории вероятностей.

Как читать оценку сложности

Запишите, что авторы обозначают через n и m, и относится ли оценка к худшему случаю, среднему времени или амортизированной стоимости. Для вероятностного алгоритма найдите вероятность ошибки; для приближённого — коэффициент приближения. Эти четыре строки помогают сравнить новый результат с уже известным решением вашей задачи.

Английские термины для поиска

approximation ratio

коэффициент приближения

streaming algorithm

потоковый алгоритм

amortized complexity

амортизированная сложность

Частые вопросы