Читать фрагмент

книга

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

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

Учебник написан по материалам курса «Дискретная математика», который читается студентам младших курсов факультета компьютерных наук НИУ ВШЭ. Темы этого курса являются частью базовой математической культуры и необходимы будущим математикам, программистам и специалистам в области анализа данных, но не входят в традиционно сложившиеся курсы начального математического цикла (математический анализ, алгебра, линейная алгебра). В книге излагаются начальные сведения из перечислительной комбинаторики, теории графов, теории чисел, теории множеств, теории вероятностей, теории игр, теории вычислимости. Не претендуя на полноценный охват какой-либо из упомянутых теорий, учебник дает введение в эти области, с одной стороны, достаточное для студентов соответствующих специальностей, а с другой – позволяющее читать специализированную литературу.
Книга будет полезной студентам младших курсов, изучающим курс дискретной математики; преподавателям этой дисциплины; а также более широкому кругу любителей математики.

Форматы: PDF

Серия: Учебники Высшей школы экономики

Издательство: Издательский дом Высшей школы экономики

Год: 2021

Место издания: Москва

ISBN: 978-5-7598-1782-6 (в пер.). – ISBN 978-5-7598-2212-7 (e-book)

Страниц: 496

Артикул: 86877

Возрастная маркировка: 16+

Электронная книга

352 ₽

Купить и скачать

Содержание

Содержание книги "Лекции по дискретной математике "

Предисловие

Часть I. Начальные примеры

Лекция 1. Математическая индукция

1.1. Задача о раскраске плоскости

1.2. Общая схема доказательств по индукции

1.3. Варианты рассуждений по индукции

1.3.1. С чего начинать

1.3.2. Сведение к меньшим

1.3.3. Переформулировка: принцип наименьшего числа

1.4. Как не надо

1.5. Как догадаться, что доказывать

1.6. Доказательства по индукции и без индукции

1.7. Индукция и рекурсия

1.8. Доказательства неравенств по индукции

1.8.1. Неравенство Бернулли

1.8.2. Среднее арифметическое и среднее геометрическое

1.9. Пример из алгебры: системы однородных уравнений

1.10. Коды Грея

1.11. Теорема Холла о представителях

1.12. Задачи для самостоятельного решения

Лекция 2. Подсчёты

2.1. Правило суммы

2.2. Рекуррентное соотношение: пример

2.3. Рекуррентное соотношение: число путей

2.4. Слова и правило произведения

2.5. Выбор с ограничениями

2.6. Подсчёты с кратностью

2.7. Подмножества и числа сочетаний

2.8. Ещё о числах сочетаний

2.8.1. Симметрия

2.8.2. Сумма чисел в строке

2.8.3. Знакочередующаяся сумма

2.8.4. Снова о включениях и исключениях

2.8.5. Пути, подмножества, слова

2.8.6. Соседние числа в строке

2.8.7. Монеты и перегородки

2.9. Бином Ньютона и производящие функции

2.10. Числа Каталана

2.10.1. Правильные последовательности скобок

2.10.2. Рекуррентная формула

2.10.3. Вычисление с помощью отражений

2.10.4. Вычисление с производящей функцией

2.10.5. Вычисление с теорией вероятностей и поворотами

2.10.6. Доказательство по индукции с дробными параметрами

2.10.7. Неассоциативные произведения, триангуляции и стековый калькулятор

2.11. Что дальше

Лекция 3. Графы

3.1. Примеры

3.1.1. Граф авиарейсов

3.1.2. Перестановка коней

3.1.3. Эйлер и мосты в Кёнигсберге

3.1.4. Рукопожатия

3.1.5. Задачи и решения

3.1.6. Разбор контрольной

3.1.7. Знакомые и незнакомые

3.2. Неориентированные графы

3.2.1. Определение

3.2.2. Соседи. Степени вершин

3.2.3. Связные компоненты

3.2.4. Расстояния. Простые пути

3.2.5. Деревья

3.2.6. Полное бинарное дерево

3.3. Ориентированные графы

3.3.1. Определение

3.3.2. Степени вершин

3.3.3. Пути и достижимость

3.3.4. Достижимость и разрезы

3.3.5. Компоненты сильной связности и ациклические графы

3.3.6. Графы преобразований

3.4. Эйлеровы циклы

3.4.1. Определение

3.4.2. Критерий существования

3.4.3. Последовательности де Брёйна

3.4.4. Гамильтоновы циклы

3.5. Двудольные графы

3.5.1. Определение

3.5.2. Двудольные графы и раскраска в два цвета

3.5.3. Степени вершин

3.5.4. Паросочетания

3.6. Клики и независимые множества

Лекция 4. Арифметика остатков

4.1. Чётные и нечётные числа

4.2. Деление на 3 и остатки

4.3. Деление с остатком

4.4. Сравнения по модулю

4.5. Таблицы сложения и умножения по модулю N

4.6. Обратимые остатки по модулю N

4.7. Обратимые элементы и диофантовы уравнения

4.8. Алгоритм Евклида

4.9. Алгоритм Евклида и диофантовы уравнения

4.10. Однозначность разложения на множители

4.11. Китайская теорема об остатках

4.12. Малая теорема Ферма

4.13. Функция Эйлера и теорема Эйлера

4.14. Что дальше

Часть II. Основные конструкции

Лекция 5. Множества и логика

5.1. Основные свойства множеств и операции с множествами

5.2. Теоретико-множественные тождества

5.3. Логические переменные, логические связки

5.4. Наблюдения

5.5. Какие связки необходимы

5.5.1. Полнота дизъюнкции, конъюнкции и отрицания

5.5.2. Полнота конъюнкции и отрицания

5.5.3. Алгебраическое доказательство полноты

5.6. Формула включений-исключений

5.6.1. Первое доказательство

5.6.2. Второе доказательство

5.6.3. Формула для симметрической разности

Лекция 6. Функции

6.1. Пример

6.2. Функции и связанные с ними понятия

6.2.1. Терминология и обозначения

6.2.2. Образ множества, полный прообраз

6.3. Декартово произведение множеств и графики функций

6.4. Инъекции, сюръекции и биекции

6.4.1. Определения

6.4.2. Биекции и сравнение множеств

6.5. Композиции функций

6.5.1. Определение

6.5.2. Ассоциативность

6.5.3. Обратная функция

6.5.4. Степени композиций

6.6. Подсчёты

6.7. Задачи для самостоятельного решения

Лекция 7. Отношения и их графы

7.1. Отношения в естественном языке

7.2. Отношения с точки зрения математики

7.3. Свойства бинарных отношений

7.4. Графы, матрицы и бинарные отношения

7.5. Отношения эквивалентности

7.6. Композиция отношений

7.7. Отношения: что дальше

7.8. Задачи для самостоятельного решения

Лекция 8. Мощность множеств

8.1. Равномощные множества

8.1.1. Определение равномощности

8.1.2. Свойства равномощности

8.1.3. Примеры равномощных множеств

8.2. Счётные множества

8.2.1. Определение и простейшие примеры

8.2.2. Свойства счётных множеств

8.3. Несчётные множества

8.3.1. Интервал и отрезок равномощны

8.3.2. Добавление счётного множества

8.3.3. Числа и последовательности

8.3.4. Отрезок и квадрат

8.4. Диагональный аргумент Кантора и сравнение мощностей

8.4.1. Несчётность отрезка

8.4.2. Сравнение мощностей

8.5. Что дальше

Лекция 9. Упорядоченные множества

9.1. Отношения порядка

9.1.1. Отношения строгого частичного порядка

9.1.2. Строгие и нестрогие порядки

9.2. Примеры

9.3. Операции над частично упорядоченными множествами

9.4. Какие порядки считать «одинаковыми»

9.5. Конечные линейные порядки

9.6. Порядки и индукция

9.7. Антицепи

Лекция 10. Вероятность: первые шаги

10.1. Элементарная теория вероятностей: определения

10.2. Вероятность объединения событий

10.3. Вероятностный метод

10.4. Условные вероятности

10.5. Случайная величина, математическое ожидание

10.6. Частота орлов при подбрасывании монеты и биномиальные коэффициенты

10.7. Большие уклонения: неравенство Чернова

10.8. Подробности для любознательных

10.8.1. Ещё одна элементарная оценка отношения биномиальных коэффициентов

10.8.2. Другое доказательство неравенства Чернова

Лекция 11. Комбинаторные игры

11.1. Позиции

11.2. Стратегии

11.3. Разбор с конца

11.4. Симметричные стратегии

11.5. Ним

11.6. Сумма игр и функция Шпрага –– Гранди

Часть III. Вычислимость

Лекция 12. Разрешающие деревья

12.1. Задача об угадывании числа. Деление пополам. Мощностная нижняя оценка

12.2. Формализация модели

12.3. Угадывание числа, неадап тивный вариант задачи

12.4. Ограниченные модели разрешающих деревьев. Сортировка, взвешивания, булевы функции

12.5. Рассуждение с противником

Лекция 13. Булевы схемы и формулы

13.1. Булевы схемы

13.2. Формулы

Лекция 14. Алгоритмическая неразрешимость

14.1. Игра FRACTRAN

14.2. Что утверждается

14.3. Отступление о процессорах

14.4. Кодирование

14.5. Класс вычислимых функций

14.6. Определение вычислимости

14.7. Компромисс

14.8. Композиция вычислимых функций

14.9. Не все функции вычислимы

14.10. Неразрешимость проблемы остановки

14.11. Самоприменимость

14.12. Перечисление останавливающихся программ

14.13. Как доказать неразрешимость

14.14. Язык программирования для доказательства теоремы Конвея

14.15. Сведение проблемы остановки: от программ к пасьянсам

Лекция 15. Вычислимые функции, разрешимые и перечислимые множества

15.1. Примеры вычислимых функций

15.2. Не все функции вычислимы (повторение)

15.3. Разрешимые множества

15.4. Перечислимые множества

15.5. Вычислимость и конечные объекты

15.6. Универсальная вычислимая функция

15.7. Главная универсальная функция

15.8. Теорема Райса –– Успенского

15.9. Теорема о неподвижной точке

15.10. Решения задач

Лекция 16. Машины Тьюринга

16.1. Определения

16.2. Тезис Чёрча –– Тьюринга

16.3. Машины Тьюринга и свойства вычислимых функций

16.4. Использование машин Тьюринга в доказательствах

16.5. Композиция функций, вычислимых по Тьюрингу, и «уборка мусора»

16.6. Многоленточные машины Тьюринга

16.7. Моделирование многоленточной МТ на одноленточной

16.8. Универсальная машина Тьюринга

16.9. Универсальная трёхленточная машина для одноленточных машин

16.10. Соответствие между абстрактной теорией алгоритмов и МТ

16.11. Машины Тьюринга в доказательствах неразрешимости

16.11.1. Задача достижимости на графе подстановок слов

16.11.2. Неразрешимость задачи достижимости для графа подстановок слов

16.12. Решения задач

Литература

Об авторах

Отрывок из книги

1.4. Как не надоПример 1.6.Докажем, что произведение любыхn0чисел равнонулю, используя индукцию поn. Базис индукции очевиден: приn= 0сомножителей нет, так что перемножать нечего. Шаг индукции. Пустьутверждение верно для некоторогоn, т. е. произведение любыхnчиселa1, a2, . . . , anравно нулю. Докажем то же утверждение для любых(n+ 1)чиселa1, a2, . . . , an+1. Рассуждая по индукции, мы считаем известным, чтоa1·a2·. . .·an= 0.Умножим это равенство наan+1, получитсяa1·a2·. . .·an·an+1= 0·an+1= 0,что и требовалось.Наверное, и здесь ошибка видна сразу, так что попробуем что-то по-хитрее.Пример 1.7.Докажем по индукции такое утверждениеAn: «в любомнаборе изnнатуральных чисел все числа равны». (Здесьn= 1,2,3, . . .)С базисом индукции всё в порядке:A1означает тривиальное утвержде-ние «каждое число равно самому себе».Докажем законность индуктивного перехода. ПустьAnверно, дока-жемAn+1. Рассмотрим набор из(n+ 1)чисел(a1, a2, . . . , an, an+1).Применим утверждениеAnк наборам(a1, a2, . . . , an)и(a2, . . . , an, an+1).Каждый из этих наборов состоит изnчисел, поэтому к ним можно при-менитьAn(и ничего страшного, что его надо применить дважды: верноеутверждение и несколько раз тоже верно). Таким образом, числа и в том,и в другом наборе равны, т. е.a1=a2=. . .=anиa2=a3=. . .=an+1.Отсюдаa1=a2=. . .=an=an+1,т. е. утверждениеAn+1верно. Применяя принцип математической индук-ции, получаем, чтоAnверно для всехn.25

Внимание!
При обнаружении неточностей или ошибок в описании книги "Лекции по дискретной математике (автор Михаил Вялый, Владимир Подольский, Александр Рубцов, Дмитрий Шварц, Александр Шень)", просим Вас отправить сообщение на почту help@directmedia.ru. Благодарим!

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

Содержание

Отрывок из книги

С книгой "Лекции по дискретной математике" читают