Предисловие

Вводная глава. Метод математической индукции. Введение в комбинаторику

• В1. Метод математической индукции (87мин.)
• • МОЖНО ЛИ ДОВЕРЯТЬ МАТЕМАТИКЕ? | IQ (0мин.)
• В2. Введение в комбинаторику (175мин.)
• • В2.1. Принцип умножения (17мин.)
  • В2.2. Перестановки, размещения, сочетания (70мин.)
  • В2.3. Перестановки и сочетания с повторениями (35мин.)
  • В2.4. Бином Ньютона (52мин.)
• Тест:  Вводная глава. Метод математической индукции. Введение в комбинаторику (60мин.)

Раздел I. ВВЕДЕНИЕ В ТЕОРИЮ МНОЖЕСТВ

• Глава 1. Основные понятия и определения теории множеств (157мин.)
• • 1.1. Что такое множество? (17мин.)
  • 1.2. Основные понятия и определения теории множеств (17мин.)
  • 1.3. Два принципа интуитивной теории множеств (52мин.)
  • 1.4. Сравнение множеств (35мин.)
  • 1.5. О парадоксах теории множеств (35мин.)
  • Основные понятия и определения теории множеств (240мин.)
• Глава 2. Основные операции над множествами (175мин.)
• • 2.1. Основные операции над множествами (52мин.)
  • 2.2. Диаграммы Эйлера — Венна (17мин.)
  • 2.3. Свойства операций над множествами (52мин.)
  • 2.4. Примеры решения задач (52мин.)
• Глава 3. Формула включения и исключения. Решение систем с неизвестными множествами (105мин.)
• • 3.1. Формула включения и исключения (35мин.)
  • 3.2. Решение систем с неизвестными множествами (70мин.)
• Глава 4. Бинарные отношения. Основные определения (175мин.)
• • 4.1. Упорядоченные пары и прямое произведение множеств (17мин.)
  • 4.2. Бинарные отношения (87мин.)
  • 4.3. Теорема о свойствах бинарного отношения (35мин.)
  • 4.4. Замыкание отношений (35мин.)
  • Бинарные отношения. Основные определения (200мин.)
• Глава 5. Ядро бинарного отношения. Матрицы конечных бинарных отношений. Отношения эквивалентности (122мин.)
• • 5.1. Ядро бинарного отношения (17мин.)
  • 5.2. Матрицы конечных бинарных отношений (52мин.)
  • 5.3. Отношения эквивалентности (52мин.)
• Глава 6. Функции (122мин.)
• • 6.1. Определение функции (52мин.)
  • 6.2. Композиция функций (17мин.)
  • 6.3. Ядро функции (52мин.)
• Глава 7. Теорема о гомоморфизме. Отношения порядка (157мин.)
• • 7.1. Теорема о гомоморфизме (35мин.)
  • 7.2. Отношения порядка (35мин.)
  • 7.3. Экстремальные элементы в частично упорядоченном множестве (35мин.)
  • 7.4. Верхняя и нижняя грани частично упорядоченного множества (52мин.)
• Глава 8. Решетки и матроиды (122мин.)
• • 8.1. Решетки (35мин.)
  • 8.2. Частичный порядок в решетке (35мин.)
  • 8.3. Матроиды (17мин.)
  • 8.4. Максимальные независимые подмножества (базы) матроида (17мин.)
  • 8.5. Ранг множества (17мин.)
• Глава 9. Алгоритм построения базы матроида. Жадный алгоритм (87мин.)
• • 9.1. Алгоритм построения базы матроида (17мин.)
  • 9.2. Жадный алгоритм (87мин.)

Раздел II. ОСНОВЫ АЛГЕБРЫ ЛОГИКИ

• Глава 10. Основные определения (140мин.)
• • 10.1. Логические переменные и логические функции (17мин.)
  • 10.2. Булевы функции одной и двух переменных (35мин.)
  • 10.3. Суперпозиция функций алгебры логики (35мин.)
  • 10.4. Примеры решения задач (52мин.)
• Глава 11. Нормальные формы логических функций (157мин.)
• • 11.1. Дизъюнктивные нормальные формы (52мин.)
  • 11.2. Конъюнктивные нормальные формы (35мин.)
  • 11.3. Как преобразовать формулу в СДНФ (17мин.)
  • 11.4. Как преобразовать формулу в СКНФ (17мин.)
  • 11.5. Разложение функции по части переменных (35мин.)
• Глава 12. Закон двойственности в алгебре логики (105мин.)
• • 12.1. Определение двойственной функции (17мин.)
  • 12.2. Принцип двойственности в упрощенной форме (17мин.)
  • 12.3. Принцип двойственности в общей форме (17мин.)
  • 12.4. Некоторые свойства несамодвойственных функций (17мин.)
  • 12.5. Число различных самодвойственных функций n переменных (35мин.)
• Глава 13. Минимизация логических функций (192мин.)
• • 13.1. Основные определения (35мин.)
  • 13.2. Метод Квайна — Мак-Класки (87мин.)
  • 13.3. Карты Карно (35мин.)
  • 13.4. Минимизация частично определенных функций (35мин.)
• Глава 14. Арифметические полиномы (122мин.)
• • 14.1. Некоторые свойства функции (17мин.)
  • 14.2. Арифметические полиномы (17мин.)
  • 14.3. Совершенные полиномиальные нормальные формы (полиномы Жегалкина) (17мин.)
  • 14.4. Линейные функции (17мин.)
  • 14.5. Некоторые свойства нелинейных функций (70мин.)
• Глава 15. Монотонные функции (105мин.)
• • 15.1. Частичный порядок на множестве двоичных наборов длины n (17мин.)
  • 15.2. Монотонные логические функции (52мин.)
  • 15.3. Немонотонные логические функции (17мин.)
  • 15.4. Функции, сохраняющие 0, и функции, сохраняющие 1 (35мин.)
• Глава 16. Функционально замкнутые классы и теорема Поста (122мин.)
• • 16.1. Полные системы функций и функционально замкнутые классы (35мин.)
  • 16.2. Теорема Поста и следствия из нее (52мин.)
  • 16.3. Предполные функционально замкнутые классы (35мин.)

Раздел III. ВВЕДЕНИЕ В ТЕОРИЮ ГРАФОВ

• Глава 17. Основные определения (175мин.)
• • 17.1. Основные определения теории графов (52мин.)
  • 17.2. Некоторые виды графов (17мин.)
  • 17.3. Изоморфизм графов (17мин.)
  • 17.4. Маршруты, цепи, циклы (87мин.)
  • Основные определения (38мин.)
• Глава 18. Операции над графами. Графы и матрицы (157мин.)
• • 18.1. Основные операции над графами. (70мин.)
  • 18.2. Матрица смежности графа (17мин.)
  • 18.3. Матрица достижимости графа (35мин.)
  • 18.4. Матрица инцидентности графа (35мин.)
  • Операции над графами. Графы и матрицы (46мин.)
• Глава 19. Деревья (157мин.)
• • 19.1. Мосты и их свойства (17мин.)
  • 19.2. Деревья (52мин.)
  • 19.3. Ориентированные, упорядоченные, бинарные деревья (52мин.)
  • 19.4. Остовные деревья графа (17мин.)
  • 19.5. Обход графа по глубине и ширине (35мин.)
  • Деревья (16мин.)
• Глава 20. Минимальные остовные деревья. Алгоритм Дейкстры отыскания кратчайших путей в графах (175мин.)
• • 20.1. Задача построения минимального остовного дерева и алгоритмы ее решения (52мин.)
  • 20.2. Задача о кратчайшем пути и алгоритм Дейкстры ее решения (122мин.)
• Глава 21. Алгоритм Беллмана решения задачи о кратчайшем пути. Алгоритм Флойда отыскания кратчайших путей между всеми парами вершин графа (210мин.)
• • 21.1. Алгоритм Беллмана (87мин.)
  • 21.2. Теорема Форда (необходимые и достаточные условия минимальности длин путей от вершины s до всех остальных вершин графа) (17мин.)
  • 21.3. Алгоритм Флойда определения кратчайших путей между всеми парами вершин данного графа (105мин.)
• Глава 22. Гамильтоновы циклы (227мин.)
• • 22.1. Гамильтоновы циклы и гамильтоновы графы (35мин.)
  • 22.2. Задача коммивояжера и ее решение методом ветвей и границ (192мин.)
• Глава 23. Задачи размещения. Поиск центров и медиан в графе (384мин.)
• • 23.1. Примеры задач размещения (17мин.)
  • 23.2. Центры и медианы графа (35мин.)
  • 23.3. Главные центры и главные медианы графа (70мин.)
  • 23.4. Абсолютные центры и абсолютные медианы (262мин.)
• Глава 24. Связность графов (175мин.)
• • 24.1. Оценка числа ребер графа через число вершин и число компонент связности (17мин.)
  • 24.2. Точки сочленения (17мин.)
  • 24.3. Меры связности графа. Вершинная и реберная связность (17мин.)
  • 24.4. Непересекающиеся цепи и разделяющие множества вершин и ребер (70мин.)
  • 24.5. Теорема Холла (52мин.)
• Глава 25. Фундаментальные циклы и разрезы (140мин.)
• • 25.1. Линейные комбинации циклов и разрезов (52мин.)
  • 25.2. Фундаментальные циклы (35мин.)
  • 25.3. Фундаментальная система разрезов (52мин.)
• Глава 26. Независимые и покрывающие множества вершин и ребер (140мин.)
• • 26.1. Покрывающие множества вершин и ребер (17мин.)
  • 26.2. Независимые множества вершин и ребер (17мин.)
  • 26.3. Связь между числами вершинного и реберного покрытий и числами вершинной и реберной независимости (35мин.)
  • 26.4. Доминирующие множества вершин (17мин.)
  • 26.5. Задача о наименьшем покрытии (17мин.)
  • 26.6. Как отыскать все максимальные независимые множества вершин данного графа (алгоритм Брона — Кербоша) (52мин.)
• Глава 27. Эйлеровы графы. Плоские графы (157мин.)
• • 27.1. Эйлеровы графы (17мин.)
  • 27.2. Критерий эйлеровости графа (35мин.)
  • 27.3. Алгоритм Флери построения эйлерова цикла в эйлеровом графе (17мин.)
  • 27.4. Ориентированные эйлеровы графы (17мин.)
  • 27.5. Определение планарного (плоского) графа (17мин.)
  • 27.6. Эйлерова характеристика плоских графов (52мин.)
  • 27.7. Критерий планарности графов (35мин.)

Раздел IV. ОСНОВЫ ИСЧИСЛЕНИЯ ВЫСКАЗЫВАНИЙ

• Глава 28. Основные определения (105мин.)
• • 28.1. Основные определения (52мин.)
  • 28.2. Логические следствия (52мин.)
• Глава 29. Теоремы о логических следствиях (122мин.)
• • 29.1. Выполнимые и невыполнимые множества формул (17мин.)
  • 29.2. Логические эквивалентности (17мин.)
  • 29.3. Несколько теорем о логических следствиях (35мин.)
  • 29.4. Modus Ponens и другие правила вывода (52мин.)
• Глава 30. Методы доказательства логических следствий (192мин.)
• • 30.1. Анализ таблиц истинности (17мин.)
  • 30.2. Доказательство от противного (17мин.)
  • 30.3. Метод резолюций в исчислении высказываний (70мин.)
  • 30.4. Применение правил вывода при доказательстве логических следствий (52мин.)
  • 30.5. Подведение итогов (35мин.)
• Глава 31. Теория доказательств в исчислении высказываний (140мин.)
• • 31.1. Формулы, секвенции, аксиомы (17мин.)
  • 31.2. Доказательства и выводы в теории доказательств (35мин.)
  • 31.3. Примеры выводов (17мин.)
  • 31.4. Теорема о дедукции (35мин.)
  • 31.5. Примеры доказательств и выводов (35мин.)
• Глава 32. Правила введения и удаления логических связок. Непротиворечивость и полнота исчисления высказываний (140мин.)
• • 32.1. Правила введения и удаления логических связок (35мин.)
  • 32.2. Примеры доказательств и выводов с использованием правил введения и удаления логических связок (17мин.)
  • 32.3. Непротиворечивость и полнота исчисления высказываний (87мин.)

Раздел V. ОСНОВЫ ИСЧИСЛЕНИЯ ПРЕДИКАТОВ

• Глава 33. Основные определения (157мин.)
• • 33.1. Основные понятия исчисления предикатов (35мин.)
  • 33.2. Формулы исчисления предикатов (35мин.)
  • 33.3. Примеры решения задач (35мин.)
  • 33.4. Свободные и связанные вхождения переменных в формулу. Область действия кванторов. Замкнутые формулы (52мин.)
• Глава 34. Общезначимость в исчислении предикатов (140мин.)
• • 34.1. Предметные области и таблицы истинности в исчислении предикатов (52мин.)
  • 34.2. Общезначимость в исчислении предикатов (87мин.)
• Глава 35. Общезначимость и логические следствия (175мин.)
• • 35.1. Методы доказательств общезначимости формул (52мин.)
  • 35.2. Примеры доказательств и опровержений общезначимости (17мин.)
  • 35.3. Логические следствия (35мин.)
  • 35.4. Примеры доказательств логических следствий (70мин.)
• Глава 36. Нормальные формы формул логики предикатов (245мин.)
• • 36.1. Равносильные (логически эквивалентные) формулы (52мин.)
  • 36.2. Предваренная нормальная форма формул (35мин.)
  • 36.3. Переход от формулы с кванторами к формуле без кванторов (35мин.)
  • 36.4. О методе резолюций в исчислении предикатов (122мин.)
• Глава 37. Теория доказательств в исчислении предикатов (87мин.)
• • 37.1. Схемы аксиом и правила вывода (17мин.)
  • 37.2. Примеры доказательств и выводов (35мин.)
  • 37.3. Теорема о дедукции для исчисления предикатов (35мин.)

Литература

Новинки издательства по дисциплине «Дискретная математика» и смежным дисциплинам

Завершение курса

• Тест:  Итоговое тестирование (60мин.)