Контрольна з основ дискретної математики, НАУ, 2 курс

Задание:Машина Тьюрінга 1. Скласти програму для машини Тюрінга, яка повинна додавати 2 до заданого двійкового числа. Прокоментувати написану програму. Числення висловлювань 2. Спростити всі вирази виду XOY, де X?{0,1,a,¬a}, Y?{0,1,a,¬a }, O?{/\,\/,?,?}. 3. Спростити вираз (1?¬a) \/ (0?b) /\(1?c) 4. Виписати всі комбінації логічних значень змінних, для яких буде хибною формула ((x \/ y) /\ ((y \/ z) /\ (z \/ x)))? ((x/\y) /\z) Теорія графів 5. Побудувати дерево найменшої довжини на графі і підрахувати суму довжин ребер дерева Ребро (1,2) (1,4) (2,3) (2,4) (2,5) (3,4) (3,5) (4,5) (4,6) (5,6) Довжина 3 7 2 3 4 6 2 1 1 2 6. Правильно пофарбувати чотирма фарбами вершини графа Ребро (1,2) (1,4) (2,3) (2,4) (2,5) (3,4) (3,5) (4,5) (4,6) (5,6) (1,6) (2,6) Це завдання є однаковим для всіх студентів. За його виконання виставляється оцінка 3(задовільно). Щоб одержати оцінку 4, треба попросити у викладача додаткове завдання. Контрольні питання Поняття алгоритму Дати неформальне визначення алгоритму. Пояснити властивості алгоритму: дискретність, детермінованість, елементарність кроків, направленість, масовість. Машина Тьюрінга З яких частин складається машина Тьюрінга? Як вона функціонує? Навести приклад команди, пояснити як вона виконується. Числення висловлювань З яких символів складається алфавіт числення висловлювань? Що таке правильно побудовані формули? Чи є вираз правильно побудованою формулою? Чому? Що таке таблиці істиності? Побудувати таблицю істиності для формули . Що таке тавтологія? Суперечність? Пояснити метод Куайна для доведення тавтологій. Пояснити метод редукції для доведення тавтологій. Сформулювати правило modus ponens для виведення формул числення висловлювань. Сформулювати теорему дедукції для виведення формул числення висловлювань. Теорія графів Пояснити форми предтавлення графів: - малюнок, - множина вершин і множина ребер, - матриця суміжності, - матриця інцидентності. Що таке: - повний граф, - двочастинний (дводольний) граф, - планарний граф, - плоский граф? Що таке правильне розфарбування графа?

Содержание: Машина Тьюрінга 3 Числення висловлювань 7 Теорія графів 9 Контрольні питання 12 Поняття алгоритму 12 Машина Тьюрінга 12 Числення висловлювань 15 Теорія графів 17 Список використаної літератури 21

Литература: 1. Гудман С., Хидетниеми С. Введение в разработку и анализ алгоритмов. – М.: Мир, 2002. 368 с. 2. Емеличев В.А., Мельников О.И., Сарванов В.И., Тышкевич Р.И. Лекции по теории графов. – М.: Наука. 2001.-384 с. 3. Кретова Л.Д. Элементы математической логики: методические указания к практическим и индивидуальным занятиям / Л.Д. Кретова, Н.Б. Ускова, В.В. Посметьев. Воронеж: ВГТУ, 2005. 21 с. 4. Леденева Т.М. Специальные главы математики. Дискретная математика: учеб. пособие / Т.М. Леденева. Воронеж: ВГТУ, 1997. 130 с. 5. Нефедов В.Н. Курс дискретной математики / В.Н. Нефедов, В.А. Осипова: Изд-во МАИ, 2002. 262 с. 6. Яблонский С.В. Введение в дискретную математику / С.В. Яблонский. Μ.: Наука, 2004. 272 с.