ЧЕРНІГІВСЬКИЙ НАЦІОНАЛЬНИЙ ТЕХНОЛОГІЧНИЙ УНІВЕРСИТЕТ кОЛЕДЖ транспорту та комп’ютерних технологій

ЧЕРНІГІВСЬКИЙ НАЦІОНАЛЬНИЙ ТЕХНОЛОГІЧНИЙ УНІВЕРСИТЕТ кОЛЕДЖ транспорту та комп’ютерних технологій

ЗАТВЕРДЖУЮ

Голова методичної ради

_________ В. М. Радченко

 « ___» __________2014р.

МЕТОДИЧНИЙ ПОСІБНИК

 

до практичних занять із дисципліни «Дискретна математика»

для студентів спеціальності 5.05010201

„Обслуговування комп’ютерних систем і мереж”

СХВАЛЕНО

Протокол засідання

циклової комісії

«___» ____ 2014р. №___

 

2014 рік

ЗМІСТ

ПОЯСНЮВАЛЬНА ЗАПИСКА.. 3

ВИТЯГ З РОБОЧОЇ НАВЧАЛЬНОЇ ПРОГРАМИ.. 4

ПЕРЕЛІК ПОСИЛАНЬ. 5

ПРАКТИЧНЕ ЗАНЯТТЯ №1. 6

ПРАКТИЧНЕ ЗАНЯТТЯ №2. 8

ПРАКТИЧНЕ ЗАНЯТТЯ №3. 10

ПРАКТИЧНЕ ЗАНЯТТЯ №4. 12

ПРАКТИЧНЕ ЗАНЯТТЯ №5. 14

ПРАКТИЧНЕ ЗАНЯТТЯ №6. 16

ПРАКТИЧНЕ ЗАНЯТТЯ №7. 18

ПРАКТИЧНЕ ЗАНЯТТЯ №8. 20

ПРАКТИЧНЕ ЗАНЯТТЯ №9. 22

ПРАКТИЧНЕ ЗАНЯТТЯ №10. 25

 

ПОЯСНЮВАЛЬНА ЗАПИСКА

Практичні заняття з предмету «Дискретна математика» розроблені згідно робочої навчальної програми для студентів спеціальності 5.05010201 „Обслуговування комп’ютерних систем і мереж”.

У навчальному процесі практичне заняття займає особливе місце. Воно відіграє важливу організуючу і керуючу роль у навчально-пізнавальній діяльності студентів.

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

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

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

Головним завданням практичних занять повинні бути перевірка знань, розвиток вмінь та навичок, розвиток самостійності, оригінальності мислення, уміння знаходити і відстоювати власну точку зору.

ВИТЯГ З РОБОЧОЇ НАВЧАЛЬНОЇ ПРОГРАМИ

№ заняття	Тема дисципліни Тема практичного заняття	Кількість годин	Зміст практичного заняття
	Тема 1 Множини
4,5	Множини та операції над ними	4	Розв’язувння задач з теми
7	Нечіткі множини та операції над ними	2	Розв’язувння задач з теми
	Тема 2 Відношення
10	Відношення та операції над ними	2	Розв’язувння задач з теми
12	Розмиті відношення	2	Розв’язувння задач з теми
	Тема 3 Комбінаторний аналіз
15	Комбінаторні задачі. Генерування	2	Розв’язувння задач з комбінаторного аналізу
18	Рекурентні рівняння	2	Розв’язування задач на використання рекурентних рівнянь
	Тема 4 Основи теорії алгоритмів
20	Приклади машини Тьюринга	2	Розв’язування задач на побудову машини Тьюринга
	Тема 5 Графи та дерева
23	Задачі теорії графів	2	Розв’язування задач з використання теорії графів
30	Використання теорії дерев	2	Розв’язування задач на використання теорії дерев

ПЕРЕЛІК ПОСИЛАНЬ

1 Аляев Ю. А. Дискретная математика и математическая логика / Ю. А. Аляев, С.Ф.Тюрин. - М. : Финансы и статистика, 2006. — 368 с.

2 Бардачов Ю. М. Дискретна математика : підручник / Ю.М. Бардачов, Н.А.Соколова.  – К. : Вища шк., 2002. – 287 с.

3 Ерусалимский Я. М. Дискретная математика / Я.М. Ерусалимский. – М. : Вузовская книга, 2005. – 254 с.

4 Капітонова Ю.В. Основи дискретної математики / Ю.В. Капітонова, С.Л.Кривий. – К. : Наукова думка, 2002. – 579 с.

5 Бондаренко М.Ф. Комп'ютерна дискретна математика : підручник / М.Ф.Бондаренко, Н. В. Білоус,  А. Г. Руткас. – Харків : Компанія СМІТ, 2004. - 480 с.

6 Михайленко В.М. Дискретна математика / В.М. Михайленко, Н. Д. Федоренко,  В.Д.Демченко. – К. : вид-во Європейського ун-ту, 2003. - 319 с.

7 Нікольський Ю. В. Дискретна математика / Ю.В. Нікольський, В.В.Пасічник, Ю.М.Щербина. – Львів : «Магнолія Плюс», 2006. – 608 с.

8 Тишин В. В. Дискретная математика в примерах и задачах / В.В. Тишин. — СПб. : БХВ-Петербург, 2008. — 352 с: ил.

 

ПРАКТИЧНЕ ЗАНЯТТЯ №1

ТЕМА: Множини та операції над ними (2 год.)

МЕТА:

навчальна: вчити студентів записувати множини різними способами, визначати потужність множини;       

розвиваюча: розвивати логічне мислення;      

виховна: виховувати інтерес до комп’ютерної математики.       

ОБЛАДНАННЯ: олівці, лінійки

ПЛАН

1 Розв’язування задач на побудову множин

ЗМІСТ ПРАКТИЧНОГО ЗАНЯТТЯ

 

 

Задача 1. Дано множину А. Знайти потужність, булеан та потужність булеану.

Розв’язання

Перелічимо елементи множини А. А={5,6}.

Кількість елементів множини А дорівнює 2, отже потужність цієї множини теж дорівнює 2: .

Визначимо булеан множини А. для цього перелічимо всі підмножини множини А: Р(А)={Æ, {5}, {6}, {5.6}}.

Потужність булеану

Задача 2 (усно). З яких елементів складаються наступні множини:

S = {x | x – натуральне число}; К ={х : х² –8х+15 = 0}; Р = {х : х – студент вашої групи жіночої статі}; А = {х : х = 2m, де m — ціле число}.

Задача 3 (усно). Серед заданих множин вказати рівні: А = {1, 3, 6}; В={3,6, 9}; С = {9, 6, 3}; Д = {3, 2, 6}; Е = {2, 3, 6}; F = {3, 6, 9}; К = {3, 6, 2}.

Задача 4. Дано множини А, В і С. Знайти , ,  на універсумі U= ={1,2,4,56,7,8,9,10}.

А={5,6,7} В={2,4,5} С={1,2,4}

Розв’язання

ВÈА = {2,4,5,6,7}

АÇС = Æ

АÇ(ВÇС)= {5,6,7} Ç{2,4}=Æ

= {6,7}

= {1,2,3,4,8,9,10}.

Задача 4. Зобразити відношення між обсягами наступних понять на кругах Ейлера:

а) А: „ціле число”; В: „натуральне число”; С: „від’ємне число”;

б) А: „дерево”; В: „рослина”; С: „кущ”:

в) А: „квадрат”; В: „ромб з прямим кутом”.

Задача 5. Навести приклади понять, відношення між обсягами яких можуть бути зображенні з допомогою наступних кругів Ейлера

                 

 

Задача 6. Для заданої множини A побудувати множину всіх підмножин множини A, тобто її булеан: а) A = {1,2,3}; б) A = {1,{2},{1,2}}.

Задача 7. Які з наведених співвідношень є правильними?

 

ДОМАШНЄ ЗАВДАННЯ

 

Задача. Довести закони де-Моргана за допомогою кругів Ейлера.

 

    ВИКЛАДАЧ – Данилова В.А.

 

ПРАКТИЧНЕ ЗАНЯТТЯ №2

ТЕМА: Множини та операції над ними (2 год.)

МЕТА:

навчальна: вчити студентів виконувати операції над множинами;       

розвиваюча: розвивати логічне мислення;      

виховна: виховувати інтерес до комп’ютерної математики.       

ОБЛАДНАННЯ: олівці, лінійки

ПЛАН

1 Розв’язування задач на виконання операцій над множинами

ЗМІСТ ПРАКТИЧНОГО ЗАНЯТТЯ

 

Задача 1. Довести рівності (за допомогою кругів Ейлера або за допомогою властивостей операцій над множинами)

Розв’язання

АÇ(ВÇС)                                     

         

 

Отримано однакові зображення. Отже, рівність доведена.

 

Задача 2. Задано множини А = {0, 2, 4, 6, 8, 10}, В = {0, 1, 2, 3, 4, 5, 6} та С = {4, 5, 6, 7, 8, 9, 10}. Побудувати множини: а)АÈВÇС; б) А È В È С; в) (АÈВ)/ С; г) (А Ç В) / С.

Задача 3. Знайти множини А та В, якщо А\В = {1, 5, 7,8}, В\А = {2,10}, і АÇВ= ={3,6,9}.

Задача 4. Довести рівність множин А\В =  двома способами.

Задача 5. Задано множини А - {а, b, с}, В = {х, у}, С= {0, 1}. Побудувати декартові добутки: а)АхВхС; б) С х В х А; в) С х А х В; г) ВхВхВ.

Задача 6. Задано універсальну множину U= {1, 2, 3, 4, 5, 6, 7, 8, 9, 10}:

 а) подати бітовими рядками множини {3, 4, 5}, {1, 3, 6, 10}, {2, 3, 4, 7, 8, 9};

б) відновити множини за бітовими рядками 0101111100, 1000000001, 1111111111.

Задача 7. Довести тотожності

Задача 8 (додатково). Чи можна твердити, що А = В, якщо для множин А, В та С виконуються рівності:

ДОМАШНЄ ЗАВДАННЯ

 

Задача. Задано множини А = {1, 2, 4, 5}, В = {0, 3, 5, 9} та С = {4, 7}. Побудувати множини: а)АÈВÇС; б) (АÈВ)/ С; в) (А Ç В)/С.

 

 

    ВИКЛАДАЧ – Данилова В.А.

 

 

ПРАКТИЧНЕ ЗАНЯТТЯ №3

ТЕМА: Нечіткі множини та операції над ними (2 год.)

МЕТА:

навчальна: вчити студентів записувати поняття у вигляді нечіткої множини, визначати нечіткі множини за їх функціями належності, виконувати операції над нечіткими множинами;       

розвиваюча: розвивати логічне мислення;      

виховна: виховувати інтерес до комп’ютерної математики.       

ОБЛАДНАННЯ: олівці, лінійки

ПЛАН

1 Розв’язування задач на побудову нечітких множин

2 Розв’язування задач на виконання операцій над нечіткими множинами

ЗМІСТ ПРАКТИЧНОГО ЗАНЯТТЯ

 

1 Розв’язування задач на побудову нечітких множин

 

Задача 1. Представити у вигляді нечіткої множини поняття «Людина середнього росту» на універсальній множині U={155,160,165,170,175,180,185,190}.

Розв’язання

Одне з можливих рішень

Задача 2. Представити у вигляді нечіткої множини поняття «Тепла вода в морі» на універсальній множині U={15, 17,19, 21, 23, 25, 27}.

Задача 3. Нехай задано нечітку множину С={х| «значення х близько до 1»}. Побудувати графік функції  належності до даної множині елементів універсальної множини  Х = {-1, -0.5, 0, 0.5, 1, 1.5, 2}.

Задача 4. Визначити самостійно нечітку множину на певному універсумі.

 

2 Розв’язування задач на виконання операцій над нечіткими множинами

 

Задача 5. Задано універсум А={2,3,4,5,6,7,8}, на якому визначені нечіткі множини Х та У. Побудувати об’єднання, перетин, алгебраїчний добуток і доповнення множин Х та У.

,

Розв’язання

XÈY=           XÇY=

  

Задача 6. Нехай задано нечіткі множини: , . Знайти об'єднання і перетин цих множин.

Задача 7. Задано універсум А={2,3,4,5,6,7,8}, на якому визначені нечіткі множини Х та У. Побудувати об’єднання, перетин, алгебраїчний добуток і доповнення множин Х та У.

,

ДОМАШНЄ ЗАВДАННЯ

 

Задача 1. Нехай задано нечітку множину А={х| «значення х близько до 5»}. Побудувати графік функції належності для множини елементів універсальної множини  Х={2,3,4,5,6,7,8}.

Задача 2. Задано універсум А={2,3,4,5,6,7,8}, на якому визначені нечіткі множини Х та У. Побудувати об’єднання, перетин, алгебраїчний добуток і доповнення множин Х та У.

,

 

    ВИКЛАДАЧ – Данилова В.А.

 

 

ПРАКТИЧНЕ ЗАНЯТТЯ №4

ТЕМА: Відношення та операції над ними (2 год.)

МЕТА:

навчальна: вчити студентів записувати відношення між множинами, знаходити область визначення та множину значень відношення, визначати властивості відношень, виконувати операції над відношеннями;       

розвиваюча: розвивати логічне мислення;      

виховна: виховувати інтерес до комп’ютерної математики.       

ОБЛАДНАННЯ: олівці, лінійки

ПЛАН

1 Розв’язування задач на побудову відношень між множинами

2 Розв’язування задач на визначення властивостей відношень

ЗМІСТ ПРАКТИЧНОГО ЗАНЯТТЯ

 

1 Розв’язування задач на побудову відношень між множинами

 

Задача 1. Задано множини A = {1, 2, 3}, B = {1,2, 3} і відношення R = {(1,2), (1,3), (2,3), (3,3)} між ними. Задати відношення за допомогою графічним та матричним способом.

Розв’язання

Матриця відношення – матриця .

Графічний спосіб задання

Задача 2. Нехай задано множини A={-2,-1,0,1,2,3} і B={0,1,2,4} та відношення між ними C={(x,y): y = x², x Î A, y Î B }. Побудувати графік і діаграму відношення C.

Задача 3. Побудувати матрицю відношення. Відношення задно на множині А={1,2,3,4}. R={a+b: a кратне 3}.

 

2 Розв’язування задач на визначення властивостей відношень

 

Задача 4. З’ясувати властивості відношення, побудованого в задачі 3.

 

Розв’язання

Відношення не є рефлексивним, оскільки на головній діагоналі його матриці є нулі.

Відношення не є антирефлексивним, оскільки на головній діагоналі його матриці присутні не лише нулі.

Відношення не є симетричним, олскільки його матриця не є симетричною.

Відношення є транзитивним, оскільки для всіх елементів цього відношення виконується:

.

Еквіваалентним відношення не буде, оскільки воно не є рефлексивним і симетричним.

Задача 5. На множині цілих чисел задані відношення

Визначити чи будуть ці відношення еквівалентними.

Задача 6. На множині M = {1,2,3,4} задано відношення

R 1={(1,1),(1,3),(2,2),(2,4),(3,1),(3,3),(4,2),(4,4)};

R2 = {(1,2),(1,3),(2,3),(2,4),(4,1),(4,3)}.

Визначити, які з цих відношень є

а) рефлексивними;

б) антирефлексивними;

в) симетричними;

г) антисиметричними;

д) транзитивними.

Побудувати графіки, графи та матриці заданих відношень.

ДОМАШНЄ ЗАВДАННЯ

 

Задача  На множині M = {1,2,3,4} задано відношення R4={(1,1),(1,2),(1,4),(2,2),(2,4),(3,3),(3,4),(4,2),(4,3),(4,4)}. Визначити чи буде воно

а) рефлексивними;

б) антирефлексивними;

в) симетричними;

г) антисиметричними;

д) транзитивними.

Побудувати графік та матрицю відношення.

 

ВИКЛАДАЧ – Данилова В.А.

 

 

ПРАКТИЧНЕ ЗАНЯТТЯ №5

ТЕМА: Розмиті відношення (2 год.)

МЕТА:

навчальна: вчити студентів формалізувати неточні твердження за допомогою розмитих відношень, визначати властивості відношень, виконувати композицію нечітких відношень;       

розвиваюча: розвивати логічне мислення;      

виховна: виховувати інтерес до комп’ютерної математики.       

ОБЛАДНАННЯ: олівці, лінійки

ПЛАН

1 Формалізація неточних тверджень за допомогою нечітких відношень

2 Розв’язування задач на знаходження композиції нечітких відношень

ЗМІСТ ПРАКТИЧНОГО ЗАНЯТТЯ

 

1 Формалізація неточних тверджень за допомогою нечітких відношень

 

Задача 1. Використовуючи означення розмитого відношення, формалізувати неточне твердження «a близьке до b», якщо A = {3, 4, 5}, B = {4, 5, 6}.

 

Розв’язання

R=

Відношення можна задати за допомогою матриці

Функція належності матиме вигляд

Задача 2. Формалізувати відношення «особа a значно старше особи b», записавши нечітке відношення аналітично; за допомогою матриці відношень; записавши функцію належності. Вважати тривалість життя людини від 0 до 110 років.

Задача 3. Задано множини А={1,5,9,13} і В= {2,12,22,32}. Побудувати розмите відношення «a значно більше, ніж b», , . Записати це відношення матрицею.

2 Розв’язування задач на знаходження композиції нечітких відношень

 

Задача 4. Нехай відношення  та , де А={а₁,а₂}, В={b₁,b₂}, С={с₁,с₂,с₃}, задані матрицями , . Композицію Q=S°R задано матрицею . Обчислити матрицю .

 

Розв’язання

Обчислюємо елементи матриці :

Аналогічно

,     

        

Отже, .

Задача 5. Задано множини А={а₁,а_2, а₃}, В={b₁,b₂} та нечітка множина , розмите відношення R  задано матрицею . Записати композицію відношення R та розмитої множини Х.

Задача 6. Обчислити композицію S°R розмитих відношень  та , якщо А={а₁,а₂}, В={b₁,b₂}, С={с₁,с₂,с₃}, задані матрицями , .

ДОМАШНЄ ЗАВДАННЯ

 

Задача. Задано множини А={а₁,а_2, а₃}, В={b₁,b₂} та нечітка множина , розмите відношення R  задано матрицею . Записати композицію відношення R та розмитої множини Х

 

ВИКЛАДАЧ – Данилова В.А.

ПРАКТИЧНЕ ЗАНЯТТЯ №6

ТЕМА: Комбінаторні задачі. Генерування (2 год.)

МЕТА:

навчальна: вчити студентів визначати кількість розміщень, перестановок, комбінацій,  будувати перестановки, сполучення в лексикографічно наступному порядку;

розвиваюча: розвивати логічне мислення;      

виховна: виховувати інтерес до комп’ютерної математики.       

ОБЛАДНАННЯ: олівці, лінійки

ПЛАН

1 Обчислення кількості розміщень, сполучень і перестановок

2 Біном Ньютона. Трикутник Паскаля

3 Генерування перестановок, сполучень і розбиттів множин

ЗМІСТ ПРАКТИЧНОГО ЗАНЯТТЯ

 

1 Обчислення кількості розміщень, сполучень і перестановок

 

Задача 1. Скількома можливими способами можна вибрати з 15 людей делегацію в складі 3 осіб.

 

Розв'язання

Шукане число (кількість можливих вибірок) є числом сполучень із 15 по 3.

.

Задача 2. Скільки різних слів можна утворити, переставляючи букви у слові математика?

Задача 3. В класі 35 учнів, з них: 20 відвідують математичний гурток, 11 – фізичний, 10 – жодного не відвідують. Скільки учнів відвідують математичний і фізичний гурток? Скільки лише математичний?

Задача 4. Є 10 дітей і 20 однакових подарунків. Скількома способами можна розподілити подарунки між дітьми?

 

2 Біном Ньютона. Трикутник Паскаля

 

Задача 5. Визначити коефіцієнт при х¹²у¹³ у розкладі (х+у)²⁵. 

 

Розв’язання

.

 

Задача 6. Обчислити біноміальні коефіцієнти для розкладу (х+у)⁴.  

Задача 7. Користуючись біноміальною теоремою довести, що .

Задача 8. Знайти кількість невід’ємних цілих розв’язків рівняння х₁ +х₂ +х₃ =11.

Задача 9. Знайти кількість невід’ємних цілих розв’язків нерівності х₁ +х₂ +х₃  11.

3 Генерування перестановок, сполучень і розбиттів множин

 

Задача 10. Побудувати перестановку, яка є лексикографічно наступною за 362541.

 

Розв’язання

Перша справа пара чисел, у якій число, що ліворуч, менше від числа, що праворуч, – це 25. Розглянемо послідовність 541. Серед чисел 5,4,1 найменше число, що більше 2, дорівнює 4. Міняємо місцями 4 і 2, а решту чисел 2,5,1 розташовуємо у зростаючому порядку на місцях, що залишилися.

Задача 11. Множина А={1,2,3,4,5,6}. Знайти сполуку, яка є наступною за сполукою {1,2,5,6} у лексикографічно наступному порядку.

ДОМАШНЄ ЗАВДАННЯ

 

Задача 1. Побудувати перестановку, яка є лексикографічно наступною за 16274.

Задача 2. Множина А={1,2,3,4,5,6}. Знайти сполуку, яка є наступною за сполукою {1,2,4,5} у лексикографічно наступному порядку.

 

ВИКЛАДАЧ – Данилова В.А.

 

ПРАКТИЧНЕ ЗАНЯТТЯ №7

ТЕМА:Рекурентні рівняння (2 год.)

МЕТА:

навчальна: вчити студентів розв’язувати однорідні та неоднорідні рекурентні рівняння;       

розвиваюча: розвивати поняття «рівняння»;      

виховна: виховувати інтерес до комп’ютерної математики.       

ОБЛАДНАННЯ: олівці, лінійки

ПЛАН

1 Розв’язування однорідних  рекурентних рівнянь

2 Розв’язування неоднорідних рекурентних рівнянь

ЗМІСТ ПРАКТИЧНОГО ЗАНЯТТЯ

 

1 Розв’язування однорідних рекурентних рівнянь

 

Задача 1. Послідовність чисел Фібоначі задає рекурентне рівняння другого порядку f_n=f_n-1+f_n-2 з початковими умовами f₀=0, f₁=1. Розв’язати це рівняння.

 

Розв'язання

Маємо рівняння другого степеня.

Запишемо характеристичне рівняння.   

r² – r -1=0

Розв’язавши це рівняння, маємо

Отже, .

Задача 2. Розв’язати рекурентне рівняння а_n=-4а_n-4+5а_n-2  з початковими умовами а₀=3, а₁=2, а₂ =6, а₃=8.

Задача 3. Розв’язати рекурентне рівняння а_n=6а_n-1-9а_n-2  з початковими умовами а₀=3, а₁=3.

Задача 4. Розв’язати рекурентне рівняння а_n=а_n-1+6а_n-2  з початковими умовами а₀=3, а₁=6.

 

2  Розв’язування неоднорідних рекурентних рівнянь

 

Задача 5. Розв’язати неоднорідне рекурентне рівняння а_n=-а_n-2+n+1  з початковими умовами а₀=5, а₁=-1.

 

Розв’язання

Відповідне однорідне рекурентне рівняння а_n=-а_n-2

Характеристичне  рівняння          r² – 1=0

Загальний розв’язок  однорідного рівняння

Частковий розв’язок неоднорідного рівняння шукаємо у вигляді .

Підставимо у неоднорідне рівняння. Отримаємо

 

D₀n+D₁n²=D₀(n-2)+D₁(n-2)²+n+1

 

(4D₁-2D₀+1)+(1-2D₁)n=0

 

,

Частковий розв’язок .

.

За даних початкових умов маємо систему лінійних рівнянь

Задача 6. Розв’язати неоднорідне рекурентне рівняння а_n=4а_n-1 -4а_n-2+n2ⁿ  з початковими умовами а₀=0, а₁=0.

 

ДОМАШНЄ ЗАВДАННЯ

 

Задача. Розв’язати рекурентне рівняння а_n=7а_n-1-10а_n-2  з початковими умовами а₀=2, а₁=1.

 

 

ВИКЛАДАЧ – Данилова В.А.

ПРАКТИЧНЕ ЗАНЯТТЯ №8

ТЕМА: Приклади машин Тьюринга (2 год.)

МЕТА:

навчальна: вчити студентів будувати машини Тьюринга та їх функціональні схеми;

розвиваюча: розвивати логічне мислення;      

виховна: виховувати інтерес до комп’ютерної математики.       

ОБЛАДНАННЯ: олівці, лінійки

ПЛАН

1 Розв’язування задач на побудову машин Тьюринга

2 Побудова машин Тьюринга для обчислення числових функцій

ЗМІСТ ПРАКТИЧНОГО ЗАНЯТТЯ

 

1 Розв’язування задач на побудову машин Тьюринга

 

Задача 1. Побудувати машину Тьюринга, яка застосовна до всіх слів у алфавіті {а, b} і довільне слово х₁х₂…х_n, де х_іÎ {а, b}, і=1,2,…, n, перетворює у слово х₂…х_n х_1. Подати функціональну схему Тьюринга.

 

Розв'язання

Зовнішній алфавіт А= {Ù, а, b}.

Команди

q₁a®ÙRq₂  / перша буква а запам’ятовується переходом у стан q₂ і стирається

q₁ b ®ÙRq_{3      /} перша буква b запам’ятовується переходом у стан q₃ і стирається

q₂a®аRq₂

q₂b®bRq₂ / проходження голівки через слово і запис у його кінці букви а

q₂Ù®aNq₀      

q₃a®аRq₃

q₃b®bRq₃ /проходження голівки через слово і запис у його кінці букви b

q₃Ù®bNq₀      

Функціональна схема Тьюринга

	Ù	а	b
q1	-	ÙRq2	ÙRq3
q2	aNq0	аRq2	bRq2
q3	bNq0	аRq3	bRq3

 

Задача 2. Зобразити конфігурації, що відповідають роботі машини Т, яка була побудована в задачі 1, над словом аbb.

Задача 3. Побудувати машину Т, яка застосовна до всіх слів у алфавіті {а, b} і знімає копію слова на стрічці, тобто слово х₁х₂…х_n в початковій конфігурації перетворює на слово х₁х₂…х_nÙх₁х₂…х_n в заключній конфігурації.

 

2 Побудова машин Тьюринга для обчислення числових функцій

 

Задача 4. Побудувати машину Т, яка обчислює числову функцію f(x)=x+1. Записати конфігурації машини для обчислення f(1).

 

Розв’язання

Зовнішній алфавіт А={Ù, 1}.

Множина станів Q={q₀; q₁}

Команди q₁1®1Rq₁  q₁Ù®1Nq₀      

Конфігурації для обчислення f(1).

1

1

q₁

 

1

1

  q₁

 

1

1

Ù

         q₁

 

1

1

1

         q₀

 

Задача 5. Побудувати машину Т, яка обчислює числову функцію f(x; y)=x+y.

Задача 6. Побудувати машину Т, яка обчислює числову функцію f(x)=2x+1.

 

ДОМАШНЄ ЗАВДАННЯ

 

Задача.  Побудувати машину Т, яка застосовна до всіх слів у алфавіті {а, b} і яка кожне слово х₁х₂…х_n-1х_n в початковій конфігурації перетворює на слово х_n х_n-1…х₂х₁ в заключній конфігурації.

ВИКЛАДАЧ – Данилова В.А.

ПРАКТИЧНЕ ЗАНЯТТЯ №9

ТЕМА:   Задачі теорії графів (2 год.)

МЕТА:

навчальна: вчити студентів зображувати графи різними способами, будувати графи за їх матрицями суміжності, інцедентності, визначати степені вершин графів, ;

розвиваюча: розвивати логічне мислення;      

виховна: виховувати інтерес до комп’ютерної математики.       

ОБЛАДНАННЯ: олівці, лінійки

ПЛАН

1 Використання основних властивостей графів

2 Розв’язування задач на побудову графів за їх матрицями суміжності, інцедентності, списком пар

ЗМІСТ ПРАКТИЧНОГО ЗАНЯТТЯ

 

1 Використання основних властивостей графів

 

Задача 1. Нехай задано граф G =(V,E ):

а) V = {1,2,3,4}, E = {(1,3),(2,3),(3,4),(4,1),(4,2)};

б) V = {a,b,c,d,e},E = {(a,d),(b,c),(b,e),(c,e),(d,b),(d,e),(e,a)};

в) V = {1,2,3}, E = {(1,2),(1,3),(2,3)};

г) V = {A,B,C,D}, E = {(A,B),(A,D),(B,C),(B,D),(C,A),(C,D)}.

Побудувати діаграму, матриці суміжності та інцидентності для кожного із заданих графів.

 

Розв'язання

 

а) діаграма 

Матриця суміжності                                 

 

                                              

Матриця інцедентності

 

 

	(1,3)	(2,3)	(3,4)	(4,1)	(4,2)
1	1	0	0	1	0
2	0	1	0	0	1
3	1	1	1	0	0
4	0	0	1	1	1

 

Задача 2. Розглянути турнір між чотирма футбольними командами, в якому кожні дві команди зіграли між собою не більше одного матчу. Подати турнір графом, вершинами якого є команди.

Задача 3. Визначити кількість вершин, ребер та степені вершин графів

Задача 4. Зобразити всі підграфи графа.

Задача 5 Знайти об’єднання графів

Задача 6. Кілька осіб (більше двох) проводять шаховий турнір в одне коло. У деякий момент виявилося, що тільки двоє шахістів зіграли однакову кількість партій. Довести, що тоді є або тільки один учасник, який не зіграв жодної партії, або тільки один, який зіграв усі партії.

 

Доведення

Мовою теорії графів задача перекладається наступним чином. У графі з n (n > 2) вершинами тільки дві вершини мають однакові степені. Довести, що є або лише одна вершина степеня 0, або лише одна степеня n-1. Розглянемо всі можливі заперечення цього твердження. Якщо припустити, що немає вершин степеня як 0, так і n-1, то n вершин мають степені від 1 до n-2, тобто серед них є або дві пари вершин, або три вершини з однаковими степенями, що суперечить умові. Отже, вершини степеня 0 або степеня n-1 є. За теоремою 1 одночасно таких бути не може. Якщо є дві вершини степеня 0, то залишається n-2 вершин з попарно різними степенями від 1 до n-3, а це неможливо. Так само неможливо, що за двох вершин степеня n-1 решта n-2 вершин мають попарно різні степені від 2 до n-2.

 

2 Розв’язування задач на побудову графів за їх матрицями суміжності, інцедентності, списком пар

 

Задача 7. Зобразити неорієнтовані графи за матрицями суміжності

а) ;     б)

 Розв’язання

а)

Задача 8. Зобразити орієнтовані графи за матрицями суміжності.

а) ;     б)

 

ДОМАШНЄ ЗАВДАННЯ

 

Задача 1.  Задати графи задачі 7 списком пар.

Задача 2. Нехай V={a,b,c,d,e}. Граф G =(V,E ) задано за допомогою матриці суміжності A.

а) A= ;          б) A= ;

Визначити множину ребер E графа G. Побудувати діаграму та матрицю інцидентності графа G.

 

 

ВИКЛАДАЧ – Данилова В.А.

ПРАКТИЧНЕ ЗАНЯТТЯ №10

ТЕМА:   Використання теорії дерев (2 год.)

МЕТА:

навчальна: вчити студентів визначати різні кореневі дерева в одному й тому ж графі, визначати висоту дерева, виконувати обхід дерев;

розвиваюча: розвивати логічне мислення;      

виховна: виховувати інтерес до комп’ютерної математики.       

ОБЛАДНАННЯ: олівці, лінійки

ПЛАН

1 Розв’язування задач на  зображення кореневих дерев

2 Розв’язування задач на впорядкування вершин дерев

ЗМІСТ ПРАКТИЧНОГО ЗАНЯТТЯ

 

1 Розв’язування задач на використання основних властивостей графів

 

Задача 1. На рисунку зображено дерево. Утворити з нього кореневі дерева з коренем у вершинах а та с.

 

Розв'язання

                   

 

Задача 2. Визначити висоту кореневих дерев задачі 1.

Задача 3. Побудувати завершене бінарне дерево висоти 4 та завершене 3-арне дерево висоти 3.

 

2 Розв’язування задач на впорядкування вершин дерев

Задача 4. Зобразити арифметичний вираз  у вигляді дерева.

Розв’язання

          

 

          

 

Задача 5. Зобразити впорядковане дерево, що відповідає виразам, записаним у префікс ній формі:

А) ­+23-51; Б) +*++-53214; В) */93+*24-76.

Задача 6. Обчислити значення виразу в польському записі: +-*235/ ­ 234

Задача 7. Обчислити значення виразу в оберненому польському записі: 723*-4­93/+.

Задача 8. Побудувати бінарне дерево пошуку для наступного списку слів: математика, фізика, географія, зоологія, біологія, психологія, хімія. Процес побудови зобразити покроково.

 

ДОМАШНЄ ЗАВДАННЯ

 

Задача 1. Обчислити значення виразу в польському записі: +-­32­23/6-42.

Задача 2 Побудувати впорядковане кореневе дерево, обхід якого зверху вниз дає послідовність abfcghidejkl, причому вершина а має чотирьох синів, с – трьох,  j – двох, b та е – по одному, а решта вершин є листками.

Задача 3. Зобразити вираз (х+ух)+х/у, використовуючи кореневе дерево.

 

 

ВИКЛАДАЧ – Данилова В.А.

ЧЕРНІГІВСЬКИЙ НАЦІОНАЛЬНИЙ ТЕХНОЛОГІЧНИЙ УНІВЕРСИТЕТ кОЛЕДЖ транспорту та комп’ютерних технологій

ЗАТВЕРДЖУЮ

Голова методичної ради

_________ В. М. Радченко

 « ___» __________2014р.

МЕТОДИЧНИЙ ПОСІБНИК

 

до практичних занять із дисципліни «Дискретна математика»

для студентів спеціальності 5.05010201

„Обслуговування комп’ютерних систем і мереж”

СХВАЛЕНО

Протокол засідання

циклової комісії

«___» ____ 2014р. №___

 

2014 рік

ЗМІСТ

ПОЯСНЮВАЛЬНА ЗАПИСКА.. 3

ВИТЯГ З РОБОЧОЇ НАВЧАЛЬНОЇ ПРОГРАМИ.. 4

ПЕРЕЛІК ПОСИЛАНЬ. 5

ПРАКТИЧНЕ ЗАНЯТТЯ №1. 6

ПРАКТИЧНЕ ЗАНЯТТЯ №2. 8

ПРАКТИЧНЕ ЗАНЯТТЯ №3. 10

ПРАКТИЧНЕ ЗАНЯТТЯ №4. 12

ПРАКТИЧНЕ ЗАНЯТТЯ №5. 14

ПРАКТИЧНЕ ЗАНЯТТЯ №6. 16

ПРАКТИЧНЕ ЗАНЯТТЯ №7. 18

ПРАКТИЧНЕ ЗАНЯТТЯ №8. 20

ПРАКТИЧНЕ ЗАНЯТТЯ №9. 22

ПРАКТИЧНЕ ЗАНЯТТЯ №10. 25

 

ПОЯСНЮВАЛЬНА ЗАПИСКА

Практичні заняття з предмету «Дискретна математика» розроблені згідно робочої навчальної програми для студентів спеціальності 5.05010201 „Обслуговування комп’ютерних систем і мереж”.

У навчальному процесі практичне заняття займає особливе місце. Воно відіграє важливу організуючу і керуючу роль у навчально-пізнавальній діяльності студентів.

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

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

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

Головним завданням практичних занять повинні бути перевірка знань, розвиток вмінь та навичок, розвиток самостійності, оригінальності мислення, уміння знаходити і відстоювати власну точку зору.

12Следующая ⇒

Поделиться: