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

Предисловие
Часть 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. Решения задач
Литература
Об авторах