Моделі алгоритмів та логічні системи

Актуальність дисципліни

Поняття і методи теорії алгоритмів та математичної логіки є концептуальною основою сучасних інформаційних та програмних систем, вони належать до основних засобів моделювання різноманітних предметних областей. З одного боку, вони дають обґрунтування правильності тих чи інших способів отримання істинного знання, а з іншого, вказують на межі застосування математичних та інформаційних моделей.

Теорія алгоритмів та математична логіка мають яскраво виражене прикладне спряму-вання. Теорія алгоритмів є теоретичним фундаментом програмування й інформатики, вона безпосередньо пов’язана з теорією керування. Саме на уточненнях поняття алгоритму базуються мови програмування. Апарат математичної логіки (алгебра логіки) лежить в основі схемотехніки комп'ютерів. Розвиток інформаційних технологій та пов'язана з цим поява нових задач і проблем ведуть до залучення для їх розв'язку все нових понять і засобів мате¬матичної логіки та теорії алгоритмів (метод нерухомої точки, теорія обчислень та процесів, теорія доведень, нетрадиційні логіки тощо). Результати, отримані в області теорії алгоритмів і математичної логіки та задачі, які розв'язуються їх засобами і методами, знаходять різноманітні й ефективні застосування в різних сферах діяльності людини.

Мета дисципліни – засвоєння базових знань з основ теорії алгоритмів та математичної логіки, включаючи вивчення формальних моделей алгоритмів та обчислюваних функцій, питань обчислюваності, розв’язності, часткової розв’язності та нерозв’яз¬ності масових проблем, вивчення логічних систем та їх можливості для опису предметних областей, систем пошуку виведень.

Завдання дисципліни – набуття компетенцій, знань, умінь та навиків на рівні сучасних досягнень у теорії алгоритмів та математичній логіці відповідно до кваліфікації фахівець з прикладної математики.

В результаті вивчення дисципліни «Моделі алгоритмів та логічні системи» студент

повинен знати:

• основні поняття, засоби і методи теорії алгоритмів та математичної логіки, їх застосування в інформатиці й програмуванні;
• основні формальні моделі алгоритмів та алгоритмічно обчислюваних функцій;
• мати уявлення про розв’язність, часткову розв’язність та нерозв’язність масових проблем, про складність обчислень;
• мови логіки та їх можливості для опису предметних областей;
• основні методи пошуку доведень та засоби логічного виведення;
• вмати уявлення про нетрадиційні логіки (багатозначні, модальні; темпоральні, епістемічні) та їх застосування;

повинен вміти:

• будувати формальні моделі алгоритмів та обчислюваних функцій (МНР-програми, машини Тьюрінга, системи Поста, рекурсивні та частково-рекурсивні функції), використовувати тезу Чорча;
• встановлювати розв’язність, часткову розв’язність та нерозв’язність масових проб¬лем, встановлювати клас множини та предиката, їх місце в арифметичній ієрархії;
• оцінювати складність алгоритмів;
• описувати на мовах логіки 1-го порядку твердження стосовно різноманітних предмет¬них областей;
• встановлювати істинність та виконуваність формул, наявність логічного наслідку, виразність та невиразність предикатів;
• проводити виведення в численнях гільбертівського типу, в секвенційних та резолюційних численнях.

Зв’язок з іншими дисциплінами

Отримані в результаті вивчення дисципліни «Моделі алгоритмів та логічні системи» знання та уміння потрібні для подальшого вивчення:

1) дисциплін обов’язкових та вибору ВНЗ: "Бази даних та інформаційні системи", "Комп’ютерна алгебра", "Основи методів обчислень", "Чисельний аналіз", "Теорія керування";

2) дисциплін вільного вибору студента: "Сучасні методи комп’ютерного моделювання", "Ймовірнісний аналіз алгоритмів", "Цифрова обробка інформації", "Технології математичного та комп’ютерного моделювання", "Паралельні методи обчислень"; "Системне програмування", "Розробка мовних процесорів", "Теорія прийняття рішень", "Моделі та методи прийняття рішень", "Обробка та розпізнавання зображень".

Структура дисципліни

Матеріал дисципліни «Моделі алгоритмів та логічні системи» складається з таких тем.

• Тема 1. Основні поняття теорії алгоритмів та математичної логіки.
• Тема 2. Обчислювальні процедури як математичне поняття. Алгоритми як конструктивні процедури.
• Тема 3. Класичні моделі алгоритмів. МНР-програми, машини Тьюрінга.
• Тема 4. Системи Поста.
• Тема 5. Частково рекурсивні функції.
• Тема 6. Елімінація примітивної рекурсії. Теза Чорча, її значення.
• Тема 7. Нумерації. Універсальні функції.
• Тема 8. Розв’язність, часткова розв’язність, нерозв’язність.
• Тема 9. Індексні множини. Теорема Райса, її значення.
• Тема 10. Відносна обчислюваність. Звідності.
• Тема 11. Складність обчислень. Елементарні функції.
• Тема 12. Пропозиційна логіка. Пропозиційне числення, теорема тавтології.
• Тема 13. Пошук виведень. Метод резолюцій. Пропозиційне секвенційне числення.
• Тема 14. Предикати, операції над предикатами. Логічні зв’язки, реномінації, суперпозиції, квантори.
• Тема 15. Логіки 1-го порядку, їх мови та семантичні моделі.
• Тема 16. Еквівалентні перетворення формул. Виразність. Метод автоморфізмів.
• Тема 17. Теорії 1-го порядку. Теорема дедукції. Несуперечливість, повнота, розв’язність теорій 1-го порядку.
• Тема 18. Теорема Гьоделя про повноту, її наслідки. Теорема компактності.
• Тема 19. Секвенційні числення логік 1-го порядку.
• Тема 20. Метод резолюцій логіки 1-го порядку. Алгоритми уніфікації.
• Тема 21. Багатозначні логіки. Модальні, темпоральні, епістемічні логіки, їх застосування.