ЗАВДАННЯ
Частина – 1. Теорія множин. Математична логіка. Комбінаторний аналіз.
1.Знайти: A B, A B, A \ B, A \ B. A {1,4,6,9}, B {2,3,5,7,9}.
2.Для множини (A C) \ (С В) зобразити діаграму Ейлера-Венна.
3.Скількома способами можна вибрати у бібліотеці r книг із n, якщо r 6,
n11?
4.У олімпіаді брали участь n студентів та r із них отримали призові місця.
Скількома способами можна розподілити призові медалі, якщо n 13.
r6?
5.Скільки різних слів (комбінацій) можна створити із символів «ковдра», «палатка»?
6.Обчислити значення C103 ; A105 .
7.Розкласти за допомогою бінома Ньютона (a 1)12 .
8.Визначити коефіцієнт у розкладі бінома Ньютона a3b5 .
9.Записати число 204 у системі з основою 2, 3 та 5.
10.Записати числа 41 і 31 у двійковій системі, виконати додавання і віднімання у двійковій системі та зробити перевірку.
11.Записати числа 41 і 11 у двійковій системі, виконати множення та
додавання у двійковій системі та зробити перевірку. |
|
||||
12.Знайти |
кількість |
цілочисельних |
розв’язків |
рівняння |
|
x1 x2 |
x3 x4 x5 x6 |
13. |
|
|
|
13.Знайти |
кількість цілочислових |
розв’язків |
рівняння x1 x2 |
15; x1 1; |
|
x2 3; |
|
|
|
|
|
14.Знайти лексикографічну наступну перестановку для 1672. |
|
||||
15.Знайти |
лексикографічне |
наступне |
сполучення |
множини |
|
A {1,2,3,4,5,6,7} для даних з завдання 14. |
|
|
|||
16.Записати характеристичне рівняння для рекурентного рівняння an 2an 2 3an 4 .
17.Розв’язати рекурентне рівняння an 13an 1 42an 2 , a0 1, a1 1, n 2. 18.Скласти таблицю істинності для висловлювання ( p (q r)) (q l). 19.Записати ДДНФ і ДКНФ для функції ((z y) x) ( y (x z)) .
20. Записати функцію з попереднього завдання поліномом Жегалкіна та зобразити функцію у вигляді логічної схеми.
Частина – 2. Теорія графів. Дерева.
1. Задано матрицю суміжності графа.
|
v1 |
v2 |
v3 |
v4 |
v5 |
v1 |
0 |
1 |
0 |
0 |
0 |
v |
0 |
0 |
1 |
0 |
0 |
2 |
|
|
|
|
|
|
|
|
|
|
|
v3 |
0 |
0 |
1 |
2 |
1 |
v4 |
|
|
|
|
|
0 |
1 |
2 |
1 |
2 |
|
v |
2 |
0 |
1 |
2 |
0 |
5 |
|
|
|
|
|
1.1.Побудувати граф, що відповідає їй.
1.2.Побудувати множину пар вершин, що відповідає їй.
1.3.Знайти кількість вершин, ребер (дуг), і степені (напівстепені) кожної вершини графу.
1.4.Побудувати матрицю інцидентності графа.
1.5.Побудувати граф, ізоморфний даному.
1.6.Чи існує Ейлерів цикл і шлях у даному графі?
1.7.Чи існує Гамільтонів цикл и шлях у даному графі?
1.8.Перетворити граф у зважений (ваги визначити самостійно) та за допомогою алгоритму Дейкстри знайти довжину найкоротшого шляху між двома вершинами (обрати самостійно) та побудувати цей шлях.
1.9.Побудувати простий граф (n=4), розфарбувати його та визначити його хроматичне число χ.
2.Задано дерево
2.1.Визначити корінь дерева, його батьків, синів, листки. Які вершини є внутрішніми?
2.2.Визначити рівень кожної вершини та висоту дерева.
2.3.Чи є дерево завершеним?
2.4.Чи є дерево збалансованим?
2.5.Виконати обхід дерева у прямому, внутрішньому та зворотному порядках.
2.6.Визначити ексцентриситет вершин та центр дерева.
3.Побудувати блок-схему алгоритму розв’язку завдання 1.2. Реалізувати отриманий алгоритм у певному середовищі програмування та зафіксувати результат.
ЗМІСТ |
|
ЗАВДАННЯ................................................................................................................................................ |
2 |
ЗМІСТ ......................................................................................................................................................... |
4 |
ВСТУП ........................................................................................................................................................ |
5 |
РОЗВ’ЯЗАННЯ ЗАВДАНЬ...................................................................................................................... |
7 |
Частина – 1. Теорія множин. Математична логіка. Комбінаторний аналіз............................. |
7 |
Завдання 1. ......................................................................................................................................... |
7 |
Завдання 2. ......................................................................................................................................... |
8 |
Завдання 3. ....................................................................................................................................... |
10 |
Завдання 4. ....................................................................................................................................... |
10 |
Завдання 5. ....................................................................................................................................... |
10 |
Завдання 6. ....................................................................................................................................... |
11 |
Завдання 7. ....................................................................................................................................... |
11 |
Завдання 8. ....................................................................................................................................... |
12 |
Завдання 9. ....................................................................................................................................... |
13 |
Завдання 10. ..................................................................................................................................... |
14 |
Завдання 11. ..................................................................................................................................... |
16 |
Завдання 12. ..................................................................................................................................... |
16 |
Завдання 13. ..................................................................................................................................... |
17 |
Завдання 14. ..................................................................................................................................... |
17 |
Завдання 15. ..................................................................................................................................... |
17 |
Завдання 16. ..................................................................................................................................... |
18 |
Завдання 17. ..................................................................................................................................... |
18 |
Завдання 18. ..................................................................................................................................... |
19 |
Завдання 19. ..................................................................................................................................... |
20 |
Завдання 20. ..................................................................................................................................... |
22 |
Частина – 2. Теорія графів. Дерева. .................................................................................................... |
23 |
Завдання 1. ....................................................................................................................................... |
23 |
Завдання 2. ....................................................................................................................................... |
31 |
Завдання 3. ....................................................................................................................................... |
34 |
СПИСОК ВИКОРИСТАНОЇ ЛІТЕРАТУРИ..................................................................................... |
36 |
ВСТУП
Дискретна математика — область математики, що вивчає властивості дискретних структур. До таких структур можуть бути віднесені скінченні групи, скінченні графи, а також деякі математичні моделі перетворювачів інформації, скінченні автомати, машини Тьюринга і так далі. Це приклади структур скінченного характеру.
Логіка
Математична логіка (теоретична логіка, символічна логіка) — розділ математики, що вивчає докази і питання підстав математики. «Предмет
сучасної математичної логіки різноманітний.» Відповідно до визначення П.
С. Порецкого, «математична логіка є логіка по предмету, математика за методом». Відповідно до визначення Н. І. Кондакова, "математична логіка
— друга, після традиційної логіки, щабель у розвитку формальної логіки,
що застосовує математичні методи та спеціальний апарат символів і досліджує мислення за допомогою числень (формалізованих мов). " Це изначення відповідає визначенню С. К. Кліні : математична логіка — це «логіка, що розвивається за допомогою математичних методів». Також А. А. Марков визначає сучасну логіку «точною наукою, яка астосовує математичні методи».
Всі ці визначення не суперечать, а доповнюють один одного.
Теорія множин
В основі теорії множин лежать первинні поняття: множина та елемент множини. Елемент множини перебуває щодо множини у відношенні бути елементом множини (позначається як x A[2] — «x є елемент множини A»).
Серед похідних понять найважливішими є наступні:
•порожня множина — множина, яка не містить елементів, позначається зазвичай ;
•підмножина і надмножина — множина, яка складається тільки з ел-
тів іншої множини, та множина, до якої належать усі ел-ти іншої множини,
відповідно;
•сімейство множин;
•простір (універсум) — множина, що є надмножиною всіх множин;
•конституента.
Комбінаторика
Комбінато́рика — розділ математики, присвячений розв'язанню задач вибору та розташування елементів деякої, зазвичай скінченної, множини відповідно до заданих правил. Кожне таке правило визначає спосіб побудови деякої конструкції із елементів вихідної множини, що зветься комбінаторною конфігурацією. Тому на меті комбінаторного аналізу стоїть дослідження комбінаторних конфігурацій, алгоритмів їх побудови,
оптимізація таких алгоритмів, а також розв'язання задач переліку.
Термін «комбінаторика» ввів Лейбніц, який у 1666 році опублікував свою працю «Міркування про комбінаторне мистецтво».
Теорія ймовірностей
Ймовірність — числова характеристика можливості того, що випадкова подія відбудеться в умовах, які можуть бути відтворені необмежену кількість разів. Імовірність є основним поняттям розділу математики, що називається теорія ймовірностей.
Випадковою подією називається подія, результат якої не може бути відомий наперед. Навіть у тому разі, коли насправді подія детермінована своїми передумовами, вплив цих передумов може бути настільки складним,
що вивести з них наслідок логічно й послідовно, неможливо. Наприклад,
при підкиданні монети, сторона на яку монета впаде визначається положенням руки і монети в руці, швидкістю, обертовим моментом тощо, однак відслідкувати всі ці фактори неможливо, тому результат можна вважати випадковим.