Нарисуйте диаграмму Венна и по областям решите, что относится к множеству, заданному выражением.
В задачах на подсчёт заполняйте области от центра к краям: сначала все множества, затем пары, затем отдельные множества, затем внешнюю область.
Используйте формулу включений и исключений как проверку: |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
Эйлер
цикл: все степени чётные; путь: ровно две нечётные степени
Гамильтоновы циклы в 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.Логика высказываний и доказательстваСредняя
Какая формула логически эквивалентна (r ∨ q) → p? Нажмите на неё.
(r ∨ q) → p
1(r → p) ∨ (q → p)
2r ∨ (q → p)
3(r → p) ∧ (q → p)
4(r ∧ q) → p
2.Логика высказываний и доказательстваСложная
Какое утверждение эквивалентно ¬∀x (P(x) → ∃y R(x, y)), если отрицание перенесено полностью внутрь? Нажмите на него.
¬∀x (P(x) → ∃y R(x, y))
1∃x (¬P(x) ∧ ∃y R(x, y))
2∃x (P(x) → ∀y ¬R(x, y))
3∃x (P(x) ∧ ∀y ¬R(x, y))
4∀x (P(x) ∧ ∀y ¬R(x, y))
3.Множества, отношения и функцииСредняя
Опрос 32 человек показал, что ноутбук (L) есть у 20, планшет (T) — у 14, смарт-часы (W) — у 19. L и T есть у 11, L и W — у 11, T и W — у 7, а все три устройства — у 6. Сколько человек не входят ни в одно из трёх множеств?
|U| = 32
|(L ∪ T ∪ W)′| =
4.Множества, отношения и функцииСложная
Стрелочная диаграмма показывает функцию f: A → B, где A = {1, 2, 3} и B = {a, b, c, d}. Нажмите на описание, подходящее для f.
f = {(1, c), (2, a), (3, a)}
1инъективна, но не сюръективна
2сюръективна, но не инъективна
3биективна
4ни то, ни другое
5.Теория графовСредняя
Сколько различных гамильтоновых циклов, H, в полном графе K7? Циклы, отличающиеся только начальной вершиной или направлением, считаются одним и тем же.
K7
H =
6.Теория графовСложная
Алгоритм Краскала строит минимальное остовное дерево. Нажмите на ребро, которое он добавляет под номером 4; пропущенные рёбра не считаются.
k = 4
1ребро AB
2ребро AC
3ребро BC
4ребро BD
5ребро CE
6ребро DE
7ребро BE
7.Теория чисел и модульная арифметикаСредняя
Найдите обратный к 31 по модулю 41: число x, для которого 0 < x < 41 и 31·x ≡ 1 (mod 41).
a = 31n = 41
31−1 mod 41 =
8.Теория чисел и модульная арифметикаСложная
В ключе RSA используются простые числа p = 23 и q = 37 и открытый показатель e = 13. Найдите закрытый показатель d (0 < d < φ(n)).
p = 23q = 37e = 13
d =
3Растворы
1.Логика высказываний и доказательства
Ответ: (r → p) ∧ (q → p)
Логическая эквивалентность: две формулы эквивалентны (≡), если в каждой строке таблицы истинности они имеют одинаковое значение. Тавтология равна 1 в каждой строке, противоречие равно 0 в каждой строке, а нейтральная формула (contingency) — ни то ни другое. Полезные законы: законы де Моргана, ¬(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) → c требует c всякий раз, когда выполняется a или b: (a → c) ∧ (b → c).
(r ∨ q) → p ≡ (r → p) ∧ (q → p)
Проверка по таблице истинности
p = 1, q = 1, r = 1: 1 | 1 1 1 1
p = 1, q = 1, r = 0: 1 | 1 1 1 1
p = 1, q = 0, r = 1: 1 | 1 1 1 1
p = 1, q = 0, r = 0: 1 | 1 1 1 1
p = 0, q = 1, r = 1: 0 | 0 1 0 0
p = 0, q = 1, r = 0: 0 | 1 0 0 1
p = 0, q = 0, r = 1: 0 | 1 1 0 1
p = 0, q = 0, r = 0: 1 | 1 1 1 1
Ответ
(r → p) ∧ (q → p)
Столбцы после черты — варианты ответа в показанном порядке.
2.Логика высказываний и доказательства
Ответ: ∃x (P(x) ∧ ∀y ¬R(x, y))
Кванторы и рассуждения: ¬∀x P(x) ≡ ∃x ¬P(x) и ¬∃x P(x) ≡ ∀x ¬P(x). Переносите отрицание внутрь, меняйте каждый квантор, через который оно проходит, и отрицайте внутреннюю формулу по законам логики высказываний, например ¬(a → b) ≡ a ∧ ¬b. Рассуждение правильно, если вывод равен 1 в каждой строке, где все посылки равны 1. Одной строки с истинными посылками и ложным выводом достаточно, чтобы получить контрпример и показать, что рассуждение неправильно.
Перенесите отрицание внутрь
¬∀x (P(x) → ∃y R(x, y)) ≡ ∃x (P(x) ∧ ∀y ¬R(x, y))
Ответ
∃x (P(x) ∧ ∀y ¬R(x, y))
Остальные варианты либо оставляют какой-то квантор без изменения, либо меняют порядок кванторов, либо неверно отрицают внутреннюю формулу.
3.Множества, отношения и функции
Ответ: |(L ∪ T ∪ W)′| = 2
Множества и диаграммы Венна: 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|.
Центр и пары
L ∩ T ∩ W: 6
L ∩ T только: 11 − 6 = 5
L ∩ W только: 11 − 6 = 5
T ∩ W только: 7 − 6 = 1
Отдельные множества
L только: 20 − 5 − 5 − 6 = 4
T только: 14 − 5 − 1 − 6 = 2
W только: 19 − 5 − 1 − 6 = 7
Ответ
|L ∪ T ∪ W| = 30
|(L ∪ T ∪ W)′| = 32 − 30 = 2
Ответ
|(L ∪ T ∪ W)′| = 2
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.
Инъективна?
f(2) = f(3) = a → не инъективна
Сюръективна?
b, d не получают ни одной стрелки → не сюръективна
Ответ
ни то, ни другое
Ответ
ни то, ни другое
5.Теория графов
Ответ: H = 360
Эйлер, Гамильтон и деревья: связный граф имеет эйлеров цикл (каждое ребро один раз, с возвратом в начало), когда все вершины имеют чётную степень, и эйлеров путь, не являющийся циклом, когда ровно две вершины имеют нечётную степень; тогда путь идёт от одной нечётной вершины к другой. Гамильтонов цикл посещает каждую вершину один раз; в Kn их (n − 1)!/2. У дерева на n вершинах n − 1 ребро, а связный граф с m рёбрами сохраняет остовное дерево после удаления m − n + 1 рёбер.
Посчитайте
H = (7 − 1)!/2 = 720/2 = 360
Ответ
H = 360
6.Теория графов
Ответ: ребро AB
Кратчайшие пути и остовные деревья: алгоритм Дейкстры фиксирует по одной вершине на шаге: нефиксированную вершину с наименьшим предварительным расстоянием. Её расстояние становится окончательным, а каждый сосед v получает d(v) = min(d(v), d(u) + w(u, v)). Алгоритм Краскала строит минимальное остовное дерево, беря рёбра от лёгких к тяжёлым и пропуская любое ребро, которое замкнуло бы цикл; алгоритм Прима растит одно дерево из начальной вершины, всегда добавляя самое лёгкое ребро, выходящее из него. В остовном дереве на n вершинах n − 1 ребро.
Алгоритм Краскала
1. CE (1)
2. BD (3)
3. BE (5)
4. AB (17)
номер ребра 4
AB
Ответ
ребро AB
7.Теория чисел и модульная арифметика
Ответ: 31−1 mod 41 = 4
Обратные элементы и сравнения: у a есть обратный по модулю n ровно тогда, когда НОД(a, n) = 1. Расширенный алгоритм Евклида записывает 1 = s·n + t·a, откуда a⁻¹ ≡ t (mod n). Сравнение a·x ≡ b (mod n) при НОД(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).
Расширенный алгоритм Евклида
Каждый остаток r записывается как r ≡ t·31 (mod 41).
r = 41, t = 0
r = 31, q = 1, t = 1
r = 10, q = 3, t = −1
r = 1, q = 10, t = 4
Обратная матрица
1 ≡ 4·31 (mod 41)
x = 4
проверка: 31·4 = 124 = 3·41 + 1
Ответ
31−1 mod 41 = 4
8.Теория чисел и модульная арифметика
Ответ: d = 61
Степени по модулю и 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.