Авторский коллектив

Предисловие ко второму изданию

Предисловие к первому изданию

Глава 1. Множества, отношения, комбинаторика

• 1.1. Алгебра логики и другие булевы алгебры (95мин.)
• • МОЖНО ЛИ ДОВЕРЯТЬ МАТЕМАТИКЕ? | IQ (0мин.)
• 1.2. Отношения. Алгебра отношений (95мин.)
• 1.3. Соответствия, функции и их свойства (68мин.)
• 1.4. Отношения эквивалентности (95мин.)
• 1.5. Отношения частичного порядка (95мин.)
• 1.6. Решетки (структуры) (68мин.)
• 1.7. Булевы полиномы. Булевы подалгебры (82мин.)
• 1.8. Грани (интервалы). Операции над гранями и над покрытиями (95мин.)
• 1.9. Комбинаторные конфигурации и задачи (27мин.)
• 1.10. Комбинаторные числа (68мин.)
• 1.11. Метод производящих функций (82мин.)
• 1.12. Принцип включения и исключения (54мин.)
• 1.13. Рекуррентные последовательности и уравнения (82мин.)
• 1.14. Некоторые рекуррентные соотношения (27мин.)
• Упражнения (27мин.)
• Тест:  Множества, отношения, комбинаторика (44мин.)

Глава 2. Оптимизация на графах

• 2.1. Основные понятия теории графов (136мин.)
• 2.2. Обходы графов (95мин.)
• 2.3. Фундаментальные циклы и фундаментальные сечения графа (54мин.)
• 2.4. Связность и устойчивость графов и орграфов. Экстремальные свойства графов (163мин.)
• 2.5. Раскраска графов. Двудольные графы (95мин.)
• 2.6. Планарные и плоские графы (109мин.)
• 2.7. Паросочетания в двудольных графах. Задача о различных представителях и о назначениях (122мин.)
• 2.8. Потоки в сетях. Задача о максимальном потоке (177мин.)
• 2.9. Задача о минимальном остовном дереве (27мин.)
• 2.10. Задача о кратчайшем расстоянии между двумя вершинами взвешенного графа (95мин.)
• Упражнения (82мин.)
• Тест:  Оптимизация на графах (62мин.)

Глава 3. Декомпозиция функций алгебры логики

• 3.1. Функции алгебры логики (82мин.)
• 3.2. Разложение функций алгебры логики. Канонические представления (82мин.)
• 3.3. Проблема полноты. Теорема о полноте (82мин.)
• 3.4. Минимизация функций алгебры логики (109мин.)
• 3.5. Минимизация систем функций алгебры логики (68мин.)
• 3.6. Элементы функциональной декомпозиции (54мин.)
• 3.7. Логические сети и их функции (54мин.)
• 3.8. Декомпозиционные методы синтеза логических сетей (122мин.)
• 3.9. Реализация систем функций алгебры логики посредством интегральных схем (54мин.)
• 3.10. Машины Тьюринга. Программная реализация функций алгебры логики (54мин.)
• Упражнения (27мин.)
• Тест:  Декомпозиция функций алгебры логики (42мин.)

Глава 4. Подходы к решению сложных задач. Сложность алгоритмов

• 4.1. Приближенные алгоритмы для сложных задач (204мин.)
• 4.2. Некоторые принципы построения алгоритмов (272мин.)
• 4.3. Алгоритмы и сложность (258мин.)
• 4.4. Нижние оценки сложности алгоритмов (217мин.)
• Упражнения (41мин.)
• Тест:  Подходы к решению сложных задач. Сложность алгоритмов (32мин.)

Рекомендуемая литература

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

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

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