Предисловие

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

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

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

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

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

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

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

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

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

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

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

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

Литература

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

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

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