Форум 'Алгоритмы' на RSDN

Анонимное проверяемое голосование - есть ли решение?

Tue, 28 Apr 2026 04:14:58 GMT

Вопрос глобальной значимости — нашли ли решение, чтобы голосование было и анонимным и проверяемым?

Как это выглядит с точки зрения простого избирателя? Т.е. что ему нужно делать, чтобы лично и проголосовать и потом проверить. Да еще так, чтобы начальник не мог с ним войти в онлайн-кабинет (или куда там) и посмотреть правильно ли проголосовал (не крыса ли).

Вроде пишут что нашли. Но сколько я не проверял — всегда была дыра. И гомоморфное шифрование и слепая подпись — а в итоге все-равно фига получается.

Просто нужно одновременно как бы противоречивые требования:

1. Чтобы тебя не могли взять за яйца, т.е. чтобы начальник не мог проверить за кого ты проголосовал.
2. При этом чтобы ты лично проверить себя таки мог.
3. Чтобы админы не могли добавлять левых людей, несуществующих. В идеале чтобы админы не могли повлиять на процесс, даже если они не честные.

Все таки позволяет математика или нет?

У меня, получается, такой вариант придумался.

1. Человеку выдают девайс (сертифицированный). На девайсе есть кнопка сгенерить новый публичный идентификатор — случайное число. Идентификатор выводится на экране в виде 10 слов (для простоты запоминания) или даже согласованное предложение из 10 слов (около 16 байт энтропии — норм). Девайс выдается или покупается анонимно, можно купить хоть 10 штук разных.

2. Чел. приходит в избирательный участок, заходит по паспорту. Войти можно только 1 раз за голосование (второй раз не пропустят). Цель участка (чего нельзя сделать удаленно) — чтобы никто другой не мог увидеть его текущий идентификатор. На участке контролируют чтобы чел был один и не фоткал идентификатор на телефон. При этом идентификатор камеры не видят.

3. Чел. жамкает кнопку на девайсе, генерит идентификатор. Может генерить хоть 10 раз. Но значение имеет только последний. Нужно чтобы жмякнул кнопку хотя бы один раз уже в участке, к примеру, без этого не отроются двери в кабинку.

4. Подходит с этим брелоком (с идентификатор на экране) к голосомату. Выбирает за кого голосовать, подносит брелок (там NFC).

5. Система учитывает голос и связывает его с публичным идентификатором. После чего дает распечатку — твой голос (на против него будет публичный идентификатор — ты проверяешь что совпадает с данными на экране брелока). НО! кроме этого будут и все другие варианты выбора, но напротив них будут публичные идентификаторы случайных людей. Это нужно чтобы у тебя не было доказательства за кого ты проголосовал — банные с экрана брелока только в памяти твоей.

Ты визуально еще раз проверяешь что слова совпадают.

6. Выходишь из кабинки, для этого нужно сбросить брелок (идентификатор остается на распечатке — но только ты знаешь какой твой).

Вроде ОК. Потом публикуют два списка:

1. Поименный список тех, кто был на участке — время и номер участка. Это по данным турникета на входе. Можно либо имя либо просто адрес. Это позволяет не дать возможность создания мертвых душ.
2. Список публичных ID а так-же какой выбор был сделан этим ID (ты сможешь сверить, твой ID записан в квитанции-распечатке на против твоего выбора).

Т.е. вроде все удалось решить кроме одного — нельзя проголосовать удаленно из дома

Дерево с O(1) доступом по ID

Fri, 09 Jan 2026 09:47:32 GMT

У меня есть дерево. То есть нулевой узел с дочерними узлами и каждый дочерний содержит свои дочерние и так далее
При создании ноды пользователю отдается unsigned int ID. И вот по этому ID нужен доступ за константное время. Идеально было бы как-то отразить дерево в вектор и чтоб ID был номером элемента в векторе. Но как-то криво выходит. Две структуры для одного и того же. Криво.
Еще вариант, что ID — это собственно сам указатель, но не нравится он мне
Какие есть варианты?

Как лучше сжать данные разрешенных ходов для игры?

Sun, 16 Nov 2025 19:16:37 GMT

Начало тут: https://rsdn.org/forum/etude/9018754.flat

В общем то классическая мельница 3*3, но с условием запрета обратного хода (т.е. походив фишкой, потом не можешь отменить/пойти взад этой последней фишкой).

Интересно что если нет этого условия — список состояний (и разрешенных ходов из данного состояния) в простом массиве занимает около 180 Кб. — что норм. Т.е. даже об этом не думал, чтобы как-то сжимать.

А вот если добавить правило запрета обратного хода — то чтобы правильно походило (с учетом запретов себя и противника) — полный список всех состояний и данных куда можно ходить — уже занимает 15.9 MB, что проблема. Т.е. уже загружать — быстро не откроется...

Что можно сделать. Очевидное — это симметрия. Левая и правая клеточка равнозначны. А вот верх и низ — уже нет, т.к. там зависит от игрока.

Т.е. за счет симметричности левого и правого — можно ужать в 2 раза.

Далее, я пишут в таком виде:

{
  red: [A1, A2, A3],
  black: [B1, B2, B3],
  redForbidden: null,
  blackForbidden: null,
  transitions: [
    [B1, C1],
    [B2, C1],
    [B2, C2],
    [B2, C3],
    [B3, C3],
  ],
}

т.е. текущее состояние и transitions — разрешенные переходы.

Но состояний то вроде не много, менее 16 тыс., значит влезет в 2 байта. Первые 4 поля значит — 8 байт с лихвой. Ну и преходы.

Еще вариант вычислять на лету, но будет нагружать слабые телефоны.

задача о таблетках

Thu, 30 Oct 2025 13:20:30 GMT

Возраст, увы, у меня почтенный, а поэтому приходится ежедневно принимать таблетки.

Таблеток N видов. Принимаю я ровно 1 таблетку каждого вида в день (это действительно так).

Таблетки в блистерах или флаконах. В одних блистерах 10 штук, в других 15, во флаконах иные значения.

Когда блистер или флакон заканчивается, я заменяю его на новый.

И вот сегодня одновременно закончились 2 разных блистера. Не помню, было ли такое когда-то раньше.

Отсюда задача — по исходному набору блистеров/флаконов найти день, когда одновременно закончатся хотя бы 2 блистера/флакона. Разумеется, у меня достаточно новых блистеров/флаконов.

Вариант 1. В день X я начинаю прием, все блистеры/флаконы полные.

Вариант 2. В день X я начинаю прием, но блистеры/флаконы неполные, в каждом осталось свое количество таблеток.

Найти день Y, в который закончатся хотя бы 2 блистера/флакона. Для определенности в течение некоторого срока, скажем, года. Если такого не будет, ответ — нет.

Программистское решение. Оно тривиально для обоих вариантов. Просто в цикле делаем T[i]-- каждому блистеру/флакону и смотрим, не получили ли мы хотя бы два нуля на данной итерации цикла. В общем, точная калька того, что я делаю в реальности.

Математическое решение для варианта 1. Оно тоже простое — нужно взять минимальное из НОК для пар блистеров/флаконов. Если, скажем, в одном блистере 10 таблеток, в другом 15, то НОК == 30, и через 30 дней я полностью съем 3 блистера первого лекарства и 2 — второго.

Существует ли математическое решение для варианта 2 ?

Не надо думать, что вариант 2 получился из варианта 1 спустя сколько-то дней, то есть начал я с полных блистеров/флаконов. Нет. Просто в день X в каждом блистере/флаконе Ti таблеток, а как их количества стали такими — не обсуждается.

Нечеткое сравнение слов.

Fri, 17 Oct 2025 01:22:18 GMT

Такая задача.

Есть набор из названий брендов (озвучено — порядка миллиона).
Есть входная строка, например "планшет Samsung"

Необходимо без ИИ сопоставить бренд из словаря этой строке.
Задача выглядит простой для решения — произвести токенизацию строки и затем поиск в хеш-таблице, где хранятся бренды.

Затем даётся дополнительное ТЗ — необходимо сделать поиск нечётким, т.е. с возможными опечатками.

И сделать поиск эффективным, т.е. придумать такой алгоритм, который не стал бы последовательно перебирать все слова используя, допустим, стороннюю библиотеку поиска дистанции между словами (есть полно готовых таких алгоритмов).

У меня есть решение, но мне банально интересно, к какой сложности относятся подобные задачи? ))

Найден способ считать кратчайшие пути быстрее Дейкстры?

Mon, 11 Aug 2025 19:51:32 GMT

На днях прошла новость: Breaking the Sorting Barrier for Directed Single-Source Shortest Paths

Классический Дейкстра устроен так: мы храним вершины в приоритетной очереди и итеративно выбираем ближайшую, проверяя рёбра и обновляя расстояния, если путь через текущее ребро короче. Узкое место тут как раз в необходимости постоянно поддерживать упорядоченность большой очереди вершин.

Из-за этой упорядоченности и возник так называемый «барьер сортировки». Считалось, что перебить его невозможно.

Но вот, что сделали авторы тут:

1. Делим задачу на подзадачи с ограничением по максимальному расстоянию, до которого считаем пути.
2. Сжимаем «фронтир»: из вершин на границе уже найденных путей оставляем только небольшое число ключевых (пивотов).
3. Рекурсивно обрабатываем только пивоты и их ближайшие вершины, избегая полной сортировки.
4. Для остальных вершин добиваем расстояния несколькими шагами по всем рёбрам (метод в духе Беллмана–Форда).
5. Повторяем процесс, постепенно уточняя расстояния до всех вершин.

Итого, сложность Дейкстры – O(m + n log n), а BMSSP – O(m log^(2/3) n). Во втором случае логарифм растет заметно медленнее.

Что это все значит для ML? Может показаться, что ничего. Но на самом деле алгоритм Дейкстры вездесущий. Например:

– В графовых нейросетях на основе расстояний между вершинами часто вычисляются самые важные фичи.
– Для всяких ML-алгоритмов для логистики просто незаменимо.
– И даже в RL есть применение. Например, при обучении роботов среда может быть представлена как граф состояний, в котором оптимальная политика – это кратчайший путь.

Отсюда: Исследователи из Пекина предложили алгоритм поиска кратчайших путей, который обходит Дейкстру

Здесь основная идея — это гибрид из алгоритма Дейкстры и алгоритма Беллмана-Форда.

Но если я все правильно понял, то в общем случае
* Новый алгоритм: O(m log²/³ n)
* Алгоритм Дейкстры: O(m + n log n)

1. Разреженные графы (Sparse Graphs): В таких графах количество рёбер m сопоставимо с количеством вершин n, то есть m ≈ n.
* Новый алгоритм: O(n log²/³ n)
* Алгоритм Дейкстры: O(n + n log n) = O(n log n)
* Вывод: В этом случае n log²/³ n растёт медленнее, чем n log n, поэтому новый алгоритм быстрее. Именно это и является его главным достижением, как указано в документе.

2. Плотные графы (Dense Graphs): В таких графах количество рёбер m близко к максимально возможному, то есть m приближается к n².
* Новый алгоритм: O(n² log²/³ n)
* Алгоритм Дейкстры: O(n² + n log n) = O(n²)
* Вывод: В этом случае n² растёт медленнее, чем n² log²/³ n. Поэтому на плотных графах алгоритм Дейкстры будет быстрее.

Получается что новый алгоритм эффективнее алгоритма Дейкстры на разреженных графах. Однако для плотных графов классический алгоритм Дейкстры остаётся более быстрым решением.

Так?

Алгоритмы и структуры данных

Sun, 27 Jul 2025 04:18:16 GMT

https://ru.algorithmica.org/cs/
На все случаи жизни...
И даже математика и даже геометрия

Написано в конце:

В этот раздел с течением времени будут переноситься статьи с алгокода, емакса и старой алгоритмики.

Хранилище интервалов

Sat, 26 Jul 2025 18:13:49 GMT

Всем привет.
Нужна помощь коллег.

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

Хотелось бы, чтобы эти операции работали быстрее, чем за линейное время.
Гугл предлагает дерево отрезков, но, если я правильно понимаю, добавление и удаление там в худшем случае будет как раз линейным.

В общем, нужна помощь коллективного разума

Трансформация дерева с простыми операциями

Wed, 04 Jun 2025 11:02:23 GMT

Привет
Пытаюсь починить парсер нашего рабочего доморощенного язычка и внезапно понял что мозг атрофировался за годы роботы в кровавом энтерпрайсе.

Итак, задача — есть дерево в котором два типа нодов — листья со значениями и узлы с операциями. Пусть операций два типа — сложение и умножение.
Надо заполнить структуру данных, которая содержит группы операций умножения, разделенные группами сложения, это неоходимо для заполнения другой структуры данных, которая потом отправится на удаленный сервак.

Т.е. выражение, распаршеное в дерево:
(a+b)*(c+d)*e должно превратиться в такое a*c*e+a*d*e+b*c*e+b*d*e.

      *
     / \
    *   e
   / \
  +   +
 / \ / \
a  b c  d

                        +
              ___________|___________
             /                       \
            +                         +
         ___|___                   ___|___
        /       \                 /       \
      (*       (* )            (* )      (* )
     /   \    /    \           /    \    /    \
   (* )  e   (* )  e         (* )   e  (* )   e
   /  \       /  \           /  \      /  \
  a    c     a    d         b    c    b    d

Какие идеи?
Спасибо.

Карацюба или Фюрер?

Sat, 17 May 2025 14:44:04 GMT

Здравствуйте!

Есть такие алгоритмы для умножения чисел:
Алгоритм Фюрера — https://ru.wikipedia.org/wiki/%D0%90%D0%BB%D0%B3%D0%BE%D1%80%D0%B8%D1%82%D0%BC_%D0%A4%D1%8E%D1%80%D0%B5%D1%80%D0%B0
Алгоритм Карацубы — https://ru.wikipedia.org/wiki/%D0%90%D0%BB%D0%B3%D0%BE%D1%80%D0%B8%D1%82%D0%BC_%D0%9A%D0%B0%D1%80%D0%B0%D1%86%D1%83%D0%B1%D1%8B

Какой из них лучше использовать?