Теория множеств и отношений. Булевы функции.

ФЕДЕРАЛЬНОЕ АГЕНТСТВО ПО ОБРАЗОВАНИЮ

Государственное образовательное учреждение

Высшего профессионального образования

«ХАКАССКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ

Им. Н.Ф.КАТАНОВА»

_______________________________________________________________________

Кафедра Информационных технологий и систем

 

 

Материалы,

устанавливающие содержание и

Порядок проведения промежуточных и итоговых аттестаций

 

по дисциплине

 

ЕН.Ф.3 «Математика. Дискретная математика»

Специальность 230100 «Информатика и вычислительная техника»

Составитель: старший преподаватель кафедры ИТиС Дернович Е.С.

 

Абакан

Вопросы к зачету по дисциплине «Дискретная математика» (5 семестр).

1. Множества. Основные операции над множествами. Дополнение множества. Универсальное множество. Диаграммы Эйлера-Венна.

2. Основные тождества алгебры множеств. Доказательство тождеств.

3. Декартово произведение множеств. Свойства декартова произведения.

4. Бинарные отношения. Область определения, область значений бинарного отношения. Геометрическая интерпретация бинарного отношения.

5. Специальные бинарные отношения. Свойства.

6. Отношение эквивалентности. Разбиение множества. Фактор-множество. Классы эквивалентности.

7. Отношение порядка. Виды порядка.

8. Упорядоченные множества. Диаграммы Хассе. Минимальный, максимальный, наибольший и наименьший элементы упорядоченного множества.

9. Отображения. Виды отображений. Функциональные отношения.

10. Булевы функции. Число всех различных n-местных булевых функций. Переключательные функции.

11. Алгебра Жегалкина. Многочлен Жегалкина. Приведение булевой функции к многочлену Жегалкина.

12. Основные функционально-замкнутые классы булевых функций (Т₀,Т₁, L, M, S).

13. Функционально-полные системы булевых функций. Примеры функционально-полных базисов.

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

15. Особые методы минимизации ПФ.

 

Вопросы к зачету по дисциплине «Дискретная математика» (6 семестр)

 

 

1. Основные понятия теории графов (определение графа, виды графов, смежность, инцидентность, кратность ребер, степень вершины). Примеры.
2. Операции над графами. Подграфы. Дополнение графа. Привести примеры.
3. Способы задания графов. Матричный способ задания. Свойства матриц смежности и инцидентности. Привести примеры.
4. Цепи, маршруты (пути), циклы (контуры) в графе (орграфе). Количество всех путей (маршрутов) длины к в ориентированном псевдографе (псевдографе). Необходимое и достаточное условие существования контура в орграфе (ориентированном псевдографе). Примеры.
5. Булевы матрицы. Логические операции над булевыми матрицами. Пример.
6. Связность графа. Компоненты связности. Матрица связности. Привести пример.
7. Алгоритм выделения компонент связности. Привести пример.
8. Полные, двудольные, однородные графы. Привести примеры.
9. Реберные графы. Нахождение матрицы смежности, степеней вершин, количества ребер реберного графа через данные исходного графа. Примеры.
10. Поиск путей (маршрутов) с минимальным числом дуг (ребер) в орграфе (графе). Алгоритм фронта волны. Привести пример.
11. Расстояние в графах. Матрица расстояний. Диаметр, радиус, центр графа. Привести примеры.
12. Нагруженные графы. Расстояние, эксцентриситет, радиус в нагруженном графе. Алгоритм нахождения кратчайшего остова в нагруженном графе.
13. Алгоритм Форда-Беллмана нахождения кратчайшего маршрута в нагруженном графе. Пример. Алгоритм Дейкстры.
14. Эйлеровы цепи и циклы в графах. Эйлеровы графы. Необходимое и достаточное условие существования эйлерова цикла. Примеры.
15. Алгоритм выделения эйлерова цикла в графе. Пример.
16. Гамильтоновы цепи и циклы в графах. Гамильтоновы графы. Достаточные условия существования гамильтонова цикла.
17. Деревья. Корневые деревья. Свойства деревьев. Остов графа. Построение остова графа. Привести пример.
18. Цикломатическое число графа. Цикловой базис. Выделение базиса в графе. Пример.
19. Раскраска вершин и ребер графа. Хроматическое число графа. Независимые множества вершин и паросочетания. Точный алгоритм раскрашивания.
20. Изоморфизм графов. Планарные графы. Теорема Эйлера и ее следствия. Теорема Понтрягина-Куратовского. Раскрашиваемость планарного графа пятью красками. Гипотеза четырех красок.

 

Вопросы к экзамену по дисциплине «Дискретная математика»

(6 семестр)

Теория множеств и отношений. Булевы функции.

1. Множества. Основные операции над множествами. Дополнение множества. Универсальное множество. Диаграммы Эйлера-Венна.

1. Основные тождества алгебры множеств. Доказательство тождеств.
2. Декартово произведение множеств. Свойства декартова произведения.
3. Бинарные отношения. Область определения, область значений бинарного отношения. Геометрическая интерпретация бинарного отношения.
4. Специальные бинарные отношения. Свойства.
5. Отношение эквивалентности. Разбиение множества. Фактор-множество. Классы эквивалентности.
6. Отношение порядка. Виды порядка.
7. Упорядоченные множества. Диаграммы Хассе. Минимальный, максимальный, наибольший и наименьший элементы упорядоченного множества.
8. Отображения. Виды отображений. Функциональные отношения.
9. Булевы функции. Число всех различных n-местных булевых функций. Переключательные функции.
10. Алгебра Жегалкина.
11. Основные функционально-замкнутые классы булевых функций (Т₀,Т₁, L, M, S).
12. Функционально-полные системы булевых функций. Примеры функционально-полных базисов.
13. Особые методы минимизации ПФ.

 

Теория графов.

 

1. Основные понятия теории графов (определение графа, виды графов, смежность, инцидентность, кратность ребер, степень вершины). Примеры.
2. Операции над графами. Подграфы. Дополнение графа. Привести примеры.
3. Способы задания графов. Матричный способ задания. Свойства матриц смежности и инцидентности. Привести примеры.
4. Цепи, маршруты (пути), циклы (контуры) в графе (орграфе). Количество всех путей (маршрутов) длины к в ориентированном псевдографе (псевдографе). Необходимое и достаточное условие существования контура в орграфе (ориентированном псевдографе). Примеры.
5. Булевы матрицы. Логические операции над булевыми матрицами. Пример.
6. Связность графа. Компоненты связности. Матрица связности. Привести пример.
7. Алгоритм выделения компонент связности. Привести пример.
8. Полные, двудольные, однородные графы. Привести примеры.
9. Реберные графы. Нахождение матрицы смежности, степеней вершин, количества ребер реберного графа через данные исходного графа. Примеры.
10. Поиск путей (маршрутов) с минимальным числом дуг (ребер) в орграфе (графе). Алгоритм фронта волны. Привести пример.
11. Расстояние в графах. Матрица расстояний. Диаметр, радиус, центр графа. Привести примеры.
12. Нагруженные графы. Расстояние, эксцентриситет, радиус в нагруженном графе. Алгоритм нахождения кратчайшего остова в нагруженном графе.
13. Алгоритм Форда-Беллмана нахождения кратчайшего маршрута в нагруженном графе. Алгоритм Дейкстры. Примеры.
14. Эйлеровы цепи и циклы в графах. Эйлеровы графы. Необходимое и достаточное условие существования эйлерова цикла. Примеры.
15. Алгоритм выделения эйлерова цикла в графе. Пример.
16. Гамильтоновы цепи и циклы в графах. Гамильтоновы графы. Достаточные условия существования гамильтонова цикла.
17. Деревья. Корневые деревья. Свойства деревьев. Остов графа. Построение остова графа. Привести пример.
18. Цикломатическое число графа. Цикловой базис. Выделение базиса в графе. Пример.
19. Раскраска вершин и ребер графа. Хроматическое число графа. Независимые множества вершин и паросочетания. Точный алгоритм раскрашивания.
20. Изоморфизм графов. Планарные графы. Теорема Эйлера и ее следствия. Теорема Понтрягина-Куратовского. Раскрашиваемость планарного графа пятью красками. Гипотеза четырех красок.