Розробники та рецензенти
Заклад вищої освіти:
Компанія-рецензент 1:
Компанія-рецензент 2:
Валідація:
Розробник навчальної програми:
Марина Гринченко — к.т.н., доцент, завідувач кафедри “Управління проєктами в інформаційних технологіях”
Базова інформація
Шифр та назва спеціальності:
122 - Комп'ютерні наукиНазва освітньо-наукової програми
Комп’ютерні науки. Штучний інтелект та управління проєктамиНазва дисципліни
Алгоритми та структури данихВид дисципліни
ОсновнаБлок дисципліни
Алгоритмізація і програмуванняКількість студентів
70Курс/Семестр
3Загальна інформація про дисципліну
Анотація
Курс «Алгоритми та структури даних» розвиває знання та навички у студентів про базові структури даних і основні обчислювальні алгоритми, знання та навички проєктування, розробки та аналізу алгоритмів, оцінки їх ефективності та складностіАнотація
Опановування теоретичними знаннями та практичними навичками основних алгоритмів та структур даних. Формування у студентів системи знань про базові поняття теорії алгоритмів, поняття часової та просторової складності алгоритмів для адекватного моделювання предметних областей і створення програмних та інформаційних систем. Використання основних алгоритмів та структур даних, розробка та аналіз алгоритмів, оцінка їх ефективності та складностіАнотація
Лекції, лабораторні роботи, самостійна робота. Підсумковий контроль – іспитРозподіл часу
Загальний обсяг (кредитів): 4; Лекції (занять): 32; Лабораторні (занять): 32; Практичні (занять): 0; Самостійна робота (годин): 56
Попередні дисципліни
Основи програмування. Дискретна математика. Об’єктно-орієнтоване програмуванняМатеріально-технічне та програмне забезпечення дисципліни
24 Wintel computers (мінімальні характеристики: Intel Pentium G4500, RAM 8 GB, HDD 350 GB) Windows 11, Office 365, Visual Studio 2022 IDE (2019) – інтегроване середовище розробки програмного забезпечення, мови програмування: Python (версія вище 3.6)Структура дисципліни
| Теоретична складова Назва, перелік питань або анотація лекції | Годин | Практична складова Опис та приклад завдання, а також посилання на методичні матеріали | Годин | Інструменти, засоби та технології | ||||||||||||||
| Тема 1 – Структури даних. Класифікація та характеристика структур даних | ||||||||||||||||||
| Поняття «структури даних». Базові структури даних. Характеристика та класифікація структур даних. Лінійні та нелінійні структури даних. Приклади практичного застосування. | 2 | Ознайомитися із основними способами організації списків та особливостями їх програмної реалізації. Набути практичних навичок по роботі зі двозв'язним та кільцевими списками | 4 | Visual Studio 2022 IDE (2019) – інтегроване середовище розробки програмного забезпечення | ||||||||||||||
| Структури даних. Основні операції роботи зі стеками, чергами та деками. Приклади практичного використання черг та стеків. | 2 | Ознайомитися із основними способами організації стеків, черг, деків та особливостями їх програмної реалізації. Набути практичних навичок роботи зі стеками, чергами та деками. | 2 | Visual Studio 2022 IDE (2019) – інтегроване середовище розробки програмного забезпечення | ||||||||||||||
| Опис дерева як структури даних. Основні характеристики бінарних дерев. Базові операції з бінарними деревами | 2 | Набуття практичних умінь та навичок опрацювання динамічних структур даних, представлених у вигляді бінарних | 2 | Visual Studio 2022 IDE (2019) – інтегроване середовище розробки програмного забезпечення | ||||||||||||||
| Опис червоно-чорного дерева як структури даних. Основні властивості червоно-чорного дерева. Базові операції з червоно-чорними деревами. Балансування червоно-чорного дерева | 4 | Набуття практичних умінь та навичок опрацювання динамічних структур даних, представлених у вигляді червоно-чорних дерев | 4 | Visual Studio 2022 IDE (2019) – інтегроване середовище розробки програмного забезпечення | ||||||||||||||
| Збалансовані дерева пошуку. Опис AVL дерева як структури даних. Основні властивості AVL дерева. Характеристика В дерева, Особливості декартового дерева. Опис splay дерева. | 4 | |||||||||||||||||
| Структури даних для пошуку. Хеш-таблиці. Визначення. Основні операції з хеш-таблицями. Методи вирішення колізій. Методи пробування хешування | 2 | Вивчити роботу: прямої адресації, хеш-таблиці і відкритої адресації. Реалізувати хеш-таблицями. | 2 | |||||||||||||||
| Тема 2 – Алгоритми та асимптотичний аналіз алгоритмів | ||||||||||||||||||
| Формалізація поняття «алгоритм». Основні властивості алгоритму, Показники ефективності алгоритмів. Аналіз складності алгоритмів. Асимптотичні позначення. Асимптотична складність. Обчислювальна складність алгоритмів сортування | 4 | 4 | Visual Studio 2022 IDE (2019) – інтегроване середовище розробки програмного забезпечення | |||||||||||||||
| Характеристика алгоритмів сортування. Основні властивості сортування. Класифікація методів сортування. Порівняльний аналіз ефективності алгоритмів сортування | 2 | Вивчити основні алгоритми сортування масивів і освоїти їх на практиці. Перевірити роботу алгоритмів на різних наборах даних, провести порівняльний аналіз алгоритмів сортування. | 4 | Visual Studio 2022 IDE (2019) – інтегроване середовище розробки програмного забезпечення | ||||||||||||||
| Ознайомитися із основними алгоритмами пошуку даних та особливостями їх програмної реалізації. Набути практичних навичок по роботі зі алгоритмами пошуку даних | 2 | Ознайомитися із основними алгоритмами пошуку даних та особливостями їх програмної реалізації. Набути практичних навичок по роботі зі алгоритмами пошуку даних. Провести асимптотичний аналіз алгоритмів пошуку даних | 4 | |||||||||||||||
| Алгоритми послідовного пошуку. Бінарного пошуку. пошуку з бар'єром. Схема та реалізація алгоритмів Кнута-Морріса-Пратта, Бойера-Мура. | 2 | |||||||||||||||||
| Основні поняття графа та різни типи графів. Алгоритм на графах (пошук у глибину). Алгоритм на графах (пошук завширшки). Алгоритми знаходження найкоротшого шляху. Алгоритми Дейкстри та Флойда-Воршелла | 2 | Набуття практичних умінь та навичок з використання алгоритмів обходу графів: алгоритм в глибину (DFS- Dipth First Search) та алгоритм в ширину (BFS- Breadth First Search). Набуття практичних умінь і навичок з використання алгоритмів Дейкстри та Флойда. | 2 | Visual Studio 2022 IDE (2019) – інтегроване середовище розробки програмного забезпечення | ||||||||||||||
| Тема 3 – Жадібні алгоритми та динамічне програмування | ||||||||||||||||||
| Поняття «жадібний» алгоритм. Властивості жадібного алгоритму. Типи жадібних алгоритмів. Застосування жадібного алгоритму | 2 | Набуття практичних умінь та навичок з використання жадібних алгоритмів | 2 | Visual Studio 2022 IDE (2019) – інтегроване середовище розробки програмного забезпечення | ||||||||||||||
| Принципи та підходи динамічного програмування. Завдання про знаходження найбільшої загальної послідовності | 2 | Набуття практичних умінь та навичок з використання алгоритмів динамічного програмування. | 2 | Visual Studio 2022 IDE (2019) – інтегроване середовище розробки програмного забезпечення | ||||||||||||||
Теми та завдання для самостійної роботи
| Назва та опис завдання | Методи контролю та критерії оцінювання | Годин | |||||||||||||||
| Реалізація наближеного розв’язання задачі комівояжера | Написання реферату, отримання додаткових балів до оцінки з іспиту | 14 | |||||||||||||||
| Ознайомитися з генераторами випадкових чисел та методами перевірки випадковості | Написання реферату, отримання додаткових балів до оцінки з іспиту | 14 | |||||||||||||||
| Застосування алгоритмів для розв’язання геометричних задач | Написання реферату, отримання додаткових балів до оцінки з іспиту | 14 | |||||||||||||||
| Побудова хеш-функції різними методами | Написання реферату, отримання додаткових балів до оцінки з іспиту | 14 | |||||||||||||||
Проєкт
Немає
Рекомендовані джерела інформації та навчальні матеріали
|
Основні |
||||||||||||||||||
| № |
Назва |
До теми (вказати номер) | ||||||||||||||||
| 1 | Корман, Томас Г. Вступ до алгоритмів: Переклад з англійської третього видання: Introduction Algorithms ^ Third Edition : [пер. З анг.]/ Томас Г. Кормен, Чарлз Е. Лейзерсон, Роналд Л. Рівест, Кліфрод Стайн. – К. : К.1.С., 2019. – 1288 с. | 1, 2, 3, 4 | ||||||||||||||||
| 2 | Креневич А.П. Алгоритми і структури даних. Підручник. / А.П. Креневич. – К.: ВПЦ "Київський Університет", 2021. – 200 с. https://www.researchgate.net/publication/354202608_Algoritmi_i_strukturi_danih_-_Pidrucnik | 1, 2, 3, 4 | ||||||||||||||||
| 3 | Helmut Knebl. Algorithms and Data Structures: Foundations and Probabilistic Methods for Design and Analysis / Helmut Knebl. – Cham: Springer Nature Switzerland AG, 2020. – 349 p. https://link.springer.com/book/10.1007/978-3-030-59758-0 | 1, 2, 3, 4 | ||||||||||||||||
| 4 | Ільман В.М., Іванов О.П., Панік Л.О. Алгоритми, дані і структури: навч. посіб. / В.М. Ільман, О.П. Іванов, Л.О. Панік. Дніпропет. нац.. ун-т залізн. трансп.ім. акад. В. Лазаряна. – Дніпро, 2019. – 134 с. https://crust.ust.edu.ua/server/api/core/bitstreams/16eada7c-c082-46f7-af81-1d6e97ac9320/content | 1, 2, 3, 4 | ||||||||||||||||
| 5 | Бульба С.С., Бречко В.О., Далека В.Д.. Алгоритми та структури даних : навч.-метод. посіб. / Бульба С.С., Бречко В.О., Далека В.Д. – Харків : НТУ «ХПІ», 2021. – 141 с. https://repository.kpi.kharkov.ua/server/api/core/bitstreams/f1a76423-2e85-4658-aeec-be167ac02e1c/content | 1, 2, 3 | ||||||||||||||||
| 6 | Методичні вказівки до виконання лабораторних робіт з дисципліни "Алгоритми та структури даних" [Електронний ресурс] : для студентів ден. форми навчання спец. "Комп’ютерні науки" / уклад.: М. А. Гринченко, Є. О. Мошко ; Нац. техн. ун-т "Харків. політехн. ін-т". – Електрон. текст. дані. – Харків, 2023. – 42 с. – URI: https://repository.kpi.kharkov.ua/handle/KhPI-Press/72548 | 1, 2, 3, 4 | ||||||||||||||||
| 7 | Shmuel Tomi Klein. Basic Concepts In Algorithms. / Shmuel Tomi Klein. – Singapore: World Scientific Publishing Co Pte Ltd, 2021. – 364 p. https://books.google.com.ua/books/about/Basic_Concepts_in_Algorithms.html?id=8NpdzgEACAAJ&redir_esc=y | 1, 2, 3, 4 | ||||||||||||||||
| 9 | Steven S. Skiena. The Algorithm Design Manual. 3rd ed. / Steven S. Skiena. – Cham: Springer Nature Switzerland AG, 2020. – 793 p. https://archive.org/details/2008-book-the-algorithm-design-manual | 1, 2, 3, 4 | ||||||||||||||||
|
Додаткові |
||||||||||||||||||
| № |
Назва |
До теми (вказати номер) | ||||||||||||||||
| 1 | Шаховська Н. Б., Голощук Р. О. Алгоритми і структури даних : навч.- посіб. / Н. Б. Шаховська, Р. О. Голощук. – Львів : Магнолія, 2018. 216 с. https://victana.lviv.ua/biblioteka/127-alhorytmizatsiya-ta-prohramuvannya/428-shakhovska-nb-holoshchuk-ro-alhorytmy-i-struktury-danykh | 1, 2, 3, 4 | ||||||||||||||||
| 2 | Бугаєва Л. М., Ковалюк Д. О. Алгоритми і структури даних. Комп'ютерний практикум: навч. посіб. / Л. М. Бугаєва, Д. О. Ковалюк – Київ : НТУ «КПІ» ім. Ігоря Сікорського, 2022. – 34 с https://ela.kpi.ua/bitstream/123456789/55685/1/Alhorytmy_ta_struktury_danykh.pdf | 1, 2, 3 | ||||||||||||||||
Контрольні заходи
| Назва та опис | Методи контролю та критерії оцінювання | |||||||||||||||||
| Тест № 1. Питання охоплюють теми: “Тема 1 – Основні характеристики алгоритмів. Динамічні структури даних” “Тема 2 – Алгоритми сортування та асимптотичний аналіз алгоритмів” | Тест складається з 30 запитань, залежно від складності питання, відповідь оцінюються в 3-4 бали. Завдання тесту оцінюються у 100 шкалі (60 балів мінімальний бал, 100 балів — максимальний бал) Посилання на тест: https://forms.office.com/e/bpgbnEw5xx | |||||||||||||||||
| Тест № 2. Питання охоплюють теми: Тема 3 – Хеш-функції. Хеш-таблиці. Тема 4 – Жадібні алгоритми та динамічне програмування | Тест складається з 30 запитань, залежно від складності питання, відповідь оцінюються в 3-4 бали. Завдання тесту оцінюються у 100 шкалі (60 балів мінімальний бал, 100 балів — максимальний бал). Посилання на тест: https://forms.office.com/e/faJZ8hvWBr | |||||||||||||||||
| Виконання та захист лабораторних робіт | Дисципліна передбачає 8 лабораторних робіт, За виконання та захист лабораторної роботи студент отримує оцінку згідно 100 шкалі (60 балів мінімальний бал, 100 балів — максимальний бал). | |||||||||||||||||
| Проведення іспиту | Усна доповідь. Підсумкова оцінка складається з середньо арифметичного значення, яке включає оцінку за тест №1, тест№2 та підсумкової оцінки за всі лабораторні роботи. | |||||||||||||||||
Результати навчання
Проєктувати, розробляти та аналізувати алгоритми розв'язування обчислювальних та логічних задач, оцінювати ефективність та складність алгоритмів на основі застосування формальних моделей алгоритмів та обчислювальних функцій
Зв'язок з ринком праці
Спеціальність/професія, підготовці до діяльності в якій читається курс:
Розробник серверної частиниПосилання на вакансії (понад 3),
- https://jobs.dou.ua/companies/cleveroad/vacancies/268772/
- https://jobs.dou.ua/companies/singlestore/vacancies/268427/
- https://www.work.ua/jobs/5652640/
Перелік компетентностей із вказаних як вимоги до вакансії, які набувають студенти, в процесі проходження дисципліни.
Інструменти оцінювання результатів навчання за дисципліною
|
Об'єкт оцінювання (знання методів та принципів, практичні навички, командна робота тощо) |
Методи контролю (тести, виконання поточних практичних завдань та їх форма: написання коду, створення діаграми Гантта, створення прототипу тощо) |
Інструмент оцінювання (доступ до результатів тесту, гостьова лекція, посилання на виконані завдання, посилання на проєкт, присутність на захисті проєктів, доступ до запису захисту тощо) |
| Знання методів та принципів | Результати виконання тестів. | Гостьова лекція |
| Практичні навички | Результати виконання лабораторних робіт (написання коду, звіти) | Доступ до результатів тесту |
| Посилання на виконані завдання |