- •7.091501: "Комп'ютерні системи та мережі"
- •7.091502: ”Системне програмування”
- •Лабораторна робота №1
- •Теоретичні відомості
- •Задачі на теорію множин
- •Задачі для самостійної роботи студентів
- •Завдання
- •Зобразити множину ab-c
- •Приклад відношень g
- •Контрольні питання
- •Лабораторна робота №2
- •Теоретичні відомості
- •Задачі на теорію множин
- •Задачі для самостійної роботи студентів
- •Контрольні питання
- •Лабораторна робота №3
- •Теоретичні відомості
- •Формули з’єднань
- •Біном Ньютона
- •2) Основна властивість біноміальних коефіцієнтів
- •Правило суми
- •Перестановки
- •Перестановки з повторенням
- •Розміщення
- •Розміщення з повтореннями
- •Сполучення
- •Сполучення з повтореннями
- •Біном Ньютона
- •Поліноміальна формула
- •Задачі для самостійної роботи студента
- •Контрольні питання
- •Лабораторна робота №4
- •Теоретичні відомості.
- •Лінійні рекурентні співвідношення з постійними коефіцієнтами
- •Твірна функція
- •Розбиття множини на підмножини
- •Задачі по темі Твірні функції:
- •Задачі для самостійної роботи студентів
- •Контрольні питання
- •Лабораторна робота №5.
- •Теоретичні відомості
- •Способи збереження інформації о графах
- •Задачі на теорію графів
- •Задачі для самостійної роботи студентів
- •Ізоморфізм графів
- •Досяжність і зв’язність.
- •Орієнтовані графи
- •Процедура пошуку в глибину у графі
- •Пошук у ширину
- •Ейлерові цикли
- •Гамільтонові цикли
- •Алгоритми пошуку мінімальних шляхів у графі
- •Задачі на теорію графів
- •Задачі для самостійної роботи студентів
- •Плоскі графи. Розфарбування графа
- •Контрольні питання
- •Пошук максимального потоку у мережі
- •Задачі з теорії графів
- •Задачі для самостійної роботи студентів
- •Лабораторна робота №8.
- •Теоретичні відомості
- •Задачі з теорії кодування
- •Задачі для самостійної роботи студентів
- •Контрольні питання
- •Список рекомендованої літератури
Правило суми
Задача. З міста А в місто Б веде 6 доріг, а з міста Б у місто В - 4 дороги, З міста А в місто Г - 2 дороги, і з міста Г у місто В - теж 2 дороги. Скількома способами можна проїхати від А до В?
Рішення. З міста А в місто В можна потрапити або через місто Б, або через місто Г. За правилом добутку через місто Б можна проїхати 6 4=24 способами, через місто Г - 2 2=4 способами. Тоді з міста А в місто В можна потрапити 24+4=28 способами.
При використанні правила суми необхідно стежити, щоб жоден зі способів вибору об'єкта А не збігався з яким-небудь способом вибору об'єкта В.
Задача. Скількома способами можна поставити на шахівницю білого й чорного королів так, щоб вийшла припустима за правилами гри комбінація.
Рішення. Шахове поле має 64 клітки, тому білого короля можна поставити 64 способами. Як відомо, король б'є клітки, розташовані безпосередньо поруч із ним. Таким чином, якщо король перебуває в куті, то під боєм перебувають 3 клітки, якщо у стіни, то - 5, якщо в центрі, то - 8. Очевидно, що ставити чорного короля не можна в ту ж клітку, де перебуває білий король й у клітку, що перебуває під боєм. Тому що існує 4 способи поставити короля в кут, 24 способу - у стіни й 36 способів - у центрі поля, отже відповідь на питання задачі обчислюється в такий спосіб: 4 (64-4)+24 (64-6)+36 (64-9)=3612.
Задача. Скількома способами можна розташувати на шахівниці 8 тур так, щоб вони не могли бити одна одну.
Рішення. На кожній вертикалі й горизонталі повинні стояти по одній турі. Уведемо позначення: перестановка (13256487) означає, що на першій горизонталі тура стоїть в першому полі, на другій – у третьому, на третій – у другому й т.д. Таким чином, число шуканих розташувань дорівнює кількості перестановок чисел 1, 2, 3, 4, 5, 6, 7, 8, тобто Р8=8!=40320.
Задача. Скільки способів розбити 6 чоловіків й 6 жінок на пари для танців?
Рішення. Поставимо чоловіків в одну лінію в довільному порядку. Нехай кожна жінка вибирає собі пару. Тоді кількість способів розбивки на пари дорівнює кількості способів переставити 6 різних предметів, тобто дорівнює 6!.
Перестановки
Задача. Скільки шестизначних чисел, кратних п'яти, можна скласти із цифр 1,2,3,4,5,6 за умови, що в числі цифри не повторюються.
Рішення: Для того, щоб число, складене із заданих цифр, ділилося на 5, необхідно й досить, щоб цифра 5 стояла на останнім місці. Інші п'ять цифр можуть стояти на п'ятьох місцях, що залишилися, у будь-якому порядку. Отже, шукане число шестизначних чисел, кратних п'яти, дорівнює числу перестановок з п'яти елементів, тобто 5! = 5* 4* 3*·2* 1 = 120.
Задача. Дванадцяти учням видані два варіанти контрольної роботи. Скількома способами їх можна посадити у два ряди, щоб поруч не було однакових варіантів, а в сидячих один за одним був той самий варіант?
Рішення: Виходячи з умови задачі маємо, що учні сидять у два ряди, по шести людин у кожному, і в кожного ряду свій варіант. Виходить, число способів буде складатися із числа перестановок у кожному ряді (тобто 6!). Але при кожному розкладі цих перестановок два будь-яких учні можуть помінятися рядами, а це число розміщень із повтореннями з 6 по 2 (тобто 62). Виходить, число способів уже стало (6!)2. Також необхідно врахувати, що ці два ряди можна поміняти місцями, отже число способів подвоїться - 2*(6!)2.