3__Вимоги_до_Розділу_3_2026 (2)

1. РЕКОМЕНДАЦії щодо виконання Розділу 3 КуРсової роботи

1
КР з Дослідженн операцій в ІУС.
НТУУ КПІ, ФІОТ, кафедра ІСТ. Олена Жданова

2. Розділ 3

2
Планування експериментів

3.

Робота над розділами 3 -4 та їх завантаження в систему
MOODLE дозволяються виключно після офіційного
зарахування розділу 2: для цього необхідно отримати
підтвердження викладача у вигляді
повідомлення/коментаря з формулюванням «Переходимо
до наступних розділів»;
До виконання зазначених умов матеріали розділів 3-4 в
MOODLE не приймаються до розгляду.
3

4.

Складання
Змістовна
постановк
а
оптимізаці
йної задачі
Змістовні
постановки
задач з
конкретними
значеннями
параметрів
Розробка
Планування експериментів
Програмна
реалізація
Жадібний
алгоритм
Жадібний
алгоритм
Експ 1
Алгоритм
А
Експ 2
Матема
тична
модель
Експ 1
Алгоритм
А
Експ 3,4
Експ 2
Експ 3,4
Результати
дослідження
алгоритмів

5. Що впливає на ефективність алгоритму

На ефективність алгоритму — а саме на час його роботи та
точність (ступінь наближеності до оптимального розв'язку)
— впливають такі чинники:
значення параметрів задачі;
умова завершення алгоритму;
значення параметрів самого алгоритму (далі – специфічні
параметри).
5

6. В розділі 3:

1) визначаються параметри досліджуваної задачі;
2) розробляється алгоритм генератора індивідуальних задач;
3) або визначаються специфічні параметри наближеного
алгоритму та обираються ті, вплив яких буде досліджено;
або (у випадку відсутності специфічних параметрів) —
обираються параметри задачі, вплив яких буде досліджено;
4) складаються плани експериментів.
6

7. В розділі 3:

Деякі розроблені в процесі курсового проєктування наближені алгоритми можуть
не мати параметрів.
У цьому випадку слід провести експеримент з аналізу впливу параметрів задачі.
3) або визначаються специфічні параметри наближеного
алгоритму та обираються ті, вплив яких буде досліджено;
або (у випадку відсутності специфічних параметрів) —
обираються параметри задачі, вплив яких буде досліджено;
7

8.

Орієнтовний набір експериментів для команди
Оскільки теми робіт,
задачі та використані
методи можуть суттєво
відрізнятися, встановити
один універсальний план
експериментів для всіх
неможливо. Тому
структура
експериментальної
частини може бути різною
залежно від змісту
роботи.
8

9.

Орієнтовний набір експериментів для команди
Якщо алгоритм не має параметрів або не дозволяє
змінювати умову завершення, потрібно провести інші
доречні експерименти. Їх потрібно заздалегідь узгодити з
керівником.
Основна вимога — у роботі має бути виконано щонайменше
чотири експерименти.
9

10.

Зміст розділу 3 ВАРІАНТ 1
3 ПЛАНУВАННЯ ЕКСПЕРИМЕНТІВ
3.1 Параметри задачі
3.2 Генератор індивідуальних задач
3.3 Планування дослідження наближеного алгоритму <назва>
3.3.1 Параметри алгоритму <назва>
3.3.2 План з визначення параметра умови завершення алгоритму
3.3.3 План дослідження впливу специфічних параметрів алгоритму <назва>
3.3.4 План визначення впливу розмірності задачі на точність та час роботи
алгоритмів
10

11.

Зміст розділу 3 ВАРІАНТ 2
3 ПЛАНУВАННЯ ЕКСПЕРИМЕНТІВ
3.1 Параметри задачі
3.2 Генератор індивідуальних задач
3.3 Планування дослідження наближеного алгоритму <назва>
3.3.1 Параметри задачі, вплив яких буде досліджуватись
3.3.2 План з визначення параметра умови завершення алгоритму
3.3.3 План дослідження впливу параметрів задачі на ефективність алгоритму
3.3.4 План визначення впливу розмірності задачі на точність та час роботи
алгоритмів
11

12. 3.1 параметри задач

3.1 ПАРАМЕТРИ ЗАДАЧ
12

13.

3.1 Параметри задач
Робота алгоритму залежить від вхідних даних.
Різні набори даних можуть по-різному впливати на швидкість
роботи алгоритму, точність результату та використання ресурсів.
Параметри задачі — це характеристики, які визначають
індивідуальний варіант задачі.
Саме вони дозволяють створювати різні тестові приклади для
дослідження алгоритму.
Отже, для аналізу алгоритму і порівняння його ефективності в
різних умовах потрібно виділити ознаки, за якими можна
класифікувати індивідуальні задачі.
13

14. Параметри задачі

3.1 Параметри задач
Параметри (вхідні дані) задачі діляться на дві групи:
параметри, що визначають розмірність задачі (наприклад,
кількість об’єктів, пунктів, замовників, виконавців, вершин
графа та ребер тощо);
умовно-постійні параметри задачі (наприклад, значення
елементів матриць і векторів, структура графа, структура
обмежень тощо).
14

15.

3.1 Параметри задач
ІЗ
відрізняються
Розмірностями
Має бути проведений
обов’язковий експеримент (2 в 1),
метою якого є оцінка впливу
розмірності задачі на час та
точність розроблених алгоритмів
Цей експеримент проводиться
тоді, коли алгоритм
1) не має умови останову
(кількість ітерацій …)
2) не має параметрів
Умовнопостійними
параметрами
Може бути проведений експеримент,
метою якого є виявлення того, як
впливають особливості параметрів
задачі на результат роботи алгоритму
15

16. Приклад 1 Задача складання розкладу Pm||T_max→min

16
Умовно-постійні параметри
(УПП) індивідуальних задач (ІЗ)
ІЗ це не «задача Васі Пупкіна», а задача, у якої усі вхідні дані відомі (екземпляр задачі).

17. Pm||T_max→min

3.1 Класифікація індивідуальних задач
① Математична модель
Дано
розмірність