Алгоритмізація та програмування, частина 2
Спеціальність: Комп'ютерні науки (Проектування і програмування інтелектуальних систем та пристроїв)
Код дисципліни: 6.122.12.O.010
Кількість кредитів: 7.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 с.
Уніфікований додаток: Національний університет «Львівська політехніка» забезпечує реалізацію права осіб з інвалідністю на здобуття вищої освіти. Інклюзивні освітні послуги надає Служба доступності до можливостей навчання «Без обмежень», метою діяльності якої є забезпечення постійного індивідуального супроводу навчального процесу студентів з інвалідністю та хронічними захворюваннями. Важливим інструментом імплементації інклюзивної освітньої політики в Університеті є Програма підвищення кваліфікації науково-педагогічних працівників та навчально-допоміжного персоналу у сфері соціальної інклюзії та інклюзивної освіти. Звертатися за адресою:
вул. Карпінського, 2/4, І-й н.к., кімн. 112
E-mail: nolimits@lpnu.ua
Websites: https://lpnu.ua/nolimits https://lpnu.ua/integration
Академічна доброчесність: Політика щодо академічної доброчесності учасників освітнього процесу формується на основі дотримання принципів академічної доброчесності з урахуванням норм «Положення про академічну доброчесність у Національному університеті «Львівська політехніка» (затверджене вченою радою університету від 20.06.2017 р., протокол № 35).