Дискретная математика — чек-лист самопроверки
Используйте после Логика → Алгебра логики — нормальные формы и схемы (по желанию) → Множества и отношения — формальный слой → Реляционная алгебра и таблицы → Дискретная математика → Графы — маршруты, остовы и раскраски → Рекуррентные соотношения → Теория чисел и анализ алгоритмов. Линейная алгебра: 342 — векторы, 343 — матрицы, 337 — NumPy. Отвечайте своими словами, затем сверяйтесь с подсказками. Практика алгоритмов на графах — 4.01 / графы.
- Сначала ответ без подсказки (2–4 предложения или схема).
- Застряли — откройте только "Куда смотреть".
- Сверка с "Суть ответа" и перечитывание статьи при расхождении.
Блок 1. Множества и отношения
1. Чем кортеж отличается от множества?
Куда смотреть: Дискретная математика, начало раздела "Множества"; Множества и отношения — формальный слой.
Суть ответа: в кортеже важен порядок координат; (1,2) ≠ (2,1), а {1,2} = {2,1}.
2. Что такое фактор-множество A/E?
Куда смотреть: Дискретная математика, "Фактор-множество"; Множества и отношения — формальный слой.
Суть ответа: множество классов эквивалентности; элемент — целый класс, не один объект. Аналог — GROUP BY по ключу.
3. Зачем матрица бинарного отношения из 0 и 1?
Куда смотреть: Дискретная математика, "Матрица отношения".
Суть ответа: компактное хранение связей на конечном множестве; для эквивалентности — блочно-диагональный вид после перестановок.
4. Назовите свойства частичного порядка.
Куда смотреть: Дискретная математика, "Отношения"; Множества и отношения — формальный слой.
Суть ответа: рефлексивность, антисимметричность, транзитивность; не любые два элемента сравнимы (в отличие от линейного порядка).
6. Что такое транзитивное замыкание и композиция отношений?
Куда смотреть: Множества и отношения — формальный слой, "Композиция, обратное отношение, замыкания"; Графы, "Достижимость".
Суть ответа: композиция R∘S — путь через промежуточный элемент; транзитивное замыкание добавляет все пары (a,c) при цепочке a→…→c. В орграфе — матрица достижимости (Уоршелл).
7. Чем симметрическая разность A △ B отличается от объединения A ∪ B?
Куда смотреть: Дискретная математика, "Операции", "Битовые представления".
Суть ответа: в △ только элементы ровно одного множества; в ∪ — все из обоих. Аналог — symmetric_difference, побитовый XOR.
8. Сформулируйте принцип Дирихле и приведите IT-пример.
Куда смотреть: Дискретная математика, "Принцип Дирихле".
Суть ответа: n объектов, m ящиков, n > m ⇒ в каком-то ящике ≥ 2 объектов. Пример: больше m ключей при m корзинах хеша — коллизия неизбежна.
Блок 2. Таблицы и SQL
9. Таблица БД как отношение — что такое строка и столбец?
Куда смотреть: Реляционная алгебра и таблицы.
Суть ответа: строка — кортеж значений доменов; столбец — домен Dᵢ; таблица — подмножество D₁×…×Dₙ.
10. Чем алгебра отношений (∪, ∩, ×) отличается от алгебры Кодда (σ, π, ⋈)?
Куда смотреть: Реляционная алгебра и таблицы, теория реляционных данных.
Суть ответа: первая оперирует множествами кортежей как в теории множеств; вторая добавляет выборку, проекцию, соединение с условием — то, из чего строится план SQL.
11. Почему JOIN без WHERE опасен на больших таблицах?
Куда смотреть: Реляционная алгебра и таблицы (декартово произведение).
Суть ответа: декартово произведение даёт |P|·|Q| строк; нужен фильтр или условие соединения.
Блок 3. Логика
12. Чем A → B отличается от A ∧ B?
Куда смотреть: Логика, "Импликация и эквивалентность".
Суть ответа: импликация ложна только при истинном A и ложном B; эквивалентно ¬A ∨ B.
13. Что такое СДНФ и зачем она нужна?
Куда смотреть: Алгебра логики — нормальные формы и схемы, Логика.
Суть ответа: дизъюнкция конъюнкт по всем единицам таблицы истинности; старт для минимизации и склеивания.
14. Для чего карта Карно (2–4 переменных)?
Куда смотреть: Алгебра логики — нормальные формы и схемы.
Суть ответа: визуальное объединение соседних единиц для короткой ДНФ; на большем числе переменных — автоматические методы.
Блок 4. Графы
15. Когда существует эйлеров цикл в связном неорграфе?
Куда смотреть: Дискретная математика, Графы — маршруты, остовы и раскраски, 4.01 / графы.
Суть ответа: все степени вершин чётны (с уточнениями для мультиграфов и компонент связности).
16. Чем гамильтонов цикл отличается от эйлерова?
Куда смотреть: Графы — маршруты, остовы и раскраски, Мыслительная база — итоги в разделе алгоритмов.
Суть ответа: эйлеров — по рёбрам; гамильтонов — по вершинам; последний связан с TSP и в общем случае вычислительно труднее.
17. Что такое DAG и топологическая сортировка?
Куда смотреть: 4.01 / графы.
Суть ответа: ориентированный граф без циклов; топопорядок — линейное расширение зависимостей (сборка, задачи).
18. Что такое минимальный остов?
Куда смотреть: Графы — маршруты, остовы и раскраски, 4.01 / графы.
Суть ответа: связный подграф без циклов на всех вершинах с минимальной суммой весов; алгоритмы Прима и Краскала.
19. Когда применять BFS, а когда Дейкстру?
Куда смотреть: Дискретная математика, Кратчайший путь — алгоритм Дейкстры.
Суть ответа: BFS — невзвешенный граф (каждое ребро = 1); Дейкстра — неотрицательные веса на рёбрах.
20. Чем алгоритм Уоршелла отличается от Флойда–Уоршелла?
Куда смотреть: Графы — маршруты, остовы и раскраски, "Достижимость"; Дискретная математика, таблица алгоритмов.
Суть ответа: Уоршелл строит достижимость (есть ли путь) через OR–AND на матрице; Флойд–Уоршелл — кратчайшие пути с весами через минимум сумм.
21. Что утверждает лемма о рукопожатиях?
Куда смотреть: Графы — маршруты, остовы и раскраски, "Задание графа".
Суть ответа: сумма степеней вершин = 2|E|; отсюда — чётное число вершин нечётной степени.
Блок 5. Комбинаторика и сложность
22. Почему полный перебор подмножеств — O(2^n)?
Куда смотреть: Дискретная математика, "Сложность перебора".
Суть ответа: у n элементов 2^n подмножеств; булеан множества мощности n.
23. Связь коммивояжёра и O(n!).
Куда смотреть: Дискретная математика, Графы — маршруты, остовы и раскраски, Теория чисел, псевдокод и анализ алгоритмов.
Суть ответа: n! перестановок вершин; полный перебор гамильтоновых циклов непрактичен при больших n.
24. Как индукция связана с циклом for?
Куда смотреть: Множества и отношения — формальный слой.
Суть ответа: база цикла = база индукции; шаг цикла сохраняет инвариант = индуктивный переход.
25. Что даёт мастер-теорема для T(n) = 2T(n/2) + n?
Куда смотреть: Рекуррентные соотношения, Теория чисел и анализ алгоритмов.
Суть ответа: Θ(n log n) — типичная сложность merge sort и других алгоритмов «два подзадачи половинного размера плюс линейное слияние».
Типичные путаницы
| Путают | Различие |
|---|---|
| Эйлер / Гамильтон | рёбра vs вершины |
| Уоршелл / Флойд–Уоршелл | достижимость vs кратчайший путь с весами |
| Кортеж / множество | порядок vs без порядка |
△ / ∪ | только в одном vs в любом из двух |
| BFS / Дейкстра | без весов vs неотрицательные веса |
| ∪ в SQL / × без условия | объединение строк vs декартово произведение |
| ДНФ / КНФ | ∨ конъюнкт vs ∧ дизъюнкт |
| Рекуррентность в коде / μ-рекурсия | оценка сложности vs теория вычислимости |
Обзор маршрута: Математическая основа IT — обзор. Самопроверка по ТАФЯ: ТАФЯ — чек-лист самопроверки.