Намалюйте діаграму Вена й вирішіть область за областю, що належить множинному виразу.
У задачах на підрахунок заповнюйте області від центру назовні: спочатку всі множини, потім пари, потім окремі множини, потім зовнішню частину.
Використовуйте принцип включення–виключення для перевірки: |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.Логіка висловлювань і доведенняСередня
Яка формула логічно еквівалентна p → q? Клікніть її.
p → q
1q → p
2p ∨ ¬q
3¬p ∨ q
4¬p ∧ q
2.Логіка висловлювань і доведенняСкладна
Скільки з 16 рядків таблиці істинності роблять (a → (d ∨ c)) → ((b ↔ a) → b) істинним? Позначте це число N.
(a → (d ∨ c)) → ((b ↔ a) → b)
N =
3.Множини, відношення та функціїСередня
З 54 студентів першого курсу 28 склали математику (M), 27 склали фізику (P) і 31 склали хімію (C). 12 склали M і P, 10 склали M і C, 17 склали P і C, а 6 склали всі три. Скільки входять рівно до двох із трьох множин? Позначте число n.
|U| = 54
n =
4.Множини, відношення та функціїСкладна
Стрілкова діаграма показує функцію f: A → B, де A = {1, 2, 3} і B = {a, b, c, d}. Клікніть опис, що підходить для f.
f = {(1, d), (2, c), (3, a)}
1ін’єктивна, не сюр’єктивна
2сюр’єктивна, не ін’єктивна
3бієктивна
4жодна з цих
5.Теорія графівСередня
Чи має зв’язний граф ейлерів цикл, ейлерів шлях, що не є циклом, чи нічого з цього? Клікніть свою відповідь.
|V| = 6|E| = 7
1Ейлерів цикл
2Ейлерів шлях, не цикл
3жодна з цих
6.Теорія графівСкладна
Знайдіть загальну вагу W мінімального остовного дерева зваженого графа.
|V| = 7|E| = 10
W =
7.Теорія чисел і арифметика за модулемСередня
Знайдіть найменше додатне ціле x, де x ≡ 4 (mod 5) і x ≡ 6 (mod 7).
x ≡ 4 (mod 5)x ≡ 6 (mod 7)
x =
8.Теорія чисел і арифметика за модулемСкладна
Ключ RSA використовує p = 5, q = 41 і e = 19. Розшифруйте шифротекст c = 13: знайдіть повідомлення m.
p = 5q = 41e = 19c = 13
m =
3Розчини
1.Логіка висловлювань і доведення
Відповідь: ¬p ∨ q
Логічна еквівалентність: дві формули еквівалентні (≡), коли мають однакове значення в кожному рядку таблиці істинності. Тавтологія дорівнює 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).
Закон
a → b дорівнює 0 лише тоді, коли a = 1 і b = 0, тож це те саме, що ¬a ∨ b.
p → q ≡ ¬p ∨ q
Перевірте за таблицею істинності
p = 1, q = 1: 1 | 1 1 1 0
p = 1, q = 0: 0 | 1 1 0 0
p = 0, q = 1: 1 | 0 0 1 1
p = 0, q = 0: 1 | 1 1 1 0
Відповідь
¬p ∨ q
Стовпці після риски — це варіанти в показаному порядку.
2.Логіка висловлювань і доведення
Відповідь: N = 12
Таблиці істинності: формула з n різними змінними має 2ⁿ рядків, по одному для кожної комбінації значень істинності (1 = істина, 0 = хибність). Працюйте зсередини назовні й дайте кожній підформулі власний стовпець. ¬a змінює значення; a ∧ b дорівнює 1 лише тоді, коли обидва дорівнюють 1; a ∨ b дорівнює 0 лише тоді, коли обидва дорівнюють 0; a → b дорівнює 0 лише тоді, коли a = 1 і b = 0; a ↔ b дорівнює 1, коли обидві частини рівні.
Стовпці
d ∨ c; a → (d ∨ c); b ↔ a; (b ↔ a) → b; (a → (d ∨ c)) → ((b ↔ a) → b)
Розділення за a
a = 1: 8
a = 0: 4
N = 8 + 4 = 12
Відповідь
N = 12
3.Множини, відношення та функції
Відповідь: n = 21
Множини та діаграми Вена: A ∪ B містить елементи з A або B (або з обох), A ∩ B — елементи з обох, A − B — елементи A, яких немає в B, а доповнення A′ — усе в U, чого немає в A. На діаграмі Вена кожен множинний вираз — це об’єднання областей, тож рахуйте його область за областю. Включення–виключення: |A ∪ B| = |A| + |B| − |A ∩ B| і |A ∪ B ∪ C| = |A| + |B| + |C| − |A ∩ B| − |A ∩ C| − |B ∩ C| + |A ∩ B ∩ C|.
Центр і пари
M ∩ P ∩ C: 6
M ∩ P лише: 12 − 6 = 6
M ∩ C лише: 10 − 6 = 4
P ∩ C лише: 17 − 6 = 11
Окремі множини
M лише: 28 − 6 − 4 − 6 = 12
P лише: 27 − 6 − 11 − 6 = 4
C лише: 31 − 4 − 11 − 6 = 10
Відповідь
6 + 4 + 11 = 21
Відповідь
n = 21
4.Множини, відношення та функції
Відповідь: ін’єктивна, не сюр’єктивна
Функції та підрахунок: функція f: A → B дає кожному елементу A рівно один образ у B. f ін’єктивна (один до одного), коли різні елементи мають різні образи, сюр’єктивна (на), коли кожен елемент B є образом, і бієктивна, коли виконується і те, і те. За |A| = m і |B| = n існує nᵐ функцій, n!/(n − m)! ін’єктивних (m ≤ n), а за принципом включення–виключення Σ (−1)ᵏ·C(n, k)·(n − k)ᵐ сюр’єктивних. |𝒫(A)| = 2ᵐ і |A × B| = m·n.
Ін’єктивна?
кожен елемент B отримує не більше однієї стрілки → ін’єктивна
Сюр’єктивна?
b не отримують стрілок → не сюр’єктивна
Відповідь
ін’єктивна, не сюр’єктивна
Відповідь
ін’єктивна, не сюр’єктивна
5.Теорія графів
Відповідь: жодна з цих
Ейлер, Гамільтон і дерева: зв’язний граф має ейлерів цикл (кожне ребро один раз, з поверненням до початку), коли кожна вершина має парний степінь, і ейлерів шлях, що не є циклом, коли рівно дві вершини мають непарний степінь; тоді шлях іде від однієї непарної вершини до другої. Гамільтонів цикл відвідує кожну вершину один раз; у Kn їх (n − 1)!/2. Дерево на n вершинах має n − 1 ребро, а зв’язний граф з m ребрами зберігає остовне дерево після вилучення m − n + 1 ребер.
Найкоротші шляхи та остовні дерева: алгоритм Дейкстри фіксує одну вершину за раунд: незафіксовану вершину з найменшою попередньою відстанню. Її відстань тоді остаточна, а кожен сусід v отримує d(v) = min(d(v), d(u) + w(u, v)). Алгоритм Крускала будує мінімальне остовне дерево, беручи ребра від легких до важких і пропускаючи кожне ребро, що замкнуло б цикл; алгоритм Пріма нарощує одне дерево від початкової вершини, завжди додаючи найлегше ребро, що виходить з нього. Остовне дерево з n вершин має n − 1 ребро.
Алгоритм Крускала
CE (1): взяти
GC (3): взяти
BD (4): взяти
GD (7): взяти
GE (8): пропустити, замикає цикл
AB (9): взяти
GB (11): пропустити, замикає цикл
BC (16): пропустити, замикає цикл
EF (19): взяти
Загальна вага
W = 1 + 3 + 4 + 7 + 9 + 19 = 43
Відповідь
W = 43
7.Теорія чисел і арифметика за модулем
Відповідь: x = 34
Обернені елементи та конгруенції: 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).
Перша конгруенція
x = 4 + 5k
Друга конгруенція
4 + 5k ≡ 6 (mod 7) → 5k ≡ 2 (mod 7)
k ≡ 3·2 ≡ 6 (mod 7)
Результат
x = 4 + 5·6 = 34
x = 34
перевірка: 34 mod 5 = 4, 34 mod 7 = 6
Відповідь
x = 34
8.Теорія чисел і арифметика за модулем
Відповідь: m = 22
Степені за модулем і 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.