Теорія алгоритмів

Дисципліна «Теорія алгоритмів» спрямована на формування у студентів фундаментальних знань про принципи побудови, подання та аналізу алгоритмів, а також про їхні обчислювальні можливості та обмеження. У курсі розглядаються математичні моделі алгоритмів, такі як машини Тюрінга, рекурсивні функції, граматики та автомати. Значна увага приділяється поняттям алгоритмічної розв’язності й нерозв’язності, оцінці складності обчислень, класифікації задач за складністю та методам оптимізації алгоритмів.
Вивчення дисципліни забезпечує розуміння фундаментальних теоретичних засад інформатики та програмування, формує здатність аналізувати ефективність алгоритмів та обирати оптимальні методи розв’язання задач. Курс є базою для подальшого опанування сучасних напрямів комп’ютерних наук, зокрема штучного інтелекту, криптографії, теорії формальних мов та розроблення складних програмних систем.
Мета вивчення дисципліни: формування у студентів системного розуміння теоретичних основ алгоритмізації та обчислень, оволодіння методами побудови, аналізу й формального опису алгоритмів, а також засвоєння принципів визначення обчислювальної складності та алгоритмічної розв’язності задач. Дисципліна спрямована на розвиток здатності студентів застосовувати математичні моделі алгоритмів для дослідження властивостей обчислювальних процесів і раціонального вибору ефективних алгоритмічних рішень.
Основні завдання дисципліни: ознайомлення студентів із фундаментальними поняттями алгоритмізації та обчислювальних процесів, вивчення математичних моделей алгоритмів, таких як машини Тюрінга, рекурсивні функції, формальні граматики та автомати, а також формування вмінь аналізувати алгоритми, оцінювати їхню коректність та обчислювальну складність. Дисципліна покликана розкрити принципи класифікації задач за складністю, поняття алгоритмічної розв’язності й нерозв’язності, навчити застосовувати формальні методи опису алгоритмів і доведення їхніх властивостей. Важливим завданням є також розвиток навичок оптимізації алгоритмів та здатності обирати ефективні методи розв’язання задач, інтегруючи теоретичні знання у практичне програмування та дослідження складних обчислювальних процесів.
Практичне значення та використання отриманих знань, отриманих під час вивчення дисципліни «Теорія алгоритмів», полягає у здатності застосовувати фундаментальні алгоритмічні принципи для створення ефективних програмних рішень, оптимізації обчислювальних процесів та моделювання складних задач у різних галузях інформаційних технологій.
Засвоєні підходи до аналізу обчислювальної складності дозволяють обирати найбільш раціональні алгоритми, підвищувати продуктивність програмних систем та забезпечувати їх надійність. Знання математичних моделей алгоритмів і методів доведення їхніх властивостей допомагають у розробленні програмного забезпечення, побудові систем штучного інтелекту, комп’ютерної безпеки, криптографії, обробці даних та створенні оптимізаційних рішень.
Практичні навички, набуті під час вивчення дисципліни, формують здатність студентів системно мислити, аналізувати структуру задач і будувати ефективні, коректні та масштабовані алгоритмічні моделі в професійній діяльності.
Тематика та види навчальних занять
Для денної форми здобуття освіти
Лекційні заняття
Лекція 1. Вступ до теорії алгоритмів. Поняття алгоритму та його властивості.
Лекція 2. Формальні моделі подання алгоритмів. Алгоритмічні мови та псевдокод.
Лекція 3. Рекурсія та рекурсивні означення. Примітивно-рекурсивні функції.
Лекція 4. Машина Тюрінга: структура, принципи роботи, приклади програм.
Лекція 5. Еквівалентність моделей обчислень. Тезис Чорча–Тюрінга.
Лекція 6. Алгоритмічна розв’язність. Поняття обчислюваної функції.
Лекція 7. Нерозв’язні задачі. Проблема зупинки та її наслідки.
Лекція 8. Формальні мови і граматики. Ієрархія Хомського.
Лекція 9. Скінченні автомати та регулярні мови. Детерміновані й недетерміновані автомати.
Лекція 10. Контекстно-вільні граматики та стекові автомати.
Лекція 11. Алгоритми й структури даних: вплив вибору структур на складність.
Лекція 12. Асимптотичний аналіз алгоритмів. Часова та просторова складність.
Лекція 13. Складнісні класи P та NP. НП-повні задачі.
Лекція 14. Методи оптимізації алгоритмів: динамічне програмування, жадібні алгоритми, методи пошуку.
Лекція 15. Застосування теорії алгоритмів у сучасних технологіях: ШІ, криптографія, компілятори, моделювання.
Лабораторні роботи
Лабораторна робота №1. Алгоритми та їх властивості.
Мета заняття: засвоїти основні властивості алгоритмів, навчитися будувати алгоритми у формі блок-схем і псевдокоду.
Лабораторна робота №2. Рекурсивні алгоритми.
Мета заняття: вивчити принцип рекурсії та способи перетворення рекурсивних алгоритмів на ітеративні.
Лабораторна робота №3. Аналіз алгоритмів. Оцінка складності.
Мета заняття: навчитися визначати часову та просторову складність.
Лабораторна робота №4. Машина Тюрінга.
Мета заняття: ознайомитися з формальною моделлю обчислювального процесу ‒ Машиною Тюрінга; навчитися будувати таблицю переходів і моделювати роботу машини.
Лабораторна робота №5. Нормальні алгоритми Маркова.
Мета заняття: вивчити формальну систему підстановок Маркова та навчитися створювати алгоритми на основі продукційних правил.
Лабораторна робота №6. Динамічне програмування.
Мета заняття: опанувати метод оптимізації обчислень через таблицю підзадач.
Лабораторна робота №7. Алгоритми на графах.
Мета заняття: дослідити фундаментальні алгоритми пошуку та знаходження найкоротших шляхів.
Для заочної форми здобуття освіти
Лекційні заняття
Лекція 1. Вступ до теорії алгоритмів. Поняття алгоритму та його властивості. Формальні моделі подання алгоритмів. Алгоритмічні мови та псевдокод. Рекурсія та рекурсивні означення. Примітивно-рекурсивні функції.
Лекція 2. Машина Тюрінга: структура, принципи роботи, приклади програм. Алгоритмічна розв’язність. Поняття обчислюваної функції. Формальні мови і граматики.
Лабораторні роботи
Лабораторна робота №1. Алгоритми та їх властивості.
Мета роботи: засвоїти основні властивості алгоритмів, навчитися будувати алгоритми у формі блок-схем і псевдокоду.
Лабораторна робота №2. Машина Тюрінга.
Мета роботи: ознайомитися з формальною моделлю обчислювального процесу ‒ Машиною Тюрінга; навчитися будувати таблицю переходів і моделювати роботу машини.
Консультації здійснюються впродовж семестру згідно встановленого розкладу.
Індивідуальна робота
Для денної форми здобуття освіти
Розрахунково-графічна робота

Метою розрахунково-графічної роботи є оволодіння принципами функціонування Машини Тюрінга як універсальної моделі обчислень, набуття навичок побудови таблиці переходів та формального опису алгоритмів у термінах станів і дій, а також дослідження роботи сконструйованої машини на конкретних прикладах для підтвердження її коректності та завершуваності.
Здобувач отримує завдання на першому в семестрі практичному занятті.
Пояснювальна записка містить 5-7 сторінок Кількість розділів – 9.
Змістовна послідовність виконання роботи.
1. Аналіз постановки задачі.
2. Вибір моделі Машини Тюрінга.
3. Побудова множини станів.
4. Складання таблиці переходів.
5. Побудова схеми роботи МТ.
6. Проведення покрокової симуляції.
7. Перевірка коректності алгоритму.
8. Оцінювання обчислювальної складності.
9. Формулювання висновків.
Захист розрахунково-графічної роботи – протягом останнього навчального тижня семестру.
Для заочної форми здобуття освіти
Розрахунково-графічна робота
Метою розрахунково-графічної роботи є оволодіння принципами функціонування Машини Тюрінга як універсальної моделі обчислень, набуття навичок побудови таблиці переходів та формального опису алгоритмів у термінах станів і дій, а також дослідження роботи сконструйованої машини на конкретних прикладах для підтвердження її коректності та завершуваності.
Здобувач отримує завдання на першому в семестрі практичному занятті.
Пояснювальна записка містить 5-7 сторінок Кількість розділів – 9.
Змістовна послідовність виконання роботи.
1. Аналіз постановки задачі.
2. Вибір моделі Машини Тюрінга.
3. Побудова множини станів.
4. Складання таблиці переходів.
5. Побудова схеми роботи МТ.
6. Проведення покрокової симуляції.
7. Перевірка коректності алгоритму.
8. Оцінювання обчислювальної складності.
9. Формулювання висновків.
Захист розрахунково-графічної роботи – протягом останнього навчального тижня семестру.
Контрольна робота
Завдання для виконання контрольної роботи здобувач отримує на установчій лекції.
Робота містить 5 теоретичних питань та 2 практичних завдання.
Обсяг відповіді на кожне теоретичне питання: не менше, ніж 1 сторінка машинописного тексту. Текст відповіді повинен бути виконаний самостійно, а не скопійованим з навчального посібника.
Практичне завдання №1. Нормальні алгоритми Маркова.
Практичне завдання №2. Алгоритми на графах.
Термін надання виконаної контрольної роботи на перевірку – не пізніше, ніж за місяць до початку сесії.

Форми контрольних заходів та оцінювання результатів навчання
Для денної форми здобуття освіти
Поточний контроль полягає у виконанні
1) 7-и індивідуальних поточних завдань. Індивідуальні поточні завдання полягають в виконанні типових завдань відповідно до мети та завдань лабораторних занять. Бездоганне виконання індивідуальних поточних завдань №1 – №7 оцінюється у 8 бали кожне;
2) розрахунково-графічної роботи. Бездоганне виконання оцінюється у 15 балів. Захист роботи – 5 балів.
3) двох модульних контрольних робіт. Модульні контрольні роботи складаються з теоретичної та практичної частини та проводяться у формі виконання наданих викладачем завдань. Бездоганне виконання кожної модульної контрольної роботи становить 12 балів.
Підсумковий контроль – екзамен. Екзамен усний. Максимальна оцінка, яку може отримати студент – 100 балів.
Підсумковий контроль знань проводиться для здобувачів вищої освіти, що не змогли з будь-яких причин набрати необхідну кількість балів, або для здобувачів вищої освіти, що бажають збільшити вже набрану кількість балів. Підсумковий контроль знань здійснюється у вигляді усної бесіди з викладачем (комісією викладачів) по тематиці навчальної дисципліни.
Для заочної форми здобуття освіти
Захист розрахунково-графічної роботи. Бездоганне виконання розрахунково-графічної роботи оцінюється у 15 балів. При її захисті студент може отримати до 5 балів. Разом 20 балів.
Захист контрольної роботи. Бездоганне виконання контрольної роботи оцінюється у 40 балів. При її захисті студент може отримати до 20 балів. Виконання двох лабораторних робіт оцінюється в 20 балів.
Підсумковий контроль – екзамен. Екзамен усний. Максимальна оцінка, яку може отримати студент – 100 балів.
Підсумковий контроль знань проводиться для здобувачів вищої освіти, що не змогли з будь-яких причин набрати необхідну кількість балів, або для здобувачів вищої освіти, що бажають збільшити вже набрану кількість балів. Підсумковий контроль знань здійснюється у вигляді усної бесіди з викладачем (комісією викладачів) по тематиці навчальної дисципліни.