Алгоритми та структури даних

Анотація навчальної дисципліни

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

Основні результати навчання

В результаті вивчення дисципліни студент повинен знати:
моделі обчислювань (обробки даних); структури даних, що оброблюються, та способи їх відображення в ЕОМ; найпоширеніші алгоритми обробки даних та способи оцінювання їх трудомісткості.
В результаті вивчення дисципліни студент повинен вміти:
вирішувати задачі на дискретних структурах; зводити нестандартні задачі до стандартних; будувати алгоритми для специфічних задач; використовувати можливості операційних систем; використовувати можливості апаратного забезпечення; використовувати Інтернет – ресурси для рішення експериментальних і практичних завдань у галузі професійної діяльності.
Форми організації освітнього процесу та види навчальних занять

Л – лекційні заняття; ПР – практичне заняття; СРС – самостійна робота здобувача вищої освіти; РГР – розрахунково-графічна робота; К – консультації.

Тематика та види навчальних занять

1    тиждень

Л1. Поняття та класифікація алгоритмів обробки даних. Поняття обчислювальної складності алгоритмів і методи її оцінки. Основні класи алгоритмів.
ПР1. Рекурсивні алгоритми та оцінка їхньої складності.
СРС. К.

2    тиждень

Л2. Алгоритмічні стратегії. Комбінування декількох алгоритмічних стратегій. Ітераційні алгоритми. Рекурсивні алгоритми. Зворотні алгоритми. Стратегія гілок і границь (Branch and bound algorithms). Стратегія розподіляй і володарюй. Динамічне програмування. Стратегія жадності (Greedy algorithms). Стратегія грубої сили (Brute force algorithms). Використання евристики. 
СРС. К.

3    тиждень

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

4    тиждень

Л4. Різновиди списків та базові алгоритми роботи з ними. 
СРС. К.

5    тиждень

Л5. Нелінійні структури даних. Визначення дерева. Бінарне дерево. Подання дерев у пам’яті комп’ютера. Бінарні дерева: Ідеально збалансовані дерева. Дерева пошуку. Збалансовані АВЛ-дерева. Червоно-чорні дерева. 
ПР3. Нелінійні структури даних.
СРС. К.

6    тиждень

Л6. Основні алгоритми для роботи з бінарними деревам: побудова, пошук, вилучення та включення вузлів дерева. Базові рекурсивні алгоритми обходу вузлів дерева.
СРС. К.

7    тиждень

Л7. Автомати. 
ПР4. Синхронні та асинхронні автомати. 
СРС. К.

8    тиждень

Л8. Графи. Представлення графів у пам’яті комп’ютера. Алгоритми обходу графів.
МКР1. СРС. К.

9    тиждень

Л9.  Алгоритми сортування масивів. Алгоритми сортування: вставки, Shellsort, злиття (mergesort), Quick sort, Radix-sort. Оцінка складності алгоритмів сортування.
ПР5. Алгоритми сортування масивів.
СРС. К.

10    тиждень

Л10. Пірамідальне сортування, зовнішнє сортування.
СРС. К.

11    тиждень

Л11. Алгоритми пошуку в тексті. Brute Force, алгоритм Рабіна-Карпа сортування рядків, Кнут–Моріc–Пратта та інші.
ПР6. Алгоритми текстового пошуку.
СРС. К.

12    тиждень

Л12. Алгоритми пошуку. Послідовний пошук, бінарний пошук.
СРС. К.

13    тиждень

Л13. Поняття хешування. Хеш-таблиці. Колізії. Алгоритми хешування. Відкрите і закрите хешування.
ПР7. Хеш-таблиці.
СРС. К.

14    тиждень

Л14. Фундаментальні алгоритми на графах. Пошук найкоротшого шляху графа.
СРС. К.

15    тиждень

Л15. Алгоритми нечіткого пошуку в тексті. Відстань Левенштейна. 
ПР7. Алгоритми нечіткого пошуку в тексті.
МКР2. СРС. К.

Індивідуальна робота

Розрахунково-графічна робота (РГР) виконується згідно з графіком навчального процесу. Робота повинна підтвердити опанування студентом дисципліни та прищепити навички самостійної роботи над вирішенням професійних завдань з застосуванням інформаційно-довідникових ресурсів і знань.
РГР виконується окремо кожним студентом.
Етапи виконання РГР:
●    видача завдань (1-2 тиждень);
●    самостійна робота студентів (3-14 тиждень);
●    захист РГР (15 тиждень).

Процедура оцінювання

Система оцінювання рівня навчальних досягнень ґрунтується на принципах ЄКТС та є накопичувальною. Здобувачі протягом семестру готуються до лекційних та практичних занять, виконують 2 модульні контрольні роботи.
Для забезпечення оперативного контролю за успішністю та якістю рівня навчальних досягнень здобувачів вищої освіти дисципліна поділяється на два семестрові модулі.
Кожний модуль оцінюється у максимально можливі 50 балів.

Критерії оцінювання модульних контрольних робіт
    Кожна модульна контрольна робота виконується у письмовій формі. Максимальна оцінка за її бездоганне виконання становить 30 балів (1,2 кредитів).
    Кожна модульна контрольна робота складається з теоретичної частини та практичної частини.
    У першій модульній контрольній роботі кожна правильна відповідь оцінюється в 1 бал; кожна неправильна відповідь оцінюється в 0 балів.
    У другій модульній контрольній роботі кожна правильна відповідь оцінюється в 2 бали; кожна неправильна відповідь оцінюється в 0 балів.
Питання теоретичної частини може бути присвячено закріпленню знань лекційного матеріалу.
Питання практичної частини може бути присвячено закріпленню знань, отриманих на практичних заняттях.

Критерії оцінювання виконання накопичувальної частини дисципліни
Кожна накопичувальна частина дисципліни складається з виконання 3-х та 4-х практичних завдань у семестровому модулі №1 та семестровому модулі №2 відповідно.
Виконання та захист кожного практичного завдання оцінюється у семестровому модулі №1 – 6,6 бала (0,27 кредитів), у семестровому модулі №2 – 5 балів (0,2 кредитів).

Критерії оцінювання виконання та захисту практичного завдання
Оцінювання практичного завдання виконується виходячи з наступних вимог.
- Практичне завдання має бути повністю виконаним у письмовій формі.
- Практичне завдання має бути оформлено за правилами, що наведені у методичних вказівках [12].
- Студент повинен знати теоретичний матеріал, який пов’язаний з практичним завданням.
- Студент повинен захистити практичне завдання у строк.
За бездоганне виконання практичного завдання, що представлено у строк, студент отримує у першому і в другому семестрових модулях – 6,6 бала та 5 балів відповідно.
За виконання кожного практичного завдання бали можуть бути зняті:
-    6,6 бала (5 балів) – за повну відсутність виконання практичного завдання;
-    3 бали – рішення не вірне, але при цьому хід розв’язання та усі використані засади обрані вірно;
-    2 бали – практичне завдання захищене не в строк.
Таким чином, максимальний «внесок» практичних завдань в оцінку модульного контролю становить 20 балів (0,8 кредиту).

Максимальна оцінка, яку може отримати здобувач за всі виконані види робіт – 100 балів. 

Критерії оцінювання підсумкового контролю
Підсумковим контролем з дисципліни за 3 семестр є усний екзамен.
Іспит складається з двох частин: перевірки теоретичних знань у способі опитування та виконання практичного завдання. Мінімальна кількість балів, що зараховується як позитивний результат, дорівнює 60 (за 100-бальною системою). Бали розподіляються наступним чином: 60 балів – теоретична частина та 40 балів – практична.
Екзаменаційний білет містить 3 теоретичних питання рівної складності. 
За бездоганну відповідь на кожне питання студент отримує – 20 балів. При цьому відповідь вважається бездоганною, якщо студент не зробив жодної помилки та повністю виклав зміст питання. 
За кожне запитання знімається 20 балів, якщо була здійснена невірна відповідь або за відсутність відповіді; 1 бал знімається за виправлення відповіді у відповіді на запитання (за кожне виправлення).
Екзаменаційний білет містить 2 практичних питання рівної складності. За бездоганне виконання кожного завдання практичної частини студент отримує – 20 балів. 
Практична частина іспиту вважається виконаною бездоганно, якщо при наявності розв’язання приклада, при цьому усі дії виконані вірно, без помилок; всі записи, щодо розв’язання записані послідовно, зроблена перевірка (якщо потрібно). Крім цього усі малюнки, креслення та схеми виконані охайно, без помилок.
За виконання кожного питання практичної частини бали можуть бути зняті:
20 балів – за повну відсутність виконання питання практичної частини;
15 балів – рішення не отримане або не вірне, але при цьому хід розв’язання та усі використані засади обрані вірно;
10 балів – наведене правильне рішення, але при цьому є помилки у розв’язанні;
7 балів – наведене правильне рішення, але при цьому не повністю виконані обов’язкові пояснення;
5 балів – за неправильне тлумачення вихідних даних, що не порушило загалом правильного ходу розв’язання задачі;
3 балів – за допущену помилку, що не вплинула на відповідь та загальний хід розв’язання питання;
2 балів – за нераціональне розв’язання завдання при наявності докладних пояснень та вірного кінцевого результату.
Якщо студент відмовився від відповідати, то він отримує незадовільну оцінку.
Іспит враховується не складаним, якщо студент отримав незадовільну оцінку.

Максимальна оцінка за правильні відповіді на всі питання екзаменаційного білету становить 100 балів.

Семестровий модуль № 1

Л1 - Л8. Термін виконання – 1-8 тиждень. 
ПР1 - ПР3. Оцінка за виконання – 20 балів. Термін виконання – 1-8 тиждень.
МКР1. Модульна контрольна робота – 30 балів (8 тиждень). Перескладання можливе протягом 9–11 тижнів за розкладом консультацій.

Семестровий модуль № 2

Л9 - Л15. Термін виконання – 9-15 тиждень.
ПР4 - ПР7. Оцінка за виконання – 20 балів. Термін виконання – 9-15 тиждень. 
МКР2. Модульна контрольна робота – 30 балів (15 тиждень).

Умови допуску до підсумкового контролю

До екзамену допускаються здобувачі вищої освіти, які виконали всі види навчальних елементів навчальної дисципліни на не менш, ніж на 60%.

Екзамен відбувається за всіма тематичними (змістовними) модулями дисципліни.

Політика освітнього процесу

Здобувач зобов’язаний своєчасно та якісно виконувати всі отримані завдання; за необхідністю з метою з’ясування всіх не зрозумілих під час самостійної та індивідуальної роботи питань, відвідувати консультації викладача. Дотримуватись принципів академічної доброчесності.

Виконаний не свій варіант завдання здобувачем не оцінюється.

Робота, яка виконана після встановлених викладачем термінів, не приймається.

Відсутність здобувача на екзамені або на контрольній роботі відповідає оцінці «0». 
Складання/перескладання екзаменів – за встановленим деканатом розкладом.

Під час лекції здійснювати телефонні дзвінки забороняється.

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

Документи (файли), що додаються: Робоча програма навчальної дисципліни.

Література

Основна література
1.    Структури даних: практикум : навч.-метод. посібник [Електронне видання] / О. Г. Трофименко, Ю. В. Прокоп, О. Г. Янковський. – Одеса : Фенікс, 2022. – 115 с. ISBN 978-966-928-807-3
2.    Ільман В.М., Іванов О.П, Панік Л.О. Алгоритми, дані і структури: навч. посібн. : Дніпр. нац. ун-т залізн. трансп.ім. акад. В.Лазаряна. Дніпро: Дніпро 2019, 134 с. URL: http://eadnurt.diit.edu.ua/bitstream/123456789/11146/1/Ilman_et_al_2019.pdf.  
3.    Креневич А.П. Алгоритми і структури даних. Підручник. – К.: ВПЦ "Київський Університет", 2021. – 200 с. http://www.mechmat.univ.kiev.ua/wp-content/uploads/2021/09/pidruchnyk-al....
4.    Стратієнко Н. К. Алгоритми і структури даних: практикум : навч. посібник / Н. К. Стратієнко, М. Д. Годлевський, І. О. Бородіна ; Нац. техн. ун-т "Харків. політехн. ін-т". – Харків : НТУ "ХПІ", 2017. – 224 с. http://repository.kpi.kharkov.ua/bitstream/KhPI-Press/50239/1/Book_2017_....
5.    Ткачук В.М. Алгоритми i структура даних: Навчальний посiбник / В.М.Ткачук. – Iвано-Франкiвськ : Видавництво Прикарпатського нацiонального унiверситету iменi Василя Стефаника, 2016. – 286 с. URL : http://194.44.152.155/elib/local/2399.pdf.
6.    Bullinaria John. Lecture Notes for Data Structures and Algorithms // School of Computer Science, University of Birmingham, UK, 2018. URL : https://www.cs.bham.ac.uk/~jxb/DSA/dsa.pdf 
7.    Roughgarden T. Algorithms illuminated. Part 2. Graph Algorithms and Data Structure. San Francisco, 2018. URL : https://www.pdfdrive.com/algorithms-illuminated-part-2-graph-algorithms-... 

Методична література

1.    Методичні вказівки до практичних занять з дисципліни «Теорія алгоритмів» для студентів напрямку підготовки 6.050103 — Програмна інженерія / Укл.: О. М. Паулін, Н. О. Комлева. – Одеса: ОНПУ, 2016. – 15 с.
2.    Методичні вказівки до практичних занять з дисципліни «Теорія алгоритмів» для студентів напрямку підготовки 6.050103 з російською мовою навчання — Програмна інженерія / Укл.: О. М. Паулін, Н. О. Комлева. – Одеса: ОНПУ, 2016. – 16 с.
3.    Методичні вказівки до практичних занять з дисципліни «Алгоритми та структури даних» для студентів напрямку підготовки 6.050103 — Програмна інженерія / Укл.: О. М. Паулін, М. І. Синегуб. – Одеса: ОНПУ, 2016. – 13 с.
4.    Методичні вказівки до практичних занять з дисципліни «Алгоритми та структури даних» для студентів напрямку підготовки 6.050103 з російською мовою навчання — Програмна інженерія / Укл.: О. М. Паулін, М. І. Синегуб. – Одеса: ОНПУ, 2016. – 14 с.

Інформаційні ресурси
1.    Марченко О.І. СДА. Лекції. Структури даних та алгоритми. URL : https://www.youtube.com/playlist?list=PLQ2NVXJ6X6IbBkPrhwE2F-NvByARRO1be 
2.    Sorting Algorithms Animations. URL : https://www.toptal.com/developers/sorting-algorithms. 
3.    Data Structures and Algorithms in C++. URL : https://sites.google.com/site/indy256/algo_cpp.