Нарисуйте диаграмму Венна и по областям решите, что относится к множеству, заданному выражением.
В задачах на подсчёт заполняйте области от центра к краям: сначала все множества, затем пары, затем отдельные множества, затем внешнюю область.
Используйте формулу включений и исключений как проверку: |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.Логика высказываний и доказательстваСредняя
Вы хотите доказать ¬a → (b ∧ c) от контрапозиции. Какую импликацию вы доказываете вместо неё? Нажмите на неё.
¬a → (b ∧ c)
1¬(b ∧ c) → ¬¬a
2¬a ∧ ¬(b ∧ c)
3¬¬a → ¬(b ∧ c)
4(b ∧ c) → ¬a
2.Логика высказываний и доказательстваСложная
Рассуждение с посылками p → q; ¬p и выводом ¬q неправильно. Нажмите на строку таблицы истинности, которая является контрпримером.
p → q¬p∴ ¬q
1p = 1, q = 1
2p = 1, q = 0
3p = 0, q = 1
4p = 0, q = 0
3.Множества, отношения и функцииСредняя
Отношение R на {1, 2, 3, 4} нарисовано как ориентированный граф (петля означает (x, x) ∈ R). Выполняется ровно одно из четырёх свойств. Нажмите на него.
На X = {1, 2, …, 9} отношение x ~ y выполняется, когда x ≡ y (mod 5). Сколько элементов в классе эквивалентности [3]?
X = {1, …, 9}x ~ y ⟺ 5 | (x − y)
|[3]| =
5.Теория графовСредняя
Есть ли в связном графе эйлеров цикл, эйлеров путь, не являющийся циклом, или ни то ни другое? Нажмите на ваш ответ.
|V| = 5|E| = 6
1Эйлеров цикл
2Эйлеров путь, не цикл
3ни то, ни другое
6.Теория графовСложная
Сколько существует замкнутых маршрутов длины 3, начинающихся и заканчивающихся в D? Маршрут может повторять вершины и рёбра. Обозначим это число N.
M = матрица смежностиL = 3
N =
7.Теория чисел и модульная арифметикаСредняя
Решите 40x ≡ 35 (mod 73). Укажите решение x, для которого 0 < x < 73.
40x ≡ 35 (mod 73)
x =
8.Теория чисел и модульная арифметикаСложная
В ключе RSA p = 7, q = 43 и e = 19. Расшифруйте шифртекст c = 74: найдите сообщение m.
p = 7q = 43e = 19c = 74
m =
3Растворы
1.Логика высказываний и доказательства
Ответ: ¬(b ∧ c) → ¬¬a
Логическая эквивалентность: две формулы эквивалентны (≡), если в каждой строке таблицы истинности они имеют одинаковое значение. Тавтология равна 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 = ¬a, b = b ∧ c
Контрапозиция
¬b → ¬a = ¬(b ∧ c) → ¬¬a
Ответ
¬(b ∧ c) → ¬¬a
Контрапозиция эквивалентна исходному утверждению, поэтому её доказательство доказывает и само утверждение.
2.Логика высказываний и доказательства
Ответ: p = 0, q = 1
Кванторы и рассуждения: ¬∀x P(x) ≡ ∃x ¬P(x) и ¬∃x P(x) ≡ ∀x ¬P(x). Переносите отрицание внутрь, меняйте каждый квантор, через который оно проходит, и отрицайте внутреннюю формулу по законам логики высказываний, например ¬(a → b) ≡ a ∧ ¬b. Рассуждение правильно, если вывод равен 1 в каждой строке, где все посылки равны 1. Одной строки с истинными посылками и ложным выводом достаточно, чтобы получить контрпример и показать, что рассуждение неправильно.
Посылки и вывод по строкам
p = 1, q = 1: 1 0 | 0
p = 1, q = 0: 0 0 | 1
p = 0, q = 1: 1 1 | 0
p = 0, q = 0: 1 1 | 1
Контрпример
p = 0, q = 1
Ответ
p = 0, q = 1
Рассуждение такой формы выглядит как правильное правило, но одной строки достаточно, чтобы показать, что это не так.
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 на непересекающиеся классы.
рефлексивно
выполняется
симметричная
не выполняется: (2, 4) ∈ R, (4, 2) ∉ R
антисимметрично
не выполняется: (1, 2), (2, 1) ∈ R
транзитивно
не выполняется: (1, 2), (2, 4) ∈ R, (1, 4) ∉ R
Ответ
рефлексивно
4.Множества, отношения и функции
Ответ: |[3]| = 2
Отношения: отношение 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 на непересекающиеся классы.
Класс
[3] = {3, 8}
|[3]| = 2
Ответ
|[3]| = 2
5.Теория графов
Ответ: Эйлеров путь, не цикл
Эйлер, Гамильтон и деревья: связный граф имеет эйлеров цикл (каждое ребро один раз, с возвратом в начало), когда все вершины имеют чётную степень, и эйлеров путь, не являющийся циклом, когда ровно две вершины имеют нечётную степень; тогда путь идёт от одной нечётной вершины к другой. Гамильтонов цикл посещает каждую вершину один раз; в Kn их (n − 1)!/2. У дерева на n вершинах n − 1 ребро, а связный граф с m рёбрами сохраняет остовное дерево после удаления m − n + 1 рёбер.
Эйлеров путь начинается в одной нечётной вершине и заканчивается в другой.
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
B: 1 0 1 1 1
C: 1 1 0 0 1
D: 0 1 0 0 1
E: 0 1 1 1 0
Ещё один шаг
(M³)DD = 1·0 + 1·1 + 2·0 + 2·0 + 1·1 = 2
Ответ
N = 2
7.Теория чисел и модульная арифметика
Ответ: x = 10
Обратные элементы и сравнения: у 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).
Обратный к 40
r = 73, t = 0
r = 40, q = 1, t = 1
r = 33, q = 1, t = −1
r = 7, q = 4, t = 2
r = 5, q = 1, t = −9
r = 2, q = 2, t = 11
r = 1, q = 2, t = −31
40−1 ≡ 42 (mod 73)
Решите
x ≡ 42·35 = 1470 ≡ 10 (mod 73)
проверка: 40·10 = 400 ≡ 35 (mod 73)
Ответ
x = 10
8.Теория чисел и модульная арифметика
Ответ: m = 81
Степени по модулю и 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.