По океану дискретной математики, От перечислительной комбинаторики до современной криптографии, Том 2, Зуев Ю.А., 2012


По океану дискретной математики, От перечислительной комбинаторики до современной криптографии, Том 2, Зуев Ю.А., 2012.

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

По океану дискретной математики, От перечислительной комбинаторики до современной криптографии, Том 2, Зуев Ю.А., 2012


Корневые деревья.
Одна из вершин в дереве может быть выделена. Такую вершину называют корневой, а дерево — корневым деревом. При этом возникает взаимно однозначное соответствие между вершинами дерева и простыми цепями, соединяющими их с корнем. Поэтому, считая рёбра ориентированными в направлении от корня, корневое дерево можно рассматривать и как орграф. Корневые деревья принято рисовать так, чтобы корень был вверху (рис. 2).

Такой рисунок напоминает диаграмму Хассе частично упорядоченного множества, в котором корень является наибольшим элементом. И действительно, корневые деревья часто используются для задания иерархических структур. Различные иерархические структуры, с которыми часто приходится сталкиваться в жизни, описываются подобными корневыми деревьями, в которых за корень принимается старший из руководителей. Весьма важную роль такие структуры играют в армии. На рис. 3 показана принятая в российских вооружённых силах полковая иерархия.

Оглавление
Глава 3. Графы
3.1. Определения и примеры
3.2. Деревья
3.3. Двудольные графы
3.4. Графы абстрактные и помеченные. Автоморфизмы
3.5. Эйлеровы графы
3.6. Гамильтоновы графы
3.7. Паросочетания
3.8. Связность
3.9. Планарность
3.10. Раскраски
3.11. Теоремы Турана и Рамсея
3.12. Перечисление графов
Задачи для самостоятельного решения
Литература  
Глава 4. Алгоритмы
4.1. Понятие алгоритма
4.2. Алгоритмы на графах
4.3. Потоки в сетях
4.4. Практические методы решения задач дискретной оптимизации
4.5. Жадные алгоритмы и матроиды
4.6. Теория сложности: классы Р и NP
4.7. Сложность приближённого решения
4.8. Машина Тьюринга
4.9. Теорема Кука
Задачи для самостоятельного решения
Литература   
Глава 5. Коды, блок-схемы, шифры
5.1. Задачи кодирования
5.2. Экономное кодирование. Алгоритм Хаффмана
5.3. Принципы помехоустойчивого кодирования
5.4. Линейные коды. Коды Хэмминга
5.5. Скорость передачи и вероятность ошибки. Теорема Шеннона
5.6. Коды Рида—Маллера
5.7. Конечные поля
5.8. Коды БЧХ
5.9. Латинские квадраты. Блок-схемы. Матрицы Адамара
5.10. Коды Адамара. Совершенный код Голея
5.11. О плотности упаковки шаров Хэмминга
5.12. Математические принципы современной криптографии
Задачи для самостоятельного решения
Литература
Дополнение 1. Упорядоченные множества
Определения и примеры (265); линейные продолжения (269); разбиения на цепи (272); решётки и булевы алгебры (279); модулярные и геометрические решётки (288); алгебра инцидентности (293); обращение Мёбиуса (295); свойства функции Мёбиуса (296); примеры обращения Мёбиуса (300)
Задачи для самостоятельного решения
Литература
Дополнение 2. Вероятностный метод
Основы (310); случайные величины (316); метод математических ожиданий (321); длина д. н. ф. типичной булевой функции (323); теорема Шеннона (328); максимальная тень антицепи (332); случайные (±1)-матрицы и детерминанты (336); дальнейшие результаты и гипотезы (343)
Задачи для самостоятельного решения
Литература
Ответы и указания к решению задач  
Оглавление тома 1.



Бесплатно скачать электронную книгу в удобном формате и читать:

Скачать книгу По океану дискретной математики, От перечислительной комбинаторики до современной криптографии, Том 2, Зуев Ю.А., 2012 - fileskachat.com, быстрое и бесплатное скачивание.

Скачать




Скачать - djvu - Яндекс.Диск.
Дата публикации:





Теги: :: ::


Следующие учебники и книги:
Предыдущие статьи:


 


 


Книги, учебники, обучение по разделам




Не нашёл? Найди:





2016-12-02 22:58:20