А.Б. Угольников - Программа экзамена по дискретной математике (1156396)
Текст из файла
Программа экзамена по дискретной математикеЛектор — Александр Борисович УгольниковVII семестр, 2006–2007 г.1. Функции алгебры логики. Равенство функций. Существенные и несущественные переменные. Формулы,представление функций формулами. Операция суперпозиции. Замкнутые классы относительно операциисуперпозиции. Операция введения несущественной переменной. Замкнутые классы относительно операцийсуперпозиции и введения несущественной переменной (замкнутые классы). Примеры замкнутых относительно операции суперпозиции классов, не являющихся замкнутыми.2. Полные системы, примеры полных систем. Полиномы Жегалкина. Теорема о представлении функцийполиномами.
Линейные функции, леммы о нелинейных функциях. Монотонные функции, свойства монотонных функций, лемма о немонотонной функции. Конъюнкции, дизъюнкции, лемма о порождениифункций х ∨ у и уz. Теорема о конечной порожденности замкнутых классов, содержащих константы 0 и1. Замкнутые классы, содержащие константы 0 и 1.3. Функции, удовлетворяющие условию h0∞ i, их свойства.
Свойства функций x∨yz и dр (х1 , . . . , xр ). Основнаялемма о порождении монотонных функций. Лемма о порождении монотонных функций формулами надмножеством {х ∨ yz, dp (f )}. Теорема о конечной порожденности замкнутых классов монотонных функций,содержащих константу 1. Замкнутые классы монотонных функций, содержащие константу 1. Лемма опорождении импликации. Лемма о монотонной функции. Теорема о конечной порожденности замкнутыхклассов, содержащих константу 1. Замкнутые классы, содержащие константу 1.4.
Самодвойственные функции, принцип двойственности. Функции, сохраняющие константы. Теорема о конечной порожденности замкнутых классов, не содержащих констант 0 и 1. Теорема Поста о конечнойпорожденности замкнутых классов булевых функций. Необходимые и достаточные условия существования констант в замкнутых классах.5. Выборки, перестановки, сочетания, перестановки с повторениями, сочетания с повторениями. Биномиальные коэффициенты, их свойства, биномиальная теорема, полиномиальные коэффициенты, полиномиальная теорема.6. Формулы обращения. Локально-конечные частично-упорядоченные множества.
Алгебра инцидентностиА(Р ) множества Р . Необходимые и достаточные условия существования обратных функций в А(Р ). Дзета-функция множества Р . Функция Мебиуса множества Р . Формула обращения Мебиуса для частично-упорядоченных множеств. Методы вычисления функций Мебиуса. Теорема о произведении. Функция Мебиусадля цепи.
Функция Мебиуса для множества всех подмножеств конечного множества, упорядоченных повключению. Основная формула метода включений и исключений. Формула для числа Е (0) объектов, необладающих ни одним из свойств. Формула для числа Е (m) объектов, обладающих ровно m свойствами.Арифметическая функция Мебиуса. Функция Мебиуса для множества натуральных чисел, упорядоченных по делимости. Формула обращения Мебиуса.
Функция Эйлера, вычисление функции Эйлера. ФормулаГаусса.7. Формальные степенные ряды, операции над степенными рядами. Кольцо формальных степенных рядов;свойства кольца. Сходимость рядов. Необходимые и достаточные условия сходимости формальных рядов.Бесконечные суммы и произведения. Производящие функции. Примеры применения метода производящих функций для решения комбинаторных задач. Линейные рекуррентные соотношения с постояннымикоэффициентами. Теорема о решении линейных рекуррентных соотношений.
Числа Фибоначчи. Симметрические функции, элементарные симметрические функции, степенные суммы. Тождества Ньютона (связывающие элементарные симметрические функции и степенные суммы).8. Конечные поля. Порядок и характеристика поля; свойства конечных полей, существование примитивногоэлемента. Поле GF (р). Неприводимые многочлены.
Нумератор множества всех нормированных многочленов с коэффициентами из GF (р). Формула для числа Ikp неприводимых нормированных многочленовс коэффициентами из GF (р) степени k. Существование неприводимых многочленов заданной степени;асимптотическая формула для Ikp . Поле GF (р m ) — поле многочленов степени не выше m − 1 с коэффициентами из GF (р).
Построение поля GF (р m ).19. Побуквенное (алфавитное) кодирование. Разделимые коды. Префиксные коды. Неравенство Крафта-Макмиллана для разделимых р-ичных кодов. Условие существования разделимого р-ичного кода с заданнымидлинами кодовых слов. Критерий взаимной однозначности алфавитного кодирования. Полные коды. Необходимые и достаточные условия для полных кодов.
Построение по заданному префиксному коду полного(двоичного) кода.10. Оптимальные коды. Свойства оптимальных р-ичных кодов. Оптимальность заданного полного префиксного кода для некоторого множества Р . Верхняя и нижняя оценки для стоимости оптимального кода.Методы построения оптимальных кодов. Метод Шеннона. Свойства двоичных оптимальных кодов. Полнота префиксного оптимального двоичного кода. Теорема редукции. Алгоритм Хаффмана построенияоптимальных двоичных кодов.11.
Коды, исправляющие ошибки над GF (р). Расстояние Хэмминга. Граница сферической упаковки (верхняяоценка мощности максимального кода). Метод построения кодов, исправляющих t ошибок.12. Линейные коды над GF (р). Проверочные и порождающие матрицы линейных кодов. Параметры линейных кодов. Необходимое и достаточное условия существования линейных кодов с заданным минимальнымрасстоянием. Граница Синглтона.
Алгоритм построения линейного кода, с заданным минимальным расстоянием. Граница Варшамова – Гилберта. Обобщенные коды Хэмминга, их свойства. Алгоритм декодирования для обобщенных кодов Хэмминга. Коды Хэмминга, их свойства. Алгоритм декодирования длякодов Хэмминга. Совершенные коды.13. Двоичные коды БЧХ (коды Боуза – Чоудхури – Хоквингема).
Построение кодов БЧХ, исправляющих t ошибок для любого натурального t. Параметры кодов БЧХ. Лемма о решении системы уравнений, связывающих степенные и элементарные симметрические функции. Теорема Питерсона. Алгоритм Питерсонадекодирования для двоичных кодов БЧХ, исправляющих t ошибок.14. Конечные автоматы. Способы задания автоматов (таблицы, диаграммы переходов, канонические уравнения). Автоматные функции. События.
Операции над событиями. Регулярные события. Обобщенные источники. Представление регулярных событий обобщенными источниками. Представимые события. Теорема опредставлении регулярных событий конечными автоматами. Пример нерегулярного события. Источники.Представление регулярных событий источниками. Теорема Клини.Литература[1] Яблонский С.
В. Введение в дискретную математику. — М.: Высшая школа, 2003.[2] Дискретная математика и математическая кибернетика. Под ред. С. В. Яблонского и О. Б. Лупанова, т. 1. —М.: Наука, 1974.[3] Гаврилов Г. П., Сапоженко А. А. Задачи и упражнения по курсу дискретной математики. — М.: Физматлит,2004.[4] Яблонский С. В, Гаврилов Г. П., Кудрявцев В. Б. Функции алгебры логики и классы Поста. — М.: Наука,1966.[5] Угольников А. Б. О замкнутых классах Поста // Известия высших учебных заведений. Математика, 1988,№7, 79 – 88.[6] Марченков С. С, Угольников А.
Б. Замкнутые классы булевых функций. — М.: Институт Прикл. Матем. им.М. В. Келдыша, 1990.[7] Холл М. Комбинаторика. — М.: Мир, 1970.[8] Сачков В. Н. Введение в комбинаторные методы дискретной математики. — М.: Наука, 1982.[9] Стенли Р. Перечислительная комбинаторика. — М.: Мир, 1990.[10] Гульден Я., Джексон Д. Перечислительная комбинаторика. — М.: Наука, 1990.[11] Питерсон У. Коды, исправляющие ошибки. — М.: Мир, 1964.[12] Берлекэмп Э.
Алгебраическая теория кодирования. — М.: Мир, 1971.[13] Мак-Вильямс Ф. Дж., Слоэн Н. Дж. А. Теория кодов, исправляющих ошибки. — М.: Связь, 1979.[14] Питерсон У., Уэлдон Э. Коды, исправляющие ошибки. — М.: Мир, 1976.[15] Курош А. Г. Курс высшей алгебры. — М.: Наука, 1975.[16] Лупанов О. Б. Асимптотические оценки сложности управляющих систем. — М.: Изд-во Московского университета, 1984.[17] Кудрявцев В. Б., Алешин С. В., Подколзин А. С. Введение в теорию автоматов. — М.: Наука, 1985.[18] Гиндсбург С. Математическая теория контекстно-свободных языков.
— М.: Мир, 1970.Последняя компиляция: 8 января 2007 г.Обновления документа — на сайтах http://dmvn.mexmat.net,http://dmvn.mexmat.ru.Об опечатках и неточностях пишите на dmvn@mccme.ru.2.
Характеристики
Тип файла PDF
PDF-формат наиболее широко используется для просмотра любого типа файлов на любом устройстве. В него можно сохранить документ, таблицы, презентацию, текст, чертежи, вычисления, графики и всё остальное, что можно показать на экране любого устройства. Именно его лучше всего использовать для печати.
Например, если Вам нужно распечатать чертёж из автокада, Вы сохраните чертёж на флешку, но будет ли автокад в пункте печати? А если будет, то нужная версия с нужными библиотеками? Именно для этого и нужен формат PDF - в нём точно будет показано верно вне зависимости от того, в какой программе создали PDF-файл и есть ли нужная программа для его просмотра.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
