Элементы дискретной математики в задачах

Автор(ы)

Глибичук А.А. и др

Год

2016

Язык

rus

Теги

Математика Программирование

Аннотация

Элементы дискретной математики в задачах Год издания : 2016 Автор : Глибичук А.А. и др. Жанр или тематика : Дискретная математика Издательство : МЦНМО ISBN : 978-5-4439-3024-4 Язык : Русский Формат : PDF Качество : Издательский макет или текст (eBook) Интерактивное оглавление : Да Описание : ___ Мы приводим подборки задач по комбинаторным разделам математики. Эти задачи подобраны так, что в процессе их решения читатель освоит основы важных теорий - как классических, так и современных. ___ Книга будет полезна студентам, руководителям и участникам кружков для старшеклассников (в частности, ориентированных на олимпиады). Некоторые приводимые красивые задачи и важные темы малоизвестны в традиции кружков по математике, но полезны как для математического образования, так и для подготовки к олимпиадам. Решение этих задач (т. е. изучение соответствующих теорий) будет полезно также всем, кто хочет стать математиком, специалистом по computer science или программистом, работающим в наукоёмких отраслях информационных технологий. Примеры страниц Оглавление Введение 5 Основные обозначения 8 §1. Элементы комбинаторики 9 1.1. Подсчёт и комбинаторные тождества 9 1.2. Формула включений и исключений 11 1.3. Принцип Дирихле 12 1.4. Комбинаторика булева куба 14 1.5. Обращение Мёбиуса 16 1.6. Подсчёт двумя способами 18 1.7. Перестановки 20 1.8. Чётность перестановок 22 1.9. Комбинаторика классов эквивалентности 24 1.10. Подсказки 27 1.11. Указания 29 §2. Основы теории графов 46 2.1. Основные определения 46 2.2. Перечисление деревьев 49 2.3. Графы с точностью до изоморфизма 51 2.4. Плоские графы 52 2.5. Эйлеровы пути и циклы 56 2.6. Гамильтоновы пути и циклы 59 2.7. Экстремальные задачи (теорема Турана) 61 2.8. Теорема Менгера 62 2.9. Подсказки 63 2.10. Указания 65 §3. Раскраски графов и многочлены 76 3.1. Раскраски графов 76 3.2. Хроматические число и индекс 78 3.3. Хроматический многочлен и многочлен Татта 79 3.4. Подсказки 81 3.5. Указания 81 §4. Основы теории Рамсея 84 4.1. Двухцветные числа Рамсея 84 4.2. Многоцветные числа Рамсея 85 4.3. Числа Рамсея для гиперграфов 86 4.4. Результаты рамсеевского типа 87 4.5. Числа Рамсея для подграфов 89 4.6. Подсказки 90 4.7. Указания 92 §5. Системы множеств (гиперграфы) 101 5.1. Пересечения подмножеств 101 5.2. Системы общих представителей 102 5.3. Системы различных представителей 103 5.4. Перманент 105 5.5. Размерность Вапника–Червоненкиса 106 5.6. Подсолнухи 108 5.7. Подсказки 109 5.8. Указания 110 §6. Аналитические и вероятностные методы 118 6.1. Асимптотики 118 6.2. Независимость и доказательства существования 121 6.3. Случайные графы 134 6.4. Подсказки 138 6.5. Указания 140 §7. Алгебраические методы 150 7.1. Линейно-алгебраический метод в комбинаторике 150 7.2. Матрицы Адамара 153 7.3. Подсказки 155 7.4. Указания 156 §8. Теоремы об инцидентностях в геометрии 160 8.1. Задачи 160 8.2. Подсказки 161 8.3. Указания 162 §9. Аддитивная комбинаторика 164 9.1. Задачи 164 9.2. Подсказки 166 9.3. Указания 16