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

ДИСКРЕТНАЯ МАТЕМАТИКА И МАТЕМАТИЧЕСКАЯ КИБЕРНЕТИКА
проф. А.Б. Угольников
1 год
1. Выборки, перестановки, сочетания, перестановки с повторениями,
сочетания с повторениями. Биномиальные коэффициенты, их свойства.
Биномиальная теорема. Полиномиальные коэффициенты. Полиномиальная теорема.
(см. [1-2, 12])
2. Формулы обращения. Метод включений и исключений. Оценки для числа
элементов, не обладающих ни одним из свойств. Формула для числа элементов,
обладающих в точности [pic] свойствами. Функция Мебиуса. Формула обращения
Мебиуса. Перечисление циклических последовательностей. (см. [1-2, 12])
3. Производящие функции. Примеры применения метода производящих функций
для решения комбинаторных задач (число способов расстановки скобок,
сочетания с повторениями, сочетания с повторениями, в которых каждый
элемент содержится не более 3-х раз). Линейные рекуррентные соотношения с
постоянными коэффициентами. Решение рекуррентных соотношений. Числа
Фибоначчи. (см. [1-2, 12])
4. Графы. Основные понятия. Способы представления графов. Перечисление
графов на занумерованных вершинах. Верхняя оценка для числа неизоморфных
графов с [pic] ребрами. Эйлеровы циклы. Теорема Эйлера. Теорема Эйлера для
ориентированных графов. Последовательности де Брейна. Алгоритм построения
Эйлерова цикла специального вида ("обход выставки"). (см. [3-6])
5. Деревья и их свойства. Оценка числа неизоморфных корневых деревьев с q
ребрами. Теорема Кэли о числе деревьев на нумерованных вершинах. Алгоритм
Краскала нахождения минимального остовного дерева, (см. [3-6, 8])
6. Потоки в сетях. Минимальные разрезы. Максимальные потоки. Лемма о
существовании максимального потока. Теорема Форда-Фалкерсона о максимальном
потоке и минимальном разрезе. Алгоритм нахождения максимального потока.
Теорема о целочисленности. (см. [5-7])
7. Рассекающие множества. Теорема Кенига-Эгервари о рассекающих
множествах в двудольном графе. Паросочетания. Теорема Холла о
паросочетаниях в двудольном графе. Частично упорядоченные множества.
Теорема Дилуорса о представлении частично упорядоченных множеств. Разбиение
Анселя множества всех двоичных наборов на непересекающиеся цепи. (см. [2,
5, 7, 9])
8. Функции алгебры логики. Существенные и несущественные переменные.
Формулы. Совершенная ДНФ. Совершенная КНФ. Полные системы. Полиномы
Жегалкина. Теорема о представлении функций полиномами. Замкнутые классы.
Двойственность, монотонность, линейность. Принцип двойственности. Критерий
полноты для булевых функций. Предполные классы. Базисы. Примеры базисов для
предполных классов. (см. [10-12])
9. Функции, удовлетворяющие условию < 0 >, их свойства. Свойства функций
[pic] и [pic]. Леммы о порождении монотонных функций. Лемма о немонотонных
функциях. Леммы о системах самодвойственных функций, о системах функций,
сохраняющих константы. Теорема Поста о конечной порожденности замкнутых
классов булевых функций. (см. [13-15])
10. Предикатное описание замкнутых классов булевых функций. Функции,
сохраняющие предикат [pic]. Множество [pic] и его свойства. Теорема о
замкнутых классах, допускающих предикатное описание. Способ построения
предикатов, задающих классы булевых функций. Размерности замкнутых классов.
Замкнутые классы, определяемые двуместными предикатами, (см. [15-16])
11. Функции k-значной логики. Элементарные функции. Полнота системы
функций [pic]. Полнота систем [pic], [pic]. Алгоритм распознавания полноты
конечных систем функций в [pic]. Теорема о представление функции из[pic]
полиномами. (см. [10-11])
12. Особенности функций k-значной логики. Пример замкнутого класса в
[pic], не имеющего базиса. Пример замкнутого класса в [pic], имеющего
счетный базис Пример континуального семейства замкнутых классов в [pic].
(см. [10-11])
13. Сложность реализации булевых функций формулами в полном базисе. Меры
сложности. Простейшие методы синтеза. Разбиение множества наборов на сферы.
Характеристические функции сфер и их свойства. Реализация системы
конъюнкций. Асимптотически наилучший метод синтеза формул в базисе [pic].
Мощностной метод получения нижних оценок сложности. Функция Шеннона.
Поведение функции Шеннона. (см. [17])
14. Глубина формул. Простейшие оценки сложности. Соотношение между
глубиной и сложностью формул в полных базисах. Полиномиальная
эквивалентность полных систем. (см. [18])
15. Контактные схемы. Простейшие методы синтеза. Асимптотически наилучший
метод синтеза контактных схем. Мощностной метод получения нижних оценок
сложности для контактных схем. Функция Шеннона. Поведение функции Шеннона.
(см. [17])
16. П-схемы. Связь между формулами в базисе [pic] и П-схемами. Нижние
оценки для индивидуальных функций. Теорема Храпченко. Сложность реализации
линейных булевых функций формулами в базисе [pic]. (см. [17, 19-20])
17. Детерминированные функции. Задание детерминированных функций при
помощи деревьев. Вес функций. Ограниченно-детерминированные функции (о.д.-
функции). Способы задания о.д.-функций (диаграммы переходов, канонические
уравнения, схемы). (см. [10, 21-22])
18. Конечные автоматы. Автоматные функции. Состояния автомата.
Эквивалентность состояний. Теорема об эквивалентных состояниях автомата.
Эквивалентность автоматов. Теорема об эквивалентности состояний автоматов.
Сокращенный автомат. Метод построения сокращенного автомата. (см. [10, 21-
22])
19. Преобразование автоматными функциями периодических
последовательностей. Отсутствие конечных полных систем автоматных функций
(в случае схем без обратных связей). Реализуемость автоматных функций
схемами из функциональных элементов и элементов задержки (схемами с
обратными связями). (см. [10, 21-22])
20. События. Операции над событиями. Регулярные события. Представимые
события. Теорема о событиях, представимых конечными автоматами. Обобщенные
источники. Представление регулярных событий обобщенными источниками.
Теорема Клини. Пример нерегулярного события. Способы задания регулярных
событий (конечные автоматы, источники, обобщенные источники, регулярные
выражения). Сравнение сложности задания. Алгоритм проверки равенства
регулярных событий. (см. [21])


Литература

1. Рыбников К.А. Введение в комбинаторный анализ. М., изд-во МГУ, 1985.
2. Холл М. Комбинаторика. М., Мир, 1970.
3. Берж К. Теория графов и ее применения. М., Ин. лит-ра, 1962.
4. Оре О. Теория графов. М., Наука, 1968.
5. Уилсон Р. Введение в теорию графов. М., Мир, 1977.
6. Кристофидес Н. Теория графов. Алгоритмический подход. М., Мир, 1978.
7. Форд Л., Фалкерсон Д. Потоки в сетях. М., Мир, 1966.
8. Ахо А., Хопкрофт Дж., Ульмант Дж. Построение и анализ вычислительных
алгоритмов. М., Мир, 1979.
9. Ансель Ж. О числе монотонных булевых функций [pic] переменных.// в кн.
Кибернетический сборник. Новая серия. Вып. 5. М., Мир, 1969. С. 53-57.
10. Яблонский С.В. Введение в дискретную математику. М., Наука, 1986.
11. Дискретная математика и математические вопросы кибернетики. (под ред.
С.В. Яблонского и О.Б. Лупанова.) Т. 1. М., Наука, 1974.
12. Гаврилов Г.П., Сапоженко А.А. Задачи и упражнения по курсу дискретной
математики. М., Наука, 1992.
13. Яблонский С.В., Гаврилов Г.П., Кудрявцев В.Б. Функции алгебры логики и
классы Поста. М., Наука, 1966.
14. Марченков С.С., Угольников А.Б. Замкнутые классы булевых функций. М.,
Институт прикладной математики им. М.В. Келдыша, 1990.
15. Угольников А.Б. О замкнутых классах Поста.// Известия высших учебных
заведений. Математика, 1988, ? 7, 79-88.
16. Блохина Г.Н. О предикатном описании классов Поста.// Дискретный анализ.
Новосибирск, 1970, ? 16, с. 16-29.
17. Лупанов О.Б. Асимптотические оценки сложности управляющих систем. М.,
изд-во МГУ, 1984.
18. Пратт В. Влияние базиса на сложность булевых формул.// в кн.
Кибернетический сборник. Новая серия. Вып. 17. М., Мир, 1980. С. 114-123.
19. Рычков К.Л. Модификация метода В.М. Храпченко и применение ее к оценкам
сложности П-схем для кодовых функций.// Методы дискретного анализа в теории
графов и схем. Новосибирск, 1985, ? 42, с. 91-98.
20. Нигматуллин Р.Г. Сложность булевых функций. М., Наука, 1990.
21. Кудрявцев В.Б., Алешин С.В., Подколзин А.С. Введение в теорию
автоматов. М., Наука, 1985.
22. Шоломов Л.А. Основы теории дискретных логических и вычислительных
устройств. М., Наука, 1970.