Алгоритми та структури даних (курсова робота)
Спеціальність: Системна інженерія (Інтернет речей)
Код дисципліни: 6.122.09.O.019
Кількість кредитів: 2.00
Кафедра: Комп'ютеризовані системи автоматики
Лектор: Верес Зеновій Євгенович
Семестр: 3 семестр
Форма навчання: денна
Завдання: Вивчення навчальної дисципліни передбачає формування та розвиток у студентів компетентностей:
загальні компетентності:
ЗК6. Здатність вчитися й оволодівати сучасними знаннями.
ЗК7. Здатність до пошуку, оброблення та аналізу інформації з різних джерел.
ЗК8. Здатність генерувати нові ідеї (креативність).
ЗК10. Здатність бути критичним і самокритичним.
ЗК11. Здатність приймати обґрунтовані рішення.
Фахові компетенції:
СК3. Здатність до логічного мислення, побудови логічних висновків, використання формальних мов і моделей алгоритмічних обчислень, проектування, розроблення й аналізу алгоритмів, оцінювання їх ефективності та складності, розв’язності та нерозв’язності алгоритмічних проблем для адекватного моделювання предметних областей і створення програмних та інформаційних систем.
СК8. Здатність проектувати та розробляти програмне забезпечення із застосуванням різних парадигм програмування: узагальненого, об’єктно-орієнтованого, функціонального, логічного, з відповідними моделями, методами й алгоритмами обчислень, структурами даних і механізмами управління.
Результати навчання: У результаті вивчення навчальної дисципліни здобувач освіти повинен бути здатним продемонструвати такі результати навчання:
знати:
- алгоритми сортування, пошуку даних, роботи з графами, динамічного програмування, роботи з стрічками;
вміти:
- Реалізовувати засвоєні поняття, концепції, теорії та методи вінтелектуальній і практичній діяльності в галузі комп’ютерних наук, осмислювати зміст і послідовність застосування способів виконання дій, узагальнювати і систематизовувати результати робіт.
- Проявляти допитливість, схильність до ризику, вміння мислити,надихатись новими ідеями, втілювати їх, запалювати ними оточуючих, комбінувати та експериментувати.
- Реалізовувати засвоєні поняття, концепції, теорії та методи в інтелектуальній і практичній діяльності в галузі комп’ютерних наук, осмислювати зміст і послідовність застосування способів виконання дій, узагальнювати і систематизовувати результати робіт.
Необхідні обов'язкові попередні та супутні навчальні дисципліни: Алгоритмізація і програмування, ч. 1
Алгоритмізація і програмування, ч. 2
Мікроконтролери, ч. 1
Короткий зміст навчальної програми: Алгоритми та структури даних є основою, на якій будується будь-яке програмне забезпечення. Їхнє знання, розуміння та вміння застосувати є критично необхідним для розробника програмного забезпечення в будь-якій галузі. Оволодіння даним предметом дасть можливість майбутньому інженеру створювати якісні, швидкі та ефективні програмні рішення в будь-якому напрямку.
Навчальна дисципліна є інструментальною основою для виконання аналітичної частини подальших дисциплін, а також курсових робіт.
Навчальна дисципліна Алгоритми та структури даних відноситься до циклу загальної підготовки навчальної програми бакалавра за спеціальністю 122 Комп’ютерні науки та інформаційні технології (спеціалізація Системна інженерія (інтернет речей)).
Опис: 1. Візуалізація роботи алгоритмів обходу графу
2. Візуалізація роботи структур даних
Методи та критерії оцінювання: 1. Курсова робота
Критерії оцінювання результатів навчання: 1. Курсова робота - 100
Порядок та критерії виставляння балів та оцінок: 100–88 балів – («відмінно») виставляється за високий рівень знань (допускаються деякі неточності) навчального матеріалу компонента, що міститься в основних і додаткових рекомендованих літературних джерелах, вміння аналізувати явища, які вивчаються, у їхньому взаємозв’язку і роз витку, чітко, лаконічно, логічно, послідовно відповідати на поставлені запитання, вміння застосовувати теоретичні положення під час розв’язання практичних задач; 87–71 бал – («добре») виставляється за загалом правильне розуміння навчального матеріалу компонента, включаючи розрахунки , аргументовані відповіді на поставлені запитання, які, однак, містять певні (неістотні) недоліки, за вміння застосовувати теоретичні положення під час розв’язання практичних задач; 70 – 50 балів – («задовільно») виставляється за слабкі знання навчального матеріалу компонента, неточні або мало аргументовані відповіді, з порушенням послідовності викладення, за слабке застосування теоретичних положень під час розв’язання практичних задач; 49–26 балів – («не атестований» з можливістю повторного складання семестрового контролю) виставляється за незнання значної частини навчального матеріалу компонента, істотні помилки у відповідях на запитання, невміння застосувати теоретичні положення під час розв’язання практичних задач; 25–00 балів – («незадовільно» з обов’язковим повторним вивченням) виставляється за незнання значної частини навчального матеріалу компонента, істотні помилки у відповідях на запитання, невміння орієнтуватися під час розв’язання практичних задач, незнання основних фундаментальних положень.
Рекомендована література: 1. Коротєєва Т. О. Алгоритми та структури даних / Т. О. Коротєєва. – Львів: Видавництво Львівської політехніки, 2014. – 280 с.
2. Skiena S. S. The Algorithm Design Manual second edition / Steven Skiena., 2008. – 730 с.
3. Wayne K. Algorithms (4th Edition) / K. Wayne, R. Sedgewick., 2011. – 992 с.
4. Introduction to Algorithms, 3rd Edition / T. H.Cormen, C. E. Leiserson, R. L. Rivest, C. Stein., 2009. – 1312 с.
Допоміжна
1. Coursera: Tim Roughgarden (Stanford) — Algorithms: Design and Analysis, Part 1. https://www.coursera.org/course/algo
2. Coursera: Tim Roughgarden (Stanford) — Algorithms: Design and Analysis, Part 2. https://www.coursera.org/course/algo
Уніфікований додаток: Національний університет «Львівська політехніка» забезпечує реалізацію права осіб з інвалідністю на здобуття вищої освіти. Інклюзивні освітні послуги надає Служба доступності до можливостей навчання «Без обмежень», метою діяльності якої є забезпечення постійного індивідуального супроводу навчального процесу студентів з інвалідністю та хронічними захворюваннями. Важливим інструментом імплементації інклюзивної освітньої політики в Університеті є Програма підвищення кваліфікації науково-педагогічних працівників та навчально-допоміжного персоналу у сфері соціальної інклюзії та інклюзивної освіти. Звертатися за адресою:
вул. Карпінського, 2/4, І-й н.к., кімн. 112
E-mail: nolimits@lpnu.ua
Websites: https://lpnu.ua/nolimits https://lpnu.ua/integration
Академічна доброчесність: Політика щодо академічної доброчесності учасників освітнього процесу формується на основі дотримання принципів академічної доброчесності з урахуванням норм «Положення про академічну доброчесність у Національному університеті «Львівська політехніка» (затверджене вченою радою університету від 20.06.2017 р., протокол № 35).
Алгоритми та структури даних
Спеціальність: Системна інженерія (Інтернет речей)
Код дисципліни: 6.122.09.O.020
Кількість кредитів: 4.00
Кафедра: Комп'ютеризовані системи автоматики
Лектор: Верес Зеновій Євгенович
Семестр: 3 семестр
Форма навчання: денна
Завдання: Вивчення навчальної дисципліни передбачає формування та розвиток у студентів компетентностей:
загальні компетентності:
ЗК6. Здатність вчитися й оволодівати сучасними знаннями.
ЗК7. Здатність до пошуку, оброблення та аналізу інформації з різних джерел.
ЗК8. Здатність генерувати нові ідеї (креативність).
ЗК10. Здатність бути критичним і самокритичним.
ЗК11. Здатність приймати обґрунтовані рішення.
Фахові компетенції:
СК3. Здатність до логічного мислення, побудови логічних висновків, використання формальних мов і моделей алгоритмічних обчислень, проектування, розроблення й аналізу алгоритмів, оцінювання їх ефективності та складності, розв’язності та нерозв’язності алгоритмічних проблем для адекватного моделювання предметних областей і створення програмних та інформаційних систем.
СК8. Здатність проектувати та розробляти програмне забезпечення із застосуванням різних парадигм програмування: узагальненого, об’єктно-орієнтованого, функціонального, логічного, з відповідними моделями, методами й алгоритмами обчислень, структурами даних і механізмами управління.
Результати навчання: У результаті вивчення навчальної дисципліни здобувач освіти повинен бути здатним продемонструвати такі результати навчання:
знати:
- алгоритми сортування, пошуку даних, роботи з графами, динамічного програмування, роботи з стрічками;
вміти:
- Реалізовувати засвоєні поняття, концепції, теорії та методи вінтелектуальній і практичній діяльності в галузі комп’ютерних наук, осмислювати зміст і послідовність застосування способів виконання дій, узагальнювати і систематизовувати результати робіт.
- Проявляти допитливість, схильність до ризику, вміння мислити,надихатись новими ідеями, втілювати їх, запалювати ними оточуючих, комбінувати та експериментувати.
- Реалізовувати засвоєні поняття, концепції, теорії та методи в інтелектуальній і практичній діяльності в галузі комп’ютерних наук, осмислювати зміст і послідовність застосування способів виконання дій, узагальнювати і систематизовувати результати робіт.
Необхідні обов'язкові попередні та супутні навчальні дисципліни: Алгоритмізація і програмування, ч. 1
Алгоритмізація і програмування, ч. 2
Мікроконтролери, ч. 1
Короткий зміст навчальної програми: Алгоритми та структури даних є основою, на якій будується будь-яке програмне забезпечення. Їхнє знання, розуміння та вміння застосувати є критично необхідним для розробника програмного забезпечення в будь-якій галузі. Оволодіння даним предметом дасть можливість майбутньому інженеру створювати якісні, швидкі та ефективні програмні рішення в будь-якому напрямку.
Навчальна дисципліна є інструментальною основою для виконання аналітичної частини подальших дисциплін, а також курсових робіт.
Навчальна дисципліна Алгоритми та структури даних відноситься до циклу загальної підготовки навчальної програми бакалавра за спеціальністю 122 Комп’ютерні науки та інформаційні технології (спеціалізація Системна інженерія (інтернет речей)).
Опис: ТРИ ЗАПИТАННЯ ДЛЯ АНАЛІЗУ АЛГОРИТМІВ. АСИМПТОТИЧНИЙ АНАЛІЗ ЧАСУ І ПРОСТОРУ.
Як доводити коректність алгоритмів. Як визначати їхню швидкість та ресурсоємкість, не реалізовуючи їх. Навіщо потрібен асимптотичний аналіз та його види (О-велике, Омега-велике, Тета-велике). Як порівнювати два алгоритми та визначити, котрий із них кращий. Властивості О-нотації (константи, члени нижчих порядків).
АЛГОРИТМИ СОРТУВАННЯ
Формулювання задачі сортування. Сортування вибором, вставкою, бульбашкою, їхні плюси й мінуси. Як вони поводяться на вироджених випадках. Чому примітивні алгоритми бувають корисними. Парадигма "Розділяй і владарюй". MergeSort. В чому суть “Розділяй і владарюй”. Застосування Розділяй і владарюй до сортування — MergeSort. Аналіз переваг і недоліків MergeSort. Оптимізації MergeSort — економія виділень пам’яті, bottom-up підхід. Оптимальність comparison-based алгоритмів (неможливо швидше, ніж O(N log N)). Рандомізовані алгоритми. Quicksort.
ДЕРЕВОВИДНІ СТРУКТУРИ ПОШУКУ. БІНАРНИЙ ПОШУК. САМОБАЛАНСОВАНІ ДЕРЕВА.
В чому полягає задача пошуку. Впорядковані дані і бінарний пошук. Бінарні дерева пошуку. Проблема з незбалансованістю та як її вирішують самобалансовані дерева. Індекси в базах даних.
ХЕШ-ТАБЛИЦІ.
Мотивація (як створити асоціативний масив). Призначення хеш-функції та як вона застосовується у хеш-таблиці. Хороші та погані хеш-функції. Стратегії роботи з колізіями у хеш-таблицях. Функція hashCode та реалізація хеш-таблиць у системних бібліотеках.
ГРАФИ.
Представлення в пам'яті та в коді. Обхід (BFS, DFS). Для чого потрібні графи. Які бувають графи (неорієнтовані, орієнтовані, мультиграфи, зважені). Представлення графів матрицею суміжності та списком ребер, аналіз ефективності. Обхід в ширину та глибину: відмінності поведінки та реалізації (черга vs стек).
ЗАСТОСУВАННЯ BFS ТА DFS: НАЙКОРОТШІ ШЛЯХИ, ГЕНЕРАЦІЯ ЛАБІРИНТІВ.
Як за допомогою DFS генерувати лабіринти. Чому DFS підходить для цього краще, ніж BFS.
ЗНАХОДЖЕННЯ ШЛЯХУ В ЛАБІРИНТІ. Як за допомогою BFS знаходити найкоротші шляхи у незваженому графі, і, як наслідок, вихід із лабіринту.
НАЙКОРОТШІ ШЛЯХИ У ЗВАЖЕНИХ ГРАФАХ. АЛГОРИТМ ДЕЙКСТРИ.
Чому BFS не підійде для зважених графів. Принцип роботи алгоритму Дейкстри. Чому алгоритм Дейкстри не працюватиме для ребер від’ємної ваги. Оптимізація часу виконання за допомогою heap.
ЗНАХОДЖЕННЯ ШЛЯХІВ У ІГРОВИХ АЛГОРИТМАХ. ЕВРИСТИКИ.
Алгоритм A*. Яким чином A* допомагає швидше знаходити цільову вершину в графі. Суть функції евристичної оцінки. Чому алгоритм Дейкстри є частковим випадком A*.
НАПРЯМЛЕНІ АЦИКЛІЧНІ ГРАФИ (DAG)
Як знаходити компоненти зв’язності на графі. Сильна та слабка зв’язаність у напрямлених графах. Алгоритми знаходження сильно зв’язаних компонентів. Задача топологічного сортування, де вона зустрічається в реальному житті та чому вона існує тільки для DAG.
ВСТУП ДО ДИНАМІЧНОГО ПРОГРАМУВАННЯ.
Задача Max-Weight Independent Set on Path Graphs (приклад із розкладом кінотеатру). Суть динамічного програмування. Мемоізація проміжних розв’язків.
НАЙКОРОТШІ ШЛЯХИ ТА ДИНАМІЧНЕ ПРОГРАМУВАННЯ.
Задача рюкзака (Knapsack). Вирішення Knapsack методом динамічного програмування для цілочисельних ваг. Застосування динамічного програмування для Single-Source Shortest Paths (алгоритм Беллмана-Форда).
АЛГОРИТМИ ОБРОБКИ ТЕКСТУ. АЛГОРИТМИ СТИСКАННЯ ДАНИХ.
Edit Distance (Hamming Distance, Levenshtein Distance, Damerau-Levenshtein Distance). Короткий огляд того, як працюють регулярні вирази (створення NFA, компіляція NFA в DFA).
Алгоритм Хаффмана. Алгоритми стискання з втратами і без (приклади форматів зображень, аудіо, відео).
NP-ПОВНІ ЗАДАЧІ. ЗАДАЧА ЗУПИНКИ.
Зведення однієї задачі до іншої. Клас задач P. Чому Knapsack не є P-задачею. Критерії NP-задач. Decision- та optimization-версія задачі Knapsack. Клас NP-hard. Клас NP-Complete. Проблема “P vs. NP”. Halting Problem як приклад нерозв’язуваної NP-Hard задачі. Сучасні невирішені задачі та майбутнє світу алгоритмів.
Методи та критерії оцінювання: 1. Лабораторні роботи.
2. Екзамен.
Критерії оцінювання результатів навчання: 1. Лабораторні роботи 45
2. Екзамен - 55
Порядок та критерії виставляння балів та оцінок: 100–88 балів – («відмінно») виставляється за високий рівень знань (допускаються деякі неточності) навчального матеріалу компонента, що міститься в основних і додаткових рекомендованих літературних джерелах, вміння аналізувати явища, які вивчаються, у їхньому взаємозв’язку і роз витку, чітко, лаконічно, логічно, послідовно відповідати на поставлені запитання, вміння застосовувати теоретичні положення під час розв’язання практичних задач; 87–71 бал – («добре») виставляється за загалом правильне розуміння навчального матеріалу компонента, включаючи розрахунки , аргументовані відповіді на поставлені запитання, які, однак, містять певні (неістотні) недоліки, за вміння застосовувати теоретичні положення під час розв’язання практичних задач; 70 – 50 балів – («задовільно») виставляється за слабкі знання навчального матеріалу компонента, неточні або мало аргументовані відповіді, з порушенням послідовності викладення, за слабке застосування теоретичних положень під час розв’язання практичних задач; 49–26 балів – («не атестований» з можливістю повторного складання семестрового контролю) виставляється за незнання значної частини навчального матеріалу компонента, істотні помилки у відповідях на запитання, невміння застосувати теоретичні положення під час розв’язання практичних задач; 25–00 балів – («незадовільно» з обов’язковим повторним вивченням) виставляється за незнання значної частини навчального матеріалу компонента, істотні помилки у відповідях на запитання, невміння орієнтуватися під час розв’язання практичних задач, незнання основних фундаментальних положень.
Рекомендована література: 1. Коротєєва Т. О. Алгоритми та структури даних / Т. О. Коротєєва. – Львів: Видавництво Львівської політехніки, 2014. – 280 с.
2. Skiena S. S. The Algorithm Design Manual second edition / Steven Skiena., 2008. – 730 с.
3. Wayne K. Algorithms (4th Edition) / K. Wayne, R. Sedgewick., 2011. – 992 с.
4. Introduction to Algorithms, 3rd Edition / T. H.Cormen, C. E. Leiserson, R. L. Rivest, C. Stein., 2009. – 1312 с.
Допоміжна
1. Coursera: Tim Roughgarden (Stanford) — Algorithms: Design and Analysis, Part 1. https://www.coursera.org/course/algo
2. Coursera: Tim Roughgarden (Stanford) — Algorithms: Design and Analysis, Part 2. https://www.coursera.org/course/algo
Уніфікований додаток: Національний університет «Львівська політехніка» забезпечує реалізацію права осіб з інвалідністю на здобуття вищої освіти. Інклюзивні освітні послуги надає Служба доступності до можливостей навчання «Без обмежень», метою діяльності якої є забезпечення постійного індивідуального супроводу навчального процесу студентів з інвалідністю та хронічними захворюваннями. Важливим інструментом імплементації інклюзивної освітньої політики в Університеті є Програма підвищення кваліфікації науково-педагогічних працівників та навчально-допоміжного персоналу у сфері соціальної інклюзії та інклюзивної освіти. Звертатися за адресою:
вул. Карпінського, 2/4, І-й н.к., кімн. 112
E-mail: nolimits@lpnu.ua
Websites: https://lpnu.ua/nolimits https://lpnu.ua/integration
Академічна доброчесність: Політика щодо академічної доброчесності учасників освітнього процесу формується на основі дотримання принципів академічної доброчесності з урахуванням норм «Положення про академічну доброчесність у Національному університеті «Львівська політехніка» (затверджене вченою радою університету від 20.06.2017 р., протокол № 35).