Онлайн-библиотека учебно-методической литературыБиблиотека mirsmartbook.ru предлагает посетителям возможность чтения книг в режиме онлайн.Книги, ГДЗ, решебники, готовые домашние задания, ЕГЭ, ГИА, наука и обучение, словари, все для преподавателей, школьников и студентов, русский язык, математика, физика, английский язык, алгебра, геометрия по всем классам, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11 класс. А ты НАШЁЛ то, что тебе нужно? У нас Вы сможете найти все! |
19:22 По океану дискретной математики.Том 2. Графы. Алгоритмы. Коды, блок-схемы, шифры / Зуев Ю.А. / 2012 | |
![]() Содержание настоящей книги охватывает вузовский курс дискретной математики, включая перечислительную комбинаторику, булевы функции, графы, алгоритмы, помехоустойчивое кодирование и криптографию, а также ряд дополнительных тем. Принцип построения «от простого — к сложному» делает начальные разделы каждой главы доступными для старшеклассника, а заключительные — ценными для аспиранта. Для самостоятельного решения предлагается большое число задач различной сложности, снабженных ответами и указаниями. В книге рассказывается также об истории математических открытий и формулируются открытые проблемы дискретной математики. Книга состоит из двух томов. В первом томе даются основные идеи и понятия дискретной математики, изучаются теория и методы перечисления, булевы функции. Второй том, посвященный графам, алгоритмам в дискретной математике, теории кодирования, выходит одновременно с первым в нашем издательстве. Написанная доступным языком, в яркой форме и с многочисленными примерами, книга будет полезна широкому кругу читателей, желающих познакомиться с основами дискретной математики. Графы. Определения и примеры Теория графов используется для построения моделей в экономических, биологических и естественных науках. Помимо этого она представляет значительный интерес и как чисто математическая дисциплина, изучающая с определённых позиций бинарные отношения на конечном множестве. Графом G = (V,E) называется конечное множество V с заданным семейством Е его двухэлементных подмножеств. Элементы множества V называются вершинами (vertices), а элементы множества Е — рёбрами (edges). Если v1,v2 Œ V и {v1,v2} Œ E, то говорят, что вершины v1 и v2 смежны. Поэтому граф можно определить также как заданное на множестве V бинарное отношение смежности. Это отношение является симметричным и иррефлексивным. Эпизодически появляясь в контексте различных исследований, термин «граф» окончательно утвердился в математике после выхода в 1936 году книги венгерского математика Денеша Кёнига (1884-1944) «Теория конечных и бесконечных графов», ставшей первой в мире монографией по теории графов. Слово «граф» в переводе с греческого означает «пишу», «черчу», «рисую». И, действительно, графы с небольшим числом вершин удобно представлять рисунками, на которых вершинам соответствуют точки, а рёбрам — соединяющие их линии. Например (рис. I). Оглавление Глава 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.Теория сложности: классы Р и NР 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. Прикрепления: Картинка 1
| |
|