О.Б. Лупанов - Курс лекций по дискретной математике (1156368)

Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла

МОСКОВСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТимени М. В. ЛОМОНОСОВАМеханико-математический факультетКурс лекций подискретной математикеЛектор — Олег Борисович Лупанов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 ячеек) и воткнём ихмежду шариками. Тогда количество шариков до первой перегородки — это в точности количество объектовпервого типа, количество шариков между первой и второй перегородкой — это количество объектов второготипа, и так далее. Итак, мы установили биекцию между расположениями перегородок и сочетаниями.

Характеристики

Тип файла PDF

PDF-формат наиболее широко используется для просмотра любого типа файлов на любом устройстве. В него можно сохранить документ, таблицы, презентацию, текст, чертежи, вычисления, графики и всё остальное, что можно показать на экране любого устройства. Именно его лучше всего использовать для печати.

Например, если Вам нужно распечатать чертёж из автокада, Вы сохраните чертёж на флешку, но будет ли автокад в пункте печати? А если будет, то нужная версия с нужными библиотеками? Именно для этого и нужен формат PDF - в нём точно будет показано верно вне зависимости от того, в какой программе создали PDF-файл и есть ли нужная программа для его просмотра.

Список файлов лекций