|
|
|
| Глава 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.Теория сложности: классы P и 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. Упорядоченные множества |
| | | Определения и примеры; линейные продолжения; разбиения на цепи; решётки и булевы алгебры; модулярные и геометрические решётки; алгебра инцидентности; обращение Мёбиуса; свойства функции Мёбиуса; примеры обращения Мёбиуса |
| | Задачи для самостоятельного решения |
| | Литература |
| Дополнение 2. Вероятностный метод |
| | | Основы; случайные величины ; метод математических ожиданий; длина д. н. ф. типичной булевой функции; теорема Шеннона; максимальная тень антицепи; случайные (±1)-матрицы и детерминанты; дальнейшие результаты и гипотезы |
| | Задачи для самостоятельного решения |
| | Литература |
| Ответы и указания к решению задач |
| Оглавление тома I |
 Зуев Юрий Анатольевич Выпускник Московского физико-технического института, доктор физико-математических наук, профессор Московского государственного технического университета им. Н.Э. Баумана, член Американского математического общества.
Автор более ста научных публикаций по дискретной математике, комбинаторной оптимизации, теории вероятностей, пороговой логике и распознаванию образов, а также ряда учебно-методических пособий по математике. Решил долгое время остававшуюся открытой проблему нахождения асимптотики логарифма числа пороговых булевых функций.
|
|
|
|
