ВУЗ:
Составители:
Рубрика:
7.1.4 Операции на алгебраических структурах
Операции на алгебраических структурах. Группы, подгруппы, нормаль-
ные группы, их свойства. Теоремы Лагранжа и Кэли. Кольца, их основные
свойства. Кольца многочленов, их свойства. Подкольца, идеалы, их свойства.
Поля, их основные свойства. Алгоритм деления многочленов.
7.1.5 Основные понятия теории графов
Основные понятия теории графов. Подграфы, изоморфизм графов и
под-
графов. Матрицы смежности и инцидентности, их основные свойства.
7.1.6 Маршруты, циклы, связность
Маршруты, цепи, циклы. Эйлеровы и гамильтоновы цепи и циклы. Ос-
товные подграфы, компоненты, связность. Операции над графами. Теоремы о
существовании эйлеровых и гамильтоновых циклов. Цикломатическое число,
его свойства. Задачи о кратчайшем пути. Теорема Менгера. Потоки и разрезы.
Вершинные
и реберные покрытия, числа внутренней и внешней устойчивости,
паросочетания. Теоремы Кенига, Холла, Фробениуса. Задачи о подсчете совер-
шенных паросочетаний.
7.1.7 Раскраски. Планарные графы
Вершинные и реберные раскраски графа. Хроматическое число и хрома-
тический индекс, их свойства. Планарность. Теорема Понтрягина – Куратовско-
го. Теорема о четырех красках.
7.1.8 Деревья. Задачи подсчета деревьев специального
вида
Деревья. Матричная теорема о деревьях, подсчет числа остовов. Подсчет
кубических деревьев специального вида. Числа Фибоначчи и Каталана, их
свойства.
7.1.9 Элементы комбинаторики
Основные методы комбинаторного анализа: рекуррентные соотношения,
производящие функции, метод включения и исключения, взаимно обратные со-
отношения. Примеры применения основных методов комбинаторного анализа к
решению задач на перечисление.
7.1.10 Переключательные
функции (ПФ)
Основные понятия, связанные с булевым кубом и функциями алгебры ло-
гики. Элементарные булевы функции. Формулы. Реализация булевых функций
формулами. Принцип двойственности. Основные классы булевых функций. Ба-
зовые функциональные элементы.
7.1.11 Способы задания ПФ, специальные разложения ПФ, не полностью
определенные (частные) ПФ
Разложение булевых функций по переменным. Совершенная дизъюнк-
тивная
нормальная и совершенная конъюнктивная нормальная формы. Поли-
номы Жегалкина. Не полностью определенные (частные) булевы функции.
7.1.4 Операции на алгебраических структурах
Операции на алгебраических структурах. Группы, подгруппы, нормаль-
ные группы, их свойства. Теоремы Лагранжа и Кэли. Кольца, их основные
свойства. Кольца многочленов, их свойства. Подкольца, идеалы, их свойства.
Поля, их основные свойства. Алгоритм деления многочленов.
7.1.5 Основные понятия теории графов
Основные понятия теории графов. Подграфы, изоморфизм графов и под-
графов. Матрицы смежности и инцидентности, их основные свойства.
7.1.6 Маршруты, циклы, связность
Маршруты, цепи, циклы. Эйлеровы и гамильтоновы цепи и циклы. Ос-
товные подграфы, компоненты, связность. Операции над графами. Теоремы о
существовании эйлеровых и гамильтоновых циклов. Цикломатическое число,
его свойства. Задачи о кратчайшем пути. Теорема Менгера. Потоки и разрезы.
Вершинные и реберные покрытия, числа внутренней и внешней устойчивости,
паросочетания. Теоремы Кенига, Холла, Фробениуса. Задачи о подсчете совер-
шенных паросочетаний.
7.1.7 Раскраски. Планарные графы
Вершинные и реберные раскраски графа. Хроматическое число и хрома-
тический индекс, их свойства. Планарность. Теорема Понтрягина – Куратовско-
го. Теорема о четырех красках.
7.1.8 Деревья. Задачи подсчета деревьев специального вида
Деревья. Матричная теорема о деревьях, подсчет числа остовов. Подсчет
кубических деревьев специального вида. Числа Фибоначчи и Каталана, их
свойства.
7.1.9 Элементы комбинаторики
Основные методы комбинаторного анализа: рекуррентные соотношения,
производящие функции, метод включения и исключения, взаимно обратные со-
отношения. Примеры применения основных методов комбинаторного анализа к
решению задач на перечисление.
7.1.10 Переключательные функции (ПФ)
Основные понятия, связанные с булевым кубом и функциями алгебры ло-
гики. Элементарные булевы функции. Формулы. Реализация булевых функций
формулами. Принцип двойственности. Основные классы булевых функций. Ба-
зовые функциональные элементы.
7.1.11 Способы задания ПФ, специальные разложения ПФ, не полностью
определенные (частные) ПФ
Разложение булевых функций по переменным. Совершенная дизъюнк-
тивная нормальная и совершенная конъюнктивная нормальная формы. Поли-
номы Жегалкина. Не полностью определенные (частные) булевы функции.
