ДИСКРЕТНА МАТЕМАТИКА
МЕТОДИЧНІ ВКАЗІВКИ
до виконання лабораторної роботи № 8
з дисципліни ”Дискретна математика”
для студентів спеціальностей
122 “Комп’ютерні науки та інформаційні технології”,
124 “Системний аналіз”
та 126 “Інформаційні системи та технології”
першого (бакалаврського) рівня вищої освіти
Затверджено
на засіданні кафедри
інформаційних систем та мереж
Протокол № 15 від 21.05.2018 р.
Львів – 2018
Дискретна математика: метод. вказівки до виконання лабораторної роботи № 8 з дисципліни ”Дискретна математика” для студентів спеціальностей 122 “Комп’ютерні науки та інформаційні технології”, 124 ”Системний аналіз” та 126 “Інформаційні системи та технології” першого (бакалаврського) рівня вищої освіти / уклад.: О.В. Лозинська, В.А. Висоцька, В.В. Савчук. – Львів: Видавництво Національного університету ”Львівська політехніка”, 2018. – 14 с.
Укладачі Лозинська О.В., асистент, к.т.н.,
Висоцька В.А., доцент, к.т.н.,
Савчук В.В., асистент, к.т.н.
Відповідальний за випуск Литвин В.В., д-р. техн. наук, проф.
Рецензенти Пукач П.Я., д.т.н., проф.
Берко А.Ю., д.т.н., проф.
Метою виконання лабораторних робіт є здобуття студентами практичних навичок застосування класичних алгоритмів дискретної математики та сучасних алгоритмів штучного інтелекту, що використовуються при побудові комп’ютерних програм.
У результаті виконання лабораторних робіт студенти повинні:
- знати основи математичної логіки і теорії множин, елементи комбінаторного аналізу, основи теорії відношень, основи теорії графів та дерев, основи теорії кодування, булеві функції, мови, граматики та автомати, основи теорії алгоритмів, основи теорії кодування.
- уміти застосовувати відомі методи та алгоритми дискретної математики для дослідження предметної області та побудови математичного опису прикладних проблем.
ЗАГАЛЬНИЙ ПОРЯДОК ВИКОНАННЯ ЛАБОРАТОРНИХ РОБІТ
Для виконання лабораторних робіт потрібно:
- використовувати літературні джерела, конспект лекцій, методичні розробки з дисципліни, засвоїти теоретичний матеріал, пов’язаний з тематикою лабораторної роботи;
- відповісти керівнику лабораторних занять на поставлені питання за темою лабораторної роботи;
- отримати набір індивідуальних завдань відповідно до свого порядкового номеру у списку групи (у разі вичерпання завдань нумерація продовжується від їх початку);
- оформити звіт про виконання лабораторної роботи у вигляді завдань та розв’язку до них;
- захистити звіт про виконання лабораторної роботи.
ВИМОГИ ДО ОФОРМЛЕННЯ ЗВІТІВ ПРО ВИКОНАННЯ ЛАБОРАТОРНИХ РОБІТ
Звіт про виконання лабораторної роботи акуратно оформляється на зшитих аркушах паперу форматом А4 та скріпляються скріпкою. Після завершення семестру звіти здаються для зберігання на кафедру.
Кожен звіт повинен мати такі розділи:
- титульна сторінка з назвою кафедри, номером та назвою роботи, назвою дисципліни, прізвищами студента і викладача (зразок оформлення титульної сторінки наведено у додатку А);
- мета виконання лабораторної роботи;
- відповіді на контрольні питання;
- порядок виконання лабораторної роботи;
- індивідуальні завдання та розв’язки до них (якщо вказано реалізувати завдання у вигляді комп’ютерної програми, то навести текст програми та результати її виконання );
- висновки. Вказується які знання та навички отримані під час виконання лабораторної роботи
Звіт про виконання лабораторної роботи необхідно захистити у строго визначені терміни. Звіт повинен бути написаний українською мовою, акуратно та грамотно, з дотриманням правил оформленням ділової документації.
Лабораторна робота № 8
ОСНОВИ ТЕОРІЇ АЛГОРИТМІВ
Мета роботи: Вивчення основних правил алгоритмів, машини Тьюрінга, теза Тьюрінга, обчислення числових функцій на машинах Тьюрінга, рекурсивні функції, теза Чорча.
1. ТЕОРЕТИЧНІ ВІДОМОСТІ
Алгоритм (латинізов. Algorithmi, від імені перського математика IX ст. аль-Хорезмі) — послідовність, система, набір систематизованих правил виконання обчислювального процесу, що обов’язково приводить до розв’язання певного класу задач після скінченного числа операцій.
При написанні комп’ютерних програм алгоритм описує логічну послідовність операцій. Для візуального зображення алгоритмів часто використовують блок-схеми.
Нормальні алгоритми Маркова — це система послідовних застосувань підстановок, які реалізують певні процедури отримання нових слів з базових, побудованих із символів деякого алфавіту. Як і машини Тьюрінга, нормальні алгоритми не виконують самих обчислень: вони лише виконують перетворення слів шляхом заміни літер за заданими правилами.
Нормально обчислюваною називають функцію, яку можна реалізувати нормальним алгоритмом. Тобто, алгоритмом, який кожне слово з множини припустимих даних функції перетворює на її вихідні значення.
Творець теорії нормальних алгоритмів А. А. Марков висунув гіпотезу, яка отримала назву принцип нормалізації Маркова: для знаходження значень функції, заданої в деякому алфавіті, тоді і лише тоді існує деякий алгоритм, коли функція нормально обчислювана.
Подібно до тез Тьюрінга та Чорча, принцип нормалізації Маркова не може бути доведений математичними засобами.
1.1. Машина Тьюрінга
Основна ідея, що лежить в основі машини Тьюрінга, дуже проста. Машина Тьюрінга — це абстрактна машина (автомат), що працює зі стрічкою окремих комірок, в яких записано символи. Машина також має голівку для запису та читання символів із комірок, яка може рухатись вздовж стрічки. На кожному кроці машина зчитує символ з комірки, на яку вказує голівка, та, на основі зчитаного символу й внутрішнього стану робить наступний крок. При цьому, машина може змінити свій стан, записати інший символ в комірку, або пересунути голівку на одну комірку ліворуч або праворуч.
На основі дослідження цих машин було висунуто тезу Тьюрінга (основна гіпотеза алгоритмів):
Для знаходження значень функції, заданої в деякому алфавіті, тоді і лише тоді існує деякий алгоритм, коли функція обчислювана за Тьюрінгом, тобто, коли її можна обчислити на придатній машині Тьюрінга.
(Для ознайомлення з повним текстом статті необхідно залогінитись)