Вопросы с тегом «online-algorithms»

19
Взвешенная сумма последних N чисел

Предположим, мы получаем цифры в потоке. После получения каждого числа необходимо вычислить взвешенную сумму последних NNN чисел, где веса всегда одинаковы, но произвольны. Насколько эффективно это можно сделать, если нам разрешено сохранять структуру данных, чтобы помочь с вычислениями? Можем ли...

18
Вычисление обратной матрицы при изменении элемента

Дана матрица . Пусть обратная матрица будет (то есть ). Предположим, что один элемент в изменен (скажем, до ). Цель состоит в том, чтобы найти после этого изменения. Есть ли способ найти эту цель, который более эффективен, чем пересчет обратной матрицы с нуля.n × nN×Nn \times...

16
Может ли персептрон забыть?

Я хотел бы создать онлайн-систему машинного обучения, где пользователи могут постоянно добавлять классифицированные образцы и обновлять модель в режиме онлайн. Я хотел бы использовать персептрон или аналогичный алгоритм онлайн-обучения. Но пользователи могут ошибаться и вставлять не относящиеся к...

14
Определить пропущенный номер в потоке данных

Мы получаем поток из n−1n−1n-1 попарно различных чисел из множества {1,…,n}{1,…,n}\left\{1,\dots,n\right\} . Как я могу определить пропущенное число с помощью алгоритма, который читает поток один раз и использует память только O(log2n)O(log2⁡n)O(\log_2 n)...

11
Честная нарезка тортов, когда игроки присоединяются поздно

Обычное изложение проблемы справедливой резки тортов предполагает, что все игроков получают свою долю одновременно. Однако во многих случаях игроки прибывают постепенно. Например, мы можем разделить торт по n игрокам, но затем приходит новый игрок и хочет получить долю.nnnnnn Как правило,...