Дискретная математика — чек-лист самопроверки
Используйте после 31 → 314 (по желанию) → 321 → 322 → 32 → 323. Отвечайте своими словами, затем сверяйтесь с подсказками. Практика алгоритмов на графах — 4.01 / графы.
- Сначала ответ без подсказки (2–4 предложения или схема).
- Застряли — откройте только «Куда смотреть».
- Сверка с «Суть ответа» и перечитывание статьи при расхождении.
Блок 1. Множества и отношения
1. Чем кортеж отличается от множества?
Куда смотреть: 32, начало раздела «Множества»; 321.
Суть ответа: в кортеже важен порядок координат; (1,2) ≠ (2,1), а {1,2} = {2,1}.
2. Что такое фактор-множество A/E?
Куда смотреть: 32, «Фактор-множество»; 321.
Суть ответа: множество классов эквивалентности; элемент — целый класс, не один объект. Аналог — GROUP BY по ключу.
3. Зачем матрица бинарного отношения из 0 и 1?
Куда смотреть: 32, «Матрица отношения».
Суть ответа: компактное хранение связей на конечном множестве; для эквивалентности — блочно-диагональный вид после перестановок.
4. Назовите свойства частичного порядка.
Куда смотреть: 32, «Отношения»; 321.
Суть ответа: рефлексивность, антисимметричность, транзитивность; не любые два элемента сравнимы (в отличие от линейного порядка).
Блок 2. Таблицы и SQL
5. Таблица БД как отношение — что такое строка и столбец?
Куда смотреть: 322.
Суть ответа: строка — кортеж значений доменов; столбец — домен Dᵢ; таблица — подмножество D₁×…×Dₙ.
6. Чем алгебра отношений (∪, ∩, ×) отличается от алгебры Кодда (σ, π, ⋈)?
Куда смотреть: 322, теория реляционных данных.
Суть ответа: первая оперирует множествами кортежей как в теории множеств; вторая добавляет выборку, проекцию, соединение с условием — то, из чего строится план SQL.
7. Почему JOIN без WHERE опасен на больших таблицах?
Куда смотреть: 322 (декартово произведение).
Суть ответа: декартово произведение даёт |P|·|Q| строк; нужен фильтр или условие соединения.
Блок 3. Логика
8. Чем A → B отличается от A ∧ B?
Куда смотреть: 31, «Импликация и эквивалентность».
Суть ответа: импликация ложна только при истинном A и ложном B; эквивалентно ¬A ∨ B.
9. Что такое СДНФ и зачем она нужна?
Суть ответа: дизъюнкция конъюнкт по всем единицам таблицы истинности; старт для минимизации и склеивания.
10. Для чего карта Карно (2–4 переменных)?
Куда смотреть: 314.
Суть ответа: визуальное объединение соседних единиц для короткой ДНФ; на большем числе переменных — автоматические методы.
Блок 4. Графы
11. Когда существует эйлеров цикл в связном неорграфе?
Куда смотреть: 32, 323, 4.01 / графы.
Суть ответа: все степени вершин чётны (с уточнениями для мультиграфов и компонент связности).
12. Чем гамильтонов цикл отличается от эйлерова?
Куда смотреть: 323, 4 в разделе алгоритмов.
Суть ответа: эйлеров — по рёбрам; гамильтонов — по вершинам; последний связан с TSP и в общем случае вычислительно труднее.
13. Что такое DAG и топологическая сортировка?
Куда смотреть: 4.01 / графы.
Суть ответа: ориентированный граф без циклов; топопорядок — линейное расширение зависимостей (сборка, задачи).
14. Что такое минимальный остов?
Куда смотреть: 323, 4.01 / графы.
Суть ответа: связный подграф без циклов на всех вершинах с минимальной суммой весов; алгоритмы Прима и Краскала.
15. Когда применять BFS, а когда Дейкстру?
Суть ответа: BFS — невзвешенный граф (каждое ребро = 1); Дейкстра — неотрицательные веса на рёбрах.
Блок 5. Комбинаторика и сложность
16. Почему полный перебор подмножеств — O(2^n)?
Куда смотреть: 32, «Сложность перебора».
Суть ответа: у n элементов 2^n подмножеств; булеан множества мощности n.
17. Связь коммивояжёра и O(n!).
Суть ответа: n! перестановок вершин; полный перебор гамильтоновых циклов непрактичен при больших n.
18. Как индукция связана с циклом for?
Куда смотреть: 321.
Суть ответа: база цикла = база индукции; шаг цикла сохраняет инвариант = индуктивный переход.
Типичные путаницы
| Путают | Различие |
|---|---|
| Эйлер / Гамильтон | рёбра vs вершины |
| Кортеж / множество | порядок vs без порядка |
| BFS / Дейкстра | без весов vs неотрицательные веса |
| ∪ в SQL / × без условия | объединение строк vs декартово произведение |
| ДНФ / КНФ | ∨ конъюнкт vs ∧ дизъюнкт |
Обзор маршрута: 3. Самопроверка по ТАФЯ: 46.
См. также
Другие статьи этого же раздела в боковом меню (как на странице "О разделе"). Когнитивистика для разработчиков — память, чанкинг, нагрузка при чтении кода и осознанное обучение новым технологиям. История термина "ментальная модель" - Крейк о внутренних представлениях мира, которые строит когнитивная система. Единый процесс - согласованные по цели, времени и пространству действия участников ради одного результата. Что такое система и её элементы, как все это связано и зачем нужно. Краткое знакомство с науками, которые лежат в основе логики программ, данных и вычислений — от булевой алгебры до теории информации. Булева и предикатная логика для разработки — операции, таблицы истинности, кванторы и законы де Моргана в условиях кода. Совершенные ДНФ и КНФ, минимизация, карты Карно и логические сети — от таблицы истинности до упрощения условий в коде. Множества, отношения, графы и комбинаторика — язык описания структур данных, сетей, зависимостей и оценки сложности в IT. Математическая индукция, мощность, биекции, матрицы и порядки — формальная база перед таблицами и графами в IT. Отношение как множество кортежей: объединение, пересечение, разность и произведение — мост к реляционной модели Кодда и SQL. Представления графов, кратчайшие пути, остовы и разрезы, раскраска и планарность — формальная теория графов для сетей и алгоритмов. Делимость и НОД, запись алгоритмов псевдокодом, худший случай и асимптотика O(n) — связь с криптографией и проектированием кода.Когнитивистика - наука о мышлении
Ментальные модели
Тектология
Системы и модели
Математическая основа IT
Логика
Алгебра логики — нормальные формы и схемы
Дискретная математика
Множества и отношения — формальный слой
Реляционная алгебра и таблицы
Графы — маршруты, остовы и раскраски
Теория чисел, псевдокод и анализ алгоритмов