З Дискретної математики Студента ФАКН Спеціальності 6.050.101. Контрольна робота з Інші. Робота № 524782

Перехід до торгівельного партнера Binance

З Дискретної математики Студента ФАКН Спеціальності 6.050.101

Інформація про навчальний заклад

ВУЗ:

Національний авіаційний університет

Інститут:

Не вказано

Факультет:

РТ

Кафедра:

Не вказано

Інформація про роботу

Рік:

2011

Тип роботи:

Контрольна робота

Предмет:

Інші

Завантажити

Частина тексту файла (без зображень, графіків і формул):

МІНІСТЕРСТВО ОСВІТИ І НАУКИ УКРАЇНИ Національний авіаційний університет Контрольна робота З Дискретної математики Студента ФАКН Спеціальності 6.050.101 № (залікової книжки)090271 Гуджал Володимира 2011 р. Машина Тюрінга Завдання №1 Скласти програму для машини Тюрінга, яка б додавала двійку до натурального числа. Прокоментувати написану програму. S (n) =n+2; n ϵ N Q ={q0,q1,q2……} – множина станів. Число n на стрічці записується в десятинній системі числення. Стан q1 заміняє останню цифру числа n: Якщо ця цифра менше 8-ми, цифрою на дві одиниці більше та переходить в стан зупинки; Якщо ця цифра дорівнює 8-ми, то її заміняє на нуль и переходить вліво в стан q2. Стан q2 додає до слідуючого розряду одиницю. Якщо ж остання цифра числа дорівнює 9-ти, то він її замінить на 1 та переходить вліво в стан q2. Розв’язок S (n) =n+2; n ϵ N (X = {0,1,2,…..,9},Q= { q0,q1,q2,q3}, q0, #,P), де P має такий вигляд: Складемо алгоритм, за яким потім побудуємо приклади, що відповідають умові завдання: цей алгоритм показує що ми з кожним разом рухаємося вправо, лише прочитуючи клітинку та залишаючи значення в клітинці незмінним. цей алгоритм показує що ми з кожним разом читаємо число що знаходиться в клітинці, додаємо як дано в умові до нього двійку та рухаємося на одну клітинку вліво. читання пустої клітинки та рух вліво на одну клітинку Машина читає число в клітинці заміняє його на одиницю, за умови що число від 1 до 8 , якщо воно рівне 9-ти то заміняє на нуль, при цьому кожний раз рухається на одну клітинку вліво Отже наведемо приклади машин Тюрінга для таких чисел: 569 та 1088.При чому машина повинна виконувати умову завдання, тобто S (n) =n+2; n ϵ N Число 569 Число 1088 Числення висловлювань Завдання №2 Завдання №3 Спростити вираз (1→¬a) \/ (0→b) /\(1→c) Спростимо вираз за допомогою закону: Завдання №4 Виписати всі комбінації логічних значень змінних, для яких буде хибною формула ((x \/ y) /\ ((y \/ z) /\ (z \/ x)))→ ((x/\y) /\z) Формулапобудована з трьох простих формул (x,y і z). Отже, існує вісім можливих комбінацій логічних значень для (x,y і z) . Знайдемо ж такі логічні значення змінних, для яких формула і буде хибною. Для цього перевіримо всі 8-ім можливих комбінацій значень формул (x,y і z) при різних значеннях нульарних операцій, тобто значень нуля та одиниці. Отже… Перевіривши складену таблицю, ми бачимо що формула є хибною для таких комбінацій змінних формул (x,y і z): № 5 – коли формули мають такі значення: x=1; y=0; z=1; № 6 – коли формули мають такі значення: x=1; y=1; z=0; № 7 – коли формули мають такі значення: x=0; y=1; z=1; Теорія графів Завдання №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 Побудувати дерево найменшої довжини на графі і підрахувати суму довжин ребер дерева – довжина ребра; - Вершина графа Побудова дерева найменшої довжини ,за допомогою алгоритму Краскала Початкова фаза - ліс складається з кореня (вершини ребра) та пустої множини (мал. 1) Обираємо ребро найм. довжини – це ребро (4,6),довжина котрого =1(мал. 2) Обираємо наступне ребро найм. довжини – це ребро (4,5) (мал. 2) Додаємо ребро (3,5) (мал. 3) Додаємо ребро (3,2) (мал. 4) Додаємо ребро (1,2). Дерево побудовано. Всі 6-ть вершин використані при побудові. (Мал. 5) Сума довжин ребер = 1+1+2+2+3=9 Завдання №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) Завдання №7 1- ий спосіб 2- ий спосіб 1) 1 2 3 4 5 6 ( ( ( ( ( ( ( ( ( ( ( ( 2) 1 2 3 4 5 6 ( ( ( ( ( ( ( ( ( ( ( ( 3) 1 2 3 4 5 6 ( ( ( ( ( ( ( ( ( ( ( ( 4) 1 2 3 4 5 6 ( ( ( ( ( ( ( ( ( ( ( ( Враховуючи транспозиції елементів (фарб) отримаємо 8 різних правильних розфарбовувань даного графа. (, (, (, ( – фарби.

Контрольна робота Інші

vladymyrlem

13.07.2013 18:07-

Коментарі

Ви не можете залишити коментар. Для цього, будь ласка, або зареєструйтесь.

Ділись своїми роботами та отримуй миттєві бонуси!

Маєш корисні навчальні матеріали, які припадають пилом на твоєму комп'ютері? Розрахункові, лабораторні, практичні чи контрольні роботи — завантажуй їх прямо зараз і одразу отримуй бали на свій рахунок! Заархівуй всі файли в один .zip (до 100 МБ) або завантажуй кожен файл окремо. Внесок у спільноту – це легкий спосіб допомогти іншим та отримати додаткові можливості на сайті. Твої старі роботи можуть приносити тобі нові нагороди!

поділитись