Зміст пояснювальної записки

Зміст пояснювальної записки 1

Постановка задачі 3

Організаційно-інформаційна сутність задачі [1] 3

Математична модель задачі [1] 3

Вхідні дані 4

Вихідні дані 4

Опис методів розв’язання задачі 4

Метод гілок та границь 4

Алгоритм гілок і границь [1] 5

Зображення даних в оперативній пам’яті [2] 5

Опис алгоритму програмного модуля [2] 5

Оцінка складності алгоритму 6

Метод решета [2] 6

Алгоритм решета [2] 6

Зображення даних в оперативній пам’яті [2] 6

Опис алгоритму програмного модуля [2] 6

Оцінка складності алгоритму 7

Опис програми 7

Методи та засоби розробки програми 7

Сценарій роботи програми 7

Функціональна структура програми 8

Специфікація модулів 8

Специфікація функцій 8

Схема взаємодій функцій програми 11

Технологія створення програми 12

Застосування алгоритму для прикладних задач 12

Задача комівояжера 12

Умова задач[1] 12

Вхідні та вихідні тести 13

Опис алгоритму методу[2] 13

Алгоритм програми 14

Відеокопії екрана 17

Аналіз достовірності результатів 18

Задача “Бики та корови ” 18

Умова задачі [2] 18

Вхідні та вихідні тести 19

Опис алгоритму методу 19

Алгоритм програми 20

Відеокопії екрана 21

Аналіз достовірності результатів 22

Решето Ератосфена 22

Умова задачі [2] 22

Вхідні та вихідні тести 22

Опис алгоритму методу 23

Алгоритм програми 23

Відеокопії екрана 23

Аналіз достовірності результатів 24

Пошук простих чисел 24

Умова задачі [2] 24

Вхідні та вихідні тести 24

Опис алгоритму методу 24

Алгоритм програми 24

Відеокопії екрана 25

Аналіз достовірності результатів 25

Порадник користувача 25

Область використання, рівень підготовки користувача. 25

Рекомендації по інсталяції програми 25

Аварійні ситуації під час роботи програми 26

Технологія користування програмою 26

Висновок. 26

Список використаної літератури. 26

Додаток 1 27

CD та опис його змісту 27

Постановка задачі Організаційно-інформаційна сутність задачі [1]

В основі комбінаторних методів лежить перебір можливих варіантів розв’язків поставленої задачі. Кожен з них характеризується певною послідовністю перебору варіантів та правилами виключення, що дають змогу ще в процесі розв’язування задачі виявити неоптимальні варіанти без попередньої їх перевірки. Відносна ефективність різних методів залежить від того, наскільки кожен з них уможливлює скорочення необхідного процесу перебору варіантів у результаті застосування правила виключення.

Метод гілок і границь дає змогу серед елементів деякої множини можливих розв’язків задачі знайти найліпший розв’язок за умови, що цю множину можна розділити на такі підмножини, які не перетинаються, і для будь-якої з них можна визначити деяку оцінку найліпшого( найоптимальнішого) можливого розв’язку. Тобто має бути можливість визначити «оптимальність» розв’язку, краще якої не можна досягти,якщо шукати розв’язок тільки у межах вибраної підмножини.

Решето представляє собою метод комбінаторного програмування, який розглядає початкову множину і виключає всі елементи цієї множини, що не представляють інтересу. Він є логічним доповненням до процесу пошуку з поверненням (бектрекінг), який перераховує всі елементи множини рішень, що представляють інтерес.

Можлива постановка наступних пошукових задач:

• Знайти всі найоптимальніші розв’язки або з’ясувати відсутність їх.

• Знайти хоча б один оптимальний розв’язок або встановити його відсутність.

• Знайти всі повні розв’язки або з’ясувати відсутність їх.

• Знайти хоча б один повний розв’язок або встановити його відсутність.