Завдання

Відповідно до номера свого варіанта виконайте завдання обраного рівня складності.

Варіанти

Варіант 1. Теплопровідність пластини

1. Початковий рівень. Створити консольну програму мовою C++ з OpenMP, яка моделює нагрівання квадратної пластини 500×500 вузлів (лівий край 100 °C, решта 0 °C) явною схемою з коефіцієнтом $r=0,2$ протягом 1000 кроків, розпаралелюючи оновлення вузлів директивою parallel for collapse(2), і виводить температуру в центрі пластини, суму температур і час обчислення (omp_get_wtime).

2. Базовий рівень. Створити консольну програму мовою C++ з OpenMP, яка моделює нагрівання квадратної пластини (лівий край 100 °C, решта 0 °C) явною схемою. Програма запитує розмір сітки $n$ (від 100 до 4000) і кількість кроків (від 1 до 10 000), перевіряє введення та моделює послідовно й паралельно (collapse(2), ініціалізація за політикою першого дотику) для 1, 2, 4, 8 і 16 потоків, перевіряє, що різниця температур не перевищує ${10}^{-12}$, і виводить таблицю «потоки – час, с – $S$ – $E$».

3. Високий рівень. Створити проєкт CMake (find_package(OpenMP), ціль OpenMP::OpenMP_CXX) з програмою heat2d, яка моделює нагрівання квадратної пластини явною схемою (оновлення вузлів parallel for collapse(2)) з опціями --size <n>, --steps <k>, --threads 1,2,4,8, --init parallel|serial, --csv <файл>, --image <файл.pgm> і --help. Програма виводить медіану трьох запусків, прискорення й ефективність для кожної кількості потоків з поточними OMP_PROC_BIND і OMP_PLACES, записує CSV і зображення температур PGM. Сценарій запускає програму для OMP_PROC_BIND=close|spread і OMP_PLACES=threads|cores. Некоректні опції – у stderr з кодом 1.

Варіант 2. Множина Мандельброта

1. Початковий рівень. Створити консольну програму мовою C++ з OpenMP, яка обчислює множину Мандельброта для зображення 1600×1200 точок (не більше 1000 ітерацій на точку) директивою parallel for за рядками, записує результат у файл mandel.pgm і виводить загальну кількість ітерацій та час обчислення.

2. Базовий рівень. Створити консольну програму мовою C++ з OpenMP, яка запитує розміри зображення (від 100 до 8000) і максимальну кількість ітерацій (від 100 до 10 000), перевіряє введення й обчислює множину Мандельброта з schedule(static), schedule(dynamic, 1), schedule(dynamic, 16) і schedule(guided). Для кожного виду програма виводить медіану трьох запусків, прискорення відносно послідовної версії, відношення часу роботи найменш і найбільш завантаженого потоку та перевіряє збіг загальної кількості ітерацій.

3. Високий рівень. Створити проєкт CMake з програмою mandelbench, яка обчислює множину Мандельброта паралельним циклом за рядками зі schedule(runtime) і приймає опції --size <ш>x<в>, --iter <n>, --schedules static,dynamic,guided, --chunks 1,8,64, --threads 1,2,4,8,16, --csv <файл>, --image <файл.pgm> і --help. Для кожної комбінації виду розподілу (omp_set_schedule), порції й кількості потоків програма вимірює медіану трьох запусків, виводить таблицю «вид – порція – потоки – час – $S$ – $E$», позначає найкращу комбінацію для кожної кількості потоків і записує CSV. Некоректний вид розподілу або розмір – у stderr з кодом 1.

Варіант 3. Задача про n ферзів

1. Початковий рівень. Створити консольну програму мовою C++ з OpenMP, яка підраховує кількість розстановок $n=12$ ферзів на шаховій дошці $n\times n$, створюючи окрему задачу task для кожного положення ферзя в першому рядку, збирає результати задач без гонитви і виводить кількість розв’язків (14 200) та час.

2. Базовий рівень. Створити консольну програму мовою C++ з OpenMP, яка запитує розмір дошки $n$ (від 4 до 16) і глибину відсікання $d$ (від 0 до 4), перевіряє введення та підраховує розв’язки задачі про $n$ ферзів рекурсивним перебором із задачами OpenMP до глибини $d$ (нижче – послідовно). Програма виводить кількість розв’язків, кількість створених задач (atomic) і таблицю часу та прискорення для 1, 2, 4, 8 і 16 потоків.

3. Високий рівень. Створити проєкт CMake з програмою nqueens, яка приймає опції --n 8-16, --cutoff 0,1,2,3,4, --threads 1,2,4,8,16,32, --csv <файл> і --help. Для кожного $n$ з діапазону програма розв’язує задачу послідовно та задачами OpenMP з різними глибинами відсікання (taskgroup, бітові маски зайнятих стовпців і діагоналей), перевіряє кількість розв’язків за відомими значеннями, виводить таблицю часу, прискорення, ефективності й кількості задач і найкращу глибину для кожної кількості потоків. Розбіжність кількості розв’язків – код завершення 2, помилки опцій – код 1.

Варіант 4. Інтеграл методом Монте-Карло

1. Початковий рівень. Створити консольну програму мовою C++ з OpenMP, яка оцінює інтеграл функції $e^{-x^2}$ на відрізку $[0,2]$ методом Монте-Карло за ${10}^8$ випадкових точок: кожен потік має власний генератор std::mt19937_64 із зерном 42 + номер потоку, а сума накопичується клаузою reduction(+:sum). Програма виводить оцінку, відхилення від точного значення $\sqrt{\pi }/2\cdot \text{erf}(2)$ і час.

2. Базовий рівень. Створити консольну програму мовою C++ з OpenMP, яка запитує кількість випробувань $N$ (від ${10}^5$ до ${10}^9$) і номер функції з меню ($\sin (x)$ на $[0,\pi ]$, $x^2$ на $[0,3]$, $e^{-x^2}$ на $[0,2]$), перевіряє введення та оцінює інтеграл для 1, 2, 4, 8 і 16 потоків. Генератори створюються для блоків по ${10}^6$ випробувань (зерно – номер блоку), тому оцінка не залежить від кількості потоків. Програма виводить таблицю «потоки – оцінка – похибка – стандартна похибка – час – $S$ – $E$».

3. Високий рівень. Створити проєкт CMake з програмою mcint, яка оцінює інтеграл методом Монте-Карло паралельно (OpenMP, незалежні генератори для блоків випробувань) з опціями --function sin|poly|gauss, --samples 1e6,1e7,1e8, --threads 1,2,4,8,16, --seed <n>, --csv <файл> і --help. Програма виводить таблицю оцінок, абсолютних і стандартних похибок, часу, прискорення та ефективності, перевіряє відтворюваність (той самий --seed з іншою кількістю потоків дає ту саму оцінку, інакше код 2) і записує CSV. Помилки аргументів – у stderr з кодом 1.

Варіант 5. Гра «Життя»

1. Початковий рівень. Створити консольну програму мовою C++ з OpenMP, яка моделює гру «Життя» Конвея на полі 2000×2000 клітинок із замкненими краями (початковий стан – випадковий, 30 % живих, фіксоване зерно) протягом 500 поколінь, розпаралелюючи обчислення нового покоління директивою parallel for, і виводить кількість живих клітинок (reduction) та час.

2. Базовий рівень. Створити консольну програму мовою C++ з OpenMP, яка читає розміри поля (від 10 до 10 000), кількість поколінь і частку живих клітинок, перевіряє введення, виконує моделювання послідовно й паралельно (обидва масиви поля ініціалізуються паралельно за політикою першого дотику), перевіряє збіг кінцевих полів і виводить таблицю часу, прискорення та ефективності для 1, 2, 4, 8 і 16 потоків, а також кількість живих клітинок кожні 100 поколінь.

3. Високий рівень. Створити проєкт CMake з програмою life, яка паралельно (OpenMP) моделює гру «Життя» Конвея. Початковий стан читається з текстового файлу (. і #) або генерується (--random <ш>x<в>); опції --generations <n>, --threads, --init parallel|serial, --out <файл>, --csv <файл>, --check і --help. Програма виводить таблицю часу на покоління для кожної кількості потоків і способу ініціалізації, зберігає кінцевий стан, а з --check порівнює результат із послідовним. До звіту додаються вимірювання з OMP_PROC_BIND=close і spread. Помилки файлу – код 2, аргументів – 1.

Варіант 6. Кластеризація клієнтів k-means

1. Початковий рівень. Створити консольну програму мовою C++ з OpenMP, яка генерує 1 000 000 клієнтів із двома ознаками (річні витрати й кількість покупок, 5 нормальних кластерів, фіксоване зерно), виконує 20 ітерацій алгоритму k-means для $k=5$, розпаралелюючи пошук найближчого центроїда директивою parallel for, і виводить координати центроїдів та час.

2. Базовий рівень. Створити консольну програму мовою C++ з OpenMP, яка запитує кількість клієнтів (від 1000 до ${10}^7$), кількість кластерів $k$ (від 2 до 20) і максимальну кількість ітерацій, перевіряє введення та виконує k-means до стабілізації центроїдів. Суми координат і кількості точок кластерів накопичуються власною редукцією (declare reduction для структури масивів сум). Програма виводить центроїди, розміри кластерів, кількість ітерацій, середній час ітерації та перевіряє збіг результату з послідовною версією.

3. Високий рівень. Створити проєкт CMake з програмою kmeans, яка читає клієнтів із CSV-файлу (id;витрати;покупки), приймає опції --k <n>, --max-iter <n>, --threads 1,2,4,8,16, --seed <n>, --out <файл> і --help, нормалізує ознаки, виконує k-means з власною редукцією, записує номер кластера кожного клієнта у вихідний CSV і виводить таблицю «потоки – ітерацій – час на ітерацію – $S$ – $E$» та сумарну внутрішньокластерну дисперсію. Помилки формату (номер рядка) виводяться в stderr з кодом 2, помилки аргументів – з кодом 1.

Варіант 7. Найкоротші шляхи Флойда–Воршелла

1. Початковий рівень. Створити консольну програму мовою C++ з OpenMP, яка генерує мережу доріг із 1500 міст (випадкові відстані від 1 до 100 км для 5 % пар, фіксоване зерно), обчислює матрицю найкоротших відстаней алгоритмом Флойда–Воршелла з паралельним циклом за рядками всередині зовнішнього циклу за $k$ і виводить суму всіх скінченних відстаней та час.

2. Базовий рівень. Створити консольну програму мовою C++ з OpenMP, яка запитує кількість міст (від 10 до 4000) і густину доріг у відсотках, перевіряє введення, виконує алгоритм Флойда–Воршелла послідовно й паралельно для 1, 2, 4, 8 і 16 потоків, перевіряє збіг матриць і виводить таблицю часу, прискорення й ефективності, а також найдовший із найкоротших шляхів (діаметр мережі) і відповідну пару міст.

3. Високий рівень. Створити проєкт CMake з програмою roads, яка читає список доріг із файлу (місто1;місто2;км), приймає опції --threads, --schedule static|dynamic, --route <A>,<B>, --sizes 500,1000,2000 (для синтетичних мереж) і --help, обчислює матриці відстаней і попередників, відновлює маршрут між заданими містами та виводить таблицю сильної масштабованості для кожного розміру з частинами часу на parallel області. Невідоме місто – код завершення 2, помилки файлу чи аргументів – код 1.

Варіант 8. Швидке сортування задачами

1. Початковий рівень. Створити консольну програму мовою C++ з OpenMP, яка заповнює вектор з 20 000 000 цілих чисел генератором із фіксованим зерном, сортує копії послідовним швидким сортуванням і паралельним швидким сортуванням на задачах OpenMP (taskgroup, поріг 10 000 елементів), перевіряє впорядкованість (std::is_sorted) і виводить час обох сортувань.

2. Базовий рівень. Створити консольну програму мовою C++ з OpenMP, яка запитує розмір масиву (від ${10}^5$ до ${10}^8$) і перелік порогів через кому, перевіряє введення та для кожного порогу вимірює медіану трьох запусків паралельного швидкого сортування задачами. Програма виводить таблицю «поріг – час – прискорення відносно послідовного – прискорення відносно std::sort», позначає найкращий поріг і перевіряє кожен результат.

3. Високий рівень. Створити проєкт CMake з програмою qsortomp, яка приймає опції --size, --threads, --cutoff, --data random|sorted|reversed|few-unique, --pivot middle|median3 і --help. Програма порівнює послідовне швидке сортування, задачі OpenMP і std::sort з std::execution::par (якщо доступний), виводить таблицю часу й прискорення для кожного виду даних і кількості потоків та перевіряє результати. Для даних sorted і few-unique програма показує вплив вибору опорного елемента. Помилки опцій – у stderr з кодом 1.

Варіант 9. LU-розклад матриці

1. Початковий рівень. Створити консольну програму мовою C++ з OpenMP, яка генерує матрицю 1000×1000 з діагональною перевагою (фіксоване зерно), виконує LU-розклад без вибору головного елемента, розпаралелюючи оновлення підматриці на кожному кроці директивою parallel for, і виводить час та максимальне відхилення добутку $LU$ від вихідної матриці.

2. Базовий рівень. Створити консольну програму мовою C++ з OpenMP, яка запитує розмір матриці (від 10 до 3000), перевіряє введення, виконує LU-розклад послідовно та паралельно з schedule(static) і schedule(dynamic) для 1, 2, 4, 8 і 16 потоків, розв’язує систему $Ax=b$ для відомого $x$ і виводить таблицю часу, прискорення та норми похибки розв’язку для кожного варіанта.

3. Високий рівень. Створити проєкт CMake з програмою lu, яка читає матрицю з файлу або генерує її (--random <n>), приймає опції --pivot none|partial, --block <b> (блоковий розклад), --threads, --csv <файл> і --help, виконує LU-розклад з частковим вибором головного елемента, обчислює визначник і розв’язок для правої частини з файлу. Програма виводить таблицю часу, прискорення, ефективності й залишку $\Vert Ax-b\Vert$ для кожного розміру блоку та кількості потоків. Вироджена матриця – код завершення 2, помилки аргументів – код 1.

Варіант 10. Метод спряжених градієнтів

1. Початковий рівень. Створити консольну програму мовою C++ з OpenMP, яка розв’язує систему з тридіагональною матрицею розміром 1 000 000 (4 на діагоналі, −1 поруч) методом спряжених градієнтів, розпаралелюючи скалярний добуток (reduction(+:…)), операцію axpy і множення матриці на вектор, та виводить кількість ітерацій, норму залишку й час.

2. Базовий рівень. Створити консольну програму мовою C++ з OpenMP, яка запитує розмір системи (від ${10}^3$ до ${10}^8$) і точність $ϵ$, перевіряє введення, розв’язує систему для п’ятиточкової матриці двовимірної задачі Пуассона методом спряжених градієнтів послідовно й паралельно і виводить таблицю: потоки, кількість ітерацій, норма залишку, загальний час, частки часу на скалярні добутки, axpy і множення матриці на вектор, прискорення.

3. Високий рівень. Створити проєкт CMake з програмою cg, яка читає розріджену симетричну матрицю у форматі Matrix Market (.mtx, зберігання CSR), приймає опції --tol, --max-iter, --threads, --schedule static|dynamic, --precond none|jacobi і --help, розв’язує систему з правою частиною з одиниць і виводить історію норми залишку кожні 10 ітерацій та таблицю масштабованості. Несиметрична матриця або відсутність збіжності – код завершення 2 з повідомленням у stderr, помилки аргументів – код 1.

Варіант 11. Розмиття Гаусса для фото

1. Початковий рівень. Створити консольну програму мовою C++ з OpenMP, яка читає зображення у форматі PGM (P5), шлях до якого вводить користувач, застосовує розмиття Гаусса з ядром 5×5 директивою parallel for collapse(2), записує результат у файл blur.pgm і виводить розміри зображення та час обробки.

2. Базовий рівень. Створити консольну програму мовою C++ з OpenMP, яка читає зображення PPM (P6) і радіус розмиття $r$ (від 1 до 20), будує одновимірне ядро Гаусса й виконує розмиття двома проходами чотирма способами: послідовно, omp simd для внутрішнього циклу, parallel for і parallel for simd. Програма перевіряє побайтовий збіг результатів і виводить таблицю часу та прискорення кожного способу.

3. Високий рівень. Створити проєкт CMake з програмою gblur, яка приймає аргументи input.ppm output.ppm та опції --radius <r>, --mode seq|simd|parallel|parallel-simd|all, --threads, --repeat <n> і --help. Ядро згортки оголошено функцією declare simd. Програма виводить таблицю «режим – потоки – час, мс – $S$ – мегапікселів за секунду», зберігає результат і перевіряє, що всі режими дають однакове зображення (інакше код завершення 3). Помилки формату PPM – код 2, аргументів – код 1.

Варіант 12. Гістограма зросту населення

1. Початковий рівень. Створити консольну програму мовою C++ з OpenMP, яка генерує зріст 50 000 000 людей (нормальний розподіл: середнє 170 см, відхилення 10 см, генератор на потік) і будує гістограму за інтервалами по 5 см від 120 до 220 см за допомогою reduction(+:hist[0:20]), виводячи гістограму у вигляді таблиці з рядками символів #.

2. Базовий рівень. Створити консольну програму мовою C++ з OpenMP, яка запитує кількість людей (від ${10}^5$ до ${10}^9$) і ширину інтервалу, перевіряє введення та будує гістограму чотирма способами: спільний масив із critical, спільний масив з atomic, локальні гістограми потоків з об’єднанням наприкінці та reduction масиву. Програма перевіряє однаковість гістограм і виводить таблицю часу й прискорення кожного способу для 16 потоків.

3. Високий рівень. Створити проєкт CMake з програмою heights, яка читає зріст із текстового чи двійкового файлу або генерує дані (--generate <n>), приймає опції --bin <см>, --method critical|atomic|local|reduction|all, --threads, --csv <файл> і --help, будує гістограму, обчислює середнє, медіану (за гістограмою) і стандартне відхилення, виводить текстовий графік і таблицю продуктивності методів. Значення поза діапазоном 50–250 см підраховуються окремо й повідомляються в stderr; помилки аргументів – код завершення 1.

Варіант 13. Прості числа

1. Початковий рівень. Створити консольну програму мовою C++ з OpenMP, яка підраховує кількість простих чисел до 20 000 000 перевіркою дільників до $\sqrt{n}$, розпаралелюючи цикл директивою parallel for reduction(+:count) schedule(dynamic), і виводить кількість простих чисел та час.

2. Базовий рівень. Створити консольну програму мовою C++ з OpenMP, яка запитує верхню межу $N$ (від 1000 до ${10}^9$), перевіряє введення та підраховує прості числа перевіркою дільників для schedule(static), schedule(static, 1000), schedule(dynamic, 1000) і schedule(guided). Програма виводить таблицю «розподіл – час – прискорення», пояснює в коментарі, чому ітерації нерівномірні, і перевіряє кількість простих чисел решетом Ератосфена.

3. Високий рівень. Створити проєкт CMake з програмою primes, яка приймає опції --limit <N>, --method trial|sieve|segmented, --segment <розмір>, --threads, --schedule static|dynamic|guided, --chunk <n>, --out <файл> і --help. Сегментоване решето обробляє сегменти паралельно. Програма виводить кількість простих, найбільший проміжок між сусідніми простими, таблицю часу й прискорення для кожного методу та записує прості числа у файл (за потреби). Помилки аргументів – у stderr з кодом 1.

Варіант 14. Задача n тіл

1. Початковий рівень. Створити консольну програму мовою C++ з OpenMP, яка моделює рух 5000 тіл (випадкові маси й положення, фіксоване зерно) протягом 50 кроків методом Ейлера, обчислюючи сили гравітації між усіма парами паралельним циклом parallel for, і виводить повну енергію системи на першому й останньому кроці та час.

2. Базовий рівень. Створити консольну програму мовою C++ з OpenMP, яка моделює рух тіл під дією гравітації (задача $n$ тіл, випадкові маси й положення) методом швидкісного Верле з паралельним обчисленням прискорень. Програма запитує кількість тіл (від 100 до 50 000) і кроків, перевіряє введення і виводить таблицю часу, прискорення та ефективності для 1, 2, 4, 8 і 16 потоків, відносну зміну енергії та перевірку збігу положень із послідовною версією.

3. Високий рівень. Створити проєкт CMake з програмою nbody, яка моделює рух тіл під дією гравітації (сили між усіма парами, OpenMP). Початкові дані читаються з CSV (маса;x;y;z;vx;vy;vz) або генеруються; опції --steps, --dt, --threads, --layout aos|soa, --out <файл> і --help. Програма виводить таблицю часу на крок для структур AoS і SoA з директивою parallel for simd і записує траєкторії; сценарій порівнює OMP_PROC_BIND=close і spread з OMP_PLACES=cores. Помилки даних – код 2, аргументів – код 1.

Варіант 15. Обхід дерева каталогів

1. Початковий рівень. Створити консольну програму мовою C++ з OpenMP, яка будує в пам’яті синтетичне дерево каталогів (глибина 8, від 2 до 6 підкаталогів і від 0 до 20 файлів розміром до 10 МБ у кожному, фіксоване зерно) і обчислює загальну кількість файлів і сумарний розмір рекурсивним обходом із задачами task та taskwait, виводячи результат і час.

2. Базовий рівень. Створити консольну програму мовою C++ з OpenMP, яка запитує глибину дерева (від 2 до 12) і максимальну кількість підкаталогів, перевіряє введення, будує синтетичне дерево та обчислює кількість файлів, сумарний розмір і найбільший файл послідовно й задачами з порогом глибини. Програма виводить розмір дерева (вузлів), результати, збіг послідовного й паралельного обходу та таблицю часу для порогів 0–5.

3. Високий рівень. Створити проєкт CMake з програмою dutree, яка обходить реальний каталог (std::filesystem) або синтетичне дерево (--synthetic <глибина>), приймає опції --threads, --cutoff <глибина>, --top <n>, --ext (групувати за розширеннями) і --help, будує дерево задачами OpenMP, виводить таблицю n найбільших каталогів і статистику за розширеннями (власна редукція словників) та час обходу. Недоступні каталоги пропускаються з попередженням у stderr; неіснуючий шлях – код завершення 2.

Варіант 16. Рівняння Пуассона методом Якобі

1. Початковий рівень. Створити консольну програму мовою C++ з OpenMP, яка розв’язує рівняння Пуассона $\mathrm{\Delta }u=-1$ у квадраті з нульовими граничними умовами на сітці 500×500 методом Якобі (паралельне оновлення collapse(2), норма різниці ітерацій через reduction(max:…)) до досягнення точності ${10}^{-6}$ і виводить кількість ітерацій, значення в центрі та час.

2. Базовий рівень. Створити консольну програму мовою C++ з OpenMP, яка розв’язує рівняння Пуассона $\mathrm{\Delta }u=-1$ у квадраті з нульовими граничними умовами методом Якобі. Програма запитує розмір сітки (від 50 до 2000), точність і максимальну кількість ітерацій, перевіряє введення та виводить таблицю сильної масштабованості (фіксована сітка, 1–16 потоків): час, прискорення, ефективність і метрику Карпа–Флатта, а також перевіряє збіг розв’язку з послідовним.

3. Високий рівень. Створити проєкт CMake з програмою poisson, яка розв’язує рівняння Пуассона $\mathrm{\Delta }u=-1$ у квадраті з нульовими граничними умовами паралельно (OpenMP) з опціями --mode strong|weak, --base <n>, --threads 1,2,4,8,16, --iters <k>, --method jacobi|redblack і --help. У режимі weak кількість вузлів сітки зростає пропорційно кількості потоків. Програма виводить таблицю сильної або слабкої масштабованості (для слабкої – $T_1/T_p$), записує CSV і перевіряє збіжність червоно-чорного методу Гаусса–Зейделя. Помилки аргументів – код 1.

Варіант 17. Ансамбль маятників

1. Початковий рівень. Створити консольну програму мовою C++ з OpenMP, яка інтегрує рівняння руху 100 000 незалежних математичних маятників (початкові кути від 1° до 179°) методом Рунге–Кутти 4-го порядку протягом 10 с з кроком 0,001 с директивою parallel for і виводить середню амплітуду наприкінці та час.

2. Базовий рівень. Створити консольну програму мовою C++ з OpenMP, яка запитує кількість маятників, час моделювання й крок, перевіряє введення та інтегрує маятники з тертям. Маятники з великими кутами обчислюються з адаптивним кроком і довше, тому програма порівнює schedule(static), schedule(dynamic, 64) і schedule(guided) і виводить таблицю часу, прискорення й найбільшу похибку енергії.

3. Високий рівень. Створити проєкт CMake з програмою pendulums, яка читає параметри маятників із CSV (довжина;кут;швидкість;тертя) або генерує їх, приймає опції --t-end, --tol, --method rk4|rk45, --threads, --schedule, --out <файл> і --help, записує кінцеві стани й періоди коливань, а також таблицю часу для кожного виду розподілу з кількістю кроків найлегшого й найважчого маятника. Помилки даних – код завершення 2, аргументів – код 1.

Варіант 18. Вирівнювання рядків ДНК

1. Початковий рівень. Створити консольну програму мовою C++ з OpenMP, яка генерує дві випадкові послідовності ДНК довжиною 20 000 (алфавіт A, C, G, T, фіксоване зерно) і обчислює оцінку глобального вирівнювання алгоритмом Нідлмана–Вунша (збіг +1, розбіжність −1, пропуск −2), заповнюючи таблицю по антидіагоналях паралельним циклом, та виводить оцінку й час.

2. Базовий рівень. Створити консольну програму мовою C++ з OpenMP, яка читає дві послідовності ДНК з файлів FASTA, перевіряє алфавіт, запитує ваги збігу, розбіжності та пропуску і обчислює оцінку вирівнювання послідовно (за рядками) та паралельно (за антидіагоналями) для 1, 2, 4, 8 і 16 потоків. Програма перевіряє збіг оцінок і виводить таблицю часу й прискорення.

3. Високий рівень. Створити проєкт CMake з програмою nwalign, яка приймає аргументи a.fasta b.fasta та опції --match, --mismatch, --gap, --threads, --block <розмір> (блокове заповнення таблиці із задачами depend), --show-alignment і --help, відновлює вирівнювання для послідовностей до 20 000 символів, виводить його фрагментами по 60 символів і таблицю часу для антидіагонального та блокового варіантів. Некоректні символи – код завершення 2, аргументи – код 1.

Варіант 19. Фрактал Барнслі

1. Початковий рівень. Створити консольну програму мовою C++ з OpenMP, яка будує папороть Барнслі системою ітерованих функцій: кожен потік генерує 5 000 000 точок власним генератором і позначає їх у спільному зображенні 1000×1000 (запис байта «1» без синхронізації допустимий), записує файл fern.pgm і виводить кількість зафарбованих пікселів та час.

2. Базовий рівень. Створити консольну програму мовою C++ з OpenMP, яка будує папороть Барнслі системою ітерованих функцій (кожен потік генерує точки власним генератором). Програма запитує кількість точок (від ${10}^6$ до ${10}^9$) і розмір зображення, перевіряє введення та рахує влучання в пікселі двома способами: atomic для спільного масиву та локальні масиви потоків з об’єднанням. Програма зберігає зображення з логарифмічною яскравістю та виводить таблицю часу й прискорення для 1, 2, 4, 8 і 16 потоків.

3. Високий рівень. Створити проєкт CMake з програмою ifs, яка читає коефіцієнти афінних перетворень і ймовірності з текстового файлу (папороть, трикутник Серпінського, дракон), приймає опції --points, --size, --threads, --seed, --out <файл.pgm> і --help, перевіряє, що сума ймовірностей дорівнює 1, будує зображення без гонитви й виводить таблицю продуктивності. Результат не залежить від кількості потоків за однакового --seed (генератор на блок точок). Помилки файлу – код завершення 2, аргументів – 1.

Варіант 20. Сортування злиттям

1. Початковий рівень. Створити консольну програму мовою C++ з OpenMP, яка сортує вектор з 20 000 000 дійсних чисел рекурсивним сортуванням злиттям, де дві половини сортуються задачами OpenMP до розміру 50 000 елементів, перевіряє результат порівнянням із std::sort і виводить час обох сортувань.

2. Базовий рівень. Створити консольну програму мовою C++ з OpenMP, яка запитує розмір масиву і кількість потоків, перевіряє введення, генерує масив випадкових чисел і сортує його злиттям двома паралельними способами: рекурсивно задачами task і знизу вгору, коли кожен рівень злиття виконується циклом taskloop. Програма перевіряє впорядкованість і виводить таблицю часу, прискорення й ефективності для 1, 2, 4, 8 і 16 потоків.

3. Високий рівень. Створити проєкт CMake з програмою msort, яка сортує рядки текстового файлу (аргументи input.txt output.txt) і приймає опції --threads, --cutoff, --method tasks|taskloop|std, --parallel-merge і --help. Опція --parallel-merge вмикає злиття поділом за медіаною з бінарним пошуком. Програма записує відсортований файл, виводить таблицю часу й прискорення і CSV для графіка. Помилки файлу – код завершення 2, аргументів – код 1.

Варіант 21. Трасування сфер

1. Початковий рівень. Створити консольну програму мовою C++ з OpenMP, яка рендерить сцену з 50 випадкових сфер і одного джерела світла (дифузне освітлення й тіні) зображенням 1280×720, розпаралелюючи цикл за рядками пікселів parallel for schedule(dynamic), записує scene.ppm і виводить час рендерингу.

2. Базовий рівень. Створити консольну програму мовою C++ з OpenMP, яка запитує розмір зображення, кількість сфер і глибину відбиттів (від 0 до 5), перевіряє введення, рендерить сцену з дзеркальними відбиттями й порівнює schedule(static), schedule(dynamic, 1) і schedule(dynamic, 16) за рядками та collapse(2) за пікселями. Програма виводить таблицю часу, прискорення й середньої кількості променів на рядок і перевіряє однаковість зображень.

3. Високий рівень. Створити проєкт CMake з програмою raytrace, яка читає опис сцени з текстового файлу (камера, сфери з матеріалами, джерела світла), приймає опції --size, --samples <n> (згладжування), --depth, --threads, --schedule, --out <файл.ppm> і --help, рендерить сцену та виводить таблицю часу, прискорення й кількості променів за секунду. Генератор випадкових чисел для згладжування має зерно пікселя, тому зображення не залежить від кількості потоків. Помилки сцени (номер рядка) – код завершення 2.

Варіант 22. Статистика транзакцій

1. Початковий рівень. Створити консольну програму мовою C++ з OpenMP, яка генерує 20 000 000 банківських транзакцій (сума від 1 до 100 000 грн, категорія з 8, фіксоване зерно) і в секціях parallel sections одночасно обчислює загальну суму, максимальну транзакцію та кількість транзакцій понад 50 000 грн, виводячи результати й час.

2. Базовий рівень. Створити консольну програму мовою C++ з OpenMP, яка запитує кількість транзакцій, перевіряє введення та обчислює п’ять метрик (сума, середнє, мінімум, максимум, кількість підозрілих понад поріг) трьома способами: послідовно, секціями (кожна метрика в окремій секції) і одним циклом parallel for з кількома редукціями. Програма виводить метрики, збіг результатів і таблицю часу, пояснюючи, чому один цикл швидший за секції.

3. Високий рівень. Створити проєкт CMake з програмою txstats, яка читає транзакції з CSV (дата;рахунок;категорія;сума), приймає опції --threads, --threshold <грн>, --by category|day, --top <n> і --help, обчислює статистику за групами власною редукцією, знаходить рахунки з найбільшою кількістю підозрілих операцій і виводить таблиці з підсумками та час етапів (читання, розбір, агрегація). Некоректні рядки підраховуються й повідомляються в stderr; помилки аргументів – код завершення 1.

Варіант 23. Ехо-фільтр звукового файлу

1. Початковий рівень. Створити консольну програму мовою C++ з OpenMP, яка генерує 60 с стереосигналу (частота дискретизації 48 кГц, синусоїди), застосовує ехо-фільтр (затримка 250 мс, ослаблення 0,5) циклом parallel for simd, записує результат у WAV-файл і виводить пікову амплітуду та час обробки.

2. Базовий рівень. Створити консольну програму мовою C++ з OpenMP, яка читає 16-бітний WAV-файл, запитує затримку (від 10 до 2000 мс) і коефіцієнт ослаблення (від 0 до 1), перевіряє введення й застосовує ехо-фільтр чотирма способами (послідовно, simd, parallel for, parallel for simd) з числами float. Програма нормалізує гучність, зберігає результат і виводить таблицю часу, прискорення та максимальної розбіжності між способами.

3. Високий рівень. Створити проєкт CMake з програмою echo, яка приймає аргументи input.wav output.wav та опції --delays 120,250,400, --gains 0.6,0.4,0.2 (багаторазове ехо), --mode, --threads, --repeat <n> і --help, обробляє моно- і стереофайли, виводить таблицю «режим – потоки – час – $S$ – хвилин звуку за секунду» та записує CSV для порівняння з реалізацією на C# із SIMD. Непідтримуваний формат WAV – код завершення 2, аргументи – код 1.

Варіант 24. Пошук у ширину в соціальному графі

1. Початковий рівень. Створити консольну програму мовою C++ з OpenMP, яка генерує соціальний граф із 1 000 000 користувачів і в середньому 20 друзями (списки суміжності, фіксоване зерно) та знаходить відстані від користувача 0 до всіх інших пошуком у ширину за рівнями: вершини поточного рівня обробляються циклом parallel for, а позначка відвідування ставиться атомарно. Програма виводить кількість вершин на кожному рівні та час.

2. Базовий рівень. Створити консольну програму мовою C++ з OpenMP, яка запитує кількість користувачів, середню кількість друзів і початкового користувача, перевіряє введення, виконує рівневий BFS послідовно й паралельно (std::atomic<int> і compare_exchange_strong для відстаней, локальні списки наступного рівня потоків) і виводить таблицю відстаней (скільки користувачів на відстані 1, 2, …), збіг результатів та час для 1–16 потоків.

3. Високий рівень. Створити проєкт CMake з програмою socialbfs, яка читає граф зі списку ребер (файл id1 id2), приймає опції --source <id>, --threads, --direction top-down|hybrid (гібридний BFS із переходом «знизу вгору» на великих рівнях), --schedule і --help, виводить розподіл відстаней, діаметр від джерела та таблицю часу й прискорення кожного варіанта. Неіснуюча вершина – код завершення 2, помилки файлу – код 1.

Варіант 25. Матриця відстаней точок

1. Початковий рівень. Створити консольну програму мовою C++ з OpenMP, яка генерує 20 000 точок на площині (фіксоване зерно), обчислює середню відстань між усіма парами точок циклом parallel for collapse(2) reduction(+:sum) і виводить результат та час.

2. Базовий рівень. Створити консольну програму мовою C++ з OpenMP, яка запитує кількість точок і розмірність простору (від 2 до 16), перевіряє введення й для кожної точки знаходить найближчого сусіда двома способами: лічильники потоків у спільному масиві counts[номер потоку] і локальні змінні потоків. Програма виводить час обох способів для 1–16 потоків і пояснює вплив хибного розділення, а також перевіряє однаковість результатів.

3. Високий рівень. Створити проєкт CMake з програмою distmatrix, яка читає точки з CSV, приймає опції --metric euclid|manhattan|cosine, --threads, --layout aos|soa, --block <b> (обхід блоками для кешу), --out <файл> і --help, обчислює верхній трикутник матриці відстаней (schedule(dynamic), бо рядки мають різну довжину), зберігає її у двійковий файл і виводить таблицю часу для кожної метрики та способу розміщення даних. Помилки файлу – код завершення 2, аргументів – код 1.

Варіант 26. Ціноутворення опціонів біноміальним деревом

1. Початковий рівень. Створити консольну програму мовою C++ з OpenMP, яка обчислює ціну європейського опціону «кол» (ціна акції 100, страйк 100, ставка 5 %, волатильність 20 %, строк 1 рік) біноміальною моделлю Кокса–Росса–Рубінштейна з 20 000 кроків, розпаралелюючи згортання кожного рівня дерева директивою parallel for, і виводить ціну, ціну за формулою Блека–Шоулза та час.

2. Базовий рівень. Створити консольну програму мовою C++ з OpenMP, яка запитує параметри опціону, тип (кол/пут, європейський/американський) і кількість кроків, перевіряє введення, обчислює ціну біноміальною моделлю послідовно й паралельно (паралельний цикл лише для рівнів, ширших за 1000 вузлів, клауза if) і виводить ціну, збіг із послідовною версією, різницю з Блеком–Шоулзом (для європейського) та таблицю часу для 1–16 потоків.

3. Високий рівень. Створити проєкт CMake з програмою options, яка читає портфель опціонів із CSV (тип;стиль;S;K;r;sigma;T), приймає опції --steps, --threads, --level outer|inner|nested (паралельно за опціонами, за вузлами дерева або вкладено з omp_set_max_active_levels(2)) і --help, обчислює ціни та грецьку «дельту», записує результат у CSV і виводить таблицю часу для кожного рівня паралелізму. Некоректні параметри опціону (номер рядка) – код завершення 2.

Варіант 27. Епідемія SIR на сітці

1. Початковий рівень. Створити консольну програму мовою C++ з OpenMP, яка моделює поширення хвороби на сітці 1000×1000 людей (стани S, I, R; заражений заражає кожного з 4 сусідів з імовірністю 0,2 і одужує через 10 днів; генератор на рядок і день) протягом 200 днів, розпаралелюючи оновлення сітки директивою parallel for, і виводить кількість S, I, R кожні 20 днів та час.

2. Базовий рівень. Створити консольну програму мовою C++ з OpenMP, яка запитує розмір сітки, кількість днів, імовірність зараження й тривалість хвороби, перевіряє введення, моделює епідемію за шаблоном 5 точок із паралельною ініціалізацією сітки (перший дотик), знаходить пік кількості заражених і день піку та виводить таблицю часу, прискорення й ефективності для 1–16 потоків. Результат не залежить від кількості потоків.

3. Високий рівень. Створити проєкт CMake з програмою sir, яка приймає опції --size, --days, --beta, --recovery, --vaccinated <частка>, --threads, --init parallel|serial, --csv <файл>, --frames <каталог> (зображення PGM кожні n днів) і --help, записує криву S/I/R у CSV, зберігає кадри та виводить таблицю продуктивності для обох способів ініціалізації. До проєкту додається сценарій запуску на вузлі NUMA з numactl --cpunodebind --membind і OMP_PROC_BIND. Помилки аргументів – код 1.

Варіант 28. Задача комівояжера

1. Початковий рівень. Створити консольну програму мовою C++ з OpenMP, яка генерує 13 міст із випадковими координатами (фіксоване зерно) і знаходить найкоротший замкнений маршрут повним перебором, створюючи задачу для кожного другого міста маршруту; найкраща довжина оновлюється в critical. Програма виводить маршрут, його довжину та час.

2. Базовий рівень. Створити консольну програму мовою C++ з OpenMP, яка запитує кількість міст (від 5 до 16), перевіряє введення та розв’язує задачу комівояжера методом гілок і меж: задачі OpenMP створюються до глибини 3, поточна найкраща довжина читається без блокування й оновлюється в critical з повторною перевіркою. Програма виводить маршрут, кількість відсічених гілок і таблицю часу для 1, 2, 4, 8 і 16 потоків.

3. Високий рівень. Створити проєкт CMake з програмою tsp, яка читає координати міст із файлу (назва;x;y), приймає опції --cutoff <глибина>, --threads, --bound simple|mst, --initial nearest (початкова межа жадібним алгоритмом), --time-limit <с> і --help, знаходить оптимальний маршрут, виводить його назвами міст, кількість задач і відсічень та таблицю прискорення. Після перевищення ліміту часу виводиться найкращий знайдений маршрут з позначкою «не доведено» і кодом завершення 3; помилки файлу – код 2.

Варіант 29. Хвиля на мембрані

1. Початковий рівень. Створити консольну програму мовою C++ з OpenMP, яка моделює коливання квадратної мембрани 800×800 із закріпленими краями (явна схема для хвильового рівняння, початкове збурення в центрі) протягом 2000 кроків циклом parallel for collapse(2) і виводить енергію мембрани кожні 500 кроків та час.

2. Базовий рівень. Створити консольну програму мовою C++ з OpenMP, яка моделює коливання квадратної мембрани із закріпленими краями (явна схема для хвильового рівняння з трьома часовими шарами, початкове збурення в центрі). Програма запитує розмір сітки, кількість кроків і число Куранта (менше за $1/\sqrt{2}$), перевіряє введення, виводить таблицю часу, прискорення й ефективності для 1–16 потоків, поточні OMP_PLACES і OMP_PROC_BIND та перевіряє збереження енергії (відхилення менше 1 %).

3. Високий рівень. Створити проєкт CMake з програмою wave2d, яка паралельно (OpenMP) моделює коливання квадратної мембрани із закріпленими краями явною схемою для хвильового рівняння з опціями --size, --steps, --courant, --source center|random:<n> (початкові збурення), --threads, --frames <каталог>, --csv <файл> і --help та зберігає кадри PGM і таблицю продуктивності. Сценарій проєкту запускає програму для OMP_PLACES=threads|cores і OMP_PROC_BIND=close|spread та будує таблицю «місця – прив’язка – потоки – час – $S$». Число Куранта поза межею стійкості – код 2, помилки аргументів – код 1.

Варіант 30. Вбудований бенчмарк OpenMP

1. Початковий рівень. Створити консольну програму мовою C++ з OpenMP, яка виконує три тестові ядра (сума масиву з reduction, множення матриць 800×800 і нерівномірний цикл підрахунку простих чисел) та для кожного виводить поточну кількість потоків (omp_get_max_threads), вид розподілу (omp_get_schedule) і час виконання.

2. Базовий рівень. Створити консольну програму мовою C++ з OpenMP, яка виконує три тестові ядра (сума масиву з reduction, множення матриць 800×800, нерівномірний цикл підрахунку простих чисел) зі schedule(runtime) для всіх комбінацій кількості потоків 1, 2, 4, 8, 16 і видів розподілу static, dynamic,64, guided, змінюючи їх функціями omp_set_num_threads і omp_set_schedule. Для кожного ядра програма виводить таблицю часу та прискорення з позначкою найкращого розподілу й перевіряє контрольні суми.

3. Високий рівень. Створити проєкт CMake з програмою ompbench, яка читає налаштування лише зі змінних середовища (OMP_NUM_THREADS, OMP_SCHEDULE, OMP_PROC_BIND, OMP_PLACES), приймає опції --kernels sum,matmul,primes,stencil, --size <n>, --csv <файл> (дописування) і --help, та сценарій (bash і PowerShell), який запускає програму для всіх комбінацій змінних середовища й будує зведену таблицю з CSV: ядро, потоки, розподіл, прив’язка, медіана часу, прискорення. Невідоме ядро – код завершення 1, розбіжність контрольної суми – код 2.

Порядок виконання та захисту роботи

1. Опрацювати теоретичні відомості та приклади розв’язання завдань.
2. Створити проєкт CMake з find_package(OpenMP REQUIRED) (GCC, CMake і Ninja в Ubuntu 26.04 або CLion) і перевірити макрос _OPENMP.
3. Реалізувати послідовну версію завдання, розпаралелити її директивами OpenMP (області видимості змінних – з default(none)) і перевірити збіг результату з послідовною версією.
4. Виміряти час для 1, 2, 4, 8 і 16 потоків (OMP_NUM_THREADS) з різними schedule і прив’язками (OMP_PLACES, OMP_PROC_BIND), побудувати таблицю й графік прискорення та ефективності й пояснити отримані значення.
5. Продемонструвати роботу програми, пояснити код і результати вимірювань, відповісти на контрольні питання.