Алгоритми і структури даних
Спеціальність: Інженерія програмного забезпечення
Код дисципліни: 6.121.00.O.016
Кількість кредитів: 4.00
Кафедра: Програмне забезпечення
Лектор: доцент Коротєєва Тетяна Олександрівна
Семестр: 3 семестр
Форма навчання: денна
Завдання: Вивчення навчальної дисципліни передбачає формування у здобувачів освіти компетентностей:
загальні компетентності:
1. Здатність до абстрактно мислення, аналізу та синтезу. (К01)
фахові компетентності:
1. Здатність застосовувати і розвивати фундаментальні і міждисциплінарні знання для
успішного розв’язання завдань інженерії програмного забезпечення. (СК08)
2. Здатність до алгоритмічного та логічного мислення. (СК14)
Результати навчання: 1. Вміти відобразити різноманітні дані реального світу наявними структурами даних.
2. Вміти представити обрані структури у вигляді прийнятному для опрацювання їх на комп‘ютері.
3. Навести класифікацію структур даних та їх основні переваги та недоліки.
4. Пояснити роботу різних алгоритмів сортування, порівняти їх складність.
5. Пояснити роботу різних алгоритмів пошуку, порівняти їх складність.
ПР05. Знати і застосовувати відповідні математичні поняття, методи доменного, системного і об’єктно-орієнтованого аналізу та математичного моделювання для розробки програмного забезпечення.
ПР07. Знати і застосовувати на практиці фундаментальні концепції, парадигми і основні принципи функціонування мовних, інструментальних і обчислювальних засобів інженерії програмного забезпечення.
ПР13. Знати і застосовувати методи розробки алгоритмів, конструювання програмного забезпечення та структур даних і знань.
ПР15. Мотивовано обирати мови програмування та технології розробки для розв’язання завдань створення і супроводження програмного забезпечення.
ПР18. Знати та вміти застосовувати інформаційні технології обробки, зберігання та передачі даних
Необхідні обов'язкові попередні та супутні навчальні дисципліни: Комп‘ютерна дискретна математика,
Об‘єктно-орієнтоване програмування.
Бази даних.
Безпека програм та даних.
Короткий зміст навчальної програми: Дисципліна передбачає вивчення основних класів структур даних, їх комп‘ютерне представлення, приклади використання, основні функції обробки. Лекції дисципліни включають матеріал про ряд методів сортування та пошуку, алгоритмів на деревах, алгоритмів побудови шляху, їх алгоритмічну складність та порівняльний аналіз. Лабораторні та практичні заняття передбачають практичне засвоєння розглянутого на лекціях матеріалу.
Частина програмних результатів дисципліни може бути оцінена через представлення результатів неформальної та інформальної освіти (сертифікати платформи Coursera для Intro to Operating Systems, сертифікати навчальних програм ІТ фірм, напр.. Linux Kernel GL BaseCamp, та ін..).
Опис: 1.Основні визначення та поняття. Термінологія. Зображення алгоритмів. Алгоритмічна складність. Поліноміальна та неполіноміальна складність алгоритмів.
2.Класифікація структур даних. Основні операції над структурами даних.
3.Сортування даних. Сортування вибіркою. Метод простої вибірки. Метод бульбашки. Швидкий метод сортування. Порівняння алгоритмічної складності методів.
4.Сортування включенням. Сортування розподілом. Сортування злиттям або об’єднанням. Порівняння алгоритмічної складності методів.
5.Дерева. Основні визначення та поняття. Бінарні дерева. Зображення в пам‘яті ЕОМ графоподібних структур. Алгоритми обходу дерев. Висхідні, нисхідні, змішані алгоритми обходу дерев.
6.Сортування на деревах. Метод вибірки з дерева. Пірамідальне сортування. Алгоритмічна складність методів.
7.Лінійні структури даних. Стеки, черги, деки. Організація стеків, черг і деків. Види черг. Представлення лінійних структур в комп‘ютері. Операції додавання та видалення елементів з лінійних структур.
8.Масиви. Множини i кортежі. Зберігання множин і масивів. Зберігання розріджених матриць. Операції з масивами, множинами та кортежами.
9.Лінійні списки. Основні визначення та поняття. Однонаправлені списки. Двонаправлені списки. Циклічні списки. Організація списків.
10.Представлення списків в комп‘ютері. Робота зі списками. Алгоритми обробки списків.
11.Нелінійні структури даних. Класифікація нелінійних структур даних. Таблиці. Зображення таблиць. Основні операції з таблицями.
12.Спискові структури. Основні поняття. Ієрархічні списки. Сіткові структурі. Організація спискових структур.
13.Пошук даних. Послідовний пошук. Двійковий пошук. Алгоритм Кнута, Моріса, Пратта. Алгоритм Бойера-Мурра. Порівняння алгоритмічної складності методів.
14.Дерева порівнянь на векторній пам‘яті. Дерева порівнянь на зчепленій пам‘яті. Пошук у таблицях з обчислюваними адресами. Таблиці з прямим доступом. Хеш-таблиці. Задача колізії.
15.Алгоритм побудови дерева згортання. Аналіз алгоритмічної складності. Застосування алгоритму до розв‘язку комбінаторних задач.
Методи та критерії оцінювання: 1. Контрольні заходи на практичних заняттях.
2. Усне опитування на практичних заняттях.
3. Тести.
4. Захист лабораторних робіт.
5. Екзаменаційний контроль (письмова компонента, усна компонента).
Критерії оцінювання результатів навчання: • поточний контроль включає захист 12 лабораторних робіт з усним опитуванням та письмовими звітами (3+4+4+4+4+4+3+2+3+4+5+5=45 %) . Для захисту лабораторних з балами встановлюються крайні терміни. За межами крайніх термінів роботи оцінюються в 0 балів;
• підсумковий контроль - екзамен: письмово-усна форма (50+5=55%)
Порядок та критерії виставляння балів та оцінок: 1. Бали за поточний контроль виставляють до початку сесії. До екзамену допускаються студенти, які виконали 100% робіт поточного контролю. Студент, який виконав менше 50% робіт поточного контролю, вважається неатестованим та має можливість пройти повторне вивчення дисципліни. Студент, який виконав більше 50% робіт але не всі 100% може довиконати завдання і скласти іспит на комісії.
2. Бали за практичні заняття виставляють згідно письмового опитування та загальної активності на занятті.
3. Бали за лабораторні роботи виставляють згідно успішного захисту. Захист вважають успішним, якщо студент вчасно продемонстрував виконання лабораторної роботи відповідно до свого варіанту завдання, правильно оформив звіт і захистив його та дав правильні відповіді на усні запитання; зміг внести корективи у лабораторну на прохання викладача. Якщо захист лабораторної роботи відбувається невчасно, з кожним тижнем затримки захисту бали за лабораторну зменшуються на 1.
4. Відповідальність за недотримання принципів академічної доброчесності під час виконання і захисту лабораторних робіт: якщо при захисті лабораторної роботи викладачем було виявлено прояви порушення академічної доброчесності, робота не зараховується, студент отримує новий варіант завдання і може повторно захищати лабораторну на мінімальну кількість балів (1 бал).
Рекомендована література: 1. Креневич А.П. Алгоритми і структури даних. Підручник. – К.: ВПЦ "Київський Університет", 2021. – 200 с.
2. Мелешко Є.В., Якименко М.С., Поліщук Л.І. Алгоритми та структури даних: Навчальний посібник для студентів технічних спеціальностей денної та заочної форми навчання. – Кропивницький: Видавець – Лисенко В.Ф., 2019. – 156 с
3. В.М. Ільман, О.П. Іванов, Л.О. Панік. Алгоритми, дані і структури. Навч. посіб. / Дніпропет. нац.. ун-т залізн. трансп.ім. акад. В. Лазаряна. – Дніпро, 2019. – 134 с.
4. Коротєєва Т.О. Алгоритми та структури даних. - Навчальний посібник. Львів: Видавництво Львівської політехніки, 2014. 280 с.
Уніфікований додаток: Національний університет «Львівська політехніка» забезпечує реалізацію права осіб з інвалідністю на здобуття вищої освіти. Інклюзивні освітні послуги надає Служба доступності до можливостей навчання «Без обмежень», метою діяльності якої є забезпечення постійного індивідуального супроводу навчального процесу студентів з інвалідністю та хронічними захворюваннями. Важливим інструментом імплементації інклюзивної освітньої політики в Університеті є Програма підвищення кваліфікації науково-педагогічних працівників та навчально-допоміжного персоналу у сфері соціальної інклюзії та інклюзивної освіти. Звертатися за адресою:
вул. Карпінського, 2/4, І-й н.к., кімн. 112
E-mail: nolimits@lpnu.ua
Websites: https://lpnu.ua/nolimits https://lpnu.ua/integration
Академічна доброчесність: Політика щодо академічної доброчесності учасників освітнього процесу формується на основі дотримання принципів академічної доброчесності з урахуванням норм «Положення про академічну доброчесність у Національному університеті «Львівська політехніка» (затверджене вченою радою університету від 20.06.2017 р., протокол № 35).