Нарисуйте диаграмму Венна и по областям решите, что относится к множеству, заданному выражением.
В задачах на подсчёт заполняйте области от центра к краям: сначала все множества, затем пары, затем отдельные множества, затем внешнюю область.
Используйте формулу включений и исключений как проверку: |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)
1a ∨ (b ∧ c)
2(a ∨ b) ∧ (a ∨ c)
3(a ∧ b) ∨ c
4(a ∧ b) ∨ (a ∧ c)
2.Логика высказываний и доказательстваСложная
В скольких из 16 строк таблицы истинности ¬(((c → d) → (d → ¬c)) ∧ (b ∧ a)) истинно? Обозначим это число N.
¬(((c → d) → (d → ¬c)) ∧ (b ∧ a))
N =
3.Множества, отношения и функцииСредняя
В группе из 61 студентов 45 говорят по-французски (F), 32 — по-немецки (G) и 26 — по-испански (S). 20 говорят по-французски и по-немецки, 18 — по-французски и по-испански, 13 — по-немецки и по-испански, а 6 — на всех трёх языках. Сколько человек не входят ни в одно из трёх множеств?
|U| = 61
|(F ∪ G ∪ S)′| =
4.Множества, отношения и функцииСложная
Отношение эквивалентности R на {1, …, 10} имеет классы {1, 4, 10}, {5, 6, 7}, {2, 3, 8, 9}. Сколько упорядоченных пар содержит R? Обозначим это число |R|.
{1, 4, 10}{5, 6, 7}{2, 3, 8, 9}
|R| =
5.Теория графовСредняя
Сколько различных гамильтоновых циклов, H, в полном графе K5? Циклы, отличающиеся только начальной вершиной или направлением, считаются одним и тем же.
K5
H =
6.Теория графовСложная
Алгоритм Дейкстры запускается из A. Нажмите на вершину, которая фиксируется (становится постоянной) на шаге 5; сама A фиксируется на шаге 1.
начало: Aшаг 5
1A
2B
3C
4D
5E
6F
7.Теория чисел и модульная арифметикаСредняя
Найдите функцию Эйлера φ(833), число целых чисел от 1 до 833, взаимно простых с 833.
n = 833 = 72·17
φ(833) =
8.Теория чисел и модульная арифметикаСложная
Сколько решений, N, имеет сравнение 4x ≡ 10 (mod 30) среди {0, 1, …, 29}?
4x ≡ 10 (mod 30)
N =
3Растворы
1.Логика высказываний и доказательства
Ответ: (a ∧ b) ∨ (a ∧ c)
Логическая эквивалентность: две формулы эквивалентны (≡), если в каждой строке таблицы истинности они имеют одинаковое значение. Тавтология равна 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) ≡ (a ∧ b) ∨ (a ∧ c).
a ∧ (b ∨ c) ≡ (a ∧ b) ∨ (a ∧ c)
Проверка по таблице истинности
a = 1, b = 1, c = 1: 1 | 1 1 1 1
a = 1, b = 1, c = 0: 1 | 1 1 1 1
a = 1, b = 0, c = 1: 1 | 1 1 1 1
a = 1, b = 0, c = 0: 0 | 1 1 0 0
a = 0, b = 1, c = 1: 0 | 1 1 1 0
a = 0, b = 1, c = 0: 0 | 0 0 0 0
a = 0, b = 0, c = 1: 0 | 0 0 1 0
a = 0, b = 0, c = 0: 0 | 0 0 0 0
Ответ
(a ∧ b) ∨ (a ∧ c)
Столбцы после черты — варианты ответа в показанном порядке.
2.Логика высказываний и доказательства
Ответ: N = 13
Таблицы истинности: у формулы с n различными переменными 2ⁿ строк, по одной для каждой комбинации значений истинности (1 = истина, 0 = ложь). Работайте изнутри наружу и отводите каждой подформуле отдельный столбец. ¬a меняет значение на противоположное; a ∧ b равно 1 только тогда, когда оба равны 1; a ∨ b равно 0 только тогда, когда оба равны 0; a → b равно 0 только при a = 1 и b = 0; a ↔ b равно 1, когда обе части равны.
Множества и диаграммы Венна: 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|.
Центр и пары
F ∩ G ∩ S: 6
F ∩ G только: 20 − 6 = 14
F ∩ S только: 18 − 6 = 12
G ∩ S только: 13 − 6 = 7
Отдельные множества
F только: 45 − 14 − 12 − 6 = 13
G только: 32 − 14 − 7 − 6 = 5
S только: 26 − 12 − 7 − 6 = 1
Ответ
|F ∪ G ∪ S| = 58
|(F ∪ G ∪ S)′| = 61 − 58 = 3
Ответ
|(F ∪ G ∪ S)′| = 3
4.Множества, отношения и функции
Ответ: |R| = 34
Отношения: отношение 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² + 3² + 4² = 34
Ответ
|R| = 34
5.Теория графов
Ответ: H = 12
Эйлер, Гамильтон и деревья: связный граф имеет эйлеров цикл (каждое ребро один раз, с возвратом в начало), когда все вершины имеют чётную степень, и эйлеров путь, не являющийся циклом, когда ровно две вершины имеют нечётную степень; тогда путь идёт от одной нечётной вершины к другой. Гамильтонов цикл посещает каждую вершину один раз; в Kn их (n − 1)!/2. У дерева на n вершинах n − 1 ребро, а связный граф с m рёбрами сохраняет остовное дерево после удаления m − n + 1 рёбер.
Посчитайте
H = (5 − 1)!/2 = 24/2 = 12
Ответ
H = 12
6.Теория графов
Ответ: E
Кратчайшие пути и остовные деревья: алгоритм Дейкстры фиксирует по одной вершине на шаге: нефиксированную вершину с наименьшим предварительным расстоянием. Её расстояние становится окончательным, а каждый сосед v получает d(v) = min(d(v), d(u) + w(u, v)). Алгоритм Краскала строит минимальное остовное дерево, беря рёбра от лёгких к тяжёлым и пропуская любое ребро, которое замкнуло бы цикл; алгоритм Прима растит одно дерево из начальной вершины, всегда добавляя самое лёгкое ребро, выходящее из него. В остовном дереве на n вершинах n − 1 ребро.
Алгоритм Дейкстры по шагам
1. A (0): B: 13, C: 5
2. C (5): B: 7, E: 13
3. B (7): D: 11
4. D (11): F: 14
5. E (13)
6. F (14)
шаг 5
E
Ответ
E
7.Теория чисел и модульная арифметика
Ответ: φ(833) = 672
Обратные элементы и сравнения: у 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).
Простые множители
833 = 72·17
Функция Эйлера
φ(833) = φ(49)·φ(17) = 42·16 = 672
Ответ
φ(833) = 672
8.Теория чисел и модульная арифметика
Ответ: N = 2
Обратные элементы и сравнения: у 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).