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