22. Ориентированные деревья. Упорядоченные деревья. Бинарные деревья.

Ориентированное (направленное) дерево — ацикличный орграф (ориентированный граф, не содержащий циклов), в котором только одна вершина имеет нулевую степень захода (в неё не ведут дуги), а все остальные вершины имеют степень захода 1 (в них ведёт ровно по одной дуге). Вершина с нулевой степенью захода называется корнем дерева, вершины с нулевой степенью исхода (из которых не исходит ни одна дуга) называются концевыми вершинами или листьями.

Упорядоченное дерево  — ордерево, в котором множество сыновей каждой вершины упорядочено; при изображении упорядоченного дерева предполагается, что указанные множества упорядочены слева направо.

Двои́чное де́рево — дерево, в котором каждый узел имеет не более двух потомков.

Как правило, первый называется родительским узлом, а дети называются левым и правым наследниками.

23. Определение плоского графа. Формула Эйлера.

Плоский граф — геометрический граф, в котором никакие два ребра не имеют общих точек, кроме инцидентной им обоим вершины (не пересекаются). Является уложенным графом на плоскости.

Укладка: граф укладывается на некоторой поверхности, если его можно нарисовать на этой поверхности так, чтобы рёбра графа при этом не пересекались.

24. Раскраска графов.

25. Эйлеров граф и его свойства.

Эйлеров граф — граф, содержащий эйлеров цикл.

Эйлеров цикл — это эйлеров путь, являющийся циклом.

Эйлеров путь (эйлерова цепь) в графе — это путь, проходящий по всем рёбрам графа и притом только по одному разу.

26. Гамильтонов граф и его свойства.

Гамильтонов граф — граф, содержащий гамильтонову цепь или гамильтонов цикл.

Гамильтонов путь (или гамильтонова цепь) —путь (цепь), содержащий каждую вершину графа ровно один раз. Гамильтонов путь, начальная и конечная вершины которого совпадают, называется гамильтоновым циклом.

27. Основные логические (булевы) функции.

→ - импликация

↓ - стрелка Пирса

| - штрих Шеффера

≡ , ↔ - эквивалентность

28. Законы булевой алгебры.

29. Нормальные формы. Переход от одной формы к другой.

Простой конъюнкцией (дизъюнкцией) называется кон. (диз.) одной или нескольких переменных, при этом каждая переменная встречается не более одного раза( лидо сама, либо её отрицание).

Дизъюнктивной (конъюнктивной) нормальной формой ДНФ (КНФ) называется дизъюнкция (конъюнкция) простых конъюнкций (дизъюнкций).

Совершенной ДНФ (КНФ) называется такая ДНФ (КНФ), у которой в каждую конъюнкцию (дизъюнкцию) входят все переменные данного списка.

30. Представление логических функций в виде СДНФ (СКНФ).

31. Минимизация СДНФ (СКНФ).

32. Полные системы. Примеры полных систем (с доказательством полноты).

33. Теорема Жегалкина о представимости алгебры логики полиномом.

Любую функцию алгебры логики f(x₁, ... ,x_n) можно единственным образом выразить полиномом Жегалкина над x₁, ... ,x_n.

34. Понятие замкнутого класса. Замкнутость классов T₀, T₁ и L.

35. Двойственность. Класс самодвойственных функций, его замкнутость.

36. Класс монотонных функций, его замкнутость.

37. Лемма о несамодвойственной функции.

38. Лемма о немонотонной функции.

39. Лемма о нелинейной функции.

40. Теорема о полноте системы функций алгебры логики.

41. Теорема о максимальном числе функций в базисе алгебры логики.

42. Понятие схемы из функциональных элементов.

43. Проблема синтеза схем из функциональных элементов.

44. Элементарные методы синтеза.

45. Определение конечного автомата, способы задания автоматов.

46. Эквивалентность автоматов Мили и Мура.

47. Частичные автоматы. Постановка задачи минимизации автоматов.

48. Нахождение эквивалентных состояний.

49. Построение минимального автомата (случай всюду определенных условий).

50. Совместимые состояния частичных автоматов. Нахождение максимальной группировки.

51. Построение минимального частичного автомата.