Теоретическая часть

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

Среднего профессионального образования

Сергиевский губернский техникум

Рассмотрено на заседании ПЦК

Протокол №_____

От «____»_________ 20 __ г.

Председатель ПЦК_________

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

Для промежуточной аттестации

По дисциплине «Дискретная математика»

специальности 230701.51 Прикладная информатика (в экономике)

II курс

Сергиевск

РАССМОТРЕНО

на заседании ПЦК

Протокол № ________________

от «____»______________20____ г.

Председатель комиссии ________

Вопросы к экзамену

II курс

По дисциплине «Дискретная математика»

Г.

Теоретическая часть

1. Логические операции. Формулы логики.
2. Законы логики. Равносильные преобразования. Упрощение формул логики с помощью равносильных преобразований.
3. Булевы функции. Способы задания булевых функций.
4. Дизъюнктивные нормальные формы (ДНФ). Конъюнктивные нормальные формы (КНФ)
5. Ориентированный граф. Основные понятия.
6. Совершенные дизъюнктивные нормальные формы (СДНФ). Совершенные конъюнктивные нормальные формы (СКНФ).
7. Представление булевых функций в виде СДНФ и СКНФ.
8. Операция двоичного сложения. Многочлен Жегалкина.
9. Понятие множества. Основные операции над множествами.

10. Предикаты. Основные понятия.

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