МІНІСТЕРСТВО ОСВІТИ УКРАЇНИ
Бердичівський політехнічний коледж
Контрольна робота
Прикладне вживання методів дискретної математики
м. Бердичів 2007 р.
Зміст
Задача 1
Задача 2
Задача 3
Задача 4
Список використаної літератури
1. Задача 1
Задана універсальна множина U={a,b,c,d,e,f,g,h,i} і дві множини S={b,c,e,i}, T={c,e,f,i}. Знайти:
об’єднання, перетин, різницю і симетричну різницю множин S i T;
доповнення множини S і доповнення множини T;
прямий добуток множин S i T;
задати функцію із S в T: ін’єктивну, сюр’єктивну і бієктивну.
Дані відображення h1 і h2, що представляють множину сумісних кортежів. Знайти:
h3=(h1h2);
h4=(h1h2);
h5=(h1h2);
h1 | у | x1 | x2 | x3 |
| h2 | у | x1 | x2 | x3 |
| 2 | b | e | 6 |
|
| 3 | с | e | 6 |
| 3 | с | e | 5 |
|
| 5 | с | b | 2 |
| 5 | с | b | 2 |
|
| 4 | а | c | 5 |
| 4 | а | e | 5 |
|
| 2 | b | e | 6 |
h6=(h1h2).
Хай дані відношення r1 і r2. Знайти:
r
3=(r1r2);
r4=(r1r2);
r5=(r1r2).
r6=(r1r2).
r1 | x1 | x2 | x3 | x4 |
| r2 | x1 | x2 | x3 | x4 |
x1 | 1 | 1 | 0 | 1 |
| x1 | 1 | 1 | 0 | 1 |
x2 | 0 | 1 | 0 | 1 |
| x2 | 1 | 1 | 0 | 0 |
x3 | 1 | 0 | 1 | 0 | x3 | 0 | 1 | 0 | 0 |
x4 | 0 | 1 | 1 | 1 |
| x4 | 0 | 0 | 1 | 1 |
Відповідь:
1.
а) А = ST = {b, c, e, f, i};
А = ST = {c, e, i};
A = ST = {b}; B = TS = {f}:
A = ST = {b, f}.
b) A = S = {a, d, f, g, h};
B = T = {a, b, d, g, h}.
c) ST = {{b, c}, {b, e}, {b, f}, {b, i}, {c, c}, {c, e}, {c, f}, {c, i}, {e, c}, {e, e}, {e, f}, {e, i}, {i, c}, {i, e}, {i, f}, {i, i}}.
2.
a) h3 =
у | x1 | x2 | x3 |
2 | b | e | 6 |
3 | с | e | 5 |
5 | с | b | 2 |
4 | а | e | 5 |
3 | с | e | 6 |
4 | а | c | 5 |
b) h4 =
c
) h5 =
у | x1 | x2 | x3 |
3 | с | e | 5 |
4 | а | e | 5 |
d) h6 =
у | x1 | x2 | x3 |
2 | b | e | 6 |
5 | с | b | 2 |
3.
a)
r3 | x1 | x2 | x3 | x4 |
x1 | 1 | 1 | 0 | 1 |
x2 | 1 | 1 | 0 | 1 |
x3 | 1 | 1 | 1 | 0 |
x4 | 0 | 1 | 1 | 1 |
b)
r4 | x1 | x2 | x3 | x4 |
x1 | 1 | 1 | 0 | 1 |
x2 | 0 | 1 | 0 | 0 |
x3 | 0 | 0 | 0 | 0 |
x4 | 0 | 0 | 1 | 1 |
c)
r3 | x1 | x2 | x3 | x4 |
x1 | 0 | 0 | 0 | 0 |
x2 | 0 | 0 | 0 | 1 |
x3 | 1 | 0 | 1 | 0 |
x4 | 0 | 1 | 0 | 0 |
d)
r3 | x1 | x2 | x3 | x4 |
x1 | 0 | 0 | 0 | 0 |
x2 | 1 | 0 | 0 | 1 |
x3 | 1 | 1 | 1 | 0 |
x4 | 0 | 1 | 0 | 0 |
2. Задача 2
У колоді 52 карти. У скількох випадках при виборі з колоди 10 карт серед них виявляться: а) рівно один туз; б) хоча б один туз; в) не менше двох тузів; г) рівно два тузи?
Відповідь:
а) Всього у колоді 4 тузи. Отже за правилом добутку перемножимо ймовірність вибору з чотирьох тузів одного туза та ймовірність вибору інших карт, тобто 9 з 48:
.
б) Хоча б один туз – це означає може бути і 4, і 3, і 2, і 1. Отже для розв'язку необхідно від ймовірності вибору 10 карт з 52 відняти ймовірність вибору 10 карт з 48:
.
в) Не менше двох тузів – означає, що з 10 карт буде 4, 3 або 2 тузи. Рішенням буде попередня відповідь від якої відняти ймовірність вибору 1 туза (першої відповіді):
.
г) Аналогічно розв'язку першого завдання отримаєм:
3. Задача 3
Граф заданий матрицею вагів. Побудувати для нього остов мінімальної ваги використовуючи алгоритми Пріма та Краскала, за алгоритмом Флойда обчислити найкоротші шляхи графа.
Відповідь:
Будова графа:
Побудова остову мінімальної ваги по алгоритму Краскала:
Встановлюємо частковий порядок по вазі ребер графа:
L13 | L15 | L14 | L12 | L23 | L45 | L34 | L35 | L24 | L25 |
8 | 8 | 9 | 11 | 12 | 12 | 14 | 15 | 18 | 20 |
Будуємо остов мінімальної ваги:
Крок | Ребра остову | Вершини остову |
L13 | L15 | L14 | L12 | x1 | x2 | x3 | x4 | x5 |
1 | 1 | 0 | 0 | 0 | 1 | 1 | 0 | 0 | 0 |
2 | 1 | 1 | 0 | 0 | 1 | 1 | 1 | 0 | 0 |
3 | 1 | 1 | 1 | 0 | 1 | 1 | 1 | 1 | 0 |
4 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 |
Lij | 8 | 8 | 9 | 11 | L=8+8+9+11=36 |
Обчислення найкоротших шляхів за алгоритмом Флойда:
Будуємо матрицю вагів та матрицю переходів:
А0 = Р0 =
Елементи матриці вагів будемо знаходити за формулою:
Ak [i; j] = min (Ak-1 [i; j], Ak-1 [i; k] + Ak-1 [k; j])
Перша ітерація: k=1
А1 = Р1 =
Друга ітерація: k=2
А2 = Р2 =
Третя ітерація: k=3
А3 = Р3 =
Четверта ітерація: k=4
А4 = Р4 =
П’ята ітерація: k=5
А5 = Р5 =
4. Задача 4
Знайти мінімальну ДНФ логічної функції F = F (хг, х2, х3, х4), яка дорівнює одиниці на наборах 2, 3, 4, 11, 14, 15 і нулю на решті наборів.
Відповідь:
Спочатку необхідно подати функцію у ДДНФ.
ДДНФ =x1x2x3x4 x1x2x3x4 x1x2x3x4 x1x2x3x4 x1x2x3x4 x1x2x3x4
Виконуємо склеювання:
1-2 x1x2x3
1-4 x2x3x4
2-4 x2x3x4
4-6 x1x3x4
5-6 x1x2x3
ДДНФ = x1x2x3 x2x3x4 x2x3x4 x1x3x4 x1x2x3 x1x2x3x4
1-2 x2x3
1-3 x2x3
2-3 x2x3
3-4 x3x4
4-5 x1x3
ДДНФ = x2x3 x3x4 x1x3 x1x2x3x4
ДДНФ | x1x2x3x4 | x1x2x3x4 | x1x2x3x4 | x1x2x3x4 | x1x2x3x4 | x1x2x3x4 |
x2x3 | + | + | - | + | - | - |
x3x4 | - | + | - | + | - | + |
x1x3 | - | - | - | + | + | + |
x1x2x3x4 | - | - | + | - | - | - |
Отже,
min ДНФ = x1x3 x2x3 x1x2x3x4
Список використаної літератури
«Дискретна математика» С.Лук’яненко. К-2000
«Комбінаторика» Д.Сафонов. М-1992
«Комбінаторика для програмістів» В.Липський. М-1988
Конспект лекцій
Комп’ютерна мережа Інтернет
Другие работы по теме:
Выпускная
Вопрос о генезисе метода проектов как педагогической технологии
Організація догляду за хворими з хронічною нирковою недостатністю
Гостра ниркова недостатність – це раптове повне або майже повне припинення діяльності нирок. Такий стан виникає при тяжкому порушенні кровообігу в риках або в зв’язку з дією на них отруйних речовин. Першою ознакою гострої ниркової недостатності є анурія (добовий діурез, менше 50 мл) або, олігурія (добовий діурез не перевищує 400 мл).
Випадкова величина
ТЕМА ВИПАДКОВА ВЕЛИЧИНА 1 Випадкова величина. Функція розподілу випадкової величини Зіставимо кожну елементарну подію конкретного випробування з деяким числом. Наприклад, розглянемо випробування, що полягає в підкиданні монети. Маємо простір елементарних подій – множину з двох можливих рівно ймовірних наслідків випробування: 1 – випадання "решки" та 2 – випадання герба.
Наведення усіх перестановок елементів множини
Перестановка як перевпорядкованість наборів елементів, об’єктів або функція, що задає таку перевпорядкованість. Всі можливі варіанти перестановок елементів множини за умови наявності трьох елементів за умови, що жоден елемент не залишається на місці.
Волшебный мир Пуанкаре
Многие профессиональные математики выделяли геометрию среди остальных разделов математики, считая её подобно механике экспериментальной наукой.
Штейнер Якоб
(Steiner Jacob) тейнер Якоб (18.3.1796-1.4.1863)-немецкий математик. Член Берлинской Академии Наук (1834г.). Родился в Утценсторфе (Швейцария). Окончил Гейдельбергский университет (1821г). Преподавал математику в Берлинском городском промышленном училище (1825-1835гг). Профессор математики Берлинского университета (с 1835г).
Випадкова величина
Функція розподілу випадкової величини. Найважливіші закони розподілу дискретних випадкових величин. Властивості функції розподілу. Дискретні і неперервні випадкові величини. Геометричний закон розподілу. Біноміальний розподіл випадкової величини.
Побудова скінченних множин
Множина як визначена сукупність елементів чи об’єктів. Списковий спосіб подання множини. Множина, кількість елементів якої скінченна (скінченна множина). Виведення декартового добутку з кожної заданої комбінації. Алгоритм рішення та реалізація програми.
Аньези, Мария Гаэтана
Мари́я Гаэта́на Анье́зи (итал. Maria Gaetana Agnesi; 16 мая 1718, Милан — 9 января 1799) — итальянский математик и филантроп. Она происходит из зажиточной купеческой семьи, в которой был 21 ребёнок. Мария Гаэтана была старшей из детей. Её отец был профессором математики, он с детства поддерживал математические способности дочери и позаботился о хорошем образовании Марии Гаэтаны.
Рафаил Островский
(1963) является профессором факультета компьютерных наук и профессором факультета математики в Университете Калифорнии в Лос-Анджелесе . Он - известный учёный в области алгоритмов и криптографии [1]. Проф. Островский получил степень доктора философии (PhD) в 1992 году в Массачузетском Технологическом Институте.
Скотт, Дана Стюарт
Да́на Стю́арт Скотт (англ. Dana Stewart Scott , р. 1932) — американский учёный в области математики и информатики. Исследования Скотта связанны с теорией моделей, теорией автоматов, модальной и интуиционистской логиками, конструктивной математикой и связью между логикой и теорией категорий.
Крамп, Кристиан
Кристиа́н (Кретье́н) Крамп (фр. Christian Kramp, 8 июля 1760, Страсбург — 13 мая 1826, там же) — французский математик (эльзасец). Известен работами по теории чисел, геометрии, математической кристаллографии, алгебре и механике. Предложил общепринятое обозначение n! для факториала.
Моделі та моделювання
Модель – це прообраз, опис або зображення якогось об'єкту. Класифікація моделей за способом зображення. Математична модель. Інформаційна модель. Комп'ютерна модель. Етапи створення комп'ютерної моделі.
Галузева термінологія
Text Функціональне термінознавство пов’язане з вивченням сучасних функцій терміну в різних текстах та ситуаціях професійного спілкування і підготовки спеціалістів, а також досліджує особливості використання термінів в мові і комп’ютерних системах.
Пирс Чарлз
Пирс Чарлз Сандерс (10 сентября 1839, Кембридж, шт. Массачусетс - 19 апреля 1914, близ Милфорда, шт. Пенсильвания), американский философ, логик, математик и естествоиспытатель.
Профілактична дезінфекція та її значення
РЕФЕРАТ на тему: “Профілактична дезінфекція, та її значення”. Профілактичну дезінфекцію здійснюють систематично в місцях ймовірно присутності патогенних мікроорганізмів (громадські туалети, вокзал, школи, спортзали). Для дезінфекції використовуються фізичні та хімічні методи. До фізичних методів належить механічне усунення збудника (миття, чищення щіткою, витрушування, фільтрація), спалювання, кип’ятіння, обробка в пароповітряній камері.
Принципи побудови формальних теорій
Реферат на тему: Принципи побудови формальних теорій Математична логіка як самостійний розділ сучасної математики сформувався відносно нещодавно - на рубежі дев’ятнадцятого і двадцятого століть. Виникнення і швидкий розвиток математичної логіки були пов’язані з так званою кризою основ (засад) математики, одним з проявів якої є відомі парадокси або антиномії канторівської теорії множин.
CAD CAM системи в гнучкому комп ютерному виробництві
КОНТРОЛЬНА РОБОТА НА ТЕМУ: CAD, CAM СИСТЕМИ В ГНУЧКОМУ КОМП’ЮТЕРНОМУ ВИРОБНИЦТВІ 1. Поняття про гнучкі системи та Cad/Cam-системи Гнучкі системи - це всеосяжний набір засобів для автоматизації процесів і технологічної підготовки виробництва, а також різних об'єктів промисловості. Системи містять у собі повний набір промислово адаптованих і програмних модулів, що довели свою ефективність, що функціонально охоплюють аналіз і створення креслень, підготовку виробництва на всіх етапах, а також забезпечують висока функціональна гнучкість усього циклу виробництва.
Алкоголізм - руйнівник зростаючого організму
ЗОШ 1-3 ступенів № 1 ім. В. Стефаника Р Е Ф Е Р А Т НА ТЕМУ: Алкоголізм - руйнівник зростаючого організму Учня 9-Г класу Гончарука Павла Коломия 2001 Руйнівник зростаючого організму.
Наркотичні речовини і їх шкідливість
Реферат на тему: Наркотичні речовини і їх шкідливість Багато тисяч років тому люди звернули увагу на те, що деякі речовини мають особливий вплив на людину - спричиняють галюцинації , заспокоєння , припиняють болісні відчуття , покращують сон , формують стан душевного комфорту , задоволення , емоційного піднесення .Вживання цих речовин найчастіше було пов’язане з релігійними містеріями.
Структура і склад по САПР
РЕФЕРАТ на тему: СТРУКТУРА І СКЛАД ПО САПР СТРУКТУРА І СКЛАД ПО САПР Програмне забезпечення САПР поділяється на загальносистемне, базове і прикладне.
Боголюбов Микола Миколайович - український математик механік фізик
Реферат На тему: Боголюбов Микола Миколайович - український математик, механік, фізик Народився у 1909 р. в Нижньому Новгороді. Після завершення семирічки самостійно займався математикою і фізикою. У віці 17 років закінчив аспірантуру при Академії наук України. В 1934—1958 рр. працював у Київському університеті (з 1936 р. — професор).
Зловживання алкоголем
Реферат на тему: „Зловживання алкоголем” Навряд чи якесь свято, сімейні урочистості або день народження обходиться без чарки спиртних напоїв. Вживання вина, пива, чи горілки міцно увійшло у побут і традиції нашого народу. Так що ж таке алкоголь? Харчовий продукт, наркотик чи отрута? У перше, і друге, і третє.