Ф 20-014
Утверждено
протокол заседания кафедры алгебры, геометрии и методики преподавания математики № 13 от 07.12.2011
Вопросы к экзамену
по дисциплине «Дискретная математика и математическая логика» 2 курса специальностей «Информатика» и «Экономическая кибернетика»
«Компьютерная безопасность»
дневной формы обучения
1. Множества, задание множеств. Подмножества и их свойства. Операции над множествами, основные равенства.
2. Высказывания, операции над высказываниями.
3. Тождественно истинные и тождественно ложные высказывания. Равносильные высказывания.
4. Суперпозиция функций. Бинарные отношения. Свойства бинарных отношений.
5. Отношение порядка. Отношение эквивалентности. Бинарные операции
6. Алгебры. Алгебра Кантора и булева алгебра. Изоморфизм. Операции над двоичными числами
7. Булевы функции. Мощность множества булевых функций от 
переменных.
8. Элементарные булевы функции.
9. Формулы. Основные эквивалентности формул.
10. Принцип двойственности. Двойственные булевы функции.
11. Теорема о разложении.
12. Совершенные дизъюнктивные нормальные формы.
13. Совершенные конъюнктивные нормальные формы.
14. Существенные и фиктивные переменные.
15. Полином Жегалкина.
16. Представление булевой функции в виде полинома Жегалкина.
17. Замкнутый класс T0.
18. Замкнутый класс Т1.
19. Замкнутый класс S.
20. Замкнутый класс L.
21. Замкнутый класс M.
22. Теорема Поста о полноте со следствием.
23. Сочетания и перестановки.
24. 
- выборки из - множества.
25. Перестановки с повторениями.
26. Полиномиальная теорема. Бином Ньютона.
27. Рекуррентные соотношения и производящие функции.
28. Принцип включения и исключения.
29. Обобщённый принцип включения и исключения.
30. Схемы правильных рассуждений. Аксиоматические теории
31. Предикативные формулы. Тавтологии. Исчисление предикатов.
32. Минимальные, кратчайшие и тупиковые ДНФ.
33. Сокращённые ДНФ. Построение сокращённых ДНФ булевых функций методом Блейка. Пример.
34. Построение сокращённых ДНФ булевых функций методом Квайна. Пример.
35. Построение сокращённых ДНФ геометрическим методом. Пример.
36. Графы. Изоморфизм графов.
37. Способы задания графов.
38. Действия над графами.
39. Ориентированные и неориентированные графы.
40. Маршруты. Пути. Цепи. Связные графы.
41. Геометрическая реализации графа. Теорема о реализации конечного графа в трёхмерном пространстве.
42. Эйлеровы циклы. Задача о кенигсбергских мостах. Теорема Эйлера.
43. Обобщенная теорема об эйлеровых цепях.
44. Гамильтоновы графы. Задача о коммивояжере.
45. Взвешенный граф. Граф-дерево.
46. Цикломатическое число. Остов графа. Базис циклов.
47. Двудольные графы.
48. Планарные графы. Критерий планарности графов.
49. Теорема Куратовского-Понтрягина. Граф Петерсена
50. Двухполюсные сети. Параллельно-последовательные сети. Поток в сети.
51. Теорема Форда-Фалкерсона о максимальном потоке. Расчет максимального потока в сети.
52. Помехоустойчивое кодирование. Примеры.
53. Код Хэмминга.
54. Алфавитное кодирование.
55. Алгоритм Фано. Пример.
56. Алгоритм кодирования Хаффмена. Пример.
57. Формальные грамматики. Основные понятия.
58. Классификация грамматик по Хомскому.
59. Типы языков. Вывод цепочек. Дерево вывода.
60. Логические сети. Пример.
61. Конечные автоматы. Таблица состояний. Диаграмма состояний.
62. Понятие алгоритма. Основные свойства алгоритмов.
63. Рекурсивные функции. Классы рекурсивных функций.
64. Машины Тьюринга. Принципы работы.
65. Машины Тьюринга. Примеры.
Составитель: доцент кафедры математического анализа
и дифференциальных уравнений ______________ / Детченя Л.В. /
Заведующий кафедрой алгебры,
геометрии и методики преподавания математики ______________ / Гринь А.А. /