Завдання

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

Варіанти

Варіант 1. Множення матриць

1. Початковий рівень. Створити консольну програму, яка заповнює дві квадратні матриці розміром 800×800 випадковими дійсними числами від 0 до 1 (генератор із фіксованим зерном), обчислює їхній добуток послідовно та за допомогою Parallel.For за рядками результату й виводить час обох варіантів, прискорення та максимальну різницю елементів двох результатів.

2. Базовий рівень. Створити консольну програму, яка запитує розмір квадратних матриць $n$ (від 100 до 2000) і перевіряє введення. Програма множить матриці послідовно та паралельно за рядками з ParallelOptions.MaxDegreeOfParallelism для $p=1,2,4,8,16$ (не більше за Environment.ProcessorCount), для кожного $p$ вимірює медіану трьох запусків після прогрівання, перевіряє збіг результату з послідовним (похибка не більше ${10}^{-9}$) і виводить вирівняну таблицю «$p$ – час, мс – прискорення $S$ – ефективність $E$».

3. Високий рівень. Створити консольний застосунок matmul, який приймає опції --sizes 500,1000,1500, --threads 1,2,4,8,16, --order ijk|ikj, --csv <файл> і --help. Для кожного розміру програма вимірює послідовне множення та паралельне множення за рядками (медіана п’яти запусків після прогрівання), перевіряє результат, виводить таблицю «$n$ – $p$ – час – $S$ – $E$» і записує її у файл CSV (десяткова крапка) для побудови графіка прискорення, а також порівнює порядки циклів ijk і ikj. Некоректні опції виводяться в потік помилок з кодом завершення 1, розбіжність результатів – з кодом 2.

Варіант 2. Розмиття зображення PPM

1. Початковий рівень. Створити консольну програму, яка читає кольорове зображення у форматі PPM (P6), шлях до якого вводить користувач, застосовує до нього розмиття середнім значенням у вікні 3×3 за допомогою Parallel.For за рядками (результат записується в новий масив) і зберігає результат у файл blur.ppm, виводячи розміри зображення й час обробки.

2. Базовий рівень. Створити консольну програму, яка читає зображення PPM (P6) і радіус фільтра Гаусса $r$ (від 1 до 10), будує ядро фільтра, розмиває зображення двома проходами (горизонтальним і вертикальним) послідовно та паралельно за рядками, перевіряє збіг результатів і виводить таблицю часу, прискорення й ефективності для 1, 2, 4, 8 і 16 потоків. Некоректний файл або радіус спричиняє зрозуміле повідомлення.

3. Високий рівень. Створити консольний застосунок gblur, який приймає аргументи input.ppm output.ppm та опції --radius <r>, --threads 1,2,4,8, --scale 1,2,4, --csv <файл> і --help. Опція --scale збільшує зображення в указану кількість разів за кожною стороною перед обробкою, щоб дослідити сильну масштабованість для різних розмірів. Програма виводить таблицю «розмір – потоки – час, мс – $S$ – $E$», записує CSV і зберігає результат найбільшого варіанта. Результат паралельної обробки має побайтно збігатися з послідовною. Помилки формату PPM (невідомий заголовок, неповні дані) виводяться в потік помилок з кодом завершення 2, помилки аргументів – з кодом 1.

Варіант 3. Інтегрування методом трапецій

1. Початковий рівень. Створити консольну програму, яка обчислює інтеграл функції $\sin (x)\cdot e^{-\frac{x}{5}}$ на відрізку $[0,20]$ методом трапецій з $n$ = 50 000 000 відрізків послідовно та паралельно за допомогою Parallel.For з локальним станом потоку (localInit, localFinally) і виводить обидва значення з 10 знаками після коми та час обчислень.

2. Базовий рівень. Створити консольну програму, яка запитує межі інтегрування $a<b$ та кількість відрізків $n$ (від 1000 до 10⁹), перевіряє введення й обчислює інтеграл функції $x^2\cdot \cos (x)$ методом трапецій трьома способами: Parallel.For з локальним станом, Parallel.ForEach з Partitioner.Create(0, n) та Partitioner.Create(0, n, rangeSize) з розміром діапазону 100 000. Програма виводить для кожного способу значення, відхилення від послідовного результату, час і прискорення.

3. Високий рівень. Створити консольний застосунок trapz, який приймає опції --function sin|exp|poly, --from, --to, --n, --threads 1,2,4,8,16, --range-sizes 1000,100000,10000000 і --help. Програма обчислює інтеграл вибраної функції послідовно та паралельно з діапазонним розбивачем для кожної пари «кількість потоків – розмір діапазону», виводить таблицю часу й прискорення, найкращий розмір діапазону для кожної кількості потоків і похибку порівняно з аналітичним значенням інтеграла. Результати записуються у файл CSV; некоректні параметри виводяться в потік помилок з кодом завершення 1.

Варіант 4. Число π методом Монте-Карло

1. Початковий рівень. Створити консольну програму, яка оцінює число π методом Монте-Карло за 100 000 000 випадкових точок у квадраті $[0,1]\times [0,1]$, розбиваючи випробування на 64 блоки, кожен з власним генератором new Random(1000 + номер блоку), які обробляються за допомогою Parallel.For. Програма виводить оцінку π, абсолютну похибку й час.

2. Базовий рівень. Створити консольну програму, яка запитує кількість випробувань $N$ (від 10⁶ до 10⁹) і кількість блоків (від 1 до 1024), перевіряє введення та оцінює π методом Монте-Карло (частка випадкових точок одиничного квадрата всередині чверті кола) паралельно з генератором на блок для 1, 2, 4, 8 і 16 потоків. Програма виводить таблицю «потоки – оцінка π – похибка – час – $S$ – $E$» і перевіряє, що оцінки для всіх кількостей потоків однакові.

3. Високий рівень. Створити консольний застосунок mcpi, який оцінює π методом Монте-Карло (випадкові точки в одиничному квадраті) паралельно з опціями --samples, --blocks, --threads 1,2,4,8,16, --seed, --mode blocks|shared і --help. У режимі blocks кожен блок має генератор із зерном seed + номер блоку, у режимі shared – Random.Shared. Для 10⁶, 10⁷, 10⁸ випробувань (або заданої кількості) програма виводить оцінку, похибку, теоретичну стандартну похибку $\sqrt{\pi (4-\pi )/N}$, час і прискорення та перевіряє відтворюваність режиму blocks. Таблиця – у CSV; помилки аргументів – код 1.

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

1. Початковий рівень. Створити консольну програму, яка заповнює масив з 5 000 000 цілих чисел генератором із фіксованим зерном, сортує копії масиву послідовним сортуванням злиттям і паралельним сортуванням злиттям (Parallel.Invoke для двох половин, поріг 10 000 елементів), перевіряє обидва результати методом порівняння з Array.Sort і виводить час сортувань та прискорення.

2. Базовий рівень. Створити консольну програму, яка запитує розмір масиву (від 10⁵ до 5·10⁷) і перелік порогів переходу на послідовне сортування через кому (наприклад, 1000,10000,100000), перевіряє введення та для кожного порогу вимірює час паралельного сортування злиттям (медіана трьох запусків). Програма виводить таблицю «поріг – час, мс – прискорення відносно послідовного», позначає найкращий поріг і перевіряє впорядкованість кожного результату.

3. Високий рівень. Створити консольний застосунок pmsort, який сортує масиви випадкових цілих чисел паралельним сортуванням злиттям (половини – в окремих задачах, фрагменти, менші за поріг, послідовно) з опціями --sizes, --threads, --threshold, --parallel-merge, --csv <файл> і --help. З --parallel-merge злиття також паралельне: середній елемент більшої половини шукається бінарним пошуком у меншій, частини зливаються в окремих задачах. Для кожного розміру й кількості потоків програма виводить час, $S$ і $E$ обох варіантів злиття, перевіряє результат з Array.Sort і записує CSV. Помилки аргументів – код 1, неправильне сортування – код 2.

Варіант 6. Гістограма яскравості фото

1. Початковий рівень. Створити консольну програму, яка генерує зображення 8000×6000 пікселів у відтінках сірого (байтові значення від 0 до 255, генератор із фіксованим зерном), будує гістограму яскравості послідовно та за допомогою Parallel.For з локальними масивами гістограм (localInit, localFinally) і виводить час обох способів, перевірку збігу гістограм і п’ять найчастіших значень яскравості.

2. Базовий рівень. Створити консольну програму, яка читає зображення PPM (P6), шлях до якого вводить користувач, обчислює яскравість кожного пікселя ($0,299R+0,587G+0,114B$) і будує гістограму трьома способами: спільний масив з Interlocked.Increment, локальні гістограми з localInit/localFinally та Partitioner.Create з діапазонами. Програма виводить таблицю часу й прискорення способів для 16 потоків, перевіряє збіг гістограм і виводить середню яскравість та медіану.

3. Високий рівень. Створити консольний застосунок histo, який приймає шляхи до одного чи кількох файлів PPM або теки та опції --threads, --bins <кількість>, --csv <файл>, --help. Для кожного файлу програма будує гістограму яскравості з локальними гістограмами розділів, виводить таблицю «файл – розмір – середнє – медіана – частка темних пікселів», а також сумарну гістограму всіх файлів у вигляді текстової діаграми з символів #. Для найбільшого файлу виводиться таблиця прискорення та ефективності для 1, 2, 4, 8, 16 потоків. Файли з помилками пропускаються з повідомленням у потік помилок; якщо не оброблено жодного файлу, код завершення 2.

Варіант 7. Гра «Життя» Конвея

1. Початковий рівень. Створити консольну програму, яка моделює 200 поколінь гри «Життя» Конвея на тороїдальному полі 1000×1000 клітинок з випадковим початковим заповненням 30 % (фіксоване зерно). Нове покоління обчислюється в окремий масив за допомогою Parallel.For за рядками; програма виводить кількість живих клітинок після кожних 50 поколінь і загальний час.

2. Базовий рівень. Створити консольну програму, яка запитує розмір поля, кількість поколінь і частку початкового заповнення (від 5 до 95 %), перевіряє введення та моделює гру «Життя» послідовно й паралельно за рядками для 1, 2, 4, 8 і 16 потоків. Програма перевіряє, що кінцеві поля всіх варіантів однакові, і виводить таблицю часу на покоління, прискорення та ефективності.

3. Високий рівень. Створити консольний застосунок life, який моделює гру «Життя» Конвея на тороїдальному полі (нове покоління обчислюється паралельно за рядками в окремий масив) з опціями --threads, --generations, --base-size <n>, --mode strong|weak, --pattern <файл> і --help. У режимі strong розмір поля сталий, у weak площа зростає пропорційно кількості потоків (сторона $n\sqrt{p}$). Програма виводить таблицю «потоки – розмір поля – час на покоління – $S$ або $T_1/T_p$» і записує CSV. Початкове поле завантажується з текстового файлу (. і O) або генерується випадково; некоректний файл – номер рядка в потоці помилок і код 2.

Варіант 8. Частота слів у корпусі текстів

1. Початковий рівень. Створити консольну програму, яка читає всі файли *.txt з теки, шлях до якої вводить користувач, і за допомогою PLINQ (AsParallel, SelectMany, GroupBy) підраховує частоту слів без урахування регістру. Програма виводить 20 найчастіших слів з кількостями та час виконання запиту.

2. Базовий рівень. Створити консольну програму, яка генерує корпус текстів (кількість речень вводить користувач, від 10⁴ до 10⁷, словник із 200 слів, фіксоване зерно) і підраховує частоту слів трьома способами: LINQ, PLINQ з GroupBy та Parallel.ForEach з локальними словниками (localInit/localFinally). Програма перевіряє збіг результатів і виводить таблицю часу й прискорення способів та 10 найчастіших слів.

3. Високий рівень. Створити консольний застосунок wordfreq, який приймає теку з текстами та опції --method linq|plinq|foreach|aggregate|all, --threads, --min-length, --top <k>, --stop-words <файл> і --help. Програма підраховує частоту слів обраними способами, виводить таблицю «спосіб – потоки – час – $S$ – $E$», перевіряє збіг частот усіх способів і записує $k$ найчастіших слів у CSV. Нечитабельні файли пропускаються з повідомленням у потік помилок; відсутня тека – код завершення 2, некоректні опції – код 1.

Варіант 9. Прості числа до 10⁸

1. Початковий рівень. Створити консольну програму, яка підраховує кількість простих чисел до 10⁷ перевіркою дільників до $\sqrt{n}$ послідовно та за допомогою Parallel.For з локальним лічильником потоку і виводить обидві кількості та час обчислень.

2. Базовий рівень. Створити консольну програму, яка запитує верхню межу $N$ (від 10⁶ до 10⁹) і розмір сегмента (від 10⁴ до 10⁷), перевіряє введення та знаходить кількість простих чисел сегментованим решетом Ератосфена: базові прості до $\sqrt{N}$ обчислюються послідовно, а сегменти просіюються паралельно. Програма виводить кількість простих чисел, найбільше просте число, час і прискорення відносно послідовного сегментованого решета.

3. Високий рівень. Створити консольний застосунок primes, який приймає опції --limit, --segment-sizes 32768,262144,2097152, --threads 1,2,4,8,16, --csv <файл> і --help. Програма підраховує прості числа паралельним сегментованим решетом (окремий масив сегмента для кожного розділу), виводить таблицю «розмір сегмента – потоки – час – $S$ – $E$», найкращу конфігурацію та кількість простих чисел, яка має збігатися для всіх запусків (для 10⁸ – 5 761 455). Таблиця записується в CSV; розбіжність кількостей – код завершення 2, помилки аргументів – код 1.

Варіант 10. Кластеризація k-means

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

2. Базовий рівень. Створити консольну програму, яка запитує кількість точок, кількість кластерів $k$ і максимальну кількість ітерацій, перевіряє введення та виконує k-means до стабілізації центрів (зміщення менше ${10}^{-6}$). Нові центри обчислюються паралельно з локальними сумами координат і кількостями точок для кожного потоку. Програма перевіряє збіг центрів з послідовною версією та виводить кількість ітерацій, розміри кластерів, час на ітерацію та прискорення.

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

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

1. Початковий рівень. Створити консольну програму, яка сортує масив з 10 000 000 випадкових цілих чисел швидким сортуванням, у якому дві частини після розділення сортуються паралельно (Parallel.Invoke) до глибини рекурсії 4, а далі – послідовно. Програма перевіряє впорядкованість і виводить час порівняно з Array.Sort.

2. Базовий рівень. Створити консольну програму, яка запитує розмір масиву та максимальну глибину паралельної рекурсії (від 0 до 10), перевіряє введення та сортує паралельним швидким сортуванням масиви трьох видів: випадкові, майже відсортовані (1 % перестановок) і з великою кількістю однакових значень. Програма виводить таблицю «вид даних – час паралельного швидкого сортування – час Array.Sort – відношення» і перевіряє правильність кожного результату.

3. Високий рівень. Створити консольний застосунок pqsort, який приймає опції --size, --depths 0,2,4,6,8, --pivot first|middle|random|median3, --cutoff <n>, --data random|sorted|dups|all і --help. Програма вимірює час паралельного швидкого сортування для кожної глибини та способу вибору опорного елемента, порівнює з Array.Sort і послідовним швидким сортуванням, виводить таблицю прискорень і найкращу конфігурацію для кожного виду даних. Неправильно відсортований результат спричиняє повідомлення в потоці помилок і код завершення 2.

Варіант 12. Префіксні суми продажів

1. Початковий рівень. Створити консольну програму, яка для масиву щоденних продажів магазину довжиною $2^{20}$ (випадкові суми від 0 до 10 000 грн, фіксоване зерно) обчислює виключну префіксну суму алгоритмом Блеллока (фази підйому та спуску, рівні виконуються через Parallel.For) і перевіряє результат послідовним накопиченням, виводячи перші 10 значень та час обох способів.

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

3. Високий рівень. Створити консольний застосунок scan, який приймає CSV-файл продажів (date,store,amount) та опції --op sum|max|min, --threads, --min-pairs <n>, --csv <файл> і --help. Для кожного магазину програма обчислює префіксну операцію (накопичена сума, поточний максимум або мінімум) алгоритмом Блеллока, перевіряє її послідовним проходом і записує результат у CSV. Для синтетичного масиву $2^{24}$ елементів програма виводить таблицю часу, прискорення й ефективності алгоритму Блеллока відносно послідовного проходу для 1, 2, 4, 8, 16 потоків. Некоректні рядки – у потік помилок, помилки аргументів – код 1.

Варіант 13. Пошук підрядка в журналах

1. Початковий рівень. Створити консольну програму, яка генерує масив з 5 000 000 рядків журналу (фіксоване зерно, у випадкових місцях вставлено рядки з текстом ERROR 503) і за допомогою Parallel.For з методом Break знаходить індекс першого рядка, що містить ERROR 503, виводячи LowestBreakIteration, сам рядок і час пошуку порівняно з послідовним.

2. Базовий рівень. Створити консольну програму, яка читає всі рядки текстового файлу журналу (шлях і шуканий підрядок вводить користувач) і виконує три пошуки: першого входження (Parallel.For з Break), будь-якого входження (Stop) і кількості всіх входжень (локальний лічильник). Програма перевіряє, що перше входження збігається з результатом послідовного пошуку, і виводить номери рядків, кількість і час кожного пошуку.

3. Високий рівень. Створити консольний застосунок loggrep, який приймає теку журналів, підрядок або регулярний вираз (--regex) і опції --first, --count, --threads, --timeout <с> та --help. Файли обробляються Parallel.ForEach з ParallelOptions (маркер скасування з таймаутом), рядки великих файлів – діапазонами. Програма виводить таблицю «файл – рядків – входжень – перше входження», загальну кількість і час, а для опції --first – перше входження в порядку файлів і рядків. Після таймауту виводяться часткові результати з позначкою «скасовано» і код завершення 3; відсутня тека – код 2.

Варіант 14. Статистика погодних архівів

1. Початковий рівень. Створити консольну програму, яка генерує 10 000 000 записів погоди (рік від 1980 до 2025, місяць, температура; фіксоване зерно) і за допомогою одного запиту PLINQ Aggregate з функціями seed, update, combine і result обчислює середню, мінімальну та максимальну температуру за весь період, виводячи результат і час порівняно з LINQ.

2. Базовий рівень. Створити консольну програму, яка читає CSV-файл погодних спостережень (date,station,temperature, шлях вводить користувач), пропускає некоректні рядки з підрахунком і за допомогою PLINQ обчислює для кожного року середню, мінімальну та максимальну температуру (Aggregate з акумулятором-структурою) та медіану (групування й сортування). Програма виводить таблицю за роками та порівнює час PLINQ і LINQ.

3. Високий рівень. Створити консольний застосунок climate, який приймає один або кілька CSV-файлів архіву та опції --from <рік>, --to <рік>, --station <код>, --threads, --merge not|auto|full і --help. Програма обчислює за допомогою PLINQ річну та місячну статистику (середнє, мінімум, максимум, медіана, кількість спостережень), виводить таблицю з трендом середньої температури (лінійна регресія за роками), порівнює час запиту для різних режимів злиття й кількостей потоків і перевіряє, що результати не залежать від налаштувань. Некоректні рядки підраховуються й виводяться в потік помилок (перші 10), помилки аргументів – код 1.

Варіант 15. Множина Жюліа

1. Початковий рівень. Створити консольну програму, яка обчислює множину Жюліа для $c=-0,8+0,156i$ на зображенні 2000×1500 пікселів (до 500 ітерацій) за допомогою Parallel.For за рядками і записує зображення у відтінках сірого у файл PGM, виводячи час обчислення.

2. Базовий рівень. Створити консольну програму, яка запитує дійсну та уявну частини $c$, розміри зображення й максимальну кількість ітерацій, перевіряє введення та обчислює множину Жюліа трьома способами розподілу рядків: статичні рівні блоки (Parallel.For за номером блоку), Parallel.For за рядками та Partitioner.Create з динамічним балансуванням. Програма виводить час кожного способу для 16 потоків, час роботи найповільнішого й найшвидшого блоку статичного розподілу та зберігає PGM.

3. Високий рівень. Створити консольний застосунок julia, який обчислює множину Жюліа паралельно за рядками й зберігає її у файл PGM (--out <файл.pgm>) з опціями --c <re,im>, --size WxH, --iter, --partition static|rows|chunk|dynamic|all, --chunk <n>, --threads і --help. Для кожного способу розбиття рядків програма вимірює час і нерівномірність навантаження (ітерацій на потік, відношення максимуму до середнього), виводить таблицю «спосіб – потоки – час – $S$ – нерівномірність» і перевіряє, що всі зображення однакові. Некоректна опція --c або --size – повідомлення в потоці помилок і код 1.

Варіант 16. Опціони Блека–Шоулза

1. Початковий рівень. Створити консольну програму, яка оцінює ціну європейського опціону call методом Монте-Карло ($S_0=100$, $K=105$, $r=5$ %, $\sigma =20$ %, $T=1$ рік, 10 000 000 траєкторій) паралельно з генератором на блок і виводить оцінку ціни, точне значення за формулою Блека–Шоулза та час обчислення.

2. Базовий рівень. Створити консольну програму, яка запитує параметри опціону ($S_0$, $K$, $r$, $\sigma$, $T$, тип call/put) і кількість траєкторій, перевіряє введення та оцінює ціну методом Монте-Карло паралельно (Parallel.For за блоками з власними генераторами й локальними сумами). Програма виводить оцінку, 95-відсотковий довірчий інтервал, точне значення за формулою Блека–Шоулза і таблицю часу й прискорення для 1, 2, 4, 8, 16 потоків.

3. Високий рівень. Створити консольний застосунок mcoption, який читає портфель опціонів з CSV-файлу (id,type,S0,K,r,sigma,T) і приймає опції --paths, --threads, --seed, --antithetic (антитетичні траєкторії для зменшення дисперсії) і --help. Програма оцінює всі опціони паралельно (рівень паралелізму --level outer|inner), виводить таблицю «опціон – оцінка – довірчий інтервал – точне значення – відхилення» та загальну вартість портфеля, а також час і прискорення. Результати відтворюються для однакового зерна; помилки файлу – код завершення 2.

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

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

2. Базовий рівень. Створити консольну програму, яка запитує кількість вершин (від 100 до 3000) і ймовірність ребра, перевіряє введення та обчислює найкоротші шляхи алгоритмом Флойда–Воршелла послідовно, з паралельним циклом за $i$ і з паралельним циклом за $j$. Програма пояснює у виведенні, чому цикл за $k$ не можна розпаралелити, перевіряє збіг матриць і виводить таблицю часу й прискорення варіантів для 16 потоків.

3. Високий рівень. Створити консольний застосунок apsp, який читає граф зі списку ребер у файлі (from to weight) або генерує випадковий граф (опції --random <n> <p>), приймає опції --threads, --path <u> <v> і --help. Програма обчислює найкоротші шляхи паралельним алгоритмом Флойда–Воршелла з відновленням шляху (матриця наступних вершин), виводить довжину й маршрут між заданими вершинами, діаметр графа, кількість недосяжних пар і таблицю часу, прискорення та ефективності для 1, 2, 4, 8, 16 потоків. Від’ємні цикли виявляються й повідомляються з кодом завершення 3; помилки файлу – код 2.

Варіант 18. Оцінки студентів великого університету

1. Початковий рівень. Створити консольну програму, яка генерує 5 000 000 записів оцінок (факультет, група, дисципліна, оцінка від 0 до 100; фіксоване зерно) і за допомогою PLINQ групує записи за факультетами, виводячи середню оцінку, кількість оцінок і частку оцінок нижче 60 для кожного факультету та час запиту.

2. Базовий рівень. Створити консольну програму, яка генерує задану користувачем кількість записів оцінок і виконує запит PLINQ «десять груп з найвищою середньою оцінкою» з різними режимами злиття (NotBuffered, AutoBuffered, FullyBuffered) та з AsOrdered і без нього. Програма виводить результат запиту, час до отримання першого елемента й загальний час для кожного режиму та перевіряє, що результати однакові.

3. Високий рівень. Створити консольний застосунок grades, який читає CSV-файли оцінок (student,faculty,group,course,score) і приймає опції --report faculty|group|course, --threshold <бал>, --threads, --merge not|auto|full, --out <файл> і --help. Програма будує звіт за допомогою PLINQ (середнє, медіана, стандартне відхилення, кількість незадовільних оцінок), виводить вирівняну таблицю з підсумковим рядком, записує звіт у CSV і порівнює час запиту LINQ та PLINQ для 1, 2, 4, 8, 16 потоків. Рядки з некоректною оцінкою пропускаються з повідомленням у потік помилок.

Варіант 19. Перетворення кольорів відеокадрів

1. Початковий рівень. Створити консольну програму, яка генерує 200 кольорових кадрів 1280×720 (масиви байтів RGB, фіксоване зерно) і перетворює кожен кадр у відтінки сірого за допомогою Parallel.ForEach за кадрами, виводячи середню яскравість першого та останнього кадру й загальний час.

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

3. Високий рівень. Створити консольний застосунок frames, який читає послідовність кадрів PPM з теки (або генерує їх опцією --generate <n> <WxH>) і приймає опції --filter gray|sepia|invert|contrast, --level outer|inner|both|auto, --threads, --out <тека> і --help. Режим auto обирає рівень паралелізму за кількістю та розміром кадрів. Програма обробляє кадри, зберігає результати, виводить таблицю «рівень – потоки – кадрів за секунду – $S$ – $E$» і пояснює вибір режиму auto. Кадри з різною роздільністю або пошкоджені файли спричиняють повідомлення в потоці помилок і код завершення 2.

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

1. Початковий рівень. Створити консольну програму, яка моделює 50 кроків руху 3000 тіл під дією гравітації (випадкові маси й координати, фіксоване зерно), обчислюючи прискорення тіл за допомогою Parallel.For (зовнішній цикл за тілами, $O(n^2)$) і оновлюючи положення після обчислення всіх сил. Програма виводить повну енергію системи на початку та наприкінці і час моделювання.

2. Базовий рівень. Створити консольну програму, яка запитує кількість тіл, кількість кроків і крок часу, перевіряє введення та моделює задачу $n$ тіл послідовно й паралельно для 1, 2, 4, 8, 16 потоків. Програма перевіряє, що координати після останнього кроку збігаються з послідовною версією (відхилення не більше ${10}^{-9}$), і виводить таблицю часу на крок, прискорення, ефективності та відносну зміну енергії.

3. Високий рівень. Створити консольний застосунок nbody, який моделює рух $n$ тіл під дією гравітації (прискорення за всіма парами, $O(n^2)$, паралельно за тілами). Початковий стан читається з CSV-файлу (mass,x,y,z,vx,vy,vz) або генерується (--random <n>); опції --steps, --dt, --threads, --mode strong|weak, --snapshot <кожні k кроків>, --help. Програма періодично записує стан у CSV, контролює збереження енергії та імпульсу й виводить таблицю сильної або слабкої масштабованості (кількість тіл зростає як $n\sqrt{p}$). Некоректні рядки файлу – номер рядка й код 2.

Варіант 21. Хешування паролів для аудиту

1. Початковий рівень. Створити консольну програму, яка має список з 20 000 паролів (генерується з фіксованим зерном) і за допомогою Parallel.ForEach обчислює хеш PBKDF2 (Rfc2898DeriveBytes.Pbkdf2, SHA-256, 10 000 ітерацій, сіль із логіна) для кожного пароля. Програма виводить кількість оброблених паролів за секунду і перші три хеші у шістнадцятковому вигляді.

2. Базовий рівень. Створити консольну програму, яка читає файл облікових записів login;salt;hash і файл словника поширених паролів (шляхи вводить користувач) та перевіряє, чи використовує хтось пароль зі словника. Перевірка виконується Parallel.ForEach за обліковими записами, прогрес виводиться щосекунди, а натискання Esc скасовує перевірку через CancellationToken у ParallelOptions. Програма виводить знайдені слабкі облікові записи (без пароля у відкритому вигляді), кількість перевірених записів і пропускну здатність.

3. Високий рівень. Створити консольний застосунок pwaudit, який приймає файл облікових записів, файл словника та опції --iterations, --threads 1,2,4,8,16, --timeout <с>, --report <файл> і --help. Програма перевіряє паролі паралельно, зупиняє перевірку облікового запису після першого збігу, скасовує роботу після таймауту, виводить таблицю «потоки – хешів за секунду – $S$ – $E$» і записує звіт аудиту (логін, результат, час перевірки) у CSV. Після скасування виводяться часткові результати й код завершення 3; помилки формату файлів – код 2.

Варіант 22. Парно-непарне сортування

1. Початковий рівень. Створити консольну програму, яка сортує масив з 20 000 випадкових цілих чисел парно-непарним сортуванням перестановками: кожна фаза порівнює пари за допомогою Parallel.For. Програма перевіряє впорядкованість, виводить кількість фаз, після яких масив фактично став відсортованим, і час порівняно з послідовною версією.

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

3. Високий рівень. Створити консольний застосунок oddeven, який приймає опції --sizes, --threads, --early-exit (зупинка, якщо у двох послідовних фазах не було перестановок), --csv <файл> і --help. Програма вимірює паралельне парно-непарне сортування та паралельне сортування злиттям для кожного розміру й кількості потоків, виводить таблицю «$n$ – $p$ – час парно-непарного – час злиттям – $S$ – $E$», знаходить розмір масиву, починаючи з якого паралельна версія швидша за послідовну, і записує результати в CSV. Неправильний результат – код завершення 2.

Варіант 23. Рівняння теплопровідності 1D

1. Початковий рівень. Створити консольну програму, яка розв’язує одновимірне рівняння теплопровідності явною схемою на стрижні з 1 000 000 вузлів (початкова температура 100 у середній десятій частині, 0 на решті, кінці – 0) протягом 1000 кроків часу. Новий шар обчислюється за допомогою Parallel.For з діапазонним розбивачем; програма виводить температуру в центрі та час.

2. Базовий рівень. Створити консольну програму, яка запитує кількість вузлів, кількість кроків і коефіцієнт $\alpha \cdot \mathrm{\Delta }t/\mathrm{\Delta }{x}^2$ (перевіряє умову стійкості: не більше 0,5), розв’язує рівняння теплопровідності явною схемою послідовно й паралельно для 1, 2, 4, 8, 16 потоків, перевіряє збіг кінцевих температур і виводить таблицю часу на крок, прискорення й ефективності.

3. Високий рівень. Створити консольний застосунок heat1d, який розв’язує одновимірне рівняння теплопровідності на стрижні явною схемою, обчислюючи новий шар паралельно діапазонами, з опціями --nodes, --steps, --r ($\alpha \cdot \mathrm{\Delta }t/\mathrm{\Delta }{x}^2$), --threads, --mode strong|weak, --range-size, --profile <файл> і --help. У режимі weak кількість вузлів зростає пропорційно кількості потоків. Програма записує профіль температури кожні 100 кроків у CSV, виводить таблицю масштабованості (для слабкої – $T_1/T_p$) і перевіряє збереження енергії для ізольованих кінців. Порушення умови стійкості ($r>0,5$) – повідомлення в потоці помилок і код 1.

Варіант 24. Ранжування пошукової видачі

1. Початковий рівень. Створити консольну програму, яка генерує 2 000 000 документів (ідентифікатор, кількість збігів ключових слів, рейтинг сторінки, дата; фіксоване зерно), обчислює оцінку релевантності кожного документа за формулою, заданою в програмі, і за допомогою PLINQ OrderByDescending виводить 10 найкращих документів і час запиту порівняно з LINQ.

2. Базовий рівень. Створити консольну програму, яка генерує документи (кількість вводить користувач) і виконує запит «20 найрелевантніших документів» чотирма способами: LINQ, PLINQ OrderByDescending(...).Take(20), PLINQ з AsOrdered і PLINQ з власною агрегацією «k найкращих» (Aggregate з локальними мінікупами PriorityQueue). Програма перевіряє однаковість результатів і виводить таблицю часу й прискорення.

3. Високий рівень. Створити консольний застосунок rank, який читає CSV-файл документів і файл запитів (по одному запиту на рядок) та приймає опції --top <k>, --method linq|orderby|topk, --ordered, --threads і --help. Для кожного запиту програма обчислює релевантність за кількістю входжень слів запиту та рейтингом, повертає $k$ найкращих документів, записує результати в CSV і виводить таблицю «спосіб – потоки – запитів за секунду – $S$». Програма перевіряє, що AsOrdered і AsUnordered дають однакові множини результатів, і повідомляє, де порядок відрізняється при рівних оцінках.

Варіант 25. Паралельна редукція максимуму

1. Початковий рівень. Створити консольну програму, яка знаходить максимальний елемент масиву з 100 000 000 випадкових дійсних чисел (фіксоване зерно) і його індекс послідовно та за допомогою Parallel.For з локальним станом (пара «значення – індекс»), виводячи результати й час.

2. Базовий рівень. Створити консольну програму, яка запитує розмір масиву й кількість частин $p$ (степінь двійки), перевіряє введення та знаходить максимум трьома способами: деревом редукції (часткові максимуми частин, потім попарне об’єднання рівнями через Parallel.For), PLINQ Max і Aggregate з власною функцією об’єднання. Програма виводить максимум і індекс, кількість рівнів дерева, час і прискорення кожного способу та перевіряє, що при рівних значеннях обирається найменший індекс.

3. Високий рівень. Створити консольний застосунок reduce, який приймає опції --size, --op max|min|sum|argmax|minmax, --parts 1,2,4,…,256, --threads і --help та виконує узагальнену паралельну редукцію деревом (операція задається делегатом з перевіркою нейтрального елемента). Програма перевіряє асоціативність операції на випадкових трійках, виводить попередження для неасоціативної операції (наприклад, avg двох чисел) і показує, як результат змінюється від кількості частин. Таблиця «операція – частини – час – $S$» записується в CSV; невідома операція – код 1.

Варіант 26. Перцептрон на наборі даних

1. Початковий рівень. Створити консольну програму, яка генерує 1 000 000 лінійно роздільних точок у 10-вимірному просторі (фіксоване зерно) і навчає перцептрон пакетним градієнтним спуском протягом 20 епох, обчислюючи градієнт за всіма точками за допомогою Parallel.For з локальними векторами градієнта. Програма виводить точність після кожної п’ятої епохи та час на епоху.

2. Базовий рівень. Створити консольну програму, яка запитує кількість точок, кількість ознак, швидкість навчання й кількість епох, перевіряє введення і навчає логістичну регресію пакетним градієнтним спуском послідовно та паралельно (Parallel.ForEach з Partitioner.Create і локальними градієнтами). Програма перевіряє, що ваги обох версій після навчання збігаються з точністю ${10}^{-9}$, і виводить функцію втрат за епохами, точність, час на епоху й прискорення.

3. Високий рівень. Створити консольний застосунок perceptron, який читає набір даних з CSV (ознаки й мітка 0/1) і приймає опції --epochs, --lr, --test-split <частка>, --threads, --batch full|mini <розмір>, --model <файл> і --help. Програма нормалізує ознаки паралельно, навчає модель з паралельним обчисленням градієнта, виводить таблицю «епоха – втрати – точність на навчальній і тестовій вибірках – час», зберігає ваги у файл і будує таблицю прискорення для 1, 2, 4, 8, 16 потоків. Некоректний формат CSV – повідомлення з номером рядка й код завершення 2.

Варіант 27. BFS на великому графі

1. Початковий рівень. Створити консольну програму, яка генерує неорієнтований граф з 2 000 000 вершин і середнім степенем 8 (фіксоване зерно) і виконує рівневий пошук у ширину від вершини 0, обробляючи вершини поточного рівня через Parallel.ForEach. Програма виводить кількість вершин на кожному рівні, кількість досяжних вершин і час.

2. Базовий рівень. Створити консольну програму, яка запитує кількість вершин і середній степінь графа, перевіряє введення та виконує послідовний і паралельний рівневий BFS, у якому вершини наступного рівня позначаються атомарно (Interlocked.CompareExchange для масиву відстаней) і збираються в локальні списки потоків. Програма перевіряє, що відстані обох версій збігаються, і виводить кількість рівнів, розміри рівнів, час і прискорення.

3. Високий рівень. Створити консольний застосунок pbfs, який читає граф зі списку ребер (u v) або генерує його (--random <n> <degree>), приймає опції --source, --threads, --direction top-down|bottom-up|hybrid і --help. Програма виконує паралельний BFS обраним способом (у bottom-up непройдені вершини шукають батька на поточному рівні), виводить таблицю «рівень – вершин – спосіб – час рівня», загальний час, прискорення для 1, 2, 4, 8, 16 потоків і перевіряє відстані з послідовним BFS. Некоректна вершина-джерело або некоректний файл – повідомлення в потоці помилок і код завершення 2.

Варіант 28. Мозаїка з фотографій

1. Початковий рівень. Створити консольну програму, яка генерує 5000 «плиток» (випадкові середні кольори RGB, фіксоване зерно) і цільове зображення 400×300 блоків, для кожного блоку знаходить плитку з найближчим середнім кольором (евклідова відстань) за допомогою Parallel.For за рядками блоків і виводить кількість різних використаних плиток та час.

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

3. Високий рівень. Створити консольний застосунок mosaic, який приймає аргументи target.ppm, tiles/, output.ppm та опції --block <розмір>, --metric rgb|lab, --no-repeat <радіус>, --threads, --cache <файл> і --help. Програма кешує середні кольори плиток у файлі CSV (повторний запуск не перечитує незмінені плитки), паралельно підбирає плитки, виводить таблицю часу етапів і частку послідовної частини програми, а також прогноз прискорення за законом Амдала порівняно з виміряним. Помилки читання окремих плиток пропускаються з повідомленням; відсутнє цільове зображення – код 2.

Варіант 29. Sample sort

1. Початковий рівень. Створити консольну програму, яка сортує масив з 10 000 000 випадкових цілих чисел алгоритмом sample sort для 8 кошиків: вибірка з 800 елементів, 7 роздільників, паралельний розподіл елементів у кошики з локальними списками, паралельне сортування кошиків і з’єднання. Програма перевіряє впорядкованість і виводить розміри кошиків та час порівняно з Array.Sort.

2. Базовий рівень. Створити консольну програму, яка запитує розмір масиву, кількість кошиків (від 2 до 64) і коефіцієнт вибірки (елементів вибірки на кошик), перевіряє введення та сортує sample sort масиви з рівномірним і нормальним розподілом значень. Програма виводить для кожного розподілу мінімальний, максимальний і середній розмір кошика, коефіцієнт дисбалансу (максимум / середнє), час, прискорення відносно Array.Sort і перевіряє правильність сортування.

3. Високий рівень. Створити консольний застосунок samplesort, який приймає опції --size, --buckets 2,4,8,16,32, --oversampling 1,4,16,64, --distribution uniform|normal|zipf|sorted, --threads, --csv <файл> і --help. Розподіл у кошики виконується у два проходи: паралельний підрахунок розмірів кошиків і префіксна сума зміщень, потім паралельний запис елементів без блокувань. Програма виводить таблицю «розподіл – кошики – коефіцієнт вибірки – дисбаланс – час – $S$» і найкращі параметри для кожного розподілу, записує CSV і перевіряє результат з Array.Sort (розбіжність – код 2).

Варіант 30. Статистика трафіку метро

1. Початковий рівень. Створити консольну програму, яка генерує 50 000 000 записів проходів турнікетів (станція від 0 до 51, година від 5 до 23; фіксоване зерно) і за допомогою Parallel.ForEach з Partitioner.Create(0, n, rangeSize) і локальними масивами лічильників обчислює кількість проходів для кожної станції, виводячи п’ять найзавантаженіших станцій і час.

2. Базовий рівень. Створити консольну програму, яка генерує записи проходів (кількість вводить користувач) і будує таблицю «станція × година» паралельно з діапазонним розбивачем для розмірів діапазону 1, 1000, 100 000 і 10 000 000 та без розбивача (Parallel.For з локальним станом). Програма перевіряє збіг таблиць з послідовним підрахунком, виводить таблицю «розмір діапазону – кількість діапазонів – час – $S$» і найкращий розмір діапазону.

3. Високий рівень. Створити консольний застосунок metro, який читає CSV-файли журналів турнікетів (timestamp,station,card,direction) і приймає опції --from, --to, --range-sizes, --threads, --report hourly|daily|peak, --out <файл> і --help. Програма паралельно обчислює пасажиропотік за станціями та годинами, години пік для кожної станції й кількість унікальних карток за день, шукає оптимальний розмір діапазону для 1, 2, 4, 8, 16 потоків, виводить таблицю часу й записує звіт у CSV. Некоректні рядки підраховуються й виводяться в потік помилок (перші 10); помилки аргументів – код 1, відсутні файли – код 2.

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

1. Опрацювати теоретичні відомості та приклади розв’язання завдань.
2. Для свого варіанта визначити, які дані діляться на частини, чи незалежні ітерації, які результати потребують редукції та яка операція їх об’єднує (асоціативність, комутативність).
3. Створити в JetBrains Rider консольний проєкт; реалізувати послідовну версію, паралельну (Parallel, Partitioner або PLINQ) і перевірку збігу результатів.
4. Виміряти час у конфігурації Release (прогрівання, медіана запусків) для 1, 2, 4, 8 і 16 потоків, обчислити прискорення й ефективність.
5. Записати результати в CSV, побудувати графік прискорення й пояснити відхилення від ідеального.
6. Продемонструвати роботу програми, пояснити код, таблицю і графік, відповісти на питання.