Лекции по дискретной математике

Автор(ы)

Вялый М, Подольский В, Рубцов А, Шварц Д, Шень А

Год

2017

Язык

rus

Теги

Математика

Аннотация

Лекции по дискретной математике Год издания : 2017 Автор : Вялый М., Подольский В., Рубцов А., Шварц Д., Шень А. Жанр или тематика : Математические лекции Издательство : Самиздат Язык : Русский Формат : PDF Качество : Издательский макет или текст (eBook) Интерактивное оглавление : Да Количество страниц : 449 Описание : Слова «дискретная математика», входящие в название этой книжки, употребляют в разных значениях. Иногда противопоставляют «дискретную» математику, говорящую о конечных или по крайней мере хорошо различимых объектах, и «непрерывную», где речь идёт о действительных числах, пределах, непрерывности, производных и т.п. Хотя это противопоставление условно и не всегда применимо (скажем, странно было бы разделять «дискретные» алгебраические кривые над конечным полем и «непрерывные» алгебраические кривые над полем комплексных чисел), некоторый смысл оно имеет. Примеры страниц Оглавление Предисловие 8 I Начальные примеры 1 Математическая индукция 1.1 Задача о раскраске плоскости . . . . . . . . . . . . . . . . . . . . . . . . 11 1.2 Общая схема доказательств по индукции . . . . . . . . . . . . . . . . . 15 1.3 Варианты рассуждений по индукции . . . . . . . . . . . . . . . . . . . . 16 1.3.1 С чего начинать? . . . . . . . . . . . . . . . . . . . . . . . . . . . 16 1.3.2 Сведение к меньшим . . . . . . . . . . . . . . . . . . . . . . . . . 18 1.3.3 Переформулировка: принцип наименьшего числа . . . . . . . . . 19 1.4 Как не надо . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 20 1.5 Как догадаться, что доказывать? . . . . . . . . . . . . . . . . . . . . . . 22 1.6 Доказательства по индукции и без . . . . . . . . . . . . . . . . . . . . . 25 1.7 Индукция и рекурсия . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 28 1.8 Доказательства неравенств по индукции . . . . . . . . . . . . . . . . . . 31 1.8.1 Неравенство Бернулли . . . . . . . . . . . . . . . . . . . . . . . . 31 1.8.2 Среднее арифметическое и геометрическое . . . . . . . . . . . . 32 1.9 Пример из алгебры: системы однородных уравнений . . . . . . . . . . . 35 1.10 Коды Грея . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 38 1.11 Теорема Холла о представителях . . . . . . . . . . . . . . . . . . . . . . 40 1.12 Задачи для самостоятельного решения . . . . . . . . . . . . . . . . . . . 42 2 Подсчёты 2.1 Правило суммы . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 44 2.2 Рекуррентное соотношение: пример . . . . . . . . . . . . . . . . . . . . . 48 2.3 Рекуррентное соотношение: число путей . . . . . . . . . . . . . . . . . . 51 2.4 Слова и правило произведения . . . . . . . . . . . . . . . . . . . . . . . 53 2.5 Выбор с ограничениями . . . . . . . . . . . . . . . . . . . . . . . . . . . 56 2.6 Подсчёты с кратностью . . . . . . . . . . . . . . . . . . . . . . . . . . . . 58 2.7 Подмножества и числа сочетаний . . . . . . . . . . . . . . . . . . . . . . 61 2.8 Ещё о числах сочетаний . . . . . . . .