М.:Либроком, 2012. — 368 с. — ISBN 978-5-397-02573-7.
Содержание настоящей книги охватывает вузовский курс дискретной
математики, включая перечислительную комбинаторику, булевы функции,
графы, алгоритмы, помехоустойчивое кодирование и криптографию, а
также ряд дополнительных тем. Принцип построения «от простого — к
сложному» делает начальные разделы каждой главы доступными для
старшеклассника, а заключительные — ценными для аспиранта. Для
самостоятельного решения предлагается большое число задач различной
сложности, снабженных ответами и указаниями. В книге рассказывается
также об истории математических открытий и формулируются открытые
проблемы дискретной математики.
Книга состоит из двух томов. Во втором томе рассматриваются графы, алгоритмы в дискретной математике и теория кодирования (в том числе задачи сжатия, информации, помехоустойчивого кодирования и криптографии), дискретной математики, изучаются теория и методы перечисления, булевы функции.
Написанная доступным языком, в яркой форме и с многочисленными примерами, книга будет полезна широкому кругу читателей, желающих познакомиться с основами дискретной математики. Графы.
Определения и примеры.
Деревья.
Двудольные графы.
Графы абстрактные и помеченные. Автоморфизмы.
Эйлеровы графы.
Гамильтоновы графы.
Паросочетания.
Связность.
Планарность.
Раскраски.
Теоремы Турана и Рамсея.
Перечисление графов.
Задачи для самостоятельного решения.
Литература. Алгоритмы.
Понятие алгоритма.
Алгоритмы на графах.
Потоки в сетях.
Практические методы решения задач дискретной оптимизации.
Жадные алгоритмы и матроиды.
Теория сложности: классы Р и NP.
Сложность приближённого решения.
Машина Тьюринга.
Теорема Кука.
Задачи для самостоятельного решения.
Литература. Коды, блок-схемы, шифры.
Задачи кодирования.
Экономное кодирование. Алгоритм Хаффмана.
Принципы помехоустойчивого кодирования.
Линейные коды. Коды Хэмминга.
Скорость передачи и вероятность ошибки. Теорема Шеннона.
Коды Рида—Маллера.
Конечные поля.
Коды БЧХ.
Латинские квадраты. Блок-схемы. Матрицы Адамара.
Коды Адамара. Совершенный код Голея плотности упаковки шаров Хэмминга.
Математические принципы современной криптографии.
Задачи для самостоятельного решения.
Литература. Дополнение.
1. Упорядоченные множества.
Определения и примеры.
Линейные продолжения.
Разбиения на цепи.
Решётки и булевы алгебры.
Модулярные и геометрические решётки.
Алгебра инцидентности.
Обращение Мёбиуса.
Свойства функции Мёбиуса.
Примеры обращения Мёбиуса.
Задачи для самостоятельного решения.
Литература. Дополнение.
2. Вероятностный метод.
Основы.
Случайные величины.
Метод математических ожиданий.
Длина д. н. ф. типичной булевой функции.
Теорема Шеннона.
Максимальная тень антицепи.
Случайные (±1)-матрицы и детерминанты.
Дальнейшие результаты и гипотезы.
Задачи для самостоятельного решения.
Литература. Ответы и указания к решению задач.
Оглавление тома
1.
Книга состоит из двух томов. Во втором томе рассматриваются графы, алгоритмы в дискретной математике и теория кодирования (в том числе задачи сжатия, информации, помехоустойчивого кодирования и криптографии), дискретной математики, изучаются теория и методы перечисления, булевы функции.
Написанная доступным языком, в яркой форме и с многочисленными примерами, книга будет полезна широкому кругу читателей, желающих познакомиться с основами дискретной математики. Графы.
Определения и примеры.
Деревья.
Двудольные графы.
Графы абстрактные и помеченные. Автоморфизмы.
Эйлеровы графы.
Гамильтоновы графы.
Паросочетания.
Связность.
Планарность.
Раскраски.
Теоремы Турана и Рамсея.
Перечисление графов.
Задачи для самостоятельного решения.
Литература. Алгоритмы.
Понятие алгоритма.
Алгоритмы на графах.
Потоки в сетях.
Практические методы решения задач дискретной оптимизации.
Жадные алгоритмы и матроиды.
Теория сложности: классы Р и NP.
Сложность приближённого решения.
Машина Тьюринга.
Теорема Кука.
Задачи для самостоятельного решения.
Литература. Коды, блок-схемы, шифры.
Задачи кодирования.
Экономное кодирование. Алгоритм Хаффмана.
Принципы помехоустойчивого кодирования.
Линейные коды. Коды Хэмминга.
Скорость передачи и вероятность ошибки. Теорема Шеннона.
Коды Рида—Маллера.
Конечные поля.
Коды БЧХ.
Латинские квадраты. Блок-схемы. Матрицы Адамара.
Коды Адамара. Совершенный код Голея плотности упаковки шаров Хэмминга.
Математические принципы современной криптографии.
Задачи для самостоятельного решения.
Литература. Дополнение.
1. Упорядоченные множества.
Определения и примеры.
Линейные продолжения.
Разбиения на цепи.
Решётки и булевы алгебры.
Модулярные и геометрические решётки.
Алгебра инцидентности.
Обращение Мёбиуса.
Свойства функции Мёбиуса.
Примеры обращения Мёбиуса.
Задачи для самостоятельного решения.
Литература. Дополнение.
2. Вероятностный метод.
Основы.
Случайные величины.
Метод математических ожиданий.
Длина д. н. ф. типичной булевой функции.
Теорема Шеннона.
Максимальная тень антицепи.
Случайные (±1)-матрицы и детерминанты.
Дальнейшие результаты и гипотезы.
Задачи для самостоятельного решения.
Литература. Ответы и указания к решению задач.
Оглавление тома
1.