Экзамен

Билет 1

Задание 1 (Булевы функции) 1.1. Булевы функции: определение. Количество булевых функций от n переменных. Способы задания булевых функций. 1.2. Привести функцию $f(x,y,z)=(x\to y)\oplus (z\wedge \bar{x})$ к СДНФ и СКНФ.

Задание 2 (Теория графов) 2.1. Шесть способов представления графа. Дать определения всем используемым понятиям и привести примеры. 2.2. Для графа, изображенного ниже, построить матрицу смежности и матрицу инцидентности. Определить степени всех вершин.

Билет 2

Задание 1 (Булевы функции) 1.1. Таблица истинности (ТИ) булевой функции. Основные функции: дизъюнкция, конъюнкция, импликация, эквивалентность, сложение по модулю два, стрелка Пирса, штрих Шеффера. 1.2. Построить полином Жегалкина для функции $f(x,y,z)$, заданной вектором значений $10110001$.

Задание 2 (Теория графов) 2.1. Связные и несвязные графы. Компоненты связности и бикомпоненты. Понятие слабой связности. Алгоритм поиска компонент. 2.2. Найти компоненты сильной связности в орграфе.

Билет 3

Задание 1 (Булевы функции) 1.1. Булев куб. Развертка булева куба. Поиск функции по развертке. 1.2. Минимизировать булеву функцию, заданную картой Карно, получить МДНФ: $f(a,b,c,d)=\Sigma (0,2,4,5,6,8,10,15)$.

Задание 2 (Теория графов) 2.1. Метод нахождения количества путей в орграфах по матрице смежности. Алгоритм Флойда-Уоршелла. 2.2. Найти кратчайший путь от вершины $0$ до вершины $5$ (Алгоритм Дейкстры).

Билет 4

Задание 1 (Булевы функции) 1.1. Сравнимые и несравнимые наборы. Доминирующий набор. Существенные и фиктивные переменные. 1.2. Проверить полноту системы функций $F=\{x\to y,xy,x\oplus z\}$. Построить критериальную таблицу (классы Поста).

Задание 2 (Теория графов) 2.1. Деревья. Минимальные и максимальные покрывающие деревья. Алгоритмы Краскала и Прима. 2.2. Найти минимальное остовное дерево (MST) графа алгоритмом Краскала. Указать вес MST.

Билет 5

Задание 1 (Булевы функции) 1.1. Основные равносильности: коммутативность, ассоциативность, дистрибутивность, законы де Моргана, формулы с константами. 1.2. Найти все существенные и фиктивные переменные функции $f(x,y,z)=xy\vee \bar{x}z\vee yz$.

Задание 2 (Теория графов) 2.1. Эйлеровы пути и циклы. Критерий существования. Алгоритм Флёри. Задача китайского почтальона. 2.2. Определить, существует ли в графе эйлеров цикл или эйлеров путь. Если да, выписать последовательность вершин.

Билет 6

Задание 1 (Булевы функции) 1.1. ДНФ, КНФ, СДНФ, СКНФ. Способы приведения функции к СДНФ, СКНФ. 1.2. Построить полином Жегалкина методом треугольника Паскаля для функции, заданной вектором $f=(10011101)$.

Задание 2 (Теория графов) 2.1. Гамильтоновы пути и циклы. Критерии Дирака и Оре. 2.2. Проверить граф на планарность. Если граф планарный — изобразить его плоскую укладку, если нет — выделить подграф, гомеоморфный $K_5$ или $K_{3,3}$.

Билет 7

Задание 1 (Булевы функции) 1.1. Карты Карно. Склейка на карте Карно. 1.2. Методом Квайна-Маккласки найти сокращенную ДНФ функции $f(w,x,y,z)=\Sigma (1,3,4,5,9,11,12,13,14,15)$.

Задание 2 (Теория графов) 2.1. Изоморфизм и гомеоморфизм графов. Полные и двудольные графы. Плоские и планарные графы. 2.2. Определить, являются ли два графа изоморфными. Обосновать (степени вершин, количество ребер и т.д.).

Билет 8

Задание 1 (Булевы функции) 1.1. Ранг конъюнкции. Длина ДНФ. Минимальные, кратчайшие, сокращенные и тупиковые ДНФ. 1.2. Выяснить, к каким классам Поста ($T_0,T_1,S,M,L$) относится функция $f(x,y,z)=xy\oplus z$.

Задание 2 (Теория графов) 2.1. Формула Эйлера для планарного графа. Критерий Куратовского. 2.2. Найти минимальное покрывающее дерево алгоритмом Прима, начав с вершины A.

Билет 9

Задание 1 (Булевы функции) 1.1. Ядро булевой функции. Что такое функция Патрика. 1.2. Получить тупиковые ДНФ с помощью импликантной матрицы для функции, заданной набором обязательных единиц $f^{-1}(1)=\{0,2,4\}$ и don’t care $\{5,6\}$.

Задание 2 (Теория графов) 2.1. Определение связности, компонент связности. Алгоритм поиска компонент связности по матрице достижимости. 2.2. Построить матрицу смежности графа. Возвести её в квадрат и найти количество путей длины 2 между вершинами 1 и 3.

digraph G {
    rankdir=LR;
    node [shape=circle];
    1 -> 2;
    1 -> 4;
    2 -> 3;
    3 -> 1;
    4 -> 3;
    2 -> 4;
}

Билет 10

Задание 1 (Булевы функции) 1.1. Алгоритм нахождения МДНФ и КрДНФ. 1.2. Разложить функцию $f(x,y,z)=x\oplus y\vee z$ по переменной $x$, затем привести результат к СДНФ.

Задание 2 (Теория графов) 2.1. Способы представления графа: список смежности, список ребер, матрицы. Сравнение по памяти. 2.2. Определить хроматическое число графа (минимальное кол-во цветов).

graph G {
    layout=circo;
    node [shape=circle];
    a -- b; b -- c; c -- d; d -- e; e -- a;
    a -- c; b -- d; c -- e; d -- a; e -- b;
}

Билет 11

Задание 1 (Булевы функции) 1.1. Импликантная матрица. Порядок построения импликантной матрицы. 1.2. Представить функцию $f(x,y)=x\mid y$ (штрих Шеффера) в виде полинома Жегалкина.

Задание 2 (Теория графов) 2.1. Деревья: определения корня, листа, уровня, высоты. Свойства деревьев. 2.2. Найти эксцентриситет каждой вершины, радиус и диаметр графа (вес ребра = 1).

graph G {
    layout=neato;
    node [shape=circle];
    1 -- 2; 2 -- 3; 3 -- 4;
    2 -- 5; 5 -- 6;
    3 -- 7;
}

Билет 12

Задание 1 (Булевы функции) 1.1. Нахождение ядра булевой функции с помощью импликантной матрицы. 1.2. Найти МДНФ функции $f(a,b,c,d)$ графическим методом (Карты Карно). Единицы на наборах: 0, 1, 4, 5, 12, 13.

Задание 2 (Теория графов) 2.1. Эйлеровы графы: алгоритм Флёри (подробное описание шагов). 2.2. Проверить граф на наличие гамильтонова цикла (условия Дирака/Оре).

graph G {
    layout=circo;
    node [shape=circle];
    1 -- 2; 2 -- 3; 3 -- 4; 4 -- 5; 5 -- 1;
    1 -- 3; 1 -- 4; 2 -- 4; 2 -- 5; 3 -- 5;
}

Билет 13

Задание 1 (Булевы функции) 1.1. Полиномиальная нормальная форма (ПНФ) и СПНФ. Положительно и отрицательно поляризованный полином. 1.2. Определить, является ли система функций $F=\{1,\bar{x},x\vee y\}$ полной.

Задание 2 (Теория графов) 2.1. Плоские графы. Грани. Формула Эйлера $V-E+F=2$. 2.2. Найти кратчайшие пути от вершины S до всех остальных (Алгоритм Дейкстры).

digraph G {
    rankdir=LR;
    node [shape=circle];
    S -> A [label="10"];
    S -> B [label="5"];
    B -> A [label="3"];
    A -> C [label="1"];
    B -> C [label="9"];
    B -> D [label="2"];
    D -> C [label="4"];
    C -> E [label="2"];
    D -> E [label="7"];
}

Билет 14

Задание 1 (Булевы функции) 1.1. Полином Жегалкина. Способы построения. 1.2. Удалить фиктивные переменные из функции $f(x_1,x_2,x_3)=(x_1\to x_2)\wedge (x_1\vee \overline{x_1})\vee x_3\overline{x_3}$.

Задание 2 (Теория графов) 2.1. Матрица достижимости. Свойства ($A^k$, транзитивное замыкание). 2.2. Является ли данный граф двудольным? Если да, разделить вершины на две доли.

graph G {
    layout=neato;
    node [shape=circle];
    1 -- 4; 1 -- 5;
    2 -- 4; 2 -- 6;
    3 -- 5; 3 -- 6;
}

Билет 15

Задание 1 (Булевы функции) 1.1. Свойства булевых функций (Классы Поста): $T_0,T_1,S,M,L$. 1.2. Записать СДНФ и СКНФ для функции мажоритарности $M(x,y,z)$ (истина, если 2 или 3 аргумента истинны).

Задание 2 (Теория графов) 2.1. Двудольные графы. Критерий двудольности. 2.2. Определить точки сочленения и мосты в графе.

graph G {
    node [shape=circle];
    1 -- 2; 2 -- 3; 3 -- 1;
    3 -- 4;
    4 -- 5; 5 -- 6; 6 -- 4;
}

Билет 16

Задание 1 (Булевы функции) 1.1. Полное множество булевых функций. Критерий Поста. 1.2. Преобразовать выражение $(x\downarrow y)\to z$ в формулу, содержащую только $\neg$ и $\wedge$.

Задание 2 (Теория графов) 2.1. Покрывающие деревья. Свойства остовных деревьев. 2.2. Для заданного орграфа построить матрицу достижимости.

digraph G {
    rankdir=LR;
    node [shape=circle];
    1 -> 2;
    2 -> 3;
    3 -> 1;
    2 -> 4;
    4 -> 5;
}

Билет 17

Задание 1 (Булевы функции) 1.1. Булевы функции: классификация (симметричные и т.д.). 1.2. Доказать самодвойственность функции $f(x,y,z)=xy\vee yz\vee zx$ или опровергнуть.

Задание 2 (Теория графов) 2.1. Орграфы: степени захода и исхода. Источники и стоки. 2.2. Проверить граф на изоморфизм графу Петерсена (или просто определить кол-во граней по формуле Эйлера, считая его планарным, и прийти к противоречию).

graph G {
    layout=circo;
    node [shape=circle];
    1 -- 2; 2 -- 3; 3 -- 4; 4 -- 5; 5 -- 1;
    1 -- 6; 2 -- 7; 3 -- 8; 4 -- 9; 5 -- 10;
    6 -- 8; 8 -- 10; 10 -- 7; 7 -- 9; 9 -- 6;
}

Билет 18

Задание 1 (Булевы функции) 1.1. Основные функции алгебры логики и их свойства. 1.2. Найти все простые импликанты функции методом Блейка. $f=xy\vee x\bar{z}\vee yz$.

Задание 2 (Теория графов) 2.1. Планарность $K_5$ и $K_{3,3}$. Доказательство непланарности. 2.2. Найти максимальное паросочетание в графе.

graph G {
    layout=neato;
    node [shape=circle];
    a -- b; b -- c; c -- d;
    e -- f; f -- g; g -- h;
    a -- e; b -- f; c -- g; d -- h;
}

Билет 19

Задание 1 (Булевы функции) 1.1. Кратчайшие и минимальные ДНФ: отличия. Функция Патрика. 1.2. Проверить линейность функции $f(x,y)=x\leftrightarrow y$ путем построения полинома Жегалкина.

Задание 2 (Теория графов) 2.1. Маршруты, цепи, циклы, пути: точные определения и различия. 2.2. Восстановить граф по матрице инцидентности (строки - вершины, столбцы - ребра) и нарисовать его.

$$I=\left(\begin{array}{cccc}1& 1& 0& 0\\ 1& 0& 1& 0\\ 0& 1& 1& 1\\ 0& 0& 0& 1\end{array}\right)$$

(Использовать viz-js.com для самопроверки, нарисовав граф по полученным данным).