Алгоритми та структури даних
Анотація курсу
Курс «Алгоритми та структури даних» розвиває знання та навички у студентів про базові структури даних і основні обчислювальні алгоритми, знання та навички проектування, розробки та аналізу алгоритмів, оцінки їх ефективності та складності. Вивчення цієї дисципліни має на меті зрозуміння та засвоєння основних принципів розробки алгоритмів і програм, а також дає підґрунтя для самостійної практичної роботи в галузі інформаційних технологій.
Мета:
Метою дисципліни «Алгоритми та структури даних» є ознайомлення студентів із основними класами алгоритмів, оволодіння методикою їх аналізу та розробки; вивчення студентами типових абстрактних структур даних, що мають широке застосування при розробці прикладних програм, та методів їх обробки, вироблення та закріплення навичок роботи з ними.
Основні завдання:
Основними завданнями вивчення дисципліни «Алгоритми та структури даних» є розвиток теоретичних та практичних навичок розробки, застосування та аналізу алгоритмів при розв’язанні поставлених задач; оволодіння основними прийомами роботи зі структурами даних, реалізація їх на мові програмування.
Що ви будете знати:
- базові поняття теорії алгоритмів;
- основні алгоритми та структури даних;
- питання обчислюваності, розв’язності та нерозв’язності масових задач;
- поняття часової та просторової складності алгоритмів при розв’язанні обчислювальних задач;
- принципи проектування алгоритму «зверхувниз» та покрокового уточнення алгоритму
Що ви будете вміти:
- використовувати, розробляти та досліджувати математичні методи та алгоритми обробки даних, алгоритми розв’язування задач моделювання об’єктів і процесів інформатизації;
- використовувати, розробляти та досліджувати алгоритми функціонування комп’ютеризованих систем;
- оцінювати складові ефективності алгоритмів функціонування комп’ютеризованих систем;
- правильно обирати структуру даних для конкретної задачі;
- розробляти алгоритм відповідно до структури даних;
- використовувати рекурсивні структури даних, рекурсивні алгоритми.
Тематичний план курсу
Поняття структури даних та абстрактного типу даних. Класифікація структур даних. Способи реалізації структур даних та абстрактного типу даних. Приклади базових структур даних. Масиви. Поняття аналізу. Класифікація методів аналізу. Емпіричний аналіз: допущення по використанню, порівняння декількох алгоритмів, застосування. Асимптотичний аналіз. Швидкість росту функції. Побудова аналітичного виразу, що оцінює ефективність алгоритму. «Тета-нотація» (θ-нотація), Онотація та Ω-нотація («омега-нотація»). Лінійний ріст, логарифмічний ріст, квадратичний ріст, експоненціальний ріст. Прості та вдосконалені алгоритми сортування масивів. Сортування простими включеннями, простим вибором, простим обміном. Шейкерне сортування. Сортування Шелла. Швидке сортування. Сортування злиттям. Пірамідальне сортування. Порівняння різних методів сортування. Поняття пошуку. Класифікація алгоритмів пошуку. Поняття ротації та її використання. Опис алгоритмів пошуку: послідовний, бінарний, інтерполяційний, індексуванням по ключу, дерево бінарного пошуку (BST), порозрядний пошук (DST-дерева та TST-дерева). Область застосування. Зв’язні списки. Стеки. Черги. Базові алгоритми для роботи зі списками, стеками, чергами. Поняття рекурсії. Особливості реалізації рекурсивних алгоритмів. Бінарні дерева. Ідеально збалансовані дерева. Дерева пошуку. Червоно-чорні дерева. Збалансовані АВЛ-дерева. Основні алгоритми для роботи з бінарними деревами. Приклад використання рекурсії для структури даних “Дерево”. Поняття хешування та хеш-коду. Методи хешування. Хеш-функції. Способи реалізації хеш-таблиці. Застосування хеш-таблиці. Таблиці з прямою адресацією. Уникнення колізій за допомогою ланцюгів. Відкрита адресація.
Загальна інформація
| Форма навчання | Кількість кредитів ECTS | Загальна кількість академічних годин | Лекційні | Лабораторні | Самостійна робота | Форма контролю |
|---|---|---|---|---|---|---|
| Денна | 5 | 150 | 16 | 32 | 102 | екзамен |
| Заочна | 5 | 150 | 6 | 6 | 138 | екзамен |
| Компетентності | Результати навчання |
|---|---|
| ЗК01 Здатність до абстрактного мислення, аналізу та синтезу. ЗК02 Здатність застосовувати знання у практичних ситуаціях. СК03 Здатність розробляти архітектури, модулі та компоненти програмних систем. СК08 Здатність застосовувати фундаментальні і міждисциплінарні знання для успішного розв’язання завдань інженерії програмного забезпечення. СК14 Здатність до алгоритмічного та логічного мислення. | ПР05 Знати і застосовувати відповідні математичні поняття, методи доменного, системного і об’єктно-орієнтованого аналізу та математичного моделювання для розробки програмного забезпечення. ПР06 Уміння вибирати та використовувати відповідну задачі методологію створення програмного забезпечення. ПР07 Знати і застосовувати на практиці фундаментальні концепції, парадигми і основні принципи функціонування мовних, інструментальних і обчислювальних засобів інженерії програмного забезпечення. ПР13 Знати і застосовувати методи розробки алгоритмів, конструювання програмного забезпечення та структур даних і знань. ПР15 Мотивовано обирати мови програмування та технології розробки для розв’язання завдань створення і супроводження програмного забезпечення. |