Дискретная математика
-
Скопировать в буфер библиографическое описание
Гашков, С. Б. Дискретная математика : учебник и практикум для вузов / С. Б. Гашков, А. Б. Фролов. — 4-е изд., перераб. и доп. — Москва : Издательство Юрайт, 2024. — 530 с. — (Высшее образование). — ISBN 978-5-534-17718-3. — Текст : электронный // Образовательная платформа Юрайт [сайт]. — URL: https://urait.ru/bcode/536528 (дата обращения: 19.04.2025).
- Добавить в избранное
-
Поделиться
- ВКонтакте
- РћРТвЂВВВВВВВВнокласснРСвЂВВВВВВВВРєРСвЂВВВВВВВВ
- Skype
- Telegram
В курсе отражены разделы дискретной математики, предусматриваемые учебными программами классических, национальных исследовательских и технических университетов. При соблюдении необходимого уровня доказательности рассматриваются задачи, встречающиеся в инженерной практике, для формализации которых необходимы математические модели дискретной математики — теоретико-множественные, комбинаторно-логические, автоматные, графовые, функциональные, алгебраические и др. Существенное внимание уделено принципам построения алгоритмов решения задач дискретной математики на базе известных моделей вычислений (рекурсия, ветвления и ограничения и т. п.) и оценкам их сложности в контексте общей теории сложности алгоритмов. По каждой теме даны задачи и теоретические упражнения. Соответствует актуальным требованиям федерального государственного образовательного стандарта высшего образования. Для студентов, слушателей факультетов повышения квалификации, специалистов, преподавателей и программистов, использующих методы дискретной математики.
- Предисловие
- Тема 1. Множества и отношения
- Тема 2. Функции алгебры логики
- Тема 3. Алгебры высказываний, предикатов и множеств
- Тема 4. Отношения эквивалентности и частичного порядка
-
Тема 5. Комбинаторика
- 5.1. Основные принципы комбинаторики
- 5.2. Упорядоченные разбиения и сочетания с повторениями
- 5.3. Формула включения-исключения и числа Стирлинга
- 5.4. Числа Фибоначчи
- 5.5. Рекуррентные последовательности
- 5.6. Производящие функции
- 5.7. Числа Стирлинга и взаимно-обратные преобразования
- 5.8. Задача Эйлера о размене монет и разбиение чисел на слагаемые
- 5.9. Числа Каталана
- 5.10. Линейные рекуррентные последовательности и производящие функции
- 5.11. Шары в ящиках: 12 вариантов задачи
- 5.12. Статистики перестановок
- 5.13. Производящие функции множеств и языков
- 5.14. Формула обращения Мёбиуса
- 5.15. Теория перечисления Пойа
- Задачи
-
Тема 6. Графы
- 6.1. Основные понятия
- 6.2. Операции над графами. Подграфы
- 6.3. Фундаментальные циклы и разрезы графа
- 6.4. Обходы графа и орграфа
- 6.5. Связность графов и орграфов
- 6.6. Множества внешней и внутренней устойчивости
- 6.7. Раскраска графов
- 6.8. Паросочетания в двудольных графах
- 6.9. Плоские графы. Критерии планарности графа
- 6.10. Потоки в сетях
- 6.11. Задача о минимальном остовном дереве
- Задачи
- Тема 7. Логика предикатов
-
Тема 8. Логические схемы
- 8.1. Схемы из функциональных элементов и логические схемы
- 8.2. Сложность схемы. Минимальные схемы
- 8.3. Некоторые элементарные методы синтеза
- 8.4. Функция Шеннона. Оценки Шеннона - Лупанова
- 8.5. Синтез схем методом каскадов
- 8.6. Декомпозиционные методы синтеза
- 8.7. Контактные схемы
- 8.8. Тестирование логических схем
- Задачи
- Тема 9. Конечные автоматы
-
Тема 10. Теория алгоритмов и вычислимых функций
- 10.1. Машины Тьюринга
- 10.2. Тьюрингово программирование и тьюринговы диаграммы
- 10.3. Алгоритмически неразрешимые проблемы
- 10.4. Вычисления на абаке
- 10.5. Рекурсивные функции
- 10.6. Универсальные функции
- 10.7. Разрешимые и перечислимые множества и предикаты
- 10.8. Формальные системы и алгорифмы Маркова
- Задачи
-
Тема 11. NP-полные задачи
- 11.1. Схемы, предикаты и конъюнктивные нормальные формы
- 11.2. Моделирование машин Тьюринга булевыми схемами
- 11.3. Классы P и NP. Теорема Кука
- 11.4. NP-полные задачи
- 11.5. Частные случаи NP-полных задач
- 11.6. Алгоритмы для точного решения некоторых NP-полных задач
- 11.7. Приближенные алгоритмы решения NP-полных задач
- Задачи
- Тема 12. Конечные поля и эллиптические кривые
- Тема 13. Теория кодов, исправляющих ошибки
- Тема 14. Криптографические приложения
- Литература
- Новые издания по дисциплине "Дискретная математика" и смежным дисциплинам
-
Дискретная математика. Задачник
Учебное пособие для вузов