Дискретная математика [Сергей Гашков, Александр Фролов]

xmypoe_ytpo · 6 сен 2021

Складчина: Дискретная математика [Сергей Гашков, Александр Фролов]
Сергей Борисович Гашков, Александр Борисович Фролов
Дискретная математика

Год: 2021
Издательство: Юрайт
Кол. страниц: 483
Издание: 3-е
Формат: Электронный pdf

Описание:
В курсе отражены разделы дискретной математики, предусматриваемые учебными программами классических, национальных исследовательских и технических университетов. При соблюдении необходимого уровня доказательности рассматриваются задачи, встречающиеся в инженерной практике, для формализации которых необходимы математические модели дискретной математики — теоретико-множественные, комбинаторно-логические, автоматные, графовые, функциональные, алгебраические и др. Существенное внимание уделено принципам построения алгоритмов решения задач дискретной математики на базе известных моделей вычислений (рекурсия, ветвления и ограничения и т. п.) и оценкам их сложности в контексте общей теории сложности алгоритмов. Соответствует актуальным требованиям Федерального государственного образовательного стандарта высшего образования. Для студентов, слушателей факультетов повышения квалификации, специалистов, преподавателей и программистов, использующих методы дискретной математики.

Предисловие
Глава 1. Множества и отношения
1.1. Множества и булеаны
1.2. Отношения
1.2.1. Соответствия
1.2.2. Гомоморфизм и изоморфизм
1.2.3. Однородные бинарные отношения
Задачи
Глава 2. Функции алгебры логики
2.1. Основные определения
2.2. Разложение булевых функций по переменным
2.3. Теорема о полноте
2.4. Минимизация булевых функций
2.5. Геометрическая интерпретация дизъюнктивной нормальной формы
2.6. Минимизация систем функций алгебры логики
Задачи
Глава 3. Алгебры высказываний, предикатов и множеств
3.1. Алгебра высказываний
3.2. Алгебра предикатов
3.3. Алгебра множеств
Задачи
Глава 4. Отношения эквивалентности и частичного порядка
4.1. Отношения эквивалентности
4.2. Ядерная эквивалентность и каноническое разложение
4.3. Отношения частичного порядка
4.4. Многокритериальная оптимизация
4.5. Решетки
4.6. Булевы решетки
Задачи
Глава 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. Логика предикатов
7.1. Формулы логики предикатов
7.2. Преобразование предикатов
7.3. Эквивалентные преобразования формул
7.4. Общезначимые и противоречивые формулы
7.5. Логические следствия
Задачи
Глава 8. Логические схемы
8.1. Схемы из функциональных элементов и логические схемы
8.2. Сложность схемы. Минимальные схемы
8.3. Некоторые элементарные методы синтеза
8.4. Функция Шеннона. Оценки Шеннона — Лупанова
8.5. Синтез схем методом каскадов
8.6. Декомпозиционные методы синтеза
8.6.1. Понятие декомпозиции
8.6.2. Использование нетривиальной декомпозиции
8.6.3. Использование программируемых логических матриц
8.7. Контактные схемы
8.8. Тестирование логических схем
Задачи
Глава 9. Конечные автоматы
9.1. Основные понятия
9.2. Эквивалентность автоматов
9.3. Изоморфизм автоматов
9.4. Минимизация автоматов
9.5. Регулярные события и регулярные выражения
9.6. Регулярность событий, представимых автоматами
9.7. Представление регулярного события автоматом
9.8. Схемы с обратной связью
Задачи
Глава 10. Теория алгоритмов и вычислимых функций
10.1. Машины Тьюринга
10.2. Тьюрингово программирование и тьюринговы диаграммы
10.3. Алгоритмически неразрешимые проблемы
10.4. Вычисления на абаке
10.5. Рекурсивные функции
10.6. Универсальные функции
10.7. Разрешимые и перечислимые множества и предикаты
10.8. Формальные системы и алгорифмы Маркова
10.8.1. Формальные системы
10.8.2. Нормальные алгорифмы Маркова
Задачи
Глава 11. NP-полные задачи
11.1. Схемы, предикаты и конъюнктивные нормальные формы
11.2. Моделирование машин Тьюринга булевыми схемами
11.3. Классы P и NP. Теорема Кука
11.4. NP-полные задачи
11.5. Частные случаи NP-полных задач
11.6. Алгоритмы для точного решения некоторых NP-полных задач
11.6.1. Динамическое программирование
11.6.2. Псевдополиномиальные алгоритмы
11.6.3. Метод ветвей и границ
11.7. Приближенные алгоритмы решения NP-полных задач
11.7.1. Жадные алгоритмы
11.7.2. Полиномиальные алгоритмы с ограниченной погрешностью
11.7.3. Алгоритмы локальной минимизации
Задачи
Глава 12. Конечные поля и эллиптические кривые
12.1. Группы, кольца, поля и многочлены
12.2. Конечные поля
12.2.1. Мультипликативная группа поля
12.2.2. Подполя и их расширения
12.2.3. Неприводимые и примитивные многочлены
12.3. Эллиптические кривые
Задачи
Глава 13. Теория кодов, исправляющих ошибки
13.1. Основные понятия
13.1.1. Двоичные коды
13.1.2. q-Ичные коды и границы сферической упаковки
13.1.3. Линейные коды. Порождающие и проверочные матрицы
13.2. Коды Хемминга
13.2.1. Коды Хемминга как циклические коды
13.2.2. q-Ичные коды Хемминга
13.3. Коды Рида — Соломона
13.4. Коды Боуза — Чоудхури — Хоквингема
13.5. Матричное определение кодов Боуза — Чоудхури — Хоквингема и Рида — Соломона
13.6. Исправление двух ошибок
13.7. Определение позиций ошибок в общем случае методом Питерсона
Задачи
Глава 14. Криптографические приложения
14.1. Линейная рекуррентная последовательность и ее характеристический многочлен
14.1.1. Основные понятия
14.1.2. Автоматная интерпретация линейной рекуррентной последовательности
14.1.3. Статистические свойства линейной рекуррентной последовательности
14.1.4. След элемента конечного поля
14.1.5. Формула общего члена линейной рекуррентной последовательности
14.2. Электронная цифровая подпись
14.2.1. Понятие, назначение и свойства цифровой подписи
14.2.2. О российском стандарте цифровой подписи 2012 года
14.3. Предварительное распределение ключей в компьютерной сети
14.3.1 Схемы предварительного распределения ключей. (k, m)‐Схема Блома
14.3.2. Многочлены в (k, m)-схеме Блома
14.3.3. Условия вскрытия и безопасности (k, m)-схемы Блома
Задачи
Литература

Книга основана на лекциях по дискретной математике, читавшихся авторами в течение многих лет соответственно в МГУ имени М. В. Ломоносова и НИУ «МЭИ». Курсы дискретной математики в классических, национальных исследовательских и технических университетах имеют свои особенности. В технических вузах в курсы дискретной математики включают обычно элементы общей алгебры, логики и теории чисел, а в классических университетах — нет, так как в них читаются отдельные курсы по этим темам. Мы хотели написать книгу, равно пригодную для изучения дискретной математики студентами и технических вузов, и университетов, поэтому первая глава посвящена элементам теории множеств, в третьей главе, наряду с алгеброй множеств, появляются высказывания и предикаты, в четвертой главе — частично-упорядоченные множества и их наиболее важный класс — решетки, и заканчивается она установлением тесной связи одного из видов решеток с булевыми алгебрами.
Мы старались сделать изложение максимально простым, поэтому не выдвигали на первый план абстрактное понятие булевой алгебры, а вместо него разбирали конкретные его разновидности, а именно алгебры высказываний, множеств, предикатов и один из видов решеток. Вторая глава посвящена функциям алгебры логики, технически она, по-видимому, сложнее третьей и четвертой, но поставлена она на второе место потому, что рассматриваемые в ней объекты более просты и менее абстрактны в сравнении с третьей и четвертой главами. Кроме того, обычно именно с функций алгебры логики начинаются курсы дискретной математики в университетах. Ввиду ограничения на объем книги эта глава не имеет продолжения, посвященного функциям многозначных логик, хотя в университетах их обычно изучают. Пятая глава содержит элементы комбинаторики. Она является одной из наиболее технически трудных глав и ее объем превышает обычно отводимый комбинаторике в курсах дискретной математики. Шестая глава посвящена теории графов. В ней ощутим уклон в прикладную тематику, а некоторые затронутые в ней вопросы рассматриваются потом в десятой главе. В седьмой главе, довольно абстрактной по содержанию (чем и объясняется ее позиция в книге), излагаются элементы логики предикатов с кванторами по предметным переменным. Эта тема в университетах входит в курсы логики, но в технических вузах часто попадает в дискретную математику. Вопросы, связанные с аксиоматизацией исчисления предикатов и теорией логического вывода, в этой главе не рассматриваются. Восьмая глава посвящена сложности булевых функций (в технической терминологии — синтезу логических схем и их тестированию). Ее изучение предполагает знание второй главы и знакомство с пятой и шестой. В ней приведены не самые сильные из известных результатов, а только те, которые имеют достаточно простые доказательства. В девятой главе излагаются элементы теории автоматов. Ее изучение предполагает знакомство в той или иной степени со всеми предыдущими главами книги, кроме седьмой. В десятой главе дается краткое введение в теорию алгоритмов, которой в университетах обычно посвящаются отдельные курсы. Она продолжается одиннадцатой главой, посвященной теории NP-полных задач. Во многих учебниках дискретной математики эта тема почти не затрагивается, и мы посчитали уместным дать ее сравнительно развернутое изложение. Двенадцатая глава содержит очень краткое введение в общую алгебру и сравнительно подробное — в теорию конечных полей (которой обычно в курсах алгебры уделяется мало внимания), также в ней излагаются простейшие факты об эллиптических кривых над конечными полями. Знакомство с конечными полями полезно при чтении тринадцатой главы, посвященной теории самокорректирующихся кодов, в которой подробно рассматриваются наиболее популярные в приложениях коды (Хемминга, Рида — Соломона и Боуза — Чоудхури — Хоквингема). Из-за ограничения объема за рамками книги осталось алфавитное кодирование (но оно подробно изложено во многих учебниках дискретной математики).
При изучении последней, четырнадцатой главы, посвященной криптографическим приложениям, читатель также может воспользоваться знаниями, полученными в двенадцатой главе. В ее первой половине разъясняются основные принципы работы автоматов, генерирующих линейные рекуррентные последовательности (эта тема продолжает линии, начатые в пятой и девятой главах). В заключительной части главы описаны системы цифровой подписи, основанные на использовании эллиптических кривых, принятые недавно в качестве стандарта в России. Каждая из глав дает лишь краткое введение в соответствующую тематику. Все они могли бы иметь существенно большие размеры, если бы не ограничение на объем книги (и на продолжительность реально читаемого курса). Некоторые из включаемых в курсы дискретной математики тем нам пришлось по упомянутой причине оставить за рамками изложения. Желающих глубже ознакомиться с вопросами, не затронутыми в книге, мы направляем к списку литературы в ее конце.
Большинство книг из этого списка мы использовали, не указывая, как принято в учебной литературе, явно ссылок на них внутри текста. Наибольшее влияние на наше изложение оказали книги [13, 33] — на изложение функций алгебры логики во второй главе; [20] — на изложение теоретических основ сложности таких функций в связи с анализом и синтезом логических схем в восьмой главе, а также на изложение логики высказываний и логики предикатов в седьмой главе; первое издание книги [17] — на изложение теории конечных автоматов в девятой главе. Первое издание учебника [3], развитием которого является настоящее издание, использовано при изложении теории отношений и теории графов. На изложение алгебраических вопросов в двенадцатой главе оказали влияние книги [9, 23], а комбинаторики — [27]. С целью облегчения понимания излагаемого материала и несмотря на ограничения на объем, в книгу помещено большое количество рисунков и иллюстрирующих примеров. В конце каждой главы имеется список задач (иногда короткий, а иногда и довольно длинный), среди
которых есть как легкие, так и трудные. Желающих глубже изучить дискретную математику и потренироваться в решении задач мы направляем к соответствующим сборникам задач, один из которых [28] параллельно нашей книге вышел в издательстве «Юрайт». В настоящем издании устранены замеченные авторами неточности первого издания. Для придания учебнику внутренней завершенности добавлены разделы по алгоритмам, упоминаемым в одиннадцатой главе в первом издании. Кроме того, данная глава дополнена примерами и упражнениями, как и пятая глава, в которую также включен параграф по теории перечисления Пойа. Добавлен ряд ссылок на используемые источники.
Авторы признательны А. В. Бабашу, В. Н. Вагину и П. А. Макарову за поддержку данного издания и полезные замечания, а также автору задачника [28] Ю. В. Таранникову, участвовавшему в формировании содержания книги и обсуждении путей изложения материала.

От себя добавлю, что книга имеет достаточно интересный набор охватываемых тем и основана на лекциях читавшихся авторами в МГУ имени М. В. Ломоносова, так что должна быть как минимум хорошей.

Продажник: Скрытая ссылка