Алгебра логики

Булевы переменные, булевы функции. Основные булевы функции одного и двух аргументов. Существенные и фиктивные переменные. Булева алгебра, основные законы. Элементарная дизъюнкция, элементарная конъюнкция, дизъюнктивная и конъюнктивная нормальные формы. Нахождение нормальных форм с использованием законов булевой алгебры. Конституента единицы, конституента нуля. Совершенные дизъюнктивная и конъюнктивная нормальные формы. Построение совершенных форм по таблице истинности и с использованием законов булевой алгебры.

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

Булева алгебра в применении к переключательным схемам.

Графы

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

Маршрут, его длина. Цепь, простая цепь. Цикл, простой цикл. Связный граф, компоненты связности графа.

Эйлеровы циклы, эйлеровы графы. Теорема Эйлера. Алгоритм Флери нахождения эйлеровой цепи в связном графе.

Остов графа. Минимальный остов взвешенного графа, алгоритм Краскала. Кратчайший маршрут, алгоритм Флойда-Уоршалла нахождения матрицы кратчайших расстояний.