- •7.091501: "Комп'ютерні системи та мережі"
- •7.091502: ”Системне програмування”
- •Лабораторна робота №1
- •Теоретичні відомості
- •Задачі на теорію множин
- •Задачі для самостійної роботи студентів
- •Завдання
- •Зобразити множину ab-c
- •Приклад відношень g
- •Контрольні питання
- •Лабораторна робота №2
- •Теоретичні відомості
- •Задачі на теорію множин
- •Задачі для самостійної роботи студентів
- •Контрольні питання
- •Лабораторна робота №3
- •Теоретичні відомості
- •Формули з’єднань
- •Біном Ньютона
- •2) Основна властивість біноміальних коефіцієнтів
- •Правило суми
- •Перестановки
- •Перестановки з повторенням
- •Розміщення
- •Розміщення з повтореннями
- •Сполучення
- •Сполучення з повтореннями
- •Біном Ньютона
- •Поліноміальна формула
- •Задачі для самостійної роботи студента
- •Контрольні питання
- •Лабораторна робота №4
- •Теоретичні відомості.
- •Лінійні рекурентні співвідношення з постійними коефіцієнтами
- •Твірна функція
- •Розбиття множини на підмножини
- •Задачі по темі Твірні функції:
- •Задачі для самостійної роботи студентів
- •Контрольні питання
- •Лабораторна робота №5.
- •Теоретичні відомості
- •Способи збереження інформації о графах
- •Задачі на теорію графів
- •Задачі для самостійної роботи студентів
- •Ізоморфізм графів
- •Досяжність і зв’язність.
- •Орієнтовані графи
- •Процедура пошуку в глибину у графі
- •Пошук у ширину
- •Ейлерові цикли
- •Гамільтонові цикли
- •Алгоритми пошуку мінімальних шляхів у графі
- •Задачі на теорію графів
- •Задачі для самостійної роботи студентів
- •Плоскі графи. Розфарбування графа
- •Контрольні питання
- •Пошук максимального потоку у мережі
- •Задачі з теорії графів
- •Задачі для самостійної роботи студентів
- •Лабораторна робота №8.
- •Теоретичні відомості
- •Задачі з теорії кодування
- •Задачі для самостійної роботи студентів
- •Контрольні питання
- •Список рекомендованої літератури
Розміщення з повтореннями
Задача. Букви абетки Морзе складаються із символів (крапок і тире). Скільки букв можна зобразити, якщо зажадати, щоб кожна буква містила не більш п'яти символів?
Рішення: Загальна кількість букв буде складатися з кількості, утвореної одним, двома, трьома й т. д символами. Виходить, для підрахунку загальної кількості букв необхідно окремо порахувати кількість слів, утворених різним числом символів.
Одним символом - А(2,1) = 21 = 2 (розміщення з повтореннями);
Двома символами - Р(2) = 22 = 4 (перестановки з повтореннями);
Трьома символами - А(2,3) = 23 = 8 (розміщення з повтореннями);
Чотирма символами - А(2,4) = 24 = 16 (розміщення з повтореннями);
П'ятьма символами - А(2,5) = 25 = 32 (розміщення з повтореннями).
Отже, загальне число символів дорівнює: 2 + 4 + 8 + 16 + 32 = 64.
Задача. Для того щоб відкрити камеру схову, використовується комбінація з 4 цифр (від 0 до 9), що набирається на 4 коліщатах. Скільки різних комбінацій існує?
Рішення. З умови задачі треба скласти всілякі комбінації по 4 елементи з даних 10. По формулі розміщень із повторенням одержуємо: =104 = 10 000 варіантів.
Сполучення
Задача. Два філателісти хочуть обмінятися марками. В одного для обміну є 7 марок, в іншого - 5. Скількома способами вони можуть поміняти дві марки одного на дві марки іншого?
Рішення. Перший філателіст повинен вибрати 2 марки з 7. Він може це зробитиспособами. Другий повинен вибрати 2 марки з 5. Він може це зробитиспособами. За правилом добутку одержуємо,способів зробити обмін.
Задача. З колоди, що містить 52 карти, вийняли 10 карт. У скількох випадках серед них виявиться рівно три тузи?
Рішення. Необхідно вибрати трьох тузів і сім «не тузів». Усього в колоді 4 тузи. Тому вибрати з них 3 можна способами. «Не тузів» у колоді 48. Вибрати з них 7 можнаспособами. За правилом добутку одержуємо:=способів вибрати з колоди 10 карт так, що серед них буде рівно три тузи.
Задача.Чотири автори повинні написати книгу з 17 глав, причому перший і третій повинні написати по 5 будь-яких глав, другий - 4, а четвертий 3 глави книги. Скількома способами можна розподілити глави між авторами?
Рішення:
У множині, що складається з 17 елементів, існує п’ятиелементних підмножин. Тому першому авторові можна дати глави способами. Аналогічно із тих 12 глав, що залишилися другий автор може одержати 4 глави способами. Третій автор одержує 5 главспособами, а четвертому дістаються 3 глави, що залишилися. Число способів розподілу глав дорівнює за правилом добутку, отже,
= 171531360
Задача.Скільки екзаменаційних комісій, що складаються з 7 членів, можна утворити з 14 викладачів?
Рішення:
Очевидно стільки, скільки існує семиелементних підмножин у чотирнадцятиелементній множині.
14 · 13 · 12 · 11· 10 · 9 · 8 14 · 13 · 12 · 11 · 10 · 9 · 8
= 7! = 7 · 6 · 5 · 4 · 3 · 2 · 1 = 3432
Задача.На першій із двох паралельних прямих лежить 10 крапок, на другій - 20. Скільки існує трикутників з вершинами в цих крапках?
Рішення: Трикутники можуть бути двох видів. У трикутників першого виду одна вершина на першій прямій, дві вершини - на другій прямій. Вершину на першій прямій можна вибрати 10 способами, дві вершини на другій прямій можна вибрати способами. Усього, отже, існує 10трикутників першого виду. У трикутників другого виду одна вершина перебуває на другій прямій, а дві інші вершини - на першій. Число таких трикутників підраховується аналогічно. Воно дорівнює 20. Таким чином, шукане число всіх трикутників
10 + 20 == 100 (19 + 9) = 2800
Задача. Скількома способами можна вибрати 5 делегатів зі складу конференції на якій присутні 15 чоловік?
Рішення: Тому що порядок вибору значення не має і делегати не повторюються, то число способів буде сполученнями без повторень. Значить
=