Завдання

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

Варіанти

Варіант 1. Площа під кривою

1. Початковий рівень. Створити консольну програму, яка обчислює ${\int }_0^{1}4/(1+x^2)dx=\pi$ складеною формулою трапецій з 10 000 000 відрізків послідовно та за допомогою Parallel.For з локальними сумами і виводить обидва значення, похибки відносно Math.PI та час обох способів.

2. Базовий рівень. Створити консольну програму, яка запитує межі інтегрування $a<b$, формулу (прямокутники, трапеції або Сімпсон) і точність $ϵ$, перевіряє введення та обчислює ${\int }_a^b{e}^{-x^2}dx$ паралельно, подвоюючи кількість відрізків, доки оцінка похибки за правилом Рунге не стане меншою за $ϵ$. Програма виводить таблицю «$n$ – значення – оцінка Рунге – час» і уточнене значення.

3. Високий рівень. Створити консольний застосунок integrate, який приймає опції --function sin|exp|poly, --from, --to, --eps, --rule mid|trap|simpson, --threads 1,2,4,8,16 і --help. Для кожної кількості потоків програма обчислює інтеграл з контролем похибки за правилом Рунге, виводить таблицю «потоки – час – $S$ – $E$» і записує її у файл CSV; для функцій з відомою первісною виводить справжню похибку. Помилки аргументів виводяться в потік помилок з кодом завершення 1, недосяжна точність (понад $2^{30}$ відрізків) – з кодом 2.

Варіант 2. Адаптивне інтегрування

1. Початковий рівень. Створити консольну програму, яка обчислює ${\int }_0^1\sqrt{x}dx=2/3$ рекурсивним адаптивним методом Сімпсона з точністю ${10}^{-10}$ послідовно та з Parallel.Invoke для двох половин відрізка до глибини 8 і виводить обидва значення, похибки, кількість обчислень функції та час.

2. Базовий рівень. Створити консольну програму, яка запитує точність (від ${10}^{-4}$ до ${10}^{-12}$) і поріг глибини для задач (від 0 до 20), перевіряє введення та обчислює ${\int }_0^{10}\sin (x^2)dx$ адаптивним методом Сімпсона послідовно й рекурсивними задачами. Програма виводить значення, кількість задач, кількість відрізків, час і прискорення, а також попередження, якщо задач менше за кількість логічних процесорів.

3. Високий рівень. Створити консольний застосунок adaptive, який порівнює для трьох функцій з особливостями ($1/\sqrt{x}$ на $[{10}^{-8};1]$, $x\sin (1/x)$ на $[0,001;1]$, $2x\cos x^2$ на $[0;100]$) статичне розбиття на $p$ частин, розбиття на $64p$ частин з Parallel.For і рекурсивні задачі з порогами глибини 4, 8, 12, 16. Опції: --eps, --threads, --csv <файл>, --help. Програма виводить таблицю «функція – спосіб – час – $S$ – max/середній час частини» і записує її в CSV; неправильні опції – повідомлення в потік помилок і код 1.

Варіант 3. Кратний інтеграл

1. Початковий рівень. Створити консольну програму, яка обчислює подвійний інтеграл ${\int }_0^1{\int }_0^1(x^2+y^2)dxdy=2/3$ формулою середніх точок на сітці $4000\times 4000$ послідовно та з Parallel.For за рядками сітки і виводить значення, похибку та час обох способів.

2. Базовий рівень. Створити консольну програму, яка запитує прямокутник $[a;b]\times [c;d]$ і кількість вузлів за кожною віссю, перевіряє введення та обчислює $\iint e^{-(x^2+y^2)}dxdy$ двовимірною формулою Сімпсона трьома розподілами: смуги рядків, смуги стовпців і блоки $4\times 4$. Програма виводить таблицю «розподіл – значення – час – $S$» і оцінку похибки за правилом Рунге.

3. Високий рівень. Створити консольний застосунок double-integral, який приймає функцію з переліку (--function gauss|poly|trig), область, кількість вузлів, опцію --layout rows|cols|blocks, --threads 1,2,4,8,16 і --help. Програма подвоює сітку до досягнення точності --eps за правилом Рунге, для кожної кількості потоків виводить час, прискорення, ефективність і записує результати в CSV. Для області поза допустимими межами або непарної кількості вузлів – повідомлення в потік помилок і код завершення 1.

Варіант 4. Об’єм тіла методом Монте-Карло

1. Початковий рівень. Створити консольну програму, яка оцінює об’єм кулі радіуса 1 методом Монте-Карло за 100 000 000 випадкових точок куба $[-1;1{]}^3$: 64 блоки Parallel.For, кожен з власним Random із зерном 2026 + k. Програма виводить оцінку, точне значення $4\pi /3$, похибку та час.

2. Базовий рівень. Створити консольну програму, яка запитує кількість точок (від ${10}^4$ до ${10}^9$) і кількість блоків, перевіряє введення та оцінює об’єм перетину двох куль радіуса 1 з центрами $(0,0,0)$ і $(1,0,0)$ методом Монте-Карло з генератором на блок. Програма виводить оцінку, 95-відсотковий довірчий інтервал, точне значення $5\pi /12$ і перевіряє, що результат не залежить від кількості потоків.

3. Високий рівень. Створити консольний застосунок montecarlo, який оцінює об’єм тіла, заданого системою нерівностей з переліку (--body ball|torus|intersection), у просторі розмірності від 2 до 10 (--dim), з опціями --points, --blocks, --seed, --threads, --help. Програма виводить оцінку з довірчим інтервалом, таблицю часу й прискорення для різної кількості потоків і перевіряє відтворюваність двох запусків з однаковим зерном. Некоректні опції – потік помилок і код 1.

Варіант 5. Корені многочлена

1. Початковий рівень. Створити консольну програму, яка знаходить усі корені многочлена Чебишова $T_{200}(x)=\cos (200\arccos x)$ на $[-1;1]$: відокремлює їх на сітці з 100 000 відрізків (Parallel.For) і уточнює бісекцією паралельно. Програма виводить кількість коренів, перші 5 коренів і найбільшу різницю з точними значеннями $\cos (\pi (2k-1)/400)$.

2. Базовий рівень. Створити консольну програму, яка запитує коефіцієнти многочлена (до степеня 20) і відрізок, перевіряє введення, відокремлює корені на сітці із заданою користувачем кількістю відрізків і уточнює їх паралельною бісекцією до ${10}^{-12}$. Програма виводить таблицю «корінь – значення многочлена – ітерацій» і попереджає, якщо на відрізку зі зміною знака може бути кілька коренів.

3. Високий рівень. Створити консольний застосунок roots, який читає многочлен з файлу (коефіцієнти через пробіл), приймає опції --from, --to, --segments, --method bisect|psection|newton, --threads і --help. Метод psection обчислює многочлен одночасно в $p$ точках відрізка на кожній ітерації. Програма виводить корені, кількість обчислень многочлена, час кожного методу й прискорення; повторює пошук з удвічі меншим кроком і повідомляє про знайдені нові корені. Помилки файлу – код 2, опцій – код 1.

Варіант 6. Басейни методу Ньютона

1. Початковий рівень. Створити консольну програму, яка для рівняння $z^3-1=0$ запускає метод Ньютона з кожної точки сітки $1000\times 1000$ на квадраті $[-2;2]\times [-2;2]$ комплексної площини (System.Numerics.Complex, Parallel.For за рядками) і виводить, скільки точок збіглося до кожного з трьох коренів, а скільки – ні, та час послідовної й паралельної версій.

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

3. Високий рівень. Створити консольний застосунок newton-basins, який приймає многочлен (--poly "1 0 0 -1"), область, розмір зображення, --schedule static|cyclic|dynamic, --threads і --help. Програма будує басейни притягання, записує зображення PGM, виводить таблицю «розподіл – час – $S$ – max/середній час потоку», бо точки поблизу меж басейнів потребують більше ітерацій. Некоректний многочлен – код 1, помилка запису файлу – код 2.

Варіант 7. Система нелінійних рівнянь

1. Початковий рівень. Створити консольну програму, яка розв’язує систему $x^2+y^2=4$, $e^x+y=1$ методом Ньютона з 10 000 початкових точок на квадраті $[-3;3{]}^2$ паралельно (Parallel.For) і виводить різні знайдені розв’язки (з точністю ${10}^{-9}$) та кількість точок, що збіглися до кожного.

2. Базовий рівень. Створити консольну програму, яка запитує розмірність $n$ (від 10 до 2000) системи $F_i(x)=3x_i-x_i^3/10-x_{i-1}-x_{i+1}-1=0$ ($x_0=x_{n+1}=0$), перевіряє введення і розв’язує її методом Ньютона, обчислюючи матрицю Якобі різницевими похідними паралельно за стовпцями. Програма виводить кількість ітерацій, нев’язку та час обчислення якобіана послідовно й паралельно.

3. Високий рівень. Створити консольний застосунок newton-system, який розв’язує систему з переліку (--system chain|broyden|trig) розмірності --n методом Ньютона з паралельним якобіаном (--jacobian analytic|numeric) і паралельним розв’язанням лінійної системи методом Гаусса. Опції --tol, --threads, --help. Програма виводить таблицю ітерацій (норма нев’язки, крок, час), підсумкове прискорення й повідомлення в потік помилок з кодом 2, якщо метод не збігся.

Варіант 8. Скалярний добуток і норми

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

2. Базовий рівень. Створити консольну програму, яка запитує довжину векторів, кількість потоків і розмір блоку, перевіряє введення та обчислює скалярний добуток, евклідову норму й максимум модулів блочним, циклічним і блочно-циклічним розподілами. Програма виводить таблицю «розподіл – час – $S$ – результат з 17 цифрами» і пояснює різницю в останніх цифрах.

3. Високий рівень. Створити консольний застосунок vecdist, який обчислює скалярний добуток двох випадкових векторів довжини --n блочним, циклічним і блочно-циклічним розподілами для --threads 1,2,4,8,16 і розмірів блоку --blocks 1,64,1024,65536, записує таблицю в CSV і окремо показує відтворюваність: 5 запусків недетермінованої редукції (lock у localFinally) і 5 запусків детермінованої. Для векторів, більших за кеш L3, програма обчислює досягнуту пропускну здатність у ГБ/с. Опція --help; помилки опцій – код 1.

Варіант 9. Множення матриці на вектор

1. Початковий рівень. Створити консольну програму, яка множить матрицю $4000\times 4000$ на вектор послідовно та горизонтальними смугами на 8 потоках (Parallel.For за номерами смуг), перевіряє збіг результатів і виводить час та прискорення.

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

3. Високий рівень. Створити консольний застосунок matvec, який множить випадкову матрицю $n\times n$ на вектор трьома паралельними схемами (смуги рядків, смуги стовпців із редукцією, шахова схема $r\times c$) для розмірів --sizes і кількостей потоків --threads. Програма вимірює пропускну здатність пам’яті окремим тестом, будує прогноз $S_p=T_1/max(T_1/p,8n^2/B)$, виводить таблицю «$n$ – схема – $p$ – прогноз – виміряне $S$» і записує її в CSV. Опція --help; помилки – код 1.

Варіант 10. Шахове множення матриць і алгоритм Фокса

1. Початковий рівень. Створити консольну програму, яка множить дві матриці $1024\times 1024$ шаховою схемою $2\times 2$ (4 задачі, кожна обчислює свій блок $C_{ij}$) і перевіряє результат порівнянням з послідовним множенням порядком ikj, виводячи час обох способів.

2. Базовий рівень. Створити консольну програму, яка запитує розмір матриць $n$ і розмір решітки $q$ ($n$ кратне $q$), перевіряє введення та множить матриці алгоритмом Фокса на $q^2$ окремих потоках з Barrier: розсилка блока $A_{ik}$ рядком решітки (спільний буфер рядка), множення, зсув блоків $B$ угору. Програма виводить час, прискорення та найбільшу різницю з послідовним множенням.

3. Високий рівень. Створити консольний застосунок fox, який множить випадкові матриці алгоритмом Фокса (потоки решітки $q\times q$ з Barrier, розсилка блоків $A$ рядком, зсув блоків $B$) і шаховою схемою без копіювання для розмірів --sizes і решіток --grids 1,2,3,4. Програма рахує обсяг скопійованих даних (аналог обмінів) і час бар’єрів, виводить таблицю «$n$ – $q$ – час – $S$ – обміни, МБ – частка бар’єрів» і записує її в CSV. Розмір, не кратний $q$, – повідомлення в потік помилок і код 1.

Варіант 11. Алгоритм Кеннона

1. Початковий рівень. Створити консольну програму, яка для решітки $3\times 3$ блоків виводить, які блоки $A_{ik}$ і $B_{kj}$ опиняються в кожній клітинці після вирівнювання і на кожному з трьох кроків алгоритму Кеннона, і перевіряє, що кожна клітинка $(i,j)$ отримала всі $k=0,1,2$ рівно один раз.

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

3. Високий рівень. Створити консольний застосунок cannon, який множить дві випадкові матриці $n\times n$ алгоритмом Кеннона на решітці $q\times q$ окремих потоків (вирівнювання, зсуви копіюванням блоків сусідів, Barrier) з опціями --n, --grid, --kernel scalar|simd, --repeat і --help. Програма вимірює окремо час вирівнювання, множень, копіювань і бар’єрів кожного потоку та виводить таблицю часу за етапами, прогноз прискорення за моделлю й виміряне прискорення. Неправильні розміри – код 1, розбіжність з послідовним множенням понад ${10}^{-9}$ – повідомлення в потік помилок і код 3.

Варіант 12. Транспонування великої матриці

1. Початковий рівень. Створити консольну програму, яка транспонує матрицю double $8192\times 8192$ простим подвійним циклом і з Parallel.For за рядками, перевіряє результат і виводить час обох способів.

2. Базовий рівень. Створити консольну програму, яка запитує розмір матриці й перелік розмірів блоку, перевіряє введення та транспонує матрицю блоками паралельно за рядками блоків. Програма виводить таблицю «блок – час – ГБ/с» і позначає найкращий розмір блоку.

3. Високий рівень. Створити консольний застосунок transpose, який порівнює транспонування в нову матрицю й на місці (для квадратної), простий і блочний варіанти, статичний і динамічний розподіл блоків, для розмірів --sizes і потоків --threads. Програма записує таблицю з пропускною здатністю в CSV, перевіряє кожен результат і приймає --help. Непарні або завеликі розміри (понад доступну пам’ять) – повідомлення в потік помилок і код 1.

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

1. Початковий рівень. Створити консольну програму, яка розв’язує тридіагональну систему з 1 000 000 рівнянь ($4x_i-x_{i-1}-x_{i+1}=b_i$, $b$ з відомого розв’язку) методом спряжених градієнтів до нев’язки ${10}^{-10}$ з паралельними скалярними добутками і множенням матриці на вектор; програма виводить кількість ітерацій, похибку й час.

2. Базовий рівень. Створити консольну програму, яка запитує розмір $n$ тридіагональної системи $4x_i-x_{i-1}-x_{i+1}=b_i$ ($b$ з відомого розв’язку) і кількість потоків, перевіряє введення та розв’язує систему методом спряжених градієнтів з детермінованими паралельними скалярними добутками (64 фіксовані частини). Програма виводить кількість ітерацій, нев’язку, час і перевіряє, що кількість ітерацій однакова для 1, 2, 4, 8 і 16 потоків.

3. Високий рівень. Створити консольний застосунок cg, який розв’язує рівняння Пуассона на сітці $N\times N$ (--size) методом спряжених градієнтів з опціями --tol, --threads, --reduction deterministic|lock і --help. Програма виводить графік збіжності у файл CSV (ітерація, норма нев’язки), таблицю «потоки – ітерацій – час – $S$» і показує, чи змінюється кількість ітерацій між запусками для кожного способу редукції. Метод, що не збігся за $10N$ ітерацій, – код 2.

Варіант 14. Степеневий метод

1. Початковий рівень. Створити консольну програму, яка знаходить найбільше за модулем власне значення симетричної матриці $2000\times 2000$ з випадковими елементами степеневим методом (100 ітерацій) з паралельним множенням матриці на вектор і виводить оцінку власного значення та час.

2. Базовий рівень. Створити консольну програму, яка запитує розмір матриці й точність, перевіряє введення, генерує випадкову симетричну матрицю та знаходить її найбільше за модулем власне значення степеневим методом з нормуванням вектора до збіжності відношення Релея. Множення матриці на вектор і норма обчислюються паралельно; програма виводить таблицю «ітерація – оцінка – зміна» кожні 10 ітерацій і час.

3. Високий рівень. Створити консольний застосунок power, який читає матрицю з файлу CSV або генерує її (--random <n>), знаходить найбільше власне значення степеневим методом і найменше – методом зворотних ітерацій (з розв’язанням системи методом спряжених градієнтів для симетричних матриць), вимірює час із різною кількістю потоків (--threads) і приймає --help. Несиметрична матриця для зворотних ітерацій – попередження, помилки файлу – код 2.

Варіант 15. Інтерполяція сплайнами

1. Початковий рівень. Створити консольну програму, яка будує кубічний сплайн за 1000 вузлами функції $\sin x$ на $[0;2\pi ]$ і обчислює його значення в 20 000 000 точках послідовно та з Parallel.For, виводячи найбільшу похибку відносно Math.Sin і час.

2. Базовий рівень. Створити консольну програму, яка запитує кількість вузлів і кількість точок обчислення, перевіряє введення, будує природний кубічний сплайн (прогонка) для функції $1/(1+25x^2)$ на $[-1;1]$ і обчислює його паралельно з бінарним пошуком відрізка. Програма виводить похибку, час і прискорення.

3. Високий рівень. Створити консольний застосунок spline, який читає вузли з файлу CSV, приймає точки обчислення з іншого файлу або опції --grid a:b:n, обчислює сплайн паралельно з трьома розподілами точок (блочний, циклічний, відсортовані точки блоками) та порівнює їх час. Опції --threads, --output, --help; невпорядковані чи повторювані вузли – повідомлення в потік помилок і код 2.

Варіант 16. Метод найменших квадратів

1. Початковий рівень. Створити консольну програму, яка генерує 10 000 000 точок $y=2x+1$ з шумом і знаходить коефіцієнти прямої методом найменших квадратів, обчислюючи суми $\sum x$, $\sum y$, $\sum x^2$, $\sum xy$ паралельною редукцією; виводить коефіцієнти та час.

2. Базовий рівень. Створити консольну програму, яка запитує степінь многочлена (від 1 до 8) і кількість точок, перевіряє введення, генерує точки заданого многочлена з шумом і апроксимує їх многочленом методом найменших квадратів: паралельно обчислює матрицю нормальних рівнянь (суми $\sum x^{i+j}$ і $\sum x^{i}y$) з детермінованою редукцією та розв’язує систему методом Гаусса. Програма виводить коефіцієнти, середньоквадратичну похибку й час.

3. Високий рівень. Створити консольний застосунок lsq, який читає точки з файлу CSV (стовпці x, y), будує апроксимацію многочленом степеня --degree або сумою функцій з опції --basis sin,cos,exp, обчислює нормальні рівняння паралельно, виводить коефіцієнти, похибку, час для різної кількості потоків і записує таблицю залишків у CSV. Опція --help; погано обумовлена система – попередження, помилки файлу – код 2.

Варіант 17. Маятник для багатьох початкових умов

1. Початковий рівень. Створити консольну програму, яка розв’язує рівняння математичного маятника ${\theta }^{″}=-\sin \theta$ методом Рунге–Кутти 4-го порядку для 10 000 початкових кутів від 0,01 до 3,1 радіана і обчислює періоди коливань паралельно; виводить періоди для кількох кутів і час.

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

3. Високий рівень. Створити консольний застосунок pendulum-map, який для маятника з опором (${\theta }^{″}=-\sin \theta -\gamma {\theta }^{\prime }$, Рунге–Кутта 4) паралельно рахує кількість повних обертів до зупинки для кожної точки сітки (початковий кут, початкова швидкість) з опціями --gamma, --size, --step, --schedule block|cyclic|dynamic, --threads і --help. Програма записує карту в PGM і таблицю часу потоків (min/max/середній) у CSV. Крок, що дає помітну похибку енергії без опору (перевірка за $\gamma =0$), позначається попередженням у потоці помилок.

Варіант 18. Модель «хижак–жертва»

1. Початковий рівень. Створити консольну програму, яка розв’язує систему Лотки–Вольтерри $x^{\prime }=ax-bxy$, $y^{\prime }=-cy+dxy$ методом Рунге–Кутти 4-го порядку для 1000 значень параметра $a$ паралельно і виводить для кожного десятого значення найбільшу й найменшу чисельність жертв.

2. Базовий рівень. Створити консольну програму, яка запитує діапазони параметрів $a$ і $c$ та кількість значень кожного, перевіряє введення, розраховує модель «хижак–жертва» з логістичним обмеженням для всієї сітки параметрів паралельно й визначає, чи коливання затухають. Програма виводить таблицю стійкості (символи + і -) і час.

3. Високий рівень. Створити консольний застосунок lotka, який паралельно розв’язує модель «хижак–жертва» Лотки–Вольтерри ($x^{\prime }=ax-bxy$, $y^{\prime }=-cy+dxy$, Рунге–Кутта 4) для кожної точки сітки параметрів з діапазонів --a, --b, --c, --d, визначає період і амплітуду коливань кожної траєкторії, записує результати в CSV, порівнює статичний і динамічний розподіли задач та виводить таблицю часу. Опція --help; від’ємні параметри – код 1.

Варіант 19. Рух тіла з опором повітря

1. Початковий рівень. Створити консольну програму, яка для кутів кидка від 1° до 89° з кроком 1° паралельно інтегрує рух тіла з квадратичним опором повітря (Рунге–Кутта 4, $v_0=50$ м/с) і виводить кут з найбільшою дальністю та саму дальність.

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

3. Високий рівень. Створити консольний застосунок ballistics, який з опціями --v0, --drag, --target, --wind, --resolution і --help будує таблицю дальності для сітки (кут, швидкість) паралельно, знаходить мінімальну швидкість влучання для кожного кута, записує таблицю в CSV і виводить час послідовної й паралельної версій. Недосяжна ціль – повідомлення в потік помилок і код 2.

Варіант 20. Поширення епідемії SIR

1. Початковий рівень. Створити консольну програму, яка розв’язує модель SIR ($S^{\prime }=-\beta SI$, $I^{\prime }=\beta SI-\gamma I$, $R^{\prime }=\gamma I$) методом Рунге–Кутти 4-го порядку для 10 000 значень $\beta$ паралельно і виводить для кожного тисячного значення пік кількості хворих і день піку.

2. Базовий рівень. Створити консольну програму, яка запитує діапазони $\beta$ і $\gamma$ та кількість значень, перевіряє введення, розраховує модель SIR на сітці параметрів паралельно до кінця епідемії ($I<1$) і виводить таблицю тривалості епідемії. Оскільки тривалість різна, програма порівнює статичний і динамічний розподіли.

3. Високий рівень. Створити консольний застосунок sir, який виконує параметричний розрахунок моделі SEIR на сітці параметрів з опцій, з динамічним балансуванням (лічильник або Parallel.For), записує в CSV пік і тривалість для кожної пари параметрів, виводить час кожного розподілу й найгірші 10 сценаріїв. Опція --help; параметри поза $(0;5]$ – повідомлення в потік помилок і код 1.

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

1. Початковий рівень. Створити консольну програму, яка розв’язує рівняння теплопровідності $u_t=u_{xx}$ на стрижні з 1 000 000 вузлів явною схемою (1000 кроків за часом) послідовно та з Parallel.For за вузлами на кожному кроці і виводить температуру в середині стрижня та час.

2. Базовий рівень. Створити консольну програму, яка запитує кількість вузлів, кроків і потоків, перевіряє умову стійкості $\tau \le h^2/2$ і розв’язує рівняння теплопровідності явною схемою, де $p$ окремих потоків обробляють смуги стрижня й синхронізуються Barrier після кожного кроку. Програма виводить час і порівнює результат з послідовною версією.

3. Високий рівень. Створити консольний застосунок heat1d, який розв’язує рівняння теплопровідності з граничними умовами з опцій і порівнює три способи: новий Parallel.For на кожному кроці, окремі потоки з Barrier і окремі потоки, що синхронізуються раз на $k$ кроків з перекриттям (гало шириною $k$). Програма виводить таблицю «спосіб – $k$ – час – $S$», перевіряє результати й приймає --help; нестійкий крок – код 1.

Варіант 22. Обчислення π рядами

1. Початковий рівень. Створити консольну програму, яка обчислює $\pi$ за рядом Лейбніца $4\sum (-1{)}^k/(2k+1)$ з 1 000 000 000 членів послідовно та паралельно (діапазони Partitioner.Create і локальні суми) і виводить значення, похибку та час.

2. Базовий рівень. Створити консольну програму, яка запитує кількість членів ряду і кількість потоків, перевіряє введення та обчислює $\pi$ рядами Лейбніца, Ейлера (${\pi }^2/6=\sum 1/k^2$) і Нілаканти паралельно з детермінованою редукцією. Програма виводить таблицю «ряд – значення – похибка – час – $S$».

3. Високий рівень. Створити консольний застосунок pi-series, який паралельно обчислює $\pi$ рядами Лейбніца, Ейлера або Нілаканти (--series) з кількістю членів --terms і досліджує вплив порядку додавання на похибку (--order forward|backward|pairwise, а також підсумовування Кехена) і прискорення для --threads. Програма виводить і записує в CSV таблицю «ряд – порядок – значення – похибка – час – $S$»; опція --help; кількість членів понад ${10}^{12}$ – повідомлення в потік помилок і код 1.

Варіант 23. Числа Фібоначчі й DAG

1. Початковий рівень. Створити консольну програму, яка обчислює $F(n)$ рекурсивно ($F(n)=F(n-1)+F(n-2)$) для $n=32$ послідовно і з Parallel.Invoke для двох викликів до глибини 10, рахує кількість викликів (робота) і глибину рекурсії (проміжок) та виводить їх, паралелізм і час.

2. Базовий рівень. Створити консольну програму, яка запитує $n$ (від 20 до 40) і поріг глибини, перевіряє введення, обчислює рекурсивні числа Фібоначчі з Parallel.Invoke до порогу, виводить роботу $T_1$, проміжок $T_{\mathrm{\infty }}$, межу теореми Брента для $p=2,4,8,16$ і виміряне прискорення.

3. Високий рівень. Створити консольний застосунок dag, який читає граф задач з файлу (рядок – «ім’я тривалість залежності»), обчислює роботу, проміжок і критичний шлях, моделює жадібний планувальник для $p$ процесорів (--procs 1,2,4,8) і виводить діаграму Ганта текстом, а також виконує граф справжніми задачами TPL із Task.Delay. Цикли в графі – повідомлення в потік помилок і код 2.

Варіант 24. Редукційне дерево і PRAM

1. Початковий рівень. Створити консольну програму, яка моделює EREW PRAM для суми 16 чисел: на кожному кроці виводить, які процесори які комірки читають і записують, і перевіряє, що жодна комірка не читається двома процесорами одночасно.

2. Базовий рівень. Створити консольну програму, яка запитує кількість чисел $n$ (степінь 2), перевіряє введення і моделює на $n/2$ «процесорах» (Parallel.For на кожному кроці) пошук суми й максимуму деревом за ${\log }_{2}n$ кроків. Програма виводить кількість кроків, операцій і результат, а також перевіряє правило EREW.

3. Високий рівень. Створити консольний застосунок pram, який моделює програми для EREW, CREW і CRCW PRAM (сума, максимум за $O(1)$ на $n^2$ процесорах, розсилка значення) з опціями --model, --n, --trace і --help. Програма рахує кроки й операції, виявляє порушення правил доступу моделі та виводить їх у потік помилок; для порушень – код завершення 3.

Варіант 25. Суперкроки BSP

1. Початковий рівень. Створити консольну програму, яка на 4 окремих потоках з Barrier виконує 5 суперкроків BSP: кожен потік додає до свого значення отримане від лівого сусіда та надсилає результат правому; програма виводить стан після кожного суперкроку.

2. Базовий рівень. Створити консольну програму, яка запитує кількість процесорів $p$ і розмір масиву, перевіряє введення та обчислює префіксну суму BSP-програмою з трьох суперкроків (локальні суми, обмін сумами, корекція) на $p$ окремих потоках з Barrier. Програма виводить для кожного суперкроку $w$, $h$ і час.

3. Високий рівень. Створити консольний застосунок bsp, який надає класи «процесор» і «повідомлення» для BSP-програм на потоках (Send, Sync, отримані повідомлення), рахує $w$, $h$ і кількість бар’єрів і на цій основі реалізує сортування вибіркою (sample sort). Опції --p, --n, --g, --l, --help; програма порівнює прогноз $\sum (w+gh+l)$ з виміряним часом.

Варіант 26. Балансування навантаження

1. Початковий рівень. Створити консольну програму, яка перевіряє простоту чисел від 1 до 20 000 000 перебором дільників блочним розподілом на 8 потоків і динамічним лічильником Interlocked.Increment з порціями по 1000 чисел, виводячи кількість простих і час обох способів.

2. Базовий рівень. Створити консольну програму, яка запитує кількість задач і закон розподілу їх тривалості (рівномірна, зростаюча, випадкова), перевіряє введення та виконує задачі-обчислення блочним, циклічним і динамічним розподілами. Програма виводить таблицю «розподіл – час – $S$ – max/середній час потоку».

3. Високий рівень. Створити консольний застосунок balance, який порівнює блочний, циклічний розподіли, лічильник з порціями --chunk, «майстер–робітник» з каналом (System.Threading.Channels) і Parallel.For для задач з файлу (тривалість або параметр кожної задачі), записує час кожного потоку в CSV і виводить підсумкову таблицю. Опція --help; порожній файл – код 2.

Варіант 27. Грід-планувальник (імітація)

1. Початковий рівень. Створити консольну програму, яка моделює 3 організації (кластери з 16, 32 і 8 ядрами) і 200 завдань з випадковою кількістю ядер і тривалістю, розподіляє завдання жадібно на ресурс з найменшим очікуванням і виводить час завершення всіх завдань.

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

3. Високий рівень. Створити консольний застосунок gridsim, який моделює грід із ресурсами, віртуальними організаціями та політиками доступу з файлу JSON, порівнює стратегії брокера (--policy random|least-queue|best-fit) і виконує моделювання паралельно для кількох зерен генератора. Програма виводить таблицю «стратегія – середнє очікування – завантаження» і приймає --help; некоректний JSON – код 2.

Варіант 28. Добровільні обчислення (імітація)

1. Початковий рівень. Створити консольну програму, яка моделює сервер з 1000 робочими одиницями (перевірка простоти чисел з діапазону) і 8 клієнтів-потоків, що беруть одиниці з черги ConcurrentQueue, обчислюють і повертають результати; програма виводить кількість простих і внесок кожного клієнта.

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

3. Високий рівень. Створити консольний застосунок volunteer, який моделює сервер і клієнтів із відмовами (зникнення, повільність, хибні результати), дедлайнами й повторною видачею робочих одиниць, з опціями --clients, --units, --failure, --quorum, --deadline і --help. Програма виводить час завершення, частку зайвих обчислень і журнал подій у файл. Некоректні ймовірності – код 1.

Варіант 29. Прогноз прискорення

1. Початковий рівень. Створити консольну програму, яка множить матриці $1024\times 1024$ смугами на 1, 2, 4 і 8 потоках, обчислює прогноз $S_p=min(p,8)$ і виводить таблицю «потоки – час – виміряне $S$ – прогноз $S$».

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

3. Високий рівень. Створити консольний застосунок predict, який для множення матриць (смуги, шахова схема, Кеннон) вимірює параметри моделі (операція, копіювання блоку, бар’єр, пропускна здатність пам’яті), будує прогноз для розмірів --sizes і потоків --threads, порівнює його з вимірюванням, обчислює метрику Карпа–Флатта й записує таблицю в CSV. Опція --help; розбіжність прогнозу понад 50 % позначається попередженням.

Варіант 30. Ізоефективність

1. Початковий рівень. Створити консольну програму, яка обчислює суму масиву з $n$ чисел на $p$ потоках для $n={10}^5,{10}^6,{10}^7$ і $p=2,4,8$ і виводить таблицю ефективності $E=T_1/(p{T}_p)$.

2. Базовий рівень. Створити консольну програму, яка запитує цільову ефективність (від 0,3 до 0,9), перевіряє введення і для $p=2,4,8,16$ подвоює розмір задачі (множення матриці на вектор) доти, доки виміряна ефективність не досягне цілі. Програма виводить таблицю «$p$ – мінімальний $n$ – $E$».

3. Високий рівень. Створити консольний застосунок isoefficiency, який експериментально визначає функцію ізоефективності для трьох алгоритмів (сума, множення матриці на вектор смугами, множення матриць) бінарним пошуком розміру задачі, записує точки $(p,W)$ у CSV, підбирає показник степеня $W{p}^{\alpha }$ методом найменших квадратів у логарифмах і порівнює його з теоретичним. Опції --target, --threads, --help.

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

1. Опрацювати теоретичні відомості та приклади розв’язання завдань.
2. Для свого варіанта виконати аналіз за методологією PCAM: визначити примітивні задачі, обміни між ними, спосіб укрупнення та розподіл між потоками (статичний чи динамічний); оцінити роботу й проміжок алгоритму.
3. Створити в JetBrains Rider консольний проєкт .NET 10; реалізувати послідовну версію, паралельну версію та перевірку результату з еталоном (для дійсних чисел – з допуском, для чисельних методів – з точним розв’язком або оцінкою похибки за правилом Рунге).
4. Скласти модель часу виконання, виміряти її параметри (час однієї операції, синхронізації, пропускну здатність пам’яті) і обчислити прогноз прискорення.
5. Виміряти час у конфігурації Release (прогрівання, медіана щонайменше 5 запусків) для 1, 2, 4, 8 і 16 потоків, записати таблицю в CSV і побудувати графік прогнозованого й виміряного прискорення в Excel або LibreOffice Calc; пояснити розбіжності.
6. Продемонструвати роботу програми, пояснити код, модель і результати вимірювань, відповісти на контрольні питання.