Поддержу Python. Во-первых ни у кого не возникает вопросов, по непонятным static, class, void, String[] args, и преподавателю не надо говорить, что «мантра» такая. А во-вторых, студентов дальше ждут курсы машинного обучения, криптографии, выпуклого анализа. В Python и библиотек достаточно, и боли в реализации не так много, как на Java или C++. Производительность программ страдает, да, но ведь цель — знакомство.
Чего-то я не понимаю. Вот обычное решето Эратосфена: pastebin.com/ck9kuEMg
700к считает примерно за секунду (нужно взять хотя бы 15М чисел).
20М считает секунд за 40.
Вывод не считаю, поскольку не зависит от алгоритма. Зачем решето Аткина?
Кстати, вот девятая задача действительно какая-то головоломная. Я знаю, как показывается нижняя оценка на подсчет числа инверсий (тоже Omega(n)). Но вот именно четность не получается пробить.
Может и не все, но многие. Пример в комментарии ниже показывает, что памяти потребуется много: Omega(n log n). Я может очень кратко там написал, могу здесь расписать.
Пусть у нас есть алгоритм, который использует t бит памяти.
Мы строим граф на основе циклической перестановки (такой, что p(x) != x для всех x). Граф двудольный, состоит из долей A и B. В каждой доле n вершин. Сначала проводим ребра из вершины a_i в вершину b_{p_i} для каждого i. Скормим эти ребра алгоритму и посмотрим на его память.
Я утверждаю, что из памяти можно извлечь всю перестановку. Если это так, то для разных перестановок состояния памяти должны быть разные. Значит, должно быть, что 2^t >= (n — 1)! или t = Omega(n log n).
Почему можно извлечь перестановку? Зафиксируем некоторое значение j и проведем ребра из b_i в a_i для вcех i != j. Скормим их алгоритму. Мы получили Эйлеров граф, в котором вторая вершина будет как раз b_{p_j}. Алгоритм её должен выдать. Понятно, что такую процедуру можно запустить для всякого j и восстановить перестановку.
P.S. Примерно такой же конструкцией можно показать, что и вероятностные алгоритмы тоже не помогут.
Для определения второго человека детерминированный алгоритм потребует Omega(n log n) памяти, где n — число вершин. Можно взять двудольный граф и зашить в него циклическую перестановку. Дальше можно расположить ребра так, что после их обработки из памяти алгоритма можно извлечь всю перестановку.
Ребра, которые сначала алгоритм обработает чтобы получить интересную память, будут иметь вид a_i -> b_{p_i}. Чтобы узнать, куда ползет элемент j, нужно добавить в граф ребра b_i -> a_i для всех i != j.
Если я правильно понял, у нас есть орграф, содержащий Эйлеров путь. В задаче мы ищем начало и конец. На самом деле можно решение упростить, если все вершины рассматривать как числа и по всем ребрам проссумировать значения u — v и u^2 — v^2. Вроде красивая система будет.
Со второй вершиной пути не очень понятно. Если стартовая вершина лежит на нескольких циклах, то вторую вершину можно определить по разному. Если она одна, сходу ничего в голову не лезет. Подумаю.
Я для себя понял, что мы берём 2k значений. Дальше для каждого a_j получаем дробь вида p(a_j) / q(a_j) = x_j / y_j. Это можно записать как y_j * p(a_j) = q(a_j) * x_j. Дальше имеем 2k таких уравнений c 2k неизвестными. Решаем Гауссом, а потом факторизуем.
В статье по ссылке чуть проще решение. Пусть p(x) = prod_{i = 1..n} (x — i), а q(x) = prod_{a in A} (x — a), где A — те элементы, которые есть в массиве. Можно заметить, что p(x) / q(x) = t(x) = prod_{i = 1..k} (x — y_i), где y_i как раз пропавшие элементы. Можно посчитать p и q в k + 1 точке над каким-нибудь конечным полем, проинтерполировать полином t(x) и потом его факторизовать.
Да, вполне. Для двух пропавших можно найти сумму всех чисел и сумму их квадратов. Получим два уравнения: x1 + x2 = S1, x1^2 + x2^2 = S2. Осталось решить систему.
Если обобщать до k пропавших, то может возникнуть проблема с большими порядками для вычислений. Есть альтернатива: ipsit.bu.edu/documents/ieee-it3-web.ps
Можно немного по-другому об этом подумать. Есть баланс между тем, как аккуратно используется память, и сколько времени занимает добавление одного элемента в среднем. Скажем, если память увеличивать в 2 раза, то добавление элемента будет стоить 4 условных такта, а если в 1.01 — то примерно 100 таких условных тактов.
Да, интересная задача. Если в один проход решать, то можно ткнуть в несколько случайных элементов и выбрать из них медиану. Если элементов будет порядка O(1/eps^2 \log(1/delta)), то вероятность, что выбранный элемент будет стоять от медианы на расстоянии не более eps * n будет не меньше 1 — delta.
А еще вроде есть хитрый алгоритм Мунро-Патерсона, который умеет эту задачу решать точно с O(1) памяти за O(log n) проходов.
Есть два замечания. Во-первых, задача о покрытии множествами является NP-полной. Ни одной такой задачи за последние лет 50 не решили, и сомнительно, что решат.
Во-вторых, я дошел до теоремы 2 и нашел там ошибку. Если в последнем условии пересечение V-шек по E^* не пусто, то соответствующее S^* никак не будет покрытием. Дальше я решил пока не вникать. Мне кажется, что вы ищете решение не среди всего множества решений, а только среди части. Думаю, что в этом основная ошибка.
Я не могу и не вижу возможным удовлетворить интерес каждого человека. Поэтому я стараюсь писать о том, что интересно хотя бы мне. Динамические деревья поразили меня своей гибкостью. Единственный аналог, который я знаю, есть в строках — это суффиксные деревья.
По поводу постановки задачи. Может она кому-то кажется сухой, но зато она лаконична и ответы легко проверяемы. Я не хочу плодить рассуждения о реальной жизни на авось. Для этого достаточно других тем. А ставить настоящие эксперименты — это действительно сложно, и одним абзацем тут не отделаешься.
По поводу востребованности. Вы можете посмотреть обзор, про который я написал в конце поста. Писать, зачем нужны потоки, именно здесь мне кажется лишним.
700к считает примерно за секунду (нужно взять хотя бы 15М чисел).
20М считает секунд за 40.
Вывод не считаю, поскольку не зависит от алгоритма. Зачем решето Аткина?
Кстати, вот девятая задача действительно какая-то головоломная. Я знаю, как показывается нижняя оценка на подсчет числа инверсий (тоже Omega(n)). Но вот именно четность не получается пробить.
Пусть у нас есть алгоритм, который использует t бит памяти.
Мы строим граф на основе циклической перестановки (такой, что p(x) != x для всех x). Граф двудольный, состоит из долей A и B. В каждой доле n вершин. Сначала проводим ребра из вершины a_i в вершину b_{p_i} для каждого i. Скормим эти ребра алгоритму и посмотрим на его память.
Я утверждаю, что из памяти можно извлечь всю перестановку. Если это так, то для разных перестановок состояния памяти должны быть разные. Значит, должно быть, что 2^t >= (n — 1)! или t = Omega(n log n).
Почему можно извлечь перестановку? Зафиксируем некоторое значение j и проведем ребра из b_i в a_i для вcех i != j. Скормим их алгоритму. Мы получили Эйлеров граф, в котором вторая вершина будет как раз b_{p_j}. Алгоритм её должен выдать. Понятно, что такую процедуру можно запустить для всякого j и восстановить перестановку.
P.S. Примерно такой же конструкцией можно показать, что и вероятностные алгоритмы тоже не помогут.
Ребра, которые сначала алгоритм обработает чтобы получить интересную память, будут иметь вид a_i -> b_{p_i}. Чтобы узнать, куда ползет элемент j, нужно добавить в граф ребра b_i -> a_i для всех i != j.
Со второй вершиной пути не очень понятно. Если стартовая вершина лежит на нескольких циклах, то вторую вершину можно определить по разному. Если она одна, сходу ничего в голову не лезет. Подумаю.
Если подумать, то это вполне элегантное решение.
Если обобщать до k пропавших, то может возникнуть проблема с большими порядками для вычислений. Есть альтернатива: ipsit.bu.edu/documents/ieee-it3-web.ps
А еще вроде есть хитрый алгоритм Мунро-Патерсона, который умеет эту задачу решать точно с O(1) памяти за O(log n) проходов.
Во-вторых, я дошел до теоремы 2 и нашел там ошибку. Если в последнем условии пересечение V-шек по E^* не пусто, то соответствующее S^* никак не будет покрытием. Дальше я решил пока не вникать. Мне кажется, что вы ищете решение не среди всего множества решений, а только среди части. Думаю, что в этом основная ошибка.
По поводу постановки задачи. Может она кому-то кажется сухой, но зато она лаконична и ответы легко проверяемы. Я не хочу плодить рассуждения о реальной жизни на авось. Для этого достаточно других тем. А ставить настоящие эксперименты — это действительно сложно, и одним абзацем тут не отделаешься.
По поводу востребованности. Вы можете посмотреть обзор, про который я написал в конце поста. Писать, зачем нужны потоки, именно здесь мне кажется лишним.