Алгоритми та структури даних
Спеціальність: Інженерія програмного забезпечення
Код дисципліни: 6.121.00.O.016
Кількість кредитів: 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-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).