Алгоритми і структури даних

Спеціальність: Комп'ютерні науки (Обчислювальний інтелект смарт-систем)
Код дисципліни: 6.122.11.O.011
Кількість кредитів: 6.00
Кафедра: Автоматизовані системи управління
Лектор: к.т.н., доц. Шпак Зореслава Ярославівна
Семестр: 2 семестр
Форма навчання: денна
Результати навчання: • знати: властивості алгоритмів, методи оцінки їх ефективності та складності; алгоритми швидкого сортування і пошуку даних; організацію динамічних структур даних: списки, черги, дерева, хеш-таблиці, словники; різновиди графів і способи обходу графа; алгоритми пошуку найкоротших шляхів та інші важливі задачі на графах; методи розробки алгоритмів: жадібні алгоритми, "поділяй і владарюй", динамічне програмування, пошук з поверненням, евристичні алгоритми; основні геометричні алгоритми; • уміти: використовувати динамічну пам’ять для збереження даних; програмно реалізовувати задачі опрацювання динамічних структур даних; розв’язувати задачі на графах; застосовувати відомі алгоритми та структури даних для програмування різноманітних інформаційних задач; аналізувати складність алгоритмів; аргументувати прийняті рішення, системно і творчо мислити, генерувати нові ідеї.
Необхідні обов'язкові попередні та супутні навчальні дисципліни: • пререквізити: Основи програмування; Дискретна математика • кореквізити: Об’єктно-орієнтоване програмування
Короткий зміст навчальної програми: Властивості алгоритмів. Оцінка ефективності та складності алгоритмів. Аналіз алгоритмів сортування і пошуку даних. Рекурсивні алгоритми та функції. Застосування рекурсії. Метод "поділяй і владарюй". Жадібні алгоритми. Використання динамічної пам’яті для збереження даних. Статичні і динамічні масиви вказівників на дані. Динамічні списки, черги, стеки, деки. Програмування одно- і двозв’язних списків. Динамічні дерева. Двійкові дерева пошуку. Балансування дерева. Червоно-чорні дерева. Розріджені масиви і множини даних, способи реалізації. Хеш-таблиці, способи побудови та доступу до даних. Словники. Різновиди графів. Способи обходу графа. Алгоритми пошуку найкоротших шляхів. Побудова остовних дерев. Топологічне сортування. Пошук циклів у графі. Складні задачі на графах. Задачі обробки текстової інформації. Алгоритми пошуку символьних підрядків. Стиснення даних. Синтаксичний розбір виразів і текстів. Методи розробки алгоритмів: динамічне програмування, пошук з поверненням, метод гілок і границь, еврістичні алгоритми, локальний пошук. Геометричні алгоритми: площі та об’єми багатогранників, обчислення опуклої оболонки, пошук віддалей та інші.
Методи та критерії оцінювання: • Поточний контроль (38 балів): виконання лабораторних робіт, контрольні опитування, розрахунково-графічна робота. • Підсумковий контроль (62 бали): екзамен.
Рекомендована література: • Шпак З.Я. Програмування мовою С. – Львів: Видав-во Львівської політехніки, 2011. – 436 с. • Кормен Т. Г. Алгоритми доступно: Пер. з англ. – К.: Вид-во К.І.С., 2021. – 194 с. • Ковалюк Т. В.. Алгоритмізація та програмування: Підручник. – Львів: «Магнолія 2006», 2021. – 400 с. • Кормен Т., Лейзерсон Ч., Рівест Р., Стайн К. Вступ до алгоритмів: Пер. з англ. – К.: К.І.С., 2019. – 1288 с. • Скиена С. Алгоритмы. Руководство по разработке: Пер. с англ. – К.: БХВ-Киев, 2020. – 720 с. • Н. Б. Шаховська, Р. О. Голощук. Алгоритми і структури даних. – Львів: «Магнолія 2006», 2021. – 216 с. • Хэзфилд Р., Кирби Л. Искусство программирования на Си. Фундаментальные алгоритмы, структуры данных и примеры приложений. Энциклопедия программиста: Пер. с англ. – К.: Изд-во “ДиаСофт”, 2001. – 736 с. • Ахо А., Хопкрофт Д., Ульман Д. Структуры данных и алгоритмы: Пер. с англ. – К.: Изд. дом «Вильямс», 2007. – 384 с.
Уніфікований додаток: Національний університет «Львівська політехніка» забезпечує реалізацію права осіб з інвалідністю на здобуття вищої освіти. Інклюзивні освітні послуги надає Служба доступності до можливостей навчання «Без обмежень», метою діяльності якої є забезпечення постійного індивідуального супроводу навчального процесу студентів з інвалідністю та хронічними захворюваннями. Важливим інструментом імплементації інклюзивної освітньої політики в Університеті є Програма підвищення кваліфікації науково-педагогічних працівників та навчально-допоміжного персоналу у сфері соціальної інклюзії та інклюзивної освіти. Звертатися за адресою: вул. Карпінського, 2/4, І-й н.к., кімн. 112 E-mail: nolimits@lpnu.ua Websites: https://lpnu.ua/nolimits https://lpnu.ua/integration
Академічна доброчесність: Політика щодо академічної доброчесності учасників освітнього процесу формується на основі дотримання принципів академічної доброчесності з урахуванням норм «Положення про академічну доброчесність у Національному університеті «Львівська політехніка» (затверджене вченою радою університету від 20.06.2017 р., протокол № 35).