Вопросы к экзамену по дискретной математике

Вопросы к экзамену по дискретной математике

1. Высказывания, предикаты и действия над ними. Логические операции над высказываниями: отрицание, конъюнкция, дизъюнкция, импликация, эквиваленция. Свойства логических операций.

2. Формулы логики высказываний, тавтология, противоречие, логическое следствие.

3. Булевы алгебры. Аксиомы булевой алгебры. Примеры булевых алгебр (алгебра высказываний, алгебра множеств, релейно-контактные схемы).

4. Элементарные функции алгебры логики. Элементарные булевы функции одной переменной. Элементарные булевы функции двух переменных. Диаграммы Венна для булевых функций одной и двух переменных. Условные обозначения булевых функций.

5. Логические функции n переменных. Способы их задания (таблица значений, вектор значений, карта Карно или диаграмма Вейча, числовой способ задания функции).

6. Представление булевых функций с помощью формул. Эквивалентные, выполнимые, опровержимые, тождественно истинные, тождественно ложные формулы. Равносильность любой формулы алгебры логики формуле, содержащей связки: 1) ¾, ; 2) ¾, ; 3)¾, ; 4) | ; 5).

7. Принцип двойственности для булевых алгебр и булевых функций.

8. Элементарная конъюнкция или конъюнкт. Минтерм или конституент набора N. Теорема о минтерме. Дизъюнктивная нормальная форма (ДНФ) и совершенная дизъюнктивная нормальная форма (СДНФ). Теорема о совершенной дизъюнктивной нормальной форме.

9. Элементарная дизъюнкция или дизъюнкт. Макстерм или антиконституент набора N (конституента нуля). Теорема о макстерме. Конъюнктивная нормальная форма (КНФ) и совершенная конъюнктивная нормальная форма (СКНФ). Теорема о совершенной конъюнктивной нормальной форме.

10. Разложение логических функций по одной переменной. Следствия.

11. Разложение булевых функций по совокупности переменных. Первая и вторая теоремы Шеннона. Следствия.

12. Индекс простоты булевой функции. Импликанта функции. Полная система импликант функции. Сокращенная ДНФ. Приведенная система импликант. Тупиковая ДНФ. Минимальная ДНФ. Построение сокращенной ДНФ методом Блейка.

13. Минимизация булевых функций методом Квайна– Мак-Класки.

14. Минимизация булевых функций матричным методом Карно.

15. Алгебра Жегалкина и линейные функции. Отрицание и дизъюнкция в алгебре Жегалкина. Теорема Жегалкина. Представление булевой функции в виде полинома Жегалкина.

16. Логические функции переменных, сохраняющие константу нуль, сохраняющие константу единица, самодвойственные, монотонные и линейные функции. Теорема о монотонной функции. Замкнутые системы булевых функций. Классы Поста. Теорема о замкнутости классов Поста.

17. Полные системы булевых функций. Базисы. Основная теорема Поста-Яблонского о функциональной полноте системы булевых функций

18. Представление булевых функций в базисах Шеффера и Вебба.

19. Булева производная булевой функции и ее вес. Смешанная производная от булевой функции, производная го порядка от булевой функции по совокупности переменных.

20. Структурные матрицы. Булевы определители и их свойства.

21. Виды графов. Вершины, ребра, дуги графа. Смежные вершины и ребра, инцидентные вершины и ребра. Орграф, неорграф, мультиграф, псевдограф, подграф. Порядок графа Полный, пустой, дополнительный граф. Степень вершины. Лемма о рукопожатиях. Способы задания графов.

22. Операции над графами: добавление вершины, добавление дуги, удаление дуги, удаление вершины, отождествление вершин, стягивание вершин. Объединение, пересечение, произведение графов. Кольцевая сумма графов.

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. Обнаружение ошибки в кодах Хемминга. Декодирование кодов, содержащих одну ошибку. Восстановление исходного кодового слова и слова сообщения.

5