Элементы комбинаторики

Критерий Понтрягина- Куратовского

Укладки графов. Планарные графы. Теорема Эйлера инварианта планарного

Поиск в глубину. Нахождение остовного дерева с помощью поиска в

Неориентированные, ориентированные графы. Способы задания графов.

Элементы математической логики. Исчисление высказываний, его полнота…….72

Метод построения сокращённой д.н.ф. с помощью обобщенного склеивания …..70

Метод нахождения всех тупиковых покрытий максимальными интервалами….66

Элементы функциональной полноты в классе двоичных функций.

1.1 Основные двоичные функции и их своства……………………..…………………….2

1.2 Утверждение о числе функций от n переменных……………………………………9

1.3 Представление функции в виде совершенной дизъюнктивной и совершенной конъюнктивной формах. Разложение функции по начальному множеству переменных…………………………………………………………………………………..13

1.4 Утверждение о представлении двоичной функции в виде полинома Жегалкина…………………………………………………………………………………..…19

1.5 Основные замкнутые классы двоичных функций относительно суперпозиций функций………………………………………………………………………………………...25

1.6 Критерий полноты в класее двоичных функций относительно суперпозиций функций…………………………………………………………………………………….…..31

1.7 Предполные классы двоичных функций……..…………………………………….….41

2. Минимизация ДНФ представляющих заданную функцию…………………………..55

2.1 Геометрическая интерпретация двоичных функций…………………………….…..57

2.2 Утверждение о максимальных интервалах и тупиковых покрытиях……………..60

2.3 Метод поиска всех максимальных интервалов заданной функции с помощью операции склеивания и поглащения……………………………………………………….63

4. Элементы теории графов………………………………………………………………….81

Матрица смежности, матрица инцендентностей, список смежности…………………..81

4.2 Азбука теории графов. Маршрут, путь, простой путь. Цикл. Простой цикл. Связность в графе……………………………………………………………………………..85

4.3 Методы анализа графа. Поиск в ширину. Нахождение кратчайших путей в графе……………………………………………………………………………..…….………88

глубину……………………………………………………………………………………91

гафа………………………………………………………………………………………..97

панарности графов………………………..…………………………………………….100

4.7 Хроматическое число графа……………………………………………………….101

5.1 Упорядоченные наборы с повторением и без повторений…………………………106

5.2 Неупорядоченные наборы элементов из данных без повторений………….109

5.3 Неупорядоченные наборы элементов из п данных с возможными повторениями……………..…………………………………………………………………110

5.4 Метод включения-исключения……………………………………………………….116

5.5 Основы метода производящих функций……………………………………………...119

5.6Основы теории перечисления Пойа. Лемма Бернсайда………………………..…...121

Дата добавления: 2017-01-13