Алгоритми та структури даних
Спеціальність: Інженерія програмного забезпечення
Код дисципліни: 6.121.00.O.015
Кількість кредитів: 4.00
Кафедра: Програмне забезпечення
Лектор: доцент Коротєєва Тетяна Олександрівна
Семестр: 3 семестр
Форма навчання: денна
Завдання: Вивчення навчальної дисципліни передбачає формування у здобувачів освіти компетентностей:
загальні компетентності:
1. Здатність до абстрактно мислення, аналізу та синтезу. (К01)
фахові компетентності:
1. Здатність застосовувати і розвивати фундаментальні і міждисциплінарні знання для
успішного розв’язання завдань інженерії програмного забезпечення. (К20)
2. Здатність до алгоритмічного та логічного мислення. (К26)
Результати навчання: 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. Екзаменаційний контроль (письмова компонента, усна компонента).
Критерії оцінювання результатів навчання: • поточний контроль включає захист 11 лабораторних робіт з усним опитуванням та письмовими звітами (3+4+4+4+4+3+4+5+4+5+5=45 %) . Для захисту лабораторних з балами встановлюються крайні терміни. За межами крайніх термінів роботи оцінюються в 0 балів;
• підсумковий контроль - екзамен: письмово-усна форма (50+5=55%)
Порядок та критерії виставляння балів та оцінок: 100–88 балів – («відмінно») виставляється за високий рівень знань (допускаються деякі неточності) навчального матеріалу компонента, що міститься в основних і додаткових рекомендованих літературних джерелах, вміння аналізувати явища, які вивчаються, у їхньому взаємозв’язку і роз витку, чітко, лаконічно, логічно, послідовно відповідати на поставлені запитання, вміння застосовувати теоретичні положення під час розв’язання практичних задач; 87–71 бал – («добре») виставляється за загалом правильне розуміння навчального матеріалу компонента, включаючи розрахунки , аргументовані відповіді на поставлені запитання, які, однак, містять певні (неістотні) недоліки, за вміння застосовувати теоретичні положення під час розв’язання практичних задач; 70 – 50 балів – («задовільно») виставляється за слабкі знання навчального матеріалу компонента, неточні або мало аргументовані відповіді, з порушенням послідовності викладення, за слабке застосування теоретичних положень під час розв’язання практичних задач; 49–26 балів – («не атестований» з можливістю повторного складання семестрового контролю) виставляється за незнання значної частини навчального матеріалу компонента, істотні помилки у відповідях на запитання, невміння застосувати теоретичні положення під час розв’язання практичних задач; 25–00 балів – («незадовільно» з обов’язковим повторним вивченням) виставляється за незнання значної частини навчального матеріалу компонента, істотні помилки у відповідях на запитання, невміння орієнтуватися під час розв’язання практичних задач, незнання основних фундаментальних положень.
Рекомендована література: 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).