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

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

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

Утверждаю

Зам. директора по реализации программ СПО

«____»_________ 20 __ г.

___________ О.К. Лозбенева

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

Протокол №_____

от «____»_________ 20 __ г.

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

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

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

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

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

II курс

Сергиевск

2012

РАССМОТРЕНО

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

Протокол № ________________

от «____»______________20____ г.

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

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

II курс

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

2011-2012г.

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

1. Логические операции. Формулы логики.

2. Законы логики. Равносильные преобразования. Упрощение формул логики с помощью равносильных преобразований.

3. Булевы функции. Способы задания булевых функций.

4. Дизъюнктивные нормальные формы (ДНФ). Конъюнктивные нормальные формы (КНФ)

5. Ориентированный граф. Основные понятия.

6. Совершенные дизъюнктивные нормальные формы (СДНФ). Совершенные конъюнктивные нормальные формы (СКНФ).

7. Представление булевых функций в виде СДНФ и СКНФ.

8. Операция двоичного сложения. Многочлен Жегалкина.

9. Понятие множества. Основные операции над множествами.

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

11. Логические и кванторные операции над предикатами.

12. Бинарные отношения. Основные понятия. Примеры.

13. Теория отображений. Основные понятия.

14. Правильный автомат (автомат Мура).

15. Алгебра подстановок. Основные понятия, свойства.

16. Основы алгебры вычетов.

17. Простейшие криптографические шифры.

18. Метод математической индукции.

19. Базовые множества и принцип работы автоматов.

20. Метод включений и исключений

21. Алгоритм фронта волны в графе. Расстояние между вершинами в графе

22. Неориентированный граф. Способы задания. Теорема о сумме степеней вершин.

23. Двудольные графы. Изоморфные графы. Эйлеровы графы. Гамильтоновы графы. Плоские графы.

24. Сочетание, размещение, перестановки. Бином Ньютона и полиномиальная формула.

Практическая часть

1. Найдите множество .

2. Дана булева функция f (x₁, x₂, x₃)=(10001010). Представьте данную булеву функцию в виде СДНФ и СКНФ с помощью таблицы истинности.

3. Д ана подстановка = 1 5 3 4 2 . Найти

4 3 2 1 5

4. Пусть граф G задан матрицей смежности А. Построить диаграмму этого графа, если

5. Определите следующие логические законы:

1) ав=ва;

2) ;

3)

6. Зашифруйте, используя теорию вычетов, сообщение «ДЕВА»

7. С помощью таблиц истинности проверьте эквивалентность формул и

8. Найдите множество .

9. Постройте матрицу смежности и матрицу инцидентности для отношений, заданных графом G. Найдите число степеней входа и выхода этого графа.

10. Количество рёбёр графа G(V,X) равно 24. Найдите сумму степеней всех вершин графа.

11. Даны два множества А={4, 3, 6, 9, 11, 13, 15, 17} и

В={0, -5, 9, 12, 13, 21, 30, 34}. Найдите следующие множества:

, , А\В, В\А, А∆В.