Тема 2: Переключательные функции

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

Тема 1: Теория множеств.

1. Множество. Элемент множества. Подмножество: собственное и несобственное. Разбиение и покрытие множества. Булеан множества. Подмножества и булеан в программном коде. Способы задания множеств (перечисление, характеристический предикат, порождающая процедура). Операции над множествами: дополнение, пересечение, объединение, разность, кольцевая сумма – определения, диаграммы Эйлера, характеристические предикаты, программный код.

2. Свойства операций над множествами (идемпотентность, коммутативность, ассоциативность, дистрибутивность, поглощение, инволютивность, законы де Моргана, законы пустого множества и универсума) и их доказательство методами: взаимного включения, построения характеристических предикатов, на диаграммах Эйлера.

3. Мощность конечного множества. Теорема о мощности булеана конечного множества.

4. Натуральный ряд чисел. Счетные множества. Аксиома математической индукции. Теорема о разности счетного и конечного множеств. Теорема о включении в любое бесконечное множество счетного.

5. Теорема о несчетности отрезка [0,1]. Континуальные множества. Установление континуальности множества всех действительных чисел.

6. Декартово произведение множеств. Декартова степень множества. Теорема о мощности прямого произведения конечных множеств. N-местное отношение. Соответствие. Область прибытия соответствия, область отправления соответствия, график соответствия. Способы задания соответствий (графический, матричный). Тождественное, универсальное и пустое соответствия и их матрицы.

7. Операции над соответствиями (объединение, дополнение, пересечение, обращение, композиция) – определения, матричное представление, свойства.

8. Ограничение соответствия. Сужение соответствия. Сечение соответствия. Фактор-множество по соответствию. Проекция отношения.

9. Свойства соответствий (рефлексивность, антирефлексивность, симметричность, антисимметричность, несимметричность, транзитивность) – определения, методы проверки (по определению и по матрице). Плотность.

10. Классы соответствий: эквивалентность, толерантность, порядок (строгий, нестрогий), предпорядок (строгий, нестрогий). Классы эквивалентности их свойства, подобная матрица для матрицы отношения эквивалентности.

11. Задача минимизации объема оперативной памяти. Схема потока данных.

12. Отношение порядка. Строгий и нестрогий порядок. Полный и частичный порядок. Наибольший и наименьший элементы. Максимальный и минимальный элементы. Нижняя граница, инфимум, верхняя граница, супремум. Диаграмма Хассэ

13. Реляционные базы данных. Атрибут, тип записи, первая нормальная форма. Операции: селекции, проекции, соединения по атрибуту.

14. Свойство функциональности, образ, прообраз, операции. Типы функций. Обратные функции. Теорема о связи типов функций с наличием обратных функций. Теорема о мощностях областей отправления и прибытия функций разных типов.

15. Функция естественной проекции в реляционных базах данных. Функциональная зависимость между атрибутами. Ключ.

Тема 2: Переключательные функции

16. Унарные и бинарные функции алгебры логики. Приоритет операций в формулах. Существенная и фиктивная переменные функции.

17. Основные эквивалентности булевых функций (идемпотентность, коммутативность, ассоциативность, дистрибутивность, поглощение, инволютивность, законы де Моргана, законы нуля и единицы). Равносильные формулы, выполнимая формула, опровержимая формула, тавтология, противоречие.

18. Теоремы о замене переменных в формулах.

19. Двойственность булевых функций, свойства двойственности, принцип двойственности.

20. ДНФ. КНФ. Теорема о построении ДНФ и КНФ.

21. СДНФ. СКНФ. Алгоритм приведения формулы в СДНФ и СКНФ путем аналитических преобразований.

22. Теоремы Шеннона (о первом и втором разложениях).

23. Теорема о количестве ДНФ для одной функции. Булев куб, грани куба. Представление функции на кубе, единичный интервал и соответствующие ему импликанты. Максимальный единичный интервал. Простая импликанта.

24. Сокращенная ДНФ. Тупиковая ДНФ. Метод Квайна построения тупиковых ДНФ. Минимальные дизъюнктивные формы.

25. Сложность формулы. Карты Карно и их использование для минимизации ДНФ. Минимизация частичных булевых функций.

26. Полином Жегалкина и алгоритм его построения. Линейная булева функция. Метод неопределенных коэффициентов для проверки линейности.

27. Классы Поста. Теорема о свойствах классов. Теорема о замкнутости классов.

28. Полная система булевых функций. Теорема Поста. Теорема о четырех функциях.

29. Приложение булевых функций к теории релейно-контактных схем. Двоичный сумматор.

30. Логические интегральные схемы. Двоичный сумматор.

31. Первая производная булевой функции и ее переключательный смысл. Смешанная производная и производная высшего порядка. Условия переключения определяемые этими производными.

32. Интеграл от булевой функции. Число первообразных и метод их отыскания. Многомерный интеграл.

Тема 3: Графы

33. Граф. Вершина графа, ребро графа, геометрическая реализация графа. Теорема о реализации графа в трехмерном пространстве.

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

35. Способы задания графов: структура смежности, матрица смежности, матрица инцидентности их особенности для орграфов и мультиграфов.

36. Степень вершины графа, полустепени захода и исхода. Лемма о рукопожатиях. Вектор степеней, регулярный граф. Расстояние между вершинами графа, матрица расстояний. Эксцентриситет вершины, диаметр и радиус графа. Центр графа, периферийные вершины графа.

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

38. Дерево. Лес. Остов графа. Ветви, хорды. Цикломатическое число графа. Алгоритмы поиска в глубину и в ширину. Матричная формула Кирхгофа.

39. Реберно-взвешенные графы. Матрица весов. Вес маршрута. Алгоритмы поиска остова минимального веса: Краскала, Прима.

40. Планарный граф. Грани. Эйлерова характеристика. Теорема о эйлеровой характеристике. Следствия о непланарности графов K₅ и K_3,3.

41. Теорема Куратовского-Понтрягина. Число планарности. Толщина графа. Алгоритм плоской укладки графа.

42. Эйлеров граф. Критерий эйлеровости.

43. Алгоритм Флёри – построения эйлерова цикла. Эйлерова цепь. Полуйлеров граф. Критерий полуэйлеровости. Эйлеровость и полуэйлеровость в орграфах.

42. Гамильтонов граф. Полугамильтонов граф. Достаточные условия гамильтоновости. Задача коммивояжера и алгоритм ее решения.

43. Фундаментальное множество циклов. Матрица фундаментальных циклов. Разрез. Простой разрез. Коцикл. Коцикломатическое число графа. Кодерево. Фундаментальное множество разрезов и алгоритм его построения. Матрица фундаментальных коциклов.

44. k-раскраска вершин графа. Правильная раскраска. Хроматическое число. Алгоритм последовательного раскрашивания. Задача составления оптимального расписания. Теорема о хроматическом числе. Гипотеза четырех красок. Теорема о 5-раскрашивании любого планарного графа. Неравенство для хроматического числа (теорема). Задача о раскрашивании ребер графа.

45. Вершинная связность. Реберная связность. Точка сочленения. Мост. Блок. Метод нахождения блоков графа.

46. Связный орграф. Сильно связный орграф. Сильная связная компонента орграфа. Матрица достижимости. Матрица контрдостижимости. Матрица сильных компонент.

47. Исследование маршрутов в графе по степени матрицы смежности.

48. Число вершинного покрытия. Число реберного покрытия. Вершинное число независимости. Реберное число независимости. Совершенное паросочетание. Клика. Максимальная и наибольшая клика. Алгоритм нахождения наибольшего паросочетания в двудольном графе.

49. Задача о назначениях. Алгоритм поиска оптимального паросочетания.

50. Алгоритм Форда-Беллмана нахождения кратчайшего маршрута в графе.

51. Алгоритм Форда-Фалкерсона нахождения максимального потока в сети.