О.Б. Лупанов - Курс лекций по дискретной математике
Описание файла
PDF-файл из архива "О.Б. Лупанов - Курс лекций по дискретной математике", который расположен в категории "". Всё это находится в предмете "дискретная математика" из 7 семестр, которые можно найти в файловом архиве МГУ им. Ломоносова. Не смотря на прямую связь этого архива с МГУ им. Ломоносова, его также можно найти и в других разделах. .
Просмотр PDF-файла онлайн
Текст из PDF
МОСКОВСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТимени М. В. ЛОМОНОСОВАМеханико-математический факультетКурс лекций подискретной математикеЛектор — Олег Борисович ЛупановIV курс, 7 семестр, поток математиковМосква, 2006 г.Оглавление1.2.3.4.Комбинаторика и теория графов1.1. Введение в комбинаторику . . . . . . . .
. . . . . . . . . . . . . . . . . . . . . . .1.1.1. Простейшие комбинаторные объекты . . . . . . . . . . . . . . . . . . . .1.1.2. Оценки . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .1.2. Теория графов . . . . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . .1.2.1. Графы. Правильная реализация. Критерий Понтрягина – Куратовского1.2.2. Оценки количества деревьев и графов . . . . . . . . . . . . . . . . . . . .1.2.3. Ориентированные графы . . . . . . . . . . . . . . . . . . . . . . . . . . . .1.2.4. Двудольные графы. Критерий Холла . . . . . . . . . . . .
. . . . . . . .1.3. Формальные степенные ряды и производящие функции . . . . . . . . . . . . . .1.3.1. Формальные степенные ряды . . . . . . . . . . . . . . . . . . . . . . . . .1.3.2. Формальное дифференцирование . . . . . . . . . . . . . . . . . . . . . . .1.3.3. Сходимость в пространстве формальных рядов . . . . .
. . . . . . . . .1.3.4. Подсчёт количества неприводимых многочленов над Fp . . . . . . . . . .1.3.5. Формула обращения Мёбиуса . . . . . . . . . . . . . . . . . . . . . . . . .1.3.6. Тождества Ньютона . . . . . . . . . . . . . . . . . . . . . . .
. . . . . . . .1.3.7. Что ещё можно делать со степенными рядами? . . . . . . . . . . . . . . .1.3.8. Принцип включений и исключений . . . . . . . . . . . . . . . . . . . . . ............................................................................................................................................................................................444555799101013131415161718Кодирование2.1. Общая теория кодирования и сжатия информации .
. . . . . . . . .2.1.1. Схемы кодирования. Коды с однозначным декодированием2.1.2. Неприводимые слова . . . . . . . . . . . . . . . . . . . . . . .2.1.3. Проверка однозначности декодирования . . . . . . . . . . . .2.1.4. Неравенство Мак-Миллана . . .
. . . . . . . . . . . . . . . .2.1.5. Оптимальные коды. Код Хаффмана . . . . . . . . . . . . . .2.2. Коды с исправлением ошибок . . . . . . . . . . . . . . . . . . . . . .2.2.1. Постановка задачи . . . . . . . . . . . . . . . . . . . . . . . .2.2.2. Коды Хемминга . . . . . . . . . . . . .
. . . . . . . . . . . . .2.2.3. Свойства кодов, исправляющих ошибки . . . . . . . . . . . .2.2.4. Коды с исправлением нескольких ошибок . . . . . . . . . . .2.2.5. Линейные коды . . . . . . . . . . . . . . . . . . . . . . . . . .2.2.6. Код Хемминга как пример линейного кода . . . . . . . . . .2.3. Коды БЧХ .
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .2.3.1. Эффективное построение корректирующих кодов . . . . . .2.3.2. Построение поля из 2m элементов . . . . . . . . . . . . . . .2.3.3. Двоичные коды БЧХ . . . . . . . . . . . . . . . . . . . . . . .2.4. Алгоритм Питерсона . . . . . . . . . . .
. . . . . . . . . . . . . . . .2.4.1. Теория . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .2.4.2. Практика . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .........................................................................................................................................................................................................................................................................................................................................................................181818181920202222222223232425252525262627Схемы из функциональных элементов3.1. Схемы из функциональных элементов . . .
. . . . . . . . .3.1.1. Метод Шеннона синтеза схем . . . . . . . . . . . . .3.1.2. Асимптотически наилучший метод построения схем3.1.3. Асимптотическая оценка снизу для сложности схем3.2. Инвариантные классы . . . . . . . . . . . . . . . . . . . . ..........................................................................................................272729293031Теория автоматов4.1. Автоматы . .
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . .4.1.1. Детерминированные функции . . . . . . . . . . . . . . . .4.1.2. Автоматы . . . . . . . . . . . . . . . . . . . . . . . . . . . .4.2. Регулярные события. Теорема Клини . . . .
. . . . . . . . . . . .4.2.1. Регулярные события . . . . . . . . . . . . . . . . . . . . .4.2.2. Свойства регулярных множеств . . . . . . . . . . . . . . .4.2.3. Обобщённые источники. Доказательство теоремы Клини4.2.4. О том, чего не могут автоматы . . . . .
. . . . . . . . . .................................................................................................................................................................3333333435353536372..........ПредисловиеПорядок изложения материала наиболее соответствует курсу 2005 г.Огромное спасибо Сергею Гладких за сотрудничество и набор главы про кодирование. В данной версииисправлено ещё несколько опечаток, написан параграф про формулу включений-исключений, а также алгоритмсжатия по Хаффману.За поиск лажи выносится благодарность Ире Шитовой, Мише Левину, Мише Берштейну и Юре Притыкину.Последняя компиляция: 26 января 2006 г.Обновления документа — на сайте http://dmvn.mexmat.net.Об опечатках и неточностях пишите на dmvn@mccme.ru.3ВведениеКурс условно можно разделить на насколько частей:••••••Комбинаторный анализТеория графовКодированиеТеория сложностиТеория автоматовРегулярные языки1.
Комбинаторика и теория графов1.1. Введение в комбинаторику1.1.1. Простейшие комбинаторные объектыВообще, теория графов — это геометрическая модель комбинаторных объектов.Будем обозначать через Mn множество из n элементов. Без ограничения общности можно считать, чтоMn = {1, . . . , n}.Определение. Перестановкой множества M называется произвольная биекция π : M → M . Очевидно, чтодля n-элементных множеств количество всевозможных перестановок равно n!.Определение. Назовём размещением из n элементов по k любое упорядоченное множество (i1 , . . .
, ik ), гдеik ∈ Mn . Количество всевозможных размещений из n элементов по k обозначается Akn .Утверждение 1.1. Справедливо равенствоAkn = n(n − 1) · . . . · (n − k + 1).(1) Первый из k элементов можно выбрать n способами, второй — (n − 1) способом, и т. д. Последний, k-йэлемент, можно выбрать (n − k + 1) способами.
Поэтому число размещений равно указанному произведению. Определение. Сочетание — это неупорядоченное размещение. Говоря более формально, сочетание из n элементов по k — это произвольное подмножество n-элементного множества. Количество сочетаний из n элементовпо k обозначается Ckn или nk .Утверждение 1.2. Справедливо равенствоCkn =Aknk!(2) Рассмотрим произвольное сочетание. Всевозможными перестановками из него можно получить k! различных размещений, причём для разных сочетаний получаются, естественно, непересекающиеся наборы размещений. Это означает, что количество размещений в k! больше числа сочетаний.
Ясно, чтоCkn =n(n − 1)(n − 2) · . . . · (n − k + 1)n(n − 1)(n − 2) · . . . · (n − k + 1) · (n − k) · . . . · 1n!==1 ·2 · ...· k1 · 2 · . . . · k · (n − k) · . . . · 1k!(n − k)!(3)Из последней формулы очевидно, что Ckn = Cn−k. У этой формулы есть и другое обоснование: существуетnбиекция между k-элементными подмножествами и их (n − k)-элементными дополнениями.Утверждение 1.3. Справедливо равенствоnXCkn = 2n .(4)k=0 Из формулы бинома Ньютона, применённой к (1 + 1)n , доказываемая формула следует немедленно.Однако, дадим второе доказательство. Поскольку Ckn — это количество k-элементных подмножеств, то искомаясумма — это количество всех подмножеств n-элементного множества. А всех подмножеств в n-элементном множестве ровно столько, сколько существует последовательностей из нулей и единиц длины n (если i-й элементесть в множестве, то ставим 1, иначе ставим 0).
А таких последовательностей, очевидно, 2n . 4Определение. Сочетание с повторениями из n элементов по k — это произвольный набор (i1 6 i2 66 . . . 6 ik ), где ij ∈ Mn . Количество различных таких наборов мы будем обозначать CCkn (от англ. completecombination).Утверждение 1.4.CCkn = Ckn+k−1 = Cn−1n+k−1 .(5) Придумаем хорошую интерпретацию для числа сочетаний с повторениями. Именно, рассмотрим k шариков, расположенных в ряд. Возьмём n − 1 «перегородку» (тогда образуется как раз n ячеек) и воткнём ихмежду шариками. Тогда количество шариков до первой перегородки — это в точности количество объектовпервого типа, количество шариков между первой и второй перегородкой — это количество объектов второготипа, и так далее. Итак, мы установили биекцию между расположениями перегородок и сочетаниями.