| Предисловие | 5
|
| Глава 1. Предварительные сведения | 6
|
| § 1.1. Множества и операции над ними | 6
|
| § 1.2. Высказывания и предикаты | 8
|
| § 1.3. Метод математической индукции | 12
|
| § 1.4. Правило произведения | 19
|
| Глава 2. Элементы теории чисел | 25
|
| § 2.1. Наибольший общий делитель. Простые числа | 25
|
| § 2.2. Сравнения по модулю | 29
|
| § 2.3. Китайская теорема об остатках | 33
|
| § 2.4. Теоремы Эйлера, Ферма, Вильсона | 34
|
| § 2.5. Квадратичные вычеты и невычеты | 38
|
| § 2.6. Уравнения в целых числах | 41
|
| § 2.7. Мультипликативные функции | 52
|
| Глава 3. Начальные понятия общей алгебры | 58
|
| Глава 4. Комбинаторика | 70
|
| § 4.1. Сочетания | 70
|
| § 4.2. Полиномиальная формула. Комбинаторные тождества | 78
|
| § 4.3. Формула включения-исключения | 83
|
| § 4.4. Задача о беспорядках и встречах | 86
|
| § 4.5. Числа Фибоначчи | 88
|
| § 4.6. Производящие функции | 93
|
| § 4.7. Рекуррентные соотношения | 99
|
| Глава 5. Теория Пойа | 107
|
| § 5.1. Лемма Бернсайда | 107
|
| § 5.2. Теорема Пойа | 109
|
| Глава 6. Введение в теорию графов | 115
|
| § 6.1. Определения и примеры | 115
|
| § 6.2. Гамильтоновы и эйлеровы графы | 129
|
| § 6.3. Деревья | 134
|
| § 6.4. Укладки графов | 143
|
| § 6.5. Ориентированные графы. Алгоритмы | 148
|
| § 6.6. Турниры | 162
|
| § 6.7. Доминирование, независимость, покрытия, паросочетания | 165
|
| § 6.8. Минимаксные теоремы. Задача о назначениях | 172
|
| Глава 7. Матроиды | 190
|
| Глава 8. Дополнительные задачи | 197
|
| § 8.1. Инвариант, полуинвариант, конструкции | 197
|
| § 8.2. Задачи с целыми числами | 210
|
| § 8.3. Числа Кармайкла | 217
|
| § 8.4. Формула обращения М¨ебиуса | 218
|
| § 8.5. Бинарные операции и отношения | 223
|
| § 8.6. Разные комбинаторные задачи | 225
|
| § 8.7. Тождества | 241
|
| § 8.8. Две классические задачи | 245
|
| § 8.9. Теорема Рамсея | 246
|
| § 8.10. Ожерелья | 250
|
| § 8.11. Графы | 251
|
| Литература | 262
|
Современная математика уже не такая, какой она была в начале XX века. В ней появилось большое количество новых дисциплин, широко применяющихся на практике. К ним, например, относятся дисциплины, объединенные под общим названием «Дискретная математика». Понимаемая в широком смысле дискретная математика включает в себя теорию чисел, общую алгебру, математическую логику, комбинаторный анализ, теорию графов, теорию кодирования, целочисленное программирование, теорию функциональных систем и др.
Дискретность (от латинского discretus — разделенный, прерывистый) нередко противопоставляют непрерывности. Однако при решении сложных практических задач дискретные и непрерывные подходы работают совместно и весьма эффективно, взаимно обогащая друг друга.
Дискретная математика является в настоящее время интенсивно развивающимся разделом математики. Это связано с повсеместным распространением кибернетических систем, языком описания которых она является. Кроме того, дискретная математика является теоретической базой информатики, которая все глубже и глубже проникает не только в науку и технику, но и в повседневную жизнь.
Настоящая книга выходит уже 6-м изданием. Первые три издания сборника (в 1998, 2002 и 2009 гг.) вышли в издательстве ЮУрГУ, а последующие в издательстве URSS. В 2015 г. задачник переведен на испанский язык. В 6-м издании исправлены выявленные опечатки и улучшены решения некоторых задач.
В книге — около 900 задач разной степени сложности. Практически ко всем задачам (кроме задач на доказательство) даны ответы. К наиболее сложным задачам приведены указания и решения. В каждый параграф включены краткие теоретические сведения (отделены от прочего текста серыми линиями) и приведены решения типовых примеров.
По темам задач и по структуре, а также по терминологии и обозначениям данная книга соответствует учебнику «Вся высшая математика. Т. 7»
(М.: URSS, 2006) и учебному пособию [11], но может использоваться и для самостоятельной работы. Названия первых семи глав сборника совпадают, в основном, с соответствующими заголовками из указанных работ [4] и [11]. Весьма обширная последняя глава содержит задачи повышенной трудности и некоторый дополнительный теоретический материал.
А. Ю. Эвнин, 23 ноября 2015 г.
Стр. 128, строки 7 и 10 снизу. Решение задачи 440:
Под двумя знаками суммы (строка 10 снизу), а также чуть ниже в отдельной строчке (строка 7 снизу) вместо \sum k_i=n и \sum k_j=n должно быть соответственно \sum ik_i=n и \sum jk_j=n
Эвнин Александр Юрьевич Кандидат педагогических наук, доцент кафедры прикладной математики Южно-Уральского государственного университета. Автор более 80 научных публикаций, в том числе одного учебника, 16 учебных пособий, а также статей в журналах «Квант», «Математическое образование», «Математика в высшем образовании», «Математика в школе».
