Завдання

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

Варіанти

Варіант 1. Паралельне сортування телефонної книги

1. Початковий рівень. Створити консольну програму мовою C++, яка генерує 2 000 000 записів телефонної книги (прізвище з 8 випадкових літер і номер, генератор std::mt19937 із фіксованим зерном), сортує їх за прізвищем викликами std::sort з політиками std::execution::seq і std::execution::par та виводить час обох варіантів і ознаку, що результати однакові.

2. Базовий рівень. Створити консольну програму мовою C++, яка запитує кількість записів телефонної книги (від 10 000 до 10 000 000) і кількість потоків $p$ (від 1 до hardware_concurrency()), перевіряє введення, генерує записи (випадкове прізвище й номер) і сортує їх за прізвищем трьома способами: std::sort послідовно, std::sort з std::execution::par і сортуванням $p$ частин у потоках std::jthread з подальшим злиттям std::inplace_merge. Програма перевіряє впорядкованість і виводить таблицю часу та прискорення.

3. Високий рівень. Створити проєкт CMake (CMakePresets.json з пресетами debug і release, ціль Threads::Threads, за наявності – TBB::tbb) з програмою phonesort, яка читає телефонну книгу з CSV-файлу (прізвище;ім’я;номер), заданого аргументом, і приймає опції --threads 1,2,4,8, --runs <n>, --out <файл> і --help. Програма сортує записи за прізвищем та ім’ям власним паралельним сортуванням злиттям для кожної кількості потоків і std::sort з par, виводить таблицю медіан часу, прискорення й ефективності, записує відсортований файл. Помилки формату (номер рядка) виводяться в stderr; коди завершення: 0 – успіх, 1 – аргументи, 2 – файл.

Варіант 2. Числове інтегрування

1. Початковий рівень. Створити консольну програму мовою C++, яка обчислює інтеграл функції $4/(1+x^2)$ на відрізку $[0,1]$ методом середніх прямокутників з $n$ = 200 000 000 відрізків, розбиваючи їх на частини для 8 потоків std::jthread, і виводить наближене значення $\pi$, похибку та час послідовного й паралельного обчислення.

2. Базовий рівень. Створити консольну програму мовою C++, яка запитує межі інтегрування $a<b$, кількість відрізків $n$ (від 1000 до ${10}^9$) і обирає з меню одну з трьох функцій. Програма перевіряє введення, обчислює інтеграл методом Сімпсона в $p=1,2,4,8,16$ потоках std::jthread (кожен потік записує результат лише у свою комірку) і виводить таблицю: $p$, значення, медіана часу трьох запусків, прискорення $S$, ефективність $E$.

3. Високий рівень. Створити проєкт CMake з файлом CMakePresets.json (пресети debug, release і tsan з ключем -fsanitize=thread) і програмою integrate, яка приймає опції --function sin|exp|poly, --from, --to, --n, --threads 1,2,4,8,16, --csv <файл> і --help. Програма обчислює інтеграл послідовно та паралельно, виводить таблицю $p$, $T_p$, $S$, $E$ і метрику Карпа–Флатта, записує CSV і перевіряє відхилення від послідовного результату (не більше ${10}^{-9}$, інакше код завершення 3). Помилки аргументів виводяться в stderr з кодом 1.

Варіант 3. Обробка PGM-зображень

1. Початковий рівень. Створити консольну програму мовою C++, яка читає зображення у форматі PGM (P5), шлях до якого вводить користувач, застосовує медіанний фільтр 3×3, розділивши рядки між hardware_concurrency() потоками std::jthread, записує результат у файл median.pgm і виводить розміри зображення та час обробки.

2. Базовий рівень. Створити консольну програму мовою C++, яка читає зображення PGM (P5) і розмір вікна медіанного фільтра (непарне число від 3 до 15), перевіряє файл і введення, обробляє зображення трьома способами: послідовно, потоками std::jthread за рядками і std::for_each з std::execution::par за індексами рядків. Програма перевіряє побайтний збіг результатів і виводить таблицю часу й прискорення.

3. Високий рівень. Створити проєкт CMake з програмою pgmfilter, яка приймає аргументи input.pgm output.pgm і опції --filter median|blur|sobel, --size <вікно>, --threads 1,2,4,8, --policy threads|par і --help. Програма виконує фільтр для кожної кількості потоків, виводить таблицю медіан часу трьох запусків, $S$ і $E$, зберігає результат і перевіряє його збіг із послідовною версією. Помилки формату PGM виводяться в stderr з кодом завершення 2, помилки аргументів – з кодом 1.

Варіант 4. Черга друку документів

1. Початковий рівень. Створити консольну програму мовою C++, у якій 3 потоки-«принтери» беруть завдання друку з черги, захищеної std::mutex і std::condition_variable. Головний потік ставить у чергу 20 документів із випадковою кількістю сторінок (1–10); друк сторінки імітується затримкою 20 мс. Програма виводить, який принтер надрукував кожен документ, і загальний час.

2. Базовий рівень. Створити консольну програму мовою C++, яка моделює черговий друк документів у пулі потоків на std::jthread, std::condition_variable і std::packaged_task з методом submit, що повертає std::future. Користувач вводить кількість принтерів (1–8) і документи «назва кількість_сторінок» до порожнього рядка з перевіркою введення; друк сторінки імітується затримкою. Кожне завдання повертає час друку; програма виводить таблицю документів із часом очікування в черзі та друку, середні значення й загальний час.

3. Високий рівень. Створити проєкт CMake з програмою printqueue, яка читає завдання з CSV-файлу (час_надходження_мс;назва;сторінки;пріоритет) і моделює друк у пулі потоків з пріоритетною чергою (std::priority_queue під м’ютексом). Опції --printers <n>, --page-ms <мс>, --report <файл> і --help. Програма коректно завершує пул (усі завдання виконано, потоки приєднано), виводить таблицю документів, статистику (середнє й максимальне очікування за пріоритетами, завантаження кожного принтера) і записує звіт. Помилки файлу – у stderr, коди завершення 0/1/2.

Варіант 5. Метод Монте-Карло для площі фігури

1. Початковий рівень. Створити консольну програму мовою C++, яка оцінює площу кола радіусом 1 методом Монте-Карло за 100 000 000 випадкових точок у 8 потоках std::jthread; кожен потік має власний генератор std::mt19937_64 із різним зерном. Програма виводить оцінку площі, похибку порівняно з $\pi$ і час.

2. Базовий рівень. Створити консольну програму мовою C++, яка оцінює площу фігури, заданої нерівністю $x^2/a^2+y^2/b^2\le 1$ (еліпс), для введених $a$, $b$ (додатні) і кількості точок $N$ (від ${10}^6$ до ${10}^9$). Генератори оголошено thread_local. Для $p=1,2,4,8,16$ потоків програма виводить оцінку, відносну похибку порівняно з $\pi ab$, час і прискорення.

3. Високий рівень. Створити проєкт CMake з програмою montecarlo, яка оцінює площу багатокутника, вершини якого читаються з файлу (по одній парі координат у рядку), у прямокутнику, що його обмежує. Опції: --points <N>, --threads 1,2,4,8, --seed <число>, --runs <n> і --help. Програма обчислює точну площу за формулою Гаусса, виводить для кожної кількості потоків оцінку, відносну похибку, медіану часу, $S$ і $E$ та перевіряє, що результат із тим самим зерном не залежить від кількості запусків. Помилки файлу або аргументів – у stderr з кодами 2 і 1.

Варіант 6. Банківські перекази на C++

1. Початковий рівень. Створити консольну програму мовою C++ з класом рахунку (номер, баланс, std::mutex), у якій 4 потоки виконують по 100 000 випадкових переказів між 10 рахунками з використанням std::scoped_lock для двох м’ютексів. Програма виводить баланси рахунків і перевіряє, що загальна сума не змінилася.

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

3. Високий рівень. Створити проєкт CMake з пресетом tsan (-fsanitize=thread -g) і програмою bank, яка читає рахунки з CSV-файлу та приймає опції --threads, --transfers, --seed, --mode mutex|scoped|atomic-total і --help. Програма виконує стрес-тест переказів, веде журнал операцій у потокобезпечному контейнері, виводить таблицю режимів з часом і пропускною здатністю (переказів за секунду) та записує підсумкові баланси. До звіту додається результат запуску збірки tsan без попереджень. Порушення інваріанта загальної суми – код завершення 3.

Варіант 7. Пошук простих чисел

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

2. Базовий рівень. Створити консольну програму мовою C++, яка запитує верхню межу (до ${10}^9$) і кількість частин, перевіряє введення та підраховує прості числа трьома способами: послідовно, std::async з політикою launch::async і з політикою launch::deferred. Програма виводить таблицю часу й прискорення та пояснювальне повідомлення, чому політика deferred не дає прискорення.

3. Високий рівень. Створити проєкт CMake з програмою primes, яка підраховує прості числа в діапазоні --from…--to за допомогою сегментованого решета Ератосфена, де кожен сегмент обробляє задача std::async. Опції --segment <розмір>, --tasks 1,2,4,8,16, --list <файл> (записати прості числа) і --help. Програма виводить таблицю «кількість задач – час – $S$ – $E$», перевіряє збіг кількості з послідовним решетом і повідомляє найкращий розмір сегмента. Помилки аргументів – у stderr з кодом 1.

Варіант 8. Статистика сейсмодатчиків

1. Початковий рівень. Створити консольну програму мовою C++, яка генерує 50 000 000 показів сейсмодатчика (нормальний розподіл, фіксоване зерно) та обчислює середнє значення й середній квадрат амплітуди за допомогою std::transform_reduce з політиками seq і par_unseq, виводячи результати та час.

2. Базовий рівень. Створити консольну програму мовою C++, яка читає з бінарного файлу покази датчика (масив float), шлях до якого вводить користувач, і обчислює мінімум, максимум, середнє, стандартне відхилення та кількість значень понад заданий поріг алгоритмами std::reduce, std::transform_reduce, std::count_if і std::minmax_element з усіма чотирма політиками виконання. Програма виводить таблицю часу та перевіряє однаковість результатів.

3. Високий рівень. Створити проєкт CMake, який підключає TBB::tbb для GCC, з програмою seismo, що обробляє каталог бінарних файлів датчиків: для кожного файлу обчислює статистику й кількість «подій» (вікна з енергією понад поріг) паралельними алгоритмами. Опції --dir, --threshold, --window, --policy seq|unseq|par|par_unseq|all, --csv і --help. Програма виводить таблицю файлів і таблицю часу політик, записує CSV і попереджає в stderr, якщо бекенд паралельних алгоритмів послідовний (TBB не знайдено під час збирання).

Варіант 9. Матричні операції

1. Початковий рівень. Створити консольну програму мовою C++, яка множить дві квадратні матриці розміром 1000×1000 (фіксоване зерно) послідовно та в 8 потоках std::jthread за рядками результату, виводить час обох варіантів, прискорення й максимальну різницю елементів.

2. Базовий рівень. Створити консольну програму мовою C++ з власним пулом потоків (std::jthread, std::condition_variable, std::packaged_task), яка запитує розмір матриць (100–3000) і розмір блоку, перевіряє введення та множить матриці блочним алгоритмом: кожен блок – окрема задача пулу. Програма порівнює час звичайного і блочного множення для 1, 2, 4, 8 і 16 потоків та виводить таблицю прискорення.

3. Високий рівень. Створити проєкт CMake з бібліотекою-ціллю matrix (клас матриці та алгоритми) і програмою matbench, що приймає опції --sizes, --blocks, --threads, --op mul|transpose|inverse і --help. Операції виконуються в пулі потоків, результати перевіряються з послідовними, а таблиця «розмір – блок – потоки – час – $S$ – $E$» виводиться та записується в CSV. Цілі у CMakeLists.txt оформлено через add_library і target_link_libraries; помилки аргументів – у stderr з кодом 1.

Варіант 10. Парковка з датчиками

1. Початковий рівень. Створити консольну програму мовою C++, у якій 20 автомобілів-потоків намагаються заїхати на парковку з 5 місцями, обмеженими std::counting_semaphore; кожен автомобіль стоїть випадковий час 50–200 мс. Програма виводить журнал подій «заїхав / виїхав» з кількістю вільних місць і загальний час.

2. Базовий рівень. Створити консольну програму мовою C++, яка запитує кількість місць (1–100), кількість автомобілів і максимальний час очікування в’їзду. Автомобіль використовує try_acquire_for і, якщо місце не звільнилося вчасно, від’їжджає. Журнал подій ведеться під м’ютексом із позначкою часу від старту; наприкінці програма виводить кількість обслугованих і від’їхалих автомобілів та середній час очікування.

3. Високий рівень. Створити проєкт CMake з програмою parking, яка моделює парковку з кількома рівнями (окремий семафор на рівень) за сценарієм із CSV-файлу (час_прибуття;номер; тривалість). Опції --levels 10,20,15, --patience <мс>, --speed <множник>, --log <файл> і --help. Програма записує журнал подій, виводить звіт із завантаженням кожного рівня, пиковою зайнятістю, відмовами та середнім очікуванням, а також перевіряє, що кількість зайнятих місць ніколи не перевищувала місткість. Помилки – у stderr, коди 0/1/2.

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

1. Початковий рівень. Створити консольну програму мовою C++, яка моделює 500 поколінь гри «Життя» на полі 1000×1000 (випадкове заповнення 30 %, фіксоване зерно) у 4 потоках std::jthread, що обробляють горизонтальні смуги поля, і виводить кількість живих клітин після кожного сотого покоління та час.

2. Базовий рівень. Створити консольну програму мовою C++, яка моделює гру «Життя» Конвея на полі з випадковим початковим заповненням. Програма запитує розмір поля, кількість поколінь і потоків; робочі потоки обробляють смуги поля протягом усього моделювання й синхронізуються між поколіннями через std::barrier (обмін полів після проходу всіх смуг). Програма перевіряє збіг результату з послідовною версією та виводить таблицю часу й прискорення для 1, 2, 4 і 8 потоків.

3. Високий рівень. Створити проєкт CMake з програмою life, яка паралельно моделює гру «Життя» Конвея (потоки обробляють смуги поля), читаючи початковий стан із файлу у форматі RLE або текстовому (. і O). Опції: --generations, --threads, --weak <розмір на потік>, --snapshot <крок>, --help. У режимі --weak розмір поля зростає пропорційно кількості потоків, і програма виводить таблицю слабкої масштабованості (час має залишатися сталим). Знімки поля записуються у файли PGM. Помилки файлу – у stderr з кодом 2.

Варіант 12. Лічильник слів у файлах

1. Початковий рівень. Створити консольну програму мовою C++, яка підраховує кількість слів у кожному з текстових файлів, шляхи до яких передано аргументами командного рядка, запускаючи для кожного файлу окремий потік, що повертає результат через std::promise, і виводить таблицю «файл – слів» та загальну кількість.

2. Базовий рівень. Створити консольну програму мовою C++, яка для каталогу, введеного користувачем, обробляє всі файли .txt: кожна задача std::async будує словник частот слів (std::unordered_map, слова в нижньому регістрі), а головний потік зливає словники й виводить 20 найчастіших слів. Помилки читання файлів передаються через future і виводяться в потік помилок, не зупиняючи обробку інших файлів.

3. Високий рівень. Створити проєкт CMake з програмою wordfreq, що приймає каталог і опції --threads <n>, --top <k>, --min-length <n>, --stop-words <файл>, --csv <файл> і --help. Файли розподіляються між $n$ потоками через спільну чергу, часткові словники зливаються в кінці. Програма виводить найчастіші слова, кількість файлів, слів і час для кожної кількості потоків з переліку, перевіряє збіг частот з послідовним підрахунком і записує CSV. Коди завершення 0/1/2.

Варіант 13. Фрактал Ньютона

1. Початковий рівень. Створити консольну програму мовою C++, яка будує фрактал Ньютона для рівняння $z^3-1=0$ на зображенні 1200×1200 за допомогою std::for_each з політикою std::execution::par за номерами рядків і записує зображення у файл PPM, виводячи час побудови.

2. Базовий рівень. Створити консольну програму мовою C++, яка будує фрактал Ньютона (басейни притягання коренів $z^n-1=0$ методом Ньютона) і записує його у файл PPM. Програма запитує розмір зображення, степінь $n$ (від 3 до 8) і максимальну кількість ітерацій, перевіряє введення, будує фрактал послідовно, з par і з par_unseq та виводить таблицю часу й прискорення, перевіряючи побайтний збіг зображень.

3. Високий рівень. Створити проєкт CMake з програмою newton, що будує фрактал Ньютона для $z^n-1=0$ (рядки зображення паралельно, std::for_each з політикою виконання) і записує файли PPM. Опції: --size WxH, --degree, --iterations, --region x1,y1,x2,y2, --policy, --frames <n>, --help. Режим --frames будує серію кадрів із поступовим збільшенням масштабу: кадри послідовно, рядки кадру паралельно. Програма виводить таблицю часу кадрів і загальне прискорення та попереджає, якщо паралельні алгоритми зібрано без TBB. Помилки – у stderr з кодом 1.

Варіант 14. Кешування результатів

1. Початковий рівень. Створити консольну програму мовою C++ з класом кешу обчислених значень функції (std::map під std::shared_mutex), у якій 8 потоків-читачів і 1 потік-записувач протягом 2 с звертаються до кешу. Програма виводить кількість виконаних читань і записів.

2. Базовий рівень. Створити консольну програму мовою C++ з кешем обчислених значень функції (std::map), до якого потоки звертаються з читаннями й записами. Програма порівнює пропускну здатність кешу з std::mutex і з std::shared_mutex для введених користувачем кількості потоків (1–16) і тривалості тесту та виводить таблицю «режим – операцій за секунду – частка влучань у кеш» для часток запису 1, 10 і 50 %.

3. Високий рівень. Створити проєкт CMake з програмою lrucache, що реалізує потокобезпечний LRU-кеш обмеженого розміру з сегментацією (кілька частин, кожна зі своїм shared_mutex). Опції --capacity, --shards 1,4,16, --threads 1,2,4,8,16, --write-ratio, --seconds і --help. Програма виводить таблицю пропускної здатності та частки влучань для кожної комбінації, перевіряє інваріант розміру кешу й записує CSV. Збірка з -fsanitize=thread не повинна давати попереджень.

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

1. Початковий рівень. Створити консольну програму мовою C++, яка сортує 10 000 000 випадкових цілих чисел рекурсивним сортуванням злиттям, де дві половини на верхніх трьох рівнях рекурсії сортуються паралельно через std::async, і виводить час, прискорення порівняно з послідовною версією та перевірку впорядкованості.

2. Базовий рівень. Створити консольну програму мовою C++, яка сортує масив випадкових цілих чисел рекурсивним сортуванням злиттям, де половини паралельно сортуються задачами std::async до заданої глибини рекурсії. Програма запитує розмір масиву, перевіряє введення, виводить таблицю часу для глибин 0–6 і порівняння з std::sort і std::stable_sort та перевіряє, що результат збігається з std::sort.

3. Високий рівень. Створити проєкт CMake з програмою mergesort, що сортує дані з бінарного або текстового файлу (--input), приймає опції --depth, --cutoff <розмір для послідовного сортування>, --runs, --csv і --help. Програма виводить таблицю «глибина – поріг – медіана часу – $S$», знаходить найкращу комбінацію, записує CSV для побудови графіка прискорення і перевіряє стабільність сортування записів. Помилки – у stderr з кодами 1 і 2.

Варіант 16. Моделювання черги в банку

1. Початковий рівень. Створити консольну програму мовою C++, у якій 3 касири-потоки std::jthread обслуговують клієнтів із черги (std::mutex і std::condition_variable), а генератор клієнтів додає клієнта кожні 30 мс. Через 3 с головний потік викликає request_stop(), касири завершують поточне обслуговування, і програма виводить кількість обслугованих клієнтів кожним касиром.

2. Базовий рівень. Створити консольну програму мовою C++, яка запитує кількість касирів, середній інтервал надходження клієнтів і середню тривалість обслуговування (мс) та тривалість моделювання. Касири чекають клієнтів у std::condition_variable_any::wait з std::stop_token. Програма виводить середній і максимальний час очікування в черзі, максимальну довжину черги та завантаження касирів.

3. Високий рівень. Створити проєкт CMake з програмою bankqueue, що приймає опції --tellers 1,2,3,4, --arrival <мс>, --service <мс>, --duration <с>, --vip <частка> і --help. VIP-клієнти обслуговуються першими. Для кожної кількості касирів програма виводить таблицю статистики очікування (середнє, 95-й процентиль, максимум) окремо для VIP і звичайних клієнтів та рекомендує мінімальну кількість касирів, за якої середнє очікування не перевищує 2 інтервали надходження. Завершення потоків – лише через stop_token.

Варіант 17. Лічильник подій

1. Початковий рівень. Створити консольну програму мовою C++, у якій 8 потоків по 5 000 000 разів збільшують спільний лічильник трьома способами: без синхронізації, під std::mutex і через std::atomic<long long>, та виводить отримані значення й час кожного способу.

2. Базовий рівень. Створити консольну програму мовою C++, яка запитує кількість потоків і подій на потік та порівнює чотири способи підрахунку: спільний std::atomic, масив std::atomic по одному на потік (сусідні елементи), той самий масив з вирівнюванням alignas(std::hardware_destructive_interference_size) і локальні лічильники з одним додаванням наприкінці. Програма виводить таблицю часу та пояснює вплив хибного розділення.

3. Високий рівень. Створити проєкт CMake з програмою counters, що вимірює пропускну здатність лічильників подій різних типів (mutex, atomic, padded, local) для кількостей потоків --threads 1,2,4,8,16 і тривалості --seconds. Програма виводить таблицю «спосіб – потоки – подій за секунду – масштабованість», записує CSV, виводить розмір кеш-лінії і sizeof структур лічильників. Опції --help, помилки аргументів – у stderr з кодом 1; збірка tsan не повинна давати попереджень для коректних способів.

Варіант 18. Хешування файлів

1. Початковий рівень. Створити консольну програму мовою C++, яка обчислює контрольну суму FNV-1a (64 біти) для кожного файлу, шлях до якого передано аргументом командного рядка, використовуючи std::packaged_task, запущені в окремих потоках, і виводить таблицю «файл – розмір – хеш» у шістнадцятковому вигляді.

2. Базовий рівень. Створити консольну програму мовою C++ з пулом потоків (кількість вводить користувач), яка обчислює хеш FNV-1a для всіх файлів введеного каталогу рекурсивно. Кожне завдання повертає std::future зі структурою результату; файли, які не вдалося прочитати, передають виняток через future. Програма виводить таблицю хешів, список помилок і загальний обсяг та швидкість (МБ/с).

3. Високий рівень. Створити проєкт CMake з програмою hashdir, що приймає каталог і опції --threads, --block <КБ>, --verify <файл> і --help. Без --verify програма записує маніфест шлях;розмір;хеш у стандартне виведення, а з ним – порівнює поточні хеші з маніфестом і виводить змінені, нові та видалені файли. Великі файли діляться на блоки, що хешуються задачами пулу, з комбінуванням хешів блоків. Коди завершення: 0 – збіг, 4 – знайдено зміни, 1/2 – помилки аргументів і файлів.

Варіант 19. Задача n ферзів

1. Початковий рівень. Створити консольну програму мовою C++, яка підраховує кількість розв’язків задачі про 12 ферзів, запускаючи для кожної позиції ферзя в першому рядку окрему задачу std::async, і виводить кількість розв’язків для кожної позиції, загальну кількість і час.

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

3. Високий рівень. Створити проєкт CMake з програмою queens, що паралельно підраховує розв’язки задачі про $n$ ферзів перебором з бітовими масками, розподіляючи префікси розміщень між потоками. Опції: --n, --prefix-depth, --threads, --first (знайти перший розв’язок і зупинити всі потоки через std::stop_source), --print, --help. Програма виводить таблицю часу для різних глибин префікса й кількостей потоків, у режимі --first друкує дошку знайденого розв’язку й час до зупинки всіх потоків. Помилки аргументів – у stderr з кодом 1.

Варіант 20. Трафік магістралі

1. Початковий рівень. Створити консольну програму мовою C++, у якій 6 потоків-датчиків готуються до роботи (випадкова затримка ініціалізації) і одночасно починають вимірювання після std::latch, кожен генерує 1000 показів швидкості, а головний потік чекає на завершення через другий std::latch і виводить середню швидкість на кожному датчику.

2. Базовий рівень. Створити консольну програму мовою C++, яка запитує кількість датчиків і тривалість вимірювання, синхронно стартує датчики через std::latch, а щосекунди датчики передають агрегатору кількість автомобілів і середню швидкість через захищену чергу. Агрегатор виводить таблицю за секундами та підсумкову інтенсивність руху, позначаючи секунди із заторами (середня швидкість менша за 30 км/год).

3. Високий рівень. Створити проєкт CMake з програмою highway, що читає опис ділянок магістралі з файлу (ділянка;довжина_км;ліміт_км/год) і журнали датчиків із каталогу. Датчики обробляються потоками з синхронним стартом (std::latch) і фазами за хвилинами (std::barrier). Опції --from, --to, --jam-speed, --csv і --help. Програма виводить звіт за ділянками (інтенсивність, середня швидкість, хвилини заторів), записує CSV і повідомляє про неповні журнали в stderr.

Варіант 21. Лексикографічні перестановки

1. Початковий рівень. Створити консольну програму мовою C++, яка генерує всі перестановки рядка з 11 різних літер, розділивши роботу між потоками за першою літерою (для кожної літери – окремий потік, std::next_permutation для решти), і виводить загальну кількість перестановок та час.

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

3. Високий рівень. Створити проєкт CMake з програмою permute, що приймає рядок і опції --threads, --prefix <довжина>, --output <файл>, --from <номер> --count <k> і --help. Програма обчислює лексикографічний номер кожного префікса, щоб паралельно згенерувати потрібний діапазон перестановок і записати його у файл у правильному порядку (кожен потік пише в буфер, буфери об’єднуються). Перевіряється впорядкованість і відсутність повторів; помилки – у stderr з кодами 1/2.

Варіант 22. Оцінка інтегралів кількох функцій

1. Початковий рівень. Створити консольну програму мовою C++, яка обчислює інтеграли п’яти заданих у програмі функцій на відрізку $[0,1]$ методом трапецій з ${10}^8$ відрізків, запускаючи кожне обчислення як std::async, і виводить таблицю «функція – значення – час».

2. Базовий рівень. Створити консольну програму мовою C++, яка для функцій з відомими первісними (обираються з меню) і введених меж обчислює інтеграли методами прямокутників, трапецій і Сімпсона для $n={10}^3\dots {10}^8$; кожна комбінація – задача з результатом у std::future. Програма виводить таблицю значень, абсолютних похибок і часу та загальний час паралельного й послідовного обчислення всієї таблиці.

3. Високий рівень. Створити проєкт CMake з програмою quadrature, що читає завдання інтегрування з файлу (функція;a;b;точність) і для кожного обчислює інтеграл адаптивним методом Сімпсона, де рекурсивні половини відрізка виконуються як задачі std::async до заданої глибини. Опції --depth, --threads-limit, --csv і --help. Програма виводить таблицю значень, оцінок похибки, кількості обчислень функції й часу, записує CSV; невідомі функції та некоректні межі – у stderr з кодом 2.

Варіант 23. Рейтинг шахістів Ело

1. Початковий рівень. Створити консольну програму мовою C++, яка генерує результати 10 000 турнірів (по 100 партій між випадковими з 1000 гравців) і обчислює для кожного турніру суму змін рейтингу за формулою Ело паралельно за допомогою std::transform_reduce з політикою par, виводячи загальну суму змін і час порівняно з seq.

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

3. Високий рівень. Створити проєкт CMake з програмою elo, що обробляє каталог файлів турнірів у хронологічному порядку: турніри одного дня обчислюються паралельно (гравці не перетинаються – це перевіряється), а дні – послідовно. Опції --k-factor, --initial, --policy seq|par, --top <n>, --out <файл> і --help. Програма виводить підсумковий рейтинг, історію обраного гравця, час обох політик і повідомлення про гравця, що бере участь у двох турнірах одного дня, у stderr з кодом 3.

Варіант 24. Фільтрація сигналу

1. Початковий рівень. Створити консольну програму мовою C++, яка генерує сигнал із 50 000 000 відліків (сума синусоїд і шуму) та застосовує до нього нелінійне перетворення кожного відліку (обмеження амплітуди й квадратичне підсилення) за допомогою std::transform з політиками seq і unseq, виводячи час обох варіантів і максимальну різницю результатів.

2. Базовий рівень. Створити консольну програму мовою C++, яка генерує сигнал (сума синусоїд і шуму) заданої довжини, запитує порядок ковзного середнього (3–101), перевіряє введення і фільтрує сигнал ковзним середнім трьома способами: простим циклом, std::transform з unseq для префіксних сум і par_unseq. Програма виводить таблицю часу, збіг результатів і порівнює час зі збіркою без -march=native.

3. Високий рівень. Створити проєкт CMake з опцією option(USE_NATIVE "Use -march=native" ON) і програмою firfilter, що читає сигнал із файлу WAV (16 біт, моно) і коефіцієнти FIR-фільтра з текстового файлу. Опції --policy seq|unseq|par|par_unseq, --runs, --out <файл.wav> і --help. Програма фільтрує сигнал (згортка), записує результат, виводить таблицю медіан часу для всіх політик і для ручної векторизованої версії (блоками по 8 відліків) та перевіряє збіг результатів з точністю ${10}^{-6}$.

Варіант 25. Шифрування XOR файлів блоками

1. Початковий рівень. Створити консольну програму мовою C++, яка шифрує файл, шлях до якого вводить користувач, операцією XOR з ключем-рядком, розбиваючи вміст на 8 блоків, що обробляються потоками std::jthread, записує результат у файл .xor і виводить розмір файлу та час.

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

3. Високий рівень. Створити проєкт CMake з програмою xorcrypt, що приймає encrypt|decrypt input output і опції --key-file, --threads, --block <МБ>, --verify і --help. Файл обробляється блоками без повного завантаження в пам’ять; до результату додається заголовок із контрольною сумою оригіналу. Режим --verify перевіряє суму після розшифрування. Програма виводить прогрес і швидкість; помилки – у stderr з кодами 1/2, невідповідність контрольної суми – код 3.

Варіант 26. Сплячий перукар на C++

1. Початковий рівень. Створити консольну програму мовою C++, яка моделює задачу сплячого перукаря: один перукар-потік, 3 стільці в приймальні та 15 клієнтів, що приходять із випадковими інтервалами; використати std::mutex і std::condition_variable. Програма виводить журнал подій (прийшов, сів чекати, пішов без стрижки, стрижеться) і підсумки.

2. Базовий рівень. Створити консольну програму мовою C++, яка запитує кількість перукарів, стільців, клієнтів і тривалість стрижки, моделює перукарню з потоками std::jthread, де перукарі чекають у std::condition_variable_any::wait з stop_token. Після останнього клієнта головний потік зупиняє перукарів через request_stop(). Програма виводить кількість обслугованих і втрачених клієнтів, середнє очікування та зайнятість кожного перукаря.

3. Високий рівень. Створити проєкт CMake з пресетом tsan і програмою barbershop, що моделює перукарню (задача сплячого перукаря: перукарі й клієнти – потоки, м’ютекс і умовні змінні) з опціями --barbers, --chairs, --customers, --arrival <мс>, --haircut <мс>, --seed, --log <файл> і --help. Програма проводить серію моделювань для кількості стільців у приймальні 0…10, виводить таблицю частки втрачених клієнтів і середнього очікування, записує журнал і перевіряє інваріанти (порушення – код 3).

Варіант 27. Порівняння C# і C++

1. Початковий рівень. Створити консольну програму мовою C++, яка обчислює суму $\sum _{i=1}^n\sqrt{i}$ для $n$ = 500 000 000 послідовно та у 8 потоках std::jthread, і аналогічну програму мовою C# на .NET 10 (Parallel.For з локальним станом), та вивести в обох програмах результат і медіану часу трьох запусків у конфігурації Release.

2. Базовий рівень. Створити дві консольні програми (C++ і C#), які розв’язують однакову задачу – множення квадратних матриць розміром, введеним користувачем, послідовно та в $p$ потоках за рядками – з однаковим генератором даних. Програми виводять у стандартному форматі рядки мова;n;p;час_мс;контрольна_сума, а третя програма мовою C++ зчитує обидва виведення з файлів і будує порівняльну таблицю часу, прискорення й відношення часу C# до C++.

3. Високий рівень. Створити проєкт CMake з програмою bench-cpp і консольний проєкт .NET bench-cs, які реалізують однаковий набір тестів (сума з коренем, множення матриць, сортування, Монте-Карло) з опціями --test, --size, --threads, --runs, --warmup. Скрипт або програма C++ запускає обидві програми для всіх комбінацій, перевіряє збіг контрольних сум (інакше код 3) і виводить зведену таблицю медіан і відношень часу.

Варіант 28. Паралельний BFS лабіринту

1. Початковий рівень. Створити консольну програму мовою C++, яка генерує лабіринт 2000×2000 (прохідні клітини з імовірністю 70 %, фіксоване зерно) і знаходить відстань від лівого верхнього до правого нижнього кута пошуком у ширину за рівнями, обробляючи клітини поточного рівня в 4 потоках, та виводить відстань і час.

2. Базовий рівень. Створити консольну програму мовою C++, яка читає лабіринт із текстового файлу (# – стіна, . – прохід, S і F – старт і фініш), виконує рівневий паралельний пошук у ширину з позначками відвідування у векторі std::atomic<bool> (compare_exchange_strong), перевіряє результат послідовним BFS і виводить довжину найкоротшого шляху та таблицю часу для 1, 2, 4 і 8 потоків.

3. Високий рівень. Створити проєкт CMake з програмою mazebfs, що приймає файл лабіринту або опцію --generate WxH, а також --threads, --path <файл> і --help. Програма виконує паралельний BFS за рівнями з локальними буферами наступного рівня в кожному потоці, відновлює найкоротший шлях, записує лабіринт зі шляхом у файл, виводить розмір кожного рівня фронту, таблицю часу й прискорення та перевіряє довжину шляху послідовним BFS. Недосяжний фініш – код 3, помилки файлу – код 2.

Варіант 29. Температурна карта регіону

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

2. Базовий рівень. Створити консольну програму мовою C++, яка читає метеостанції з файлу (назва;x;y;температура), запитує розмір карти й степінь зважування, перевіряє введення, будує карту послідовно та в $p$ потоках і виводить мінімальну, максимальну й середню температуру карти, таблицю часу для 1, 2, 4, 8 потоків і перевірку збігу результатів.

3. Високий рівень. Створити проєкт CMake з опціями option(ENABLE_NATIVE …) та option(ENABLE_LTO …) і програмою heatmap, що приймає файл станцій і опції --size WxH, --power, --radius <км>, --threads, --policy threads|par, --out <файл.ppm> і --help. Програма будує кольорову карту, виводить таблицю часу для різних кількостей потоків і збірок з -O2, -O3, -march=native. Помилки – у stderr з кодами 1/2.

Варіант 30. Тестування потокобезпеки черги

1. Початковий рівень. Створити консольну програму мовою C++ з потокобезпечною чергою (std::queue під std::mutex з методами push і try_pop), у якій 4 потоки-виробники додають по 100 000 чисел, а 4 споживачі їх вилучають. Програма перевіряє, що сума вилучених чисел дорівнює сумі доданих, і виводить результат перевірки.

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

3. Високий рівень. Створити проєкт CMake із пресетами release і tsan та програмою queuetest, що тестує кілька реалізацій черги (mutex, two-locks з окремими м’ютексами голови й хвоста, bounded на семафорах). Опції --impl, --producers, --consumers, --items і --help. Програма виводить таблицю пропускної здатності й результати перевірки інваріантів (порушення – код 3); до звіту додається виведення збірки tsan.

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

1. Опрацювати теоретичні відомості та приклади розв’язання завдань.
2. Встановити в Ubuntu 26.04 (WSL2) пакети build-essential, cmake, ninja-build, gdb, libtbb-dev, налаштувати в CLion тулчейн WSL і профілі CMake Debug та Release з генератором Ninja.
3. Створити проєкт CMake з файлом CMakePresets.json, реалізувати завдання обраного рівня складності й перевірити збирання з командного рядка.
4. Перевірити результат із послідовною версією, усунути попередження ThreadSanitizer (-fsanitize=thread), виміряти в Release медіану часу, прискорення й ефективність.
5. Продемонструвати роботу програми викладачеві, пояснити програмний код, файли CMake і результати вимірювань, відповісти на контрольні питання.