Вступ

Теорія алгоритмів і практика їхньої побудови та аналізу посідають важливе місце в освіті фахівців з комп'ютерних інтелектуальних систем і мереж (спеціальність 7.091501). У оволодінні цією теорією і виробленні алгоритмічного мислення велике значення надається курсовому проектуванню. Дані методичні вказівки призначені для надання допомоги студентам при вирішенні ключових питань теорії і практики проектування — розробці ефективних алгоритмів.

Завдання вибирається зі списку алгоритмів покриття, алгоритмів на графах і сортування. Для полегшення процесу виконання курсової роботи наводяться рекомендації і приклади побудови.

1. Зміст і порядок виконання курсової роботи

1.1. Загальні положення

Курсова робота складається з пояснювальної записки (20 – 25 с.) і графічних матеріалів (один, два аркуші креслярського паперу формату А1). Пояснювальна записка і графічні матеріали повинні бути виконані відповідно до вимог ДСТУ й ЄСПД [1-3] .

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

Пояснювальна записка починається титульним аркушем. В анотації наводяться мета і короткий зміст курсової роботи з вказівкою заданих алгоритмів, а також висновків щодо особливостей, ефективності, можливості й галузі їхнього застосування. Розділ "ЗМІСТ" оформлюється звичайним чином [1] з перерахуванням конкретних розділів, підрозділів і пунктів із зазначенням їхнього початкового номера сторінки.

У розділі "ВСТУП" має бути відбито:

• актуальність теми;

• що таке алгоритм, його призначення, види алгоритмів;

• ефективність алгоритмів і методи її досягнення;

• короткий зміст курсової роботи.

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

1.1. Задача про покриття.

1.2. Побудова алгоритму покриття.

1.3. Приклад(и) розв’язання задачі за допомогою алгоритму.

1.4. Ефективність алгоритму.

У розділі "ВИСНОВОК" повинні бути відзначені:

• числові дані, які характеризують результати курсової роботи;

• висновки про ефективність розроблених алгоритмів;

• пропозиції по удосконалюванню алгоритмів.

У розділі "СПИСОК ЛІТЕРАТУРИ" наводяться тільки ті джерела, які були використані при розробці, на них повинні бути посилання в тексті. Список повинен оформлятися за ДСТУ [1].

Кожен розділ необхідно починати з нової сторінки. Нумеруються розділи арабськими числами; розділи "АНОТАЦІЯ", "ЗМІСТ", "ВСТУП", "ВИСНОВОК" і "СПИСОК ЛІТЕРАТУРИ" не нумеруються.

На графічних аркушах подаються схеми алгоритмів, основна і її модулі (підпрограми). Вони виконуються відповідно до [2]. Аркуш повинен мати свій основний напис (штамп).

Пояснювальна записка і графічні аркуші повинні бути зброшуровані.

Захист курсової роботи здійснюється перед комісією, яка призначається завідувачем кафедри. Перед захистом (не менше ніж за 3 дні) робота повинна бути здана на перевірку своєму керівникові. Захист включає доповідь (5 хв.), у якій студент викладає завдання, способи й особливості розв’язання задач побудови алгоритмів (включаючи використовувані структури даних), характеристику результатів розв’язання, а також відповіді на питання комісії з всієї області, які відносяться до курсової роботи.

1.2. Вибір варіанта завдання

Алгоритми вибираються з таких списків:

Алгоритми покриття

А1 – граничний перебір за увігнутою множиною;

А2 – побудова одного найкоротшого покриття;

A3 – побудова одного мінімального покриття;

А4 – за методом "мінімальний стовпець – максимальний рядок".

Алгоритми на графах

B1 – пошук найкоротшого шляху;

B2 – пошук найдовшого шляху;

В3 – побудова мінімального остова;

В4 – побудова системи незалежних циклів;

В5 – пошук компонентів зв’язності;

В6 – найкоротше розфарбування.

Алгоритми сортування

С1 – сортування простими включеннями;

С2 – сортування бінарними включеннями;

С3 – сортування простим вибором;

С4 – сортування простим обміном (бульбашкове сортування);

С5 - шейкер-сортування.

В основі вибору індивідуального варіанта завдання лежить процедура визначення цілочислової остачі від ділення виразу Y, утвореного сумою номера студента за журнальним списком і числом Х, отриманим множенням останньої цифри номера групи на 100. Наприклад, для групи АЕ-044 число Х = 4*100 = 400, для АЕ-045 — Х = 500 і т.д.

Після визначення значення виразу Y знаходиться остача від ділення для відповідного списку алгоритмів:

(Y mod 4) + 1 — алгоритми покриття;

(Y mod 6) + 1— алгоритми на графах;

(Y mod 5) + 1 — алгоритми сортування.

Наприклад, для студента групи АЕ-046, якій має 16-й номер за списком, вираз для визначення остачі від ділення буде визначений як сума Y = 6*100 + 16 = 616. Виходячи з цього, в якості алгоритму покриття буде виступати алгоритм Y = (616 mod 4) + 1 = 1, тобто алгоритм А1 – граничний перебір за увігнутою множиною. Як алгоритм на графах буде виступати Y = (616 mod 6) + 1 = 5 — алгоритм пошуку компонент зв’язності (В5), а як алгоритм сортування Y = (616 mod 5) + 1 = 2 — сортування бінарними включеннями (С2).