Алгоритмізація та програмування, частина 2
Спеціальність: Комп'ютерні науки
Код дисципліни: 6.122.00.O.018
Кількість кредитів: 5.00
Кафедра: Автоматизовані системи управління
Лектор: к.т.н., доц. Шпак Зореслава Ярославівна
Семестр: 2 семестр
Форма навчання: денна
Результати навчання: • знати форми організації даних, зокрема, динамічні масиви і масиви вказівників;
• знати базові алгоритми швидкого сортування даних;
• знати динамічні стуктури даних: списки, динамічні дерева, хеш-таблиці;
• знати алгоритми опрацювання графів, зокрема, обходу графа, пошуку найкоротших шляхів, сіткового планування та інші;
• знати методи пошуку даних у текстах та синтаксичного розбору виразів;
• уміти критично аналізувати інформацію, отриману з різних джерел;
• уміти здійснювати постановку задачі та вибір оптимальних методів її розв’язування;
• володіти іструментальними засобами iнтегрованих середовищах програмування;
• уміти застосовувати набуті знання для програмування різнотипних обчислювальних та інформацiйних задач;
• уміти аргументувати прийняті рішення, системно і творчо мислити, генерувати нові ідеї.
Необхідні обов'язкові попередні та супутні навчальні дисципліни: • пререквізити: Алгоритмізація та програмування, част. 1
• кореквізити: Об’єктно-орієнтоване програмування
Короткий зміст навчальної програми: Функції. Взаємодія формальних і фактичних параметрів. Рекурсивні функції. Функції з неоголошеними параметрами. Обмін даними з дисковими файлами. Редагування вмісту файла. Робота з динамічною пам’яттю. Одно- і двозв’язні динамічні списки. Програмування хеш-таблиць та хеш-функцій. Двійкові дерева пошуку, програмування та застосування. Червоно-чорні дерева. Різновиди графів. Способи обходу графа. Типові задачі на графах. Алгоритми пошуку підрядків. Регулярні вирази. Синтаксичний розбір виразів і текстів.
Методи та критерії оцінювання: • Поточний контроль (38 балів): виконання лабораторних робіт, контрольні опитування, розрахунково-графічна робота.
• Підсумковий контроль (62 бали): екзамен.
Рекомендована література: 1. Шпак З.Я. Програмування мовою С. – Львів: Видав-во Львівської політехніки, 2011. – 436 с.
2. Ковалюк Т. В.. Алгоритмізація та програмування: Підручник. – Львів: «Магнолія 2006», 2021. – 400 с.
3. Кормен Т., Лейзерсон Ч., Рівест Р., Стайн К. Вступ до алгоритмів: Пер. з англ. – К.: К.І.С., 2019. – 1288 с.
4. Шилдт Г. Полный справочник по С: Пер. с англ. – М.: Вильямс, 2009. – 704 с.
5. Хэзфилд Р., Кирби Л. Искусство программирования на Си. Фундаментальные алгоритмы, структуры данных и примеры приложений. Энциклопедия программиста: Пер. с англ. – К.: Изд-во “ДиаСофт”, 2001. – 736 с.
6. Скиена С. Алгоритмы. Руководство по разработке: Пер. с англ. – К.: БХВ-Киев, 2016. 720 с.
7. Ахо А., Хопкрофт Д., Ульман Д. Структуры данных и алгоритмы: Пер. с англ. – М.: Вильямс, 2016. – 400 с.
Уніфікований додаток: Національний університет «Львівська політехніка» забезпечує реалізацію права осіб з інвалідністю на здобуття вищої освіти. Інклюзивні освітні послуги надає Служба доступності до можливостей навчання «Без обмежень», метою діяльності якої є забезпечення постійного індивідуального супроводу навчального процесу студентів з інвалідністю та хронічними захворюваннями. Важливим інструментом імплементації інклюзивної освітньої політики в Університеті є Програма підвищення кваліфікації науково-педагогічних працівників та навчально-допоміжного персоналу у сфері соціальної інклюзії та інклюзивної освіти. Звертатися за адресою:
вул. Карпінського, 2/4, І-й н.к., кімн. 112
E-mail: nolimits@lpnu.ua
Websites: https://lpnu.ua/nolimits https://lpnu.ua/integration
Академічна доброчесність: Політика щодо академічної доброчесності учасників освітнього процесу формується на основі дотримання принципів академічної доброчесності з урахуванням норм «Положення про академічну доброчесність у Національному університеті «Львівська політехніка» (затверджене вченою радою університету від 20.06.2017 р., протокол № 35).
Алгоритмізація та програмування, частина 2
Спеціальність: Комп'ютерні науки
Код дисципліни: 6.122.00.O.020
Кількість кредитів: 5.00
Кафедра: Системи штучного інтелекту
Лектор: Засоба Є.
Семестр: 2 семестр
Форма навчання: денна
Результати навчання: знати:
- набір найпоширеніших алгоритмів
- набір найпоширеніших структур даних
вміти:
- адаптувати відомі алгоритми та структури даних під конкретні задачі
- розробляти нові алгоритми ти структури даних
- аналізувати складність алгоритмів
Необхідні обов'язкові попередні та супутні навчальні дисципліни: Математичний аналіз
Алгоритмізація та програмування
Дискретна математика
Короткий зміст навчальної програми: Основи амортизаційного аналізу. О-нотації P-NP алгоритми. Перегляд Жадібних алгоритмів. Поняття поліноміальної та експоненційної складності. Еквівалентність алгоритмів НП. Двійковий та трійковий пошук. Монотонна функція як необхідна та достатня умова для двоичного пошуку. Сортування. Опис сортування: бульбашка, підрахунок, швидке злиття. Оцінки складності, обмеження застосування та порівняльний аналіз. Відправлення до іншого N log N сортування (піраміда, дерево)
Динамічне програмування. Загальна ідея ДП. Три необхідних умови для ефективності методу: вирішення проблем для підзадач, перетин підзадань, тривіальні підзадачі. Створення ДП з вершини вниз і знизу вгору. Алгоритми на стрічках. Функція Hash Двійкове дерево. Застосування та оцінка складності середньостатистичної ситуації. Оцінка складності найгіршого випадку. Збалансоване подвійне дерево. Чорні та червоні дерева. Купа. Дерево відрізків. Геометричні алгоритми. Площа багатокутника та об'єм ного багатокутника. Випукла оболонка
Методи та критерії оцінювання: лабораторні роботи - 40
практичні роботи - 10
письмова компонента - 40
усна компонента – 10
Рекомендована література: 1. Cormen, Thomas H.; Leiserson, Charles E.; Rivest, Ronald L.; Stein, Clifford (2009) [1990]. Introduction to Algorithms (3rd ed.). MIT Press and McGraw-Hill. ISBN 0-262-03384-4.
2. Algorithms in C++, Parts 1-4: Fundamentals, Data Structure, Sorting, Searching, 3rd Edition. ISBN-10: 0201350882
3. Donald Knuth The Art of Computer Programming . — Addison-Wesley Professional, 2015. ISBN 978-0-13-439760-3.
4. kiena, Steven S, Revilla, Miguel A. Programming Challenges: The Programming Contest Training Manual
Алгоритмізація та програмування, частина 2
Спеціальність: Комп'ютерні науки
Код дисципліни: 6.122.00.O.019
Кількість кредитів: 5.00
Кафедра: Системи автоматизованого проектування
Лектор: д.т.н., професор каф. САП Андрійчук Михайло Ярославович
к.т.н., асистент каф. САП Оборська Оксана Володимирівна
Семестр: 2 семестр
Форма навчання: денна
Результати навчання: У результаті вивчення дисципліни, студент повинен знати:
1. поняття алгоритму та його властивості, загальні схеми побудови алгоритмічних систем;
2. основні способи композиції нормальних алгоритмів;
3. основні кількісні характеристики (сигнальні функції) алгоритмів;
4. означення алгоритмічної та обчислювальної складності масової проблеми;
5. поняття і приклад NP-повної проблеми;
6. принципи функціонування периферійних пристроїв.
Вміти:
1. використовувати базові структури даних;
2. використовувати дерева пошуку;
3. будувати нормальні алгоритми, композиції алгоритмів;
4. будувати програми для машин Поста і Тьюрінга;
5. будувати алгоритми сортування;
6. будувати алгоритми Флойда, Дейкстри, Пріма, Краскала;
7. проводити кластеризацію образів за допомогою алгоритмів розпізнавання;
8. будувати алгоритми пошуку.
Необхідні обов'язкові попередні та супутні навчальні дисципліни: пререквізити:
1. Алгоритмізація та програмування,
частина 1.
2. Основи програмування, частина 1.
3. Інноваційні інформаційні технології.
кореквізити:
1. Об’єктно-орієнтоване програмування.
2. Комп’ютерна графіка.
3. Операційні системи.
prerequisites:
Короткий зміст навчальної програми: Тема 1. Основні поняття теорії алгоритмів.
Поняття алгоритму та його властивості. Приклади алгоритмів. Необхідність формалізації поняття алгоритму.
Алгоритмічна система (модель обчислень), загальна схема її побудови. Граф-схеми і блок-схеми алгоритмів. Алфавітні алгоритми. Нормальні алгоритми Маркова. Приклади побудови нормальних алгоритмів.
Принцип нормалізації. Основні способи композиції нормальних алгоритмів. Поняття універсального нормального алгоритму. Теорема про універсальний нормальний алгоритм. Алгоритмічно нерозв’язні проблеми. Обчислювані функції. Елементарні арифметичні функції.
Примітивно рекурсивні функції, їх приклади.
Оператор мінімізації. Частково рекурсивні функції. Теза Черча. Машини Поста і Тюрінга. Структура і функціонування машин Поста і Тюрінга. Поняття команди, програми і конфігурації. Приклади побудови програм для машини Тюрінга. Універсальна машина Тюрінга. Теза Тюрінга. Проблема зупинки та її алгоритмічна нерозв’язність. Зв’язок рекурсивних функцій з машинами Тюрінга.
Тема 2. Аналіз ефективності і складності алгоритмів.
Використання процесора, пам’яті, дискового простору, мережі. Поняття часової складності. Сумування ряду Фібоначчі двома типами алгоритмів. Порівняння складності. Обчислення практичної складності алгоритмів. Оптимістичний, песимістичний та середні випадки. Нотація великого О. Асимптотична складність алгоритмів. Поліноміальні алгоритми vs. експоненційні алгоритми.
Тема 3. Елементарні обчислювальні структури. Бінарні дерева.
Черги, стеки, деки. Зв’язаний розподіл. Бінарні дерева. Ініціалізація. Вставляння елемента. Пошук. Видалення.
Тема 4. Бінарні дерева пошуку. Збалансовані бінарні дерева.
Бінарні дерева пошуку. Типи обходу дерев. Збалансовані бінарні дерева. 2-3 дерева. Ініціалізація. Вставляння елемента. Пошук. Видалення.
Тема 5. Червоно-чорні дерева.
Правила побудови червоно-чорних дерев. Обхід дерев.
Ініціалізація. Вставляння елемента. Пошук. Видалення.
Тема 6. Хеш таблиці.
Ініціалізація. Вставляння елемента. Пошук. Видалення. Обчислення хеш функцій. Вимоги до хеш функцій. Колізії. Методи лінійного зондування, подвійного хешування, зчеплення.
Тема 7. Алгоритми сортування.
Стійке і нестійке сортування. Бульбашкове сортування. Сортування вставками. Сортування вибором. Сортування Шелла. Сортування злиттям. Пірамідальне сортування. Швидке сортування.
Тема 8. Графи і алгоритми на графах.
Представлення графів. Досяжність у графах, знаходження найкоротших шляхів.
Тема 9. Жадібні алгоритми на графах.
Знаходження найкоротших шляхів. Алгоритми Флойда, Дейкстри, Прима, Краскала. Обхід графів.
Тема 10. Жадібні алгоритми. Алгоритм Хафмана.
Тема 11. Алгоритми класу поділяй і владарюй.
Алгоритм сортування Mergesort Quicksort.
Тема 12. Алгоритми класу поділяй і владарюй.
Множення чисел. Рекурентні співвідношення. Множення матриць.
Тема 13. Алгоритми пошуку.
Алгоритм грубої сили, алгоритми Кнута-Морріса-Пратта,
Боєра-Мура, Рабіна-Карпа
Тема 14. Алгоритми штучного інтелекту.
Алгоритми розпізнавання образів. Алгоритм порогової величини. Алгоритм К-внутрішніх групових середніх. Максимінний алгоритм. Альфа-бета алгоритм.
Методи та критерії оцінювання: лабораторні роботи - 40 балів, розрахункова робота- 8 балів.
екзамен-52 бали.
Рекомендована література: Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein. Introduction to algorithms. MIT Press, Cambridge, MA, third edition, 2009.
2. Donald E. Knuth. The art of computer programming. Vol. 3: Sorting and Searching. Addison-Wesley, Upper Saddle River, NJ, 1998.
3. Algorithms, 4th Edition by Robert Sedgewick, Kevin Wayne
4. Narasimha Karumanchi. Data Structures and Algorithms Made Easyю 2016 CareerMonk Publications and othersю
5. The Algorithm Design Manual, 2nd Edition by Steven S Skiena
6. Яворський Б.І. Теорія алгоритмів/Конспект лекцій.— Тернопіль: ТДТУ імені Івана Пулюя, 2000.— 36 с.