Документ взят из кэша поисковой машины. Адрес оригинального документа : http://new.math.msu.su/content_root/programs/kaf/special/discra/discra-ug.doc Дата изменения: Mon Nov 10 08:56:13 2008 Дата индексирования: Sun Apr 10 03:13:37 2016 Кодировка: koi8-r

ДИСКРЕТНАЯ МАТЕМАТИКА

проф. А.Б. Угольников
1/2 года, 4 курс
1. Функции алгебры логики. Существенные и несущественные переменные.
Формулы. Совершенная ДНФ. Полные системы. Полиномы Жегалкина. Теорема о
представлении функций полиномами. Замкнутые классы. Двойственность,
монотонность, линейность. Принцип двойственности. Критерий полноты для
множества всех булевых функций.
2. Леммы о порождении функций [pic], [pic], [pic]. Функции,
удовлетворяющие условию [pic], их свойства. Свойства функций [pic], [pic],
[pic]. Леммы о порождении монотонных функций. Лемма о немонотонных
функциях. Лемма о системах самодвойственных функций. Лемма о системах
функций, сохраняющих константы.
3. Теорема Поста о конечной порожденное замкнутых классов булевых
функций.
4. Синтез формул в базисе [pic]. Простейшие методы синтеза. Разбиение
множества двоичных наборов на сферы. Характеристические функции сфер, их
свойства. Асимптотически оптимальный метод синтеза формул. Мощностной метод
получения нижней оценки для функции [pic].
5. Схемы из функциональных элементов в базисе [pic]. Простейшие методы
синтеза. Асимптотически оптимальный метод синтеза схем.
6. Графы. Основные понятия. Способы задания графов. Геометрическая
реализация графов. Деревья. Характеристические свойства деревьев. Верхняя
оценка числа неизоморфных корневых деревьев с q ребрами. Теорема Кэли о
числе деревьев с занумерованными вершинами. Верхняя оценка числа
неизоморфных графов с q ребрами.
7. Производящие функции. Примеры применения метода производящих функций
для решения комбинаторных задач: сочетания с повторениями, задача о
расстановке скобок в неассоциативном произведении. Линейные рекуррентные
соотношения с постоянными коэффициентами. Решение линейных рекуррентных
соотношений. Функция Мебиуса. Формула обращения Мебиуса.
8. Конечные поля. Порядок и характеристика поля. Свойства конечных полей.
Поле [pic], p - простое. Неприводимые многочлены. Нумератор множества всех
двоичных многочленов. Формула для числа неприводимых двоичных многочленов
заданной степени. Поле [pic] - поле двоичных многочленов степени не выше m-
1. Построение поля [pic].
9. Побуквенное кодирование. Разделимые коды. Префиксные коды. Неравенство
Крафта-Макмиллана для разделимых кодов. Условие существования разделимого
кода с заданными длинами кодовых слов. Критерий взаимной однозначности
алфавитного кодирования.
10. Оптимальные коды. Свойства оптимальных двоичных кодов. Теорема
редукции. Алгоритм Хаффмена построения оптимальных кодов.
11. Самокорректирующиеся двоичные коды. Коды Хэмминга, их свойства.
Алгоритм декодирования для кодов Хэмминга. Геометрическая интерпретация.
Коды с исправлением t ошибок. Верхняя оценка построения максимального кода
(граница сферической упаковки). Построение кодов, исправляющих t ошибок.
12. Линейные коды. Порождающие и проверочные матрицы линейных кодов.
Параметры линейных кодов. Необходимое и достаточное условие существования
линейных кодов с заданным минимальным расстоянием.
13. Двоичные коды Боуза-Чоудхури-Хоквингема (коды БЧХ). Построение кодов
БЧХ, исправляющих t ошибок для любого натурального t. Алгоритм
декодирования для кодов БЧХ, исправляющих двойные ошибки.
14. Детерминированные функции. Задание детерминированных функций при
помощи деревьев. Вес функций. Ограниченно-детерминированные функции (о.д.-
функции). Способы задания о.д.-функций.
15. Конечные автоматы. Автоматные функции. Способы задания автоматных
функций. Схемы из функциональных элементов и элементов задержки.
Реализуемость автоматных функций схемами из функциональных элементов и
элементов задержки. Состояния автомата. Эквивалентность состояний. Теорема
Мура об эквивалентных состояниях автомата. Эквивалентность автоматов.
Теорема об эквивалентности состояний автоматов. Сокращенный автомат. Метод
построения сокращенного автомата.
16. События. Операции над событиями. Регулярные события. Представимые
события. Теорема о событиях, представимых конечными автоматами. Обобщенные
источники. Представление регулярных событий обобщенными источниками.
Теорема Клини. Пример нерегулярного события. Источники. Регулярные
выражения. Представление регулярных событий источниками и регулярными
выражениями. Равенство регулярных событий. Свойства регулярных событий.


Литература

1. Яблонский С.В. Введение в дискретную математику. М., Наука, 1986.
2. Дискретная математика и математическая кибернетика. (Под ред. С.В.
Яблонского и О.Б. Лупанова.) Т. 1. М., Наука, 1974.
3. Гаврилов Г.П., Сапоженко А.А. Задачи и упражнения по курсу дискретной
математики. М., Наука, 1992.
4. Угольников А.Б. О замкнутых классах Поста.// Известия высших учебных
заведений. Математика, 1988, ? 7, 79-88.
5. Марченков С.С., Угольников А.Б. Замкнутые классы булевых функций. М.,
Институт Прикладной математики им. М.В. Келдыша, 1990.
6. Марченков С.С. Замкнутые классы булевых функций. М., Физматлит, 2000.
7. Лупанов О.Б. Асимптотические оценки сложности управляющих систем. М.,
изд-во МГУ, 1984.
8. Холл М. Комбинаторика. М., Мир, 1970.
9. Рыбников К.А. Введение в комбинаторный анализ. М., изд-во МГУ, 1985.
10. Берлекэмп Э. Алгебраическая теория кодирования. М., Мир, 1971.
11. Мак-Вильямс Ф.Дж., Слоэн Н.Дж.А. Теория кодов, исправляющих ошибки. М.,
Связь, 1979.
12. Кудрявцев В.Б., Алешин С.В., Подколзин А.С. Введение в теорию
автоматов. М., Наука, 1985.