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

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

Мета дисципліни:
метою вивчення дисципліни є навчання студентів основам побудови алгоритмів та оцінювання їх трудомісткості при вирішуванні комбінаторних задач, задач символьної, графічної та іншого виду обробки.
Для досягнення мети вивчення дисципліни студенти повинні мати:
СК8. Здатність розробляти і аналізувати алгоритми і структури даних при створенні програмного забезпечення. 
Дисципліна узагальнює набуті студентами знання основ програмування, потребує володіння методами структурної та алгоритмічної декомпозиції системи, методами та технологіями організації та застосування даних.
Завдання дисципліни:
у результаті вивчення дисципліни студенти повинні уміти:
РН30. (З) Аналізувати, оцінювати і вибирати інструментальні та обчислювальні засоби, технології, алгоритмічні і програмні рішення для розв’язання завдань інженерії програмного забезпечення.
РН25. (АВ) Мотивовано обирати мови програмування для розв’язання завдань створення і супроводження програмного забезпечення.
Дисципліна має націлити майбутніх фахівців на осмислене і творче застосування отриманих знань в їх практичній діяльності.

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

В результаті вивчення дисципліни студент повинен знати:
РН20. (У) Знати, розуміти і застосовувати відповідні математичні поняття, методи доменного, системного і об’єктно-орієнтованого аналізів та математичного моделювання для розробки програмного забезпечення. 
РН21. (АВ) Знати та мати навички реалізації основних алгоритмів та структур даних програмування. 
РН24. (У) Знати і застосовувати методи розробки алгоритмів, конструювання програмного забезпечення та структур даних і знань. 
В результаті вивчення дисципліни студент повинен мати:
РН16. (АВ) Вміння аналізувати проблеми щодо створення програмного забезпечення.

Форми організації освітнього процесу та види навчальних занять

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

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

1    тиждень

Л1. Інтуїтивне визначення алгоритму, види обчислювань та алгоритмів [1, с. 4-14, 177-178].
ПР1. Методи сортування [19, с. 4-12].
СРС. К.

2    тиждень

Л2. Види алгоритмів [2, с. 174-242, 285-318, 319-340, 626-649; 1, с. 15-20].
СРС. К.

3    тиждень

Л3. Організація розгалужень та організація циклів в СА [1, с. 20-42].
ПР2. Алгоритми покриття [19, с. 13-23].
СРС. К.

4    тиждень

Л4. Логічні алгоритми [1, с. 43-48].
СРС. К.

5    тиждень

Л5. Структурування даних [1, с. 96-103].
ПР3. Алгоритми на графах [19, с. 24-43].
СРС. К.

6    тиждень

Л6. Списки і їх різновидності [1, с. 104-110].
СРС. К.

7    тиждень

Л7. Абстрактні структури даних [1, с. 111-116; 3, с. 256-263; 4, с. 293-337].
ПР4. Структури даних [19, с. 58-64].
СРС. К.

8    тиждень

Л8. Асимптотика [1, с. 129-135, 179-183].
МКР1. СРС. К.

9    тиждень

Л9. Моделі обчислювань [1, с. 52-60].
ПР5. Скінченний автомат [19, с. 44-49].
СРС. К.

10    тиждень

Л10. Уточнення поняття “алгоритм”; теза Чьорча [1, с. 91-95].
СРС. К.

11    тиждень

Л11. Скінченний автомат [1, 73-79].
ПР6. Машини Тюрінга [19, с. 50-57].
СРС. К.

12    тиждень

Л12. Машина Тюрінга [1, 80-90].
СРС. К.

13    тиждень

Л13. Характеристики алгоритмів [1, с. 136-138].
ПР7. Повна побудова алгоритму [1, с. 158-174].
СРС. К.

14    тиждень

Л14. Методи збільшення ефективності алгоритмів [1, с. 139-157].
СРС. К.

15    тиждень

Л15. Заключення.
ПР7. Повна побудова алгоритму [1, с. 158-174].
МКР2. СРС. К.

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

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

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

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

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

Максимальна оцінка, яку може отримати здобувач за всі виконані види робіт – 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 тиждень).

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

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

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

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

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

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

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

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

Література

Основна література
1.    Паулин О.Н. Основы теории алгоритмов. ⎯ Одесса: Автограф, 2006. ⎯ 188 с. /1 прим./
2.    Кормен, Томас Х. и др. Алгоритмы: построение и анализ, 3-е изд.: Пер. с англ. ⎯ М.: ООО “И.Д. Вильямс”, 2013. ⎯ 1328 с. /http://www.williamspublishing.com/Books/978-5-8459-1794-2.html/
3.    Никлаус Вирт. Алгоритмы и структуры данных. Новая версия для Оберона + CD / Пер. с англ. Ткачев Ф.В. ⎯ М.: ДМК Пресс, 2010. ⎯ 272 с. /15 прим., 1989 р./
4.    Скиена С. Алгоритмы. Руководство по разработке. ⎯ 2-е изд.: Пер. с англ. ⎯ Спб.: БХВ-Петербург, 2011. ⎯ 720 с. /https://www.twirpx.com/file/1218951/

Додаткова література
5.    Альфред В. Ахо, Джон Э. Хопкрофт, Джеффри Д. Ульман. Структуры данных и алгоритмы: Пер. с англ.: Учеб. пособие. ⎯ М.: Изд. дом “Вильямс”, 2000. ⎯ 384 с. /25 прим., 2001 р./
6.    Кормен Т., Лейзерсон Ч., Ривест Р. Алгоритмы: Построение и анализ. ⎯ М.: МЦМНО, 2000. ⎯ 960 с. /https://ru.wikipedia.org/wiki/%D0%90%D0%BB%D0%B3%D0%BE%D1%80%D0%B8%D1%82...
7.    Кнут Д. Искусство программирования. В 3 т. (Т.1: Основные алгоритмы. Т.2: Получисленные алгоритмы. Т.3: Сортировка и поиск). ⎯ М.: Изд. дом “Вильямс”, 2000. ⎯ (T.1: 720 с., Т.2: 832 с., Т.3: 832 с.) /15 прим., 2001 р./
8.    Н. Вирт. Алгоритмы + структуры данных = программы. ⎯ М.: 1995. ⎯ 406 с. /http://snilit.tspu.ru/uploads/files/default/virt.pdf/
9.    Гудман С., Хидетниеми С. Введение в разработку и анализ алгоритмов. ⎯ М.: Мир, 1991. ⎯ 368 с. /16 прим., 1989 р./
10.    Вирт Н. Алгоритмы и структуры данных: Пер. с англ. ⎯ 2-е изд., испр. ⎯ СПб.: Невский Диалект, 2005. ⎯ 352 с. /1прим., 2010 р./
11.    Дж. Макконнелл. Анализ алгоритмов. Активный обучающий подход. 3-е дополненное издание / Дж. Макконнелл. ⎯ М.: Техносфера, 2009. ⎯ 416 с. /http://www.technosphera.ru/lib/book/8/
12.    Т.К. Кацаран. Машина Тьюринга и рекурсивные функции: Учебное пособие для вузов / Т.К. Кацаран, Л.Н. Строева. ⎯ Воронеж: Издательско-полиграфический центр Воронежского государственного университета, 2008. ⎯ 36 с.
13.    Ю.И. Шемакин. Машинный поиск и сортировка информации: Учебное пособие / Ю.И. Шемакин, А.А. Романов. ⎯ М.: Моск. ин-т нар. хоз-ва, 1989. ⎯ 168 с.
14.    О.Н. Паулин. Представление вычислительных процессов сетями Петри. Научные труды SWorld. ⎯ Выпуск 4(41). Том 2 / О.Н. Паулин, Ю.С. Поляков, В.А. Шульгин. ⎯ Иваново: Научный мир, 2015 ⎯ С. 64 ⎯ 71.
15.    Крисилов В.А. Программный программируемый модуль на основе машины Тьюринга / В.А. Крисилов, Н.И. Синегуб, Г.Е. Романов // Электротехнические и компьютерные системы. — 2016. — №21 (97). — С. 88 — 92.
16.    Паулин О.Н. Вычислительные модели алгоритмов покрытия /О.Н. Паулин// Информатика и математические методы в моделировании. Т. 6, №4. – Одесса: ОНПУ, 2016. – С. 385-396.
17.    Паулин О.Н. Методы и алгоритмы покрытия (Часть 2). /О.Н. Паулин// Информатика и математические методы в моделировании. Т. 7, №4. – Одесса: ОНПУ, 2017. – С. 333-338.
18.    Paulin О.M., Komleva N.O., Sinegub M.I., Sarafaniuk D.E. About Modification the Coverage Algorithm Using the “Minimum Column – Maximum Row” Method. - Вчені записки ТНУ імені В.І. Вернадського. Серія: технічні науки. – Київ, 2020. – Том 31 (70) Ч. 1. № 1. – С. 112 – 118. DOI https://doi.org/10.32838/2663-5941/2020.1-1/21 http://www.tech.vernadskyjournals.in.ua/journals/2020/1_2020/part_1/23.pdf

Методична література
19.    Методические указания к практическим занятиям по дисциплине "Теория алгоритмов и вычислительных процессов" для студентов специальностей 7.080403 и 7.091501 / Сост.: О.Н. Паулин. ⎯ Одесса: ОНПУ, 2003. ⎯ 65 с.
20.    Методичні вказівки до практичних занять з дисципліни «Теорія алгоритмів» для студентів напрямку підготовки 6.050103 — Програмна інженерія / Укл.: О. М. Паулін, Н. О. Комлева. – Одеса: ОНПУ, 2016. – 15 с.
21.    Методичні вказівки до практичних занять з дисципліни «Теорія алгоритмів» для студентів напрямку підготовки 6.050103 з російською мовою навчання — Програмна інженерія / Укл.: О. М. Паулін, Н. О. Комлева. – Одеса: ОНПУ, 2016. – 16 с.
22.    Методичні вказівки до практичних занять з дисципліни «Алгоритми та структури даних» для студентів напрямку підготовки 6.050103 — Програмна інженерія / Укл.: О. М. Паулін, М. І. Синегуб. – Одеса: ОНПУ, 2016. – 13 с.
23.    Методичні вказівки до практичних занять з дисципліни «Алгоритми та структури даних» для студентів напрямку підготовки 6.050103 з російською мовою навчання — Програмна інженерія / Укл.: О. М. Паулін, М. І. Синегуб. – Одеса: ОНПУ, 2016. – 14 с.