Задание: дан неупорядоченный массив чисел, разбитый на два подмассива относительно выбранного элемента с определенным индексом. Элементы массива с индексом меньше индекса выбранного элемента находятся слева, с индексом больше – справа. Алгоритм быстрой сортировки рекурсивно вызывается для левого, а затем для правого подмассивов. Так как подмассивы не пересекаются, возможна параллельная (одновременная) сортировка.
Для решения данной задачи можно применить итеративную версию алгоритма быстрой сортировки, эмулируя рекурсивные вызовы посредством специальной структуры данных, например – стека. Таким образом, задание сводится к написанию многопоточной версии алгоритма быстрой сортировки.
Последовательная версия алгоритма итерактивного быстрой сортировки приложена к заданию. Приложение читает текстовый файл с набором целых чисел. В первой строке файла содержится размерность целочисленного массива (N), затем следуют N элементов массива, по одному в каждой строке.Количество элементов в массиве меньше чем 2^31 – 1. Отсортированный массив должен быть выведен в другой текстовый файл, по одному значению в строке.
Ограничение: Алгоритм Parallel Sort Algorithm библиотеки Intel(R) Threading Building Blocks не может быть использован в данном задании. Однако вы можете использовать любые другие функции и алгоритмы Intel(R) TBB.
Исходный файл: Quicksort.zip (Windows), Quicksort.tar (Linux)
Входные данные: InputData.in
Результат: Sorted.out
Внимание: Это конкурсное задание закрыто, решения больше не принимаются.
Совершенным числом принято называть натуральное число, равное сумме всех своих положительных делителей, отличных от самого числа. Древнегреческий математик Никомах из Геразы (60-120 до н.э.) предложил следующий алгоритм для вычисления совершенных чисел:
Записывайте степени числа два, начиная с единицы (1, 2, 4, 8, 16, 32, 64, 128, 256, 512, 1024, 2048, 4096 …). Каждый раз, записывая новое число, складывайте его со всеми предыдущими числами. Если сумма является простым числом, умножьте эту сумму на число, добавленное последним. Результат умножения является совершенным числом. Продолжайте до бесконечности.
Этот последовательный алгоритм изложен в теореме Евклида: каждое четное совершенное число можно представить в виде (2k − 1)2k−1, где k>1, при условии, что 2k − 1 является простым числом. Числа вида 2k − 1 также принято называть числами Мерсенна.
Задание: напишите программу для вычисления и вывода первых N совершенных чисел, где N – аргумент командной строки и N <= 10.
Пример:
> pnum.exe 4
The first 4 perfect numbers are:
6
28
496
8128
Ограничения: так как на данный момент первые 44 последовательных совершенных числа известны, вывод результата из таблицы заранее вычисленных данных не является допустимым решением. Приложение должно выполнять вычисление совершенных чисел.
Файлы данных: данное задание не включает файлов исходных данных. Результат должен быть выведен в поток stdout. Кроме файлов с исходным кодом, готовое решение должно содержать все необходимые файлы проекта, например solution файл или make файл, необходимые для того, чтобы построить и запустить приложение.
Критерии судейства: основным критериями будут время выполнения и точность результатов. Баллы за изящность будут начисляться за прозрачность кода и использование параллелизма. Дополнительные баллы могут быть начислены по решению жюри за алгоритмические находки, в особенности за уменьшение количества вычислений (например, использование только четных делителей для поиска простых чисел). Использование библиотеки Intel Threading Building Blocks также принесет дополнительные баллы.
Это интересно: 288(289 − 1) – это последнее совершенное число, вычисленное вручную, в 1911 году. Все остальные совершенные числа были найдены с использованием компьютеров. На данный момент самое большое найденное совершенное число это 232582656(232582657 − 1). Оно было вычислено на кластере из 700 компьютеров.
Внимание: Это конкурсное задание закрыто, решения больше не принимаются.
Февраль – месяц короткий, и, чтобы управиться с судейством до начала следующего этапа конкурса, мы выбрали сравнительно легкое задание. Если повезет, то дополнительный день високосного года использовать не придется.
Задание
Конкурсное задание «поиск корней» состоит из двух подзадач:
1. Найти наименьший положительный корень функции F(x) = -2 + sin(x) + sin(x^2) + … + sin(x^1000) в полуоткрытом интервале [0, 1) с точностью 10^(-11).
2. Определить количество корней приведенной выше функции в полуоткрытом интервале [1.0, 1.5), с точностью 10^(-7).
Требования: программный код для решения первой подзадачи должен представлять имплементацию какого-либо алгоритма поиска корней. Несколько примеров таких алгоритмов можно найти по ссылке http://en.wikipedia.org/wiki/Root-finding_algorithm.
Вторая подзадача может быть решена любым удобным вам методом. Корень считается найденным, если при заданной точности deltaX значения F(x) и F(x+deltaX) противоположны по знаку. Пример: для deltaX = 10^(-7), функция F(1.1234567) принимает значение 24.53456, а значением F(1.1234568) является -3.45812, следовательно, найден один корень.
В любом заданном интервале существует конечное число корней, но подсчитать их точное количество не представляется практически возможным, поскольку мы используем приближенные методы вычислений. Таким образом, несмотря на то, что между x и x+deltaX может существовать несколько корней, в рамках данного задания мы считаем найденным только один корень. Это позволит получить неизменные и повторяемые результаты решения задачи.
Ограничения: заранее вычисленные корни, заранее вычисленное число корней, также как и любые другие заранее известные данные (исключая данные из формулировки задания) не могут быть использованы в вашем коде. Судьи будут применять штрафы в случае нарушения данного ограничения. Ваш алгоритм может использовать первую, вторую, третью производные и производные функции F(x) более высокого порядка
Чтобы облегчить чтение вашего кода, рекомендуется привести краткое обоснование и описание использованных алгоритмов и подходов к распараллеливанию заданий.
Внимание: Это конкурсное задание закрыто. Решения больше не принимаются.
Оптимальное расселение
Комнаты студенческого общежития рассчитаны на двоих человек. При заселении студенты заполняют анкету, из которой можно узнать об их интересах. Необходимо написать многопоточное приложение, позволяющее распределить студентов по комнатам общежития, минимизируя расхождения во вкусах и интересах между соседями по комнате.
Анкета, заполненная студентами, содержит 50 вопросов. Каждый вопрос имеет 5 вариантов ответа, от «совершенно не согласен» (ноль) до «совершенно согласен» (четыре). Расхождение между любой парой студентов вычисляется путем суммирования абсолютной разницы между каждым из ответов двух анкет, с последующей нормализацией делением на 200,0 (максимально возможное расхождение двух анкет). Общее Расхождение в общежитии (ОР) вычисляется как сумма Расхождений между всеми парами студентов в комнатах.
Таким образом, задание сводится к минимизации величины ОР путем оценки различный вариантов расселения студентов.
Входные данные для задания представляют собой текстовый файл, первая строка которого содержит общее число студентов (N) для расселения. Затем следует N строк в следующем формате: уникальный идентификатор студента (10 символов), пробел, строка ответов на вопросы анкеты (50 символов). Строка ответов на вопросы анкеты состоит из символов 0, 1, 2, 3, 4.
Объем входных данных позволяет разместить их в основной памяти системы; N является четным числом, меньшим, чем 2^28 – 1.
Последовательность студентов в файле представляет собой «начальный» вариант расселения: первые два студента заселяются в одну комнату, следующие два – во вторую комнату, и т.д.
Пример входного файла:
2
ПупкинВася 01230230420314203422301230230420332023410123023042
ПетровПетя 20342230123023042031420342230123042031420342233042
Величина Общего Расхождения в данном примере составляет 0,305.
Ограничения структуры программы:
Основная программа должна иметь следующую структуру:
InputDataFromFile(Rooms, N);
first = EvaluateRooms(Rooms, N);
print("The initial Disharmony is", first);
start = GetTime;
ComputeRoomAssignments(Rooms, N);
end = GetTime;
print("Time to compute room assignments is ", end - start, "seconds");
final = EvaluateRooms(Rooms, N);
print("Final Disharmony is", final);
PrintRoomAssignmentToFile(Rooms, N);
Таким образом, вам необходимо: получить данные, вычислить и вывести начальное значение Общего Расхождения, запомнить время, вычислить вариант расселения с ОР меньшим начального, вывести потребовавшееся на вычисления время, вычислить и вывести величину ОР окончательного расселения, вывести идентификационные строки окончательного расселения в файл. Точное следование приведенным выше именам функций и переменных не требуется.
Ограничения алгоритма:
Так как прямые методы решения подобного рода задач могут быть ненадежными, а количество комбинаций при расселении увеличивается геометрически при увеличении числа студентов, ваш код должен использовать итерационные техники оптимизации, такие как эмуляция отжига (Simulated Annealing).
Ограничения времени:
Установлено двухминутное ограничение времени выполнения программы. Если ваше приложение вычисляет результат дольше, чем 120 секунд, конкурсные баллы не начисляются.
Входные данные: Students.in
Результат: Assignments.out
Внимание: Это конкурсное задание закрыто. Решения больше не принемаются.
Игра "жизнь" (Game of Life)
Игра «Жизнь», придуманная математиком Джоном Конвеем (John Conway) представляет собой модель колонии организмов, населяющих прямоугольную решетку.
Каждая клетка решетки либо заселена живым организмом (жива), либо пуста (мертва). Моделирование представляет собой «регистрацию» рождений и смертей организмов в последовательных временных интервалах (поколениях). Теоретически, решетка «вселенной» бесконечна, но для данной компьютерной модели мы ограничим размер решетки соотвественно доступному объему памяти.
Состояние клеток изменяется от поколения к поколению по следующим правилами:
- Соседями клетки являются восемь клеток, граничащие с ней по вертикали, горизонтали и диагоналям.
- Если клетка жива и не имеет соседей или имеет единственного живого соседа, она погибнет от голода в следующем поколении.
- Если клетка жива и имеет четырех и более живых соседей, она погибнет от перенеселения в следующем поколении.
- Живые клетки с двумя или тремя живыми соседями продолжают жить в следующем поколении.
- Если клетка мертва и имеет ровно троих живых соседей, она оживает в следующем поколении. Все прочие мертвые клетки остаются мертвыми в следующем поколении.
- Все рождения и смерти происходят одновременно: умирающая клетка может способствовать рождению, но не может предотвратить смерть, уменьшая перенаселенность. Также как рождающиеся клетки не могут убить или защитить клетки, жившие в предыдущем поколении.
Типовой алгоритм моделирования проверяет все ячейки решетки, подсчитывает соседей для каждой ячейки, и определяет остается ли клетка живой, умрет или родится в данном поколении.
Альтернативный алгоритм хранит список клеток, которые могут потребовать внимания в следующем поколении. Таким образом, вычисления происходят только для ячеек, которые могут изменить статус или повлиять на его изменение. Данный алгоритм приведен в приложенном коде. Текстовый файл с более детальным описанием ключен в архив кода.
Ограничения кода: необходимо сохранить и использовать алгоритм функции Main, и четыре процедуры, использующиеся для обработки списков. Реализация структур данных (клетки, решетка и списки) могут быть изменены при необходимости.
Описание файла с исходными данными: приложение должно принимать начальный набор данных для моделирования из файла. Имя файла с исходными данными можно передать, например, через аргумент командной строки. Файл содержит строки с парами целых чисел, определяющих координаты (строки и столбцы) клеток, которые живы в начале моделирования. Строка с нулевой координатой (0 0) является признаком окончания списка живых клеток. Далее следует строка, содержащая целое число поколений, которые необходимо смоделировать. За ней следует пара координат, определяющих область решетки, которую необходимо вывести на стандартное уствройство (stdout) по окончании моделирования. (Пример файла с исходными данными virus.dat входит в задание).
Внимание: Это конкурсное задание закрыто. Решения больше не принимаются.
Исходный архив задания: Game of Life.zip (Windows), gameoflife.tar (Linux)
Дана матрица. Транспонируйте её.
Внимание: Это конкурсное задание закрыто. Решения больше не принимаются.
Дан неотсортированный массив чисел. Необходимо разделить его на два подмассива и рекурсивно отсортировать их. Когда останется отсортировать один или два элемента подмассивов, подмассивы необходимо объединить в один отсортированный список.
Внимание: Это конкурсное задание закрыто. Решения больше не принимаются.
Дан взвешенный ориентированный граф. Необходимо найти кратчайшие пути между любыми двумя его вершинами.
Внимание: Это конкурсное задание закрыто. Решения больше не принимаются.
Судоку – логическая головоломка, которая решается путём размещения чисел в матрице таким образом, чтобы одно и то же число не повторялось в строке, столбце или подгруппе матрицы. Наиболее часто используется матрица размером 9x9, где каждая строка, столбец и каждая из девяти непересекающихся подгрупп 3х3 могут содержать только одно целое число из группы 1-9. Помимо формата 9х9, также встречаются матрицы 16x16 и 6x6. Кроме того, существуют версии головоломки, в которых не используются квадратные подгруппы.
Задача: Напишите многопоточное приложение для определения того, имеют ли заданные головоломки судоку с матрицей 6х6 уникальное решение. В верных решениях для данного варианта головоломок числа от 1 до 6 должны встречаться в каждой строке и каждом столбце только один раз. При этом непересекающиеся подгруппы 2х3 (2 строки, 3 столбца) должны содержать только по одному из указанных 6 целых чисел. Например:
2 3 1 | 4 5 6
6 5 4 | 3 2 1
-------------
1 4 3 | 5 6 2
5 6 2 | 1 3 4
-------------
3 1 6 | 2 4 5
4 2 5 | 6 1 3
Описание файла ввода данных: Имя файла ввода данных (input file) передается программе при ее запуске номинально в виде аргумента командной строки. Файл содержит некоторое количество строк, каждая из которых должна состоять из 36 непустых символов. Каждая строка представляет собой начальное положение возможной головоломки Судоку 6х6, развернутой в виде двумерного массива. Пустые поля в исходной головоломке отображаются в виде символа звездочки (*). Конец файла обозначает конец ввода.
Вывод: Вывод реализуется в виде потока stdout. Должно иметься указание на то, имеет ли каждая головоломка уникальное решение, не имеет решения вообще или имеет несколько верных решений.
Пример ввода с тремя головоломками:
*314*******1**356**621**3*******561*
***4****41*2*4321**6534*5*16****6***
*****5*5*******5****5*******5*5*****
(Первая строка соответствует начальному положению решенной головоломки, представленной выше)
Пример вывода:
Головоломка №1 имеет УНИКАЛЬНОЕ решение
Головоломка №2 НЕ имеет решения
Головоломка №3 имеет НЕСКОЛЬКО решений
Время на решение задачи: В судействе жюри будет руководствоваться показаниями настенных часов (включая время ввода/вывода).
Пара целых чисел считается "дружественной" (AMICABLE), если сумма собственных делителей одного числа равна сумме делителей второго числа и наоборот.
Пример: 220, 284 220=2^2*5*11 (1+2+4+5+10+11+20+22+44+55+110 = 284) 284=2^2*71 (1+2+4+71+142 = 220)
Возьмем отношение суммы делителей натурального числа к самому числу, R(n). Если у двух натуральных чисел имеются равные отношения, такие числа называются «дружескими» (FRIENDLY).
Пример: 30, 140 R(30) = (1+2+3+5+6+10+15+30)/30 = 12/5 R(140) = (1+2+4+5+7+10+14+20+28+35+70+140)/140 = 12/5
Задача: Напишите многопоточное приложение для нахождения и вывода на печать каждой пары дружественных чисел и каждой пары дружеских чисел, находящихся в заданном диапазоне. Диапазон – два положительных целых числа – вводится в приложение перед началом выполнения номинально в виде аргументов командной строки.
Пример выполнения:
> amicable.exe 200 600
220 и 284 дружественные (AMICABLE)
240 и 600 дружеские (FRIENDLY)
Ограничения: В исходные файлы или вспомогательные файлы, используемые приложением, нельзя включать непосредственные данные или информацию. Например, нельзя использовать таблицы простых чисел или списков дружественных или дружеских чисел. Вся информация такого рода должна быть сгенерирована приложением в процессе выполнения.
Время на решение: При судействе будет учитываться реальное время (включая ввод и вывод).
Существует несколько методов обеспечения сбалансированности бинарных деревьев при добавлении новых элементов. Возможно ли создание бинарного дерева, в котором среднее количество узлов, пройденных при поиске по определённому критерию, будет минимальным?
Подробная информация о данном задании будет доступна позднее.
Разместите N ферзей на шахматном поле размером N х N клеток таким образом, чтобы ни один из ферзей не находился под боем другого. Вариантом этой задачи является условие разместить на поле заданного размера равное количество ферзей и коней.
Подробная информация о данном задании будет доступна позднее.
|
|
