Намалюйте діаграму Вена й вирішіть область за областю, що належить множинному виразу.
У задачах на підрахунок заповнюйте області від центру назовні: спочатку всі множини, потім пари, потім окремі множини, потім зовнішню частину.
Використовуйте принцип включення–виключення для перевірки: |A ∪ B| = |A| + |B| − |A ∩ B|.
Для відношення перевіряйте кожну властивість на кожній парі й наводьте один контрприклад, коли вона не виконується.
Для функції порахуйте стрілки, що приходять до кожного елемента B: не більше однієї означає ін’єктивність, щонайменше одна — сюр’єктивність.
Теорія графів
Лема про рукостискання
Σ deg(v) = 2|E|
Повні графи
|E(Kn)| = n(n − 1)/2, |E(Km,n)| = m·n
Регулярний граф
|E| = n·k/2
Дерево і ліс
|E| = n − 1, |E| = n − c
Листки дерева
L = 2 + Σ (deg(v) − 2) over deg(v) ≥ 3
Ейлер
цикл: усі степені парні; шлях: рівно 2 непарні степені
Гамільтонові цикли в Kn
(n − 1)!/2
Оновлення в алгоритмі Дейкстри
d(v) = min(d(v), d(u) + w(u, v))
Маршрути довжиною L
(Mᴸ)ij
Метод
Випишіть степінь кожної вершини; сума степенів дорівнює подвоєній кількості ребер.
У задачах про Ейлера перевірте, що граф зв’язний, і порахуйте вершини з непарним степенем.
Для дерев використовуйте n − 1 ребро та лему про рукостискання.
Для алгоритму Дейкстри ведіть таблицю попередніх відстаней і щоразу фіксуйте незафіксовану вершину з найменшою відстанню.
Для мінімального остовного дерева відсортуйте ребра за вагою й пропускайте кожне ребро, що замикає цикл (Крускал), або нарощуйте одне дерево від початкової вершини (Прім).
Теорія чисел і арифметика за модулем
Ділення із залишком
a = q·n + r, 0 ≤ r < n
Евклід
gcd(a, b) = gcd(b, a mod b)
Найменше спільне кратне
lcm(a, b) = a·b/gcd(a, b)
Обернена
a·a⁻¹ ≡ 1 (mod n), gcd(a, n) = 1
Лінійна конгруенція
a·x ≡ b → x ≡ a⁻¹·b (mod n)
Функція Ейлера
φ(n) = n·∏(1 − 1/p), φ(pᵏ) = pᵏ − pᵏ⁻¹
Ферма
aᵖ⁻¹ ≡ 1 (mod p)
RSA
n = pq, φ = (p − 1)(q − 1), d = e⁻¹ mod φ, c = mᵉ mod n, m = cᵈ mod n
Метод
Спершу зведіть кожне число за модулем n; залишки лежать між 0 і n − 1.
Для НСД діліть послідовно за алгоритмом Евкліда; останній ненульовий залишок і є НСД.
Для оберненого елемента виконайте розширений алгоритм і візьміть коефіцієнт при a; якщо він від’ємний, додайте n.
Розв’язуйте a·x ≡ b множенням на a⁻¹; поєднуйте дві конгруенції, записавши x = r₁ + m₁k.
Для степенів запишіть показник у двійковому вигляді й послідовно підносьте до квадрата; в RSA d = e⁻¹ mod φ(n), де φ(n) = (p − 1)(q − 1).
2Задачі для практики
1.Логіка висловлювань і доведенняСередня
Чи є (q → r) ↔ (r → q) тавтологією, суперечністю чи випадковою формулою? Клікніть свою відповідь.
(q → r) ↔ (r → q)
1тавтологія
2суперечність
3випадкова формула
2.Логіка висловлювань і доведенняСкладна
Міркування з передумовами c → b; b і висновком c некоректне. Клікніть рядок таблиці істинності, що є контрприкладом.
c → bb∴ c
1b = 1, c = 1
2b = 1, c = 0
3b = 0, c = 1
4b = 0, c = 0
3.Множини, відношення та функціїСередня
Відношення R на {1, 2, 3, 4} зображено орієнтованим графом (петля означає (x, x) ∈ R). Виконується рівно одна з чотирьох властивостей. Клікніть її.
R = {(2, 2), (2, 3), (3, 2), (3, 3), (4, 1)}
1рефлексивне
2симетрична
3антисиметричне
4транзитивне
4.Множини, відношення та функціїСкладна
Відношення еквівалентності R на {1, …, 6} має класи {1, 3, 4}, {2, 5}, {6}. Скільки впорядкованих пар містить R? Позначте це число |R|.
{1, 3, 4}{2, 5}{6}
|R| =
5.Теорія графівСередня
Зв’язний граф має 16 вершин і 24 ребер. Скільки ребер k треба вилучити, щоб залишилося остовне дерево?
|V| = 16|E| = 24
k =
6.Теорія графівСкладна
Скільки замкнених маршрутів довжиною 2 починаються й закінчуються в A? Маршрут може повторювати вершини й ребра. Позначте число N.
M = матриця суміжностіL = 2
N =
7.Теорія чисел і арифметика за модулемСередня
Розв’яжіть 24x ≡ 25 (mod 37). Дайте розв’язок x, де 0 < x < 37.
24x ≡ 25 (mod 37)
x =
8.Теорія чисел і арифметика за модулемСкладна
Скористайтеся повторним піднесенням до квадрата, щоб знайти 2135 mod 45.
a = 2k = 135n = 45
2135 mod 45 =
3Розчини
1.Логіка висловлювань і доведення
Відповідь: випадкова формула
Логічна еквівалентність: дві формули еквівалентні (≡), коли мають однакове значення в кожному рядку таблиці істинності. Тавтологія дорівнює 1 у кожному рядку, суперечність — 0 у кожному рядку, а випадкова формула — ні те, ні інше. Корисні закони: закони де Моргана, ¬(a ∧ b) ≡ ¬a ∨ ¬b і ¬(a ∨ b) ≡ ¬a ∧ ¬b; a → b ≡ ¬a ∨ b ≡ ¬b → ¬a (контрапозиція); ¬(a → b) ≡ a ∧ ¬b; а також закони дистрибутивності, a ∨ (b ∧ c) ≡ (a ∨ b) ∧ (a ∨ c).
Таблиця істинності рядок за рядком
q = 1, r = 1: q → r = 1, r → q = 1, (q → r) ↔ (r → q) = 1
q = 1, r = 0: q → r = 0, r → q = 1, (q → r) ↔ (r → q) = 0
q = 0, r = 1: q → r = 1, r → q = 0, (q → r) ↔ (r → q) = 0
q = 0, r = 0: q → r = 1, r → q = 1, (q → r) ↔ (r → q) = 1
Класифікуйте
(q → r) ↔ (r → q): 1, 0, 0, 1
1 у 2 з 4 рядків, 0 в інших: випадкова формула.
Відповідь
випадкова формула
2.Логіка висловлювань і доведення
Відповідь: b = 1, c = 0
Квантори та міркування: ¬∀x P(x) ≡ ∃x ¬P(x) і ¬∃x P(x) ≡ ∀x ¬P(x). Переносьте заперечення досередини, міняйте кожен квантор, який воно проходить, і заперечуйте внутрішню формулу за законами логіки висловлювань, наприклад ¬(a → b) ≡ a ∧ ¬b. Міркування коректне, коли висновок дорівнює 1 у кожному рядку, де всі передумови дорівнюють 1. Один рядок з істинними передумовами та хибним висновком — це контрприклад, який показує, що міркування некоректне.
Передумови та висновок рядок за рядком
b = 1, c = 1: 1 1 | 1
b = 1, c = 0: 1 1 | 0
b = 0, c = 1: 0 0 | 1
b = 0, c = 0: 1 0 | 0
Контрприклад
b = 1, c = 0
Відповідь
b = 1, c = 0
Міркування такої форми схоже на коректне правило, але одного рядка досить, щоб показати, що це не так.
3.Множини, відношення та функції
Відповідь: транзитивне
Відношення: відношення R на множині X — це множина впорядкованих пар (x, y). R рефлексивне, коли (x, x) ∈ R для кожного x з X; симетричне, коли (x, y) ∈ R завжди супроводжується (y, x) ∈ R; антисиметричне, коли (x, y) і (y, x) одночасно належать R лише якщо x = y; і транзитивне, коли (x, y) та (y, z) в R тягнуть за собою (x, z) ∈ R. Відношення еквівалентності рефлексивне, симетричне й транзитивне та розбиває X на неперетинні класи.
рефлексивне
не виконується: (1, 1) ∉ R
симетрична
не виконується: (4, 1) ∈ R, (1, 4) ∉ R
антисиметричне
не виконується: (2, 3), (3, 2) ∈ R
транзитивне
виконується
Відповідь
транзитивне
4.Множини, відношення та функції
Відповідь: |R| = 14
Відношення: відношення R на множині X — це множина впорядкованих пар (x, y). R рефлексивне, коли (x, x) ∈ R для кожного x з X; симетричне, коли (x, y) ∈ R завжди супроводжується (y, x) ∈ R; антисиметричне, коли (x, y) і (y, x) одночасно належать R лише якщо x = y; і транзитивне, коли (x, y) та (y, z) в R тягнуть за собою (x, z) ∈ R. Відношення еквівалентності рефлексивне, симетричне й транзитивне та розбиває X на неперетинні класи.
Пари на клас
|R| = 3² + 2² + 1² = 14
Відповідь
|R| = 14
5.Теорія графів
Відповідь: k = 9
Ейлер, Гамільтон і дерева: зв’язний граф має ейлерів цикл (кожне ребро один раз, з поверненням до початку), коли кожна вершина має парний степінь, і ейлерів шлях, що не є циклом, коли рівно дві вершини мають непарний степінь; тоді шлях іде від однієї непарної вершини до другої. Гамільтонів цикл відвідує кожну вершину один раз; у Kn їх (n − 1)!/2. Дерево на n вершинах має n − 1 ребро, а зв’язний граф з m ребрами зберігає остовне дерево після вилучення m − n + 1 ребер.
Ребра остовного дерева
16 − 1 = 15
Ребра для вилучення
k = 24 − 15 = 9
Відповідь
k = 9
6.Теорія графів
Відповідь: N = 2
Степені: степінь вершини — це кількість ребер, що в ній сходяться. Кожне ребро має два кінці, тож степені в сумі дають подвоєну кількість ребер: Σ deg(v) = 2|E| (лема про рукостискання). Тому кількість вершин з непарним степенем парна. Kn має n(n − 1)/2 ребер, k-регулярний граф на n вершинах має nk/2, а дерево на n вершинах має n − 1 ребро.
Матриця суміжності
A: 0 1 1 0 0 0
B: 1 0 1 1 1 0
C: 1 1 0 0 1 0
D: 0 1 0 0 0 1
E: 0 1 1 0 0 0
F: 0 0 0 1 0 0
Спільні сусіди
(M²)AA = 0·0 + 1·1 + 1·1 + 0·0 + 0·0 + 0·0 = 2
Відповідь
N = 2
7.Теорія чисел і арифметика за модулем
Відповідь: x = 18
Обернені елементи та конгруенції: a має обернений за модулем n саме тоді, коли gcd(a, n) = 1. Розширений алгоритм Евкліда записує 1 = s·n + t·a, і тоді a⁻¹ ≡ t (mod n). Конгруенція a·x ≡ b (mod n) з gcd(a, n) = 1 має розв’язок x ≡ a⁻¹·b. Дві конгруенції x ≡ r₁ (mod m₁) і x ≡ r₂ (mod m₂) зі взаємно простими модулями мають один розв’язок за модулем m₁·m₂ (китайська теорема про лишки). Функція Ейлера φ(n) рахує числа від 1 до n, взаємно прості з n: φ(n) = n·∏(1 − 1/p).
Обернений до 24
r = 37, t = 0
r = 24, q = 1, t = 1
r = 13, q = 1, t = −1
r = 11, q = 1, t = 2
r = 2, q = 5, t = −3
r = 1, q = 2, t = 17
24−1 ≡ 17 (mod 37)
Розв’яжіть
x ≡ 17·25 = 425 ≡ 18 (mod 37)
перевірка: 24·18 = 432 ≡ 25 (mod 37)
Відповідь
x = 18
8.Теорія чисел і арифметика за модулем
Відповідь: 2135 mod 45 = 8
Степені за модулем і RSA: обчислюйте aᵏ mod n повторним піднесенням до квадрата: запишіть k у двійковому вигляді, підносьте до квадрата, зводьте після кожного кроку й перемножте степені, біти яких дорівнюють 1. Ферма: aᵖ⁻¹ ≡ 1 (mod p) для простого p, що не ділить a, тож показник можна зводити за модулем p − 1. RSA: оберіть прості p і q, n = p·q і φ(n) = (p − 1)(q − 1); відкритий показник e взаємно простий із φ(n), а закритий показник — d = e⁻¹ mod φ(n). Шифруйте за c = mᵉ mod n, а дешифруйте за m = cᵈ mod n.