Вопросы к экзамену
Понятие мультиграфа. Ориентированные и неориентированные мультиграфы. Понятие графа. Понятие смежности в теории графов. Степень вершины. Теорема Эйлера о рукопожатиях.
Способы задания графов. Матрицы смежности и инцидентности.
Бинарные операции над графами. Части и подграфы графа. Унарные операции над графами.
Маршруты и их виды. Исследование маршрутов графа с помощью матрицы смежности.
Отношение достижимости на множестве вершин графа. Матрицы достижимости и контрдостижимости.
Связные графы и их свойства. Метрические характеристики связных графов.
Эйлеровы графы и их основные свойства. Критерий эйлеровости графа. Гамильтоновы графы.
Деревья и их простейшие свойства. Характеризационная теорема.
Отношение делимости во множестве целых чисел и его свойства. Теорема о делении с остатком целых чисел.
НОД целых чисел и его свойства. Алгоритм Евклида. Линейное представление НОД целых чисел.
Простые числа и их свойства. Взаимно простые числа.
НОК целых чисел и его свойства.
Каноническое представление натурального числа. Теорема о делителях натурального числа. Нахождение НОД и НОК натуральных чисел.
Бесконечность множества простых чисел. Теорема об интервалах. Решето Эратосфена.
Числовые функции. Число и сумма натуральных делителей натурального числа.
Целая часть действительного числа. Теорема о каноническом разложении числа
.Позиционные и непозиционные системы счисления. Целые систематические числа. Операции над числами в g-ичной системе счисления. Переход из одной системы счисления в другую.
Сравнение во множестве целых чисел. Критерий сравнимости. Свойства сравнений.
Понятие кодирования. Основные задачи кодирования.
Алфавитное кодирование. Разделимые, префиксные схемы кодирования.
Взаимно однозначное кодирование. Алгоритм распознавания однозначности декодирования.
Коды с минимальной избыточностью. Теорема редукции.
Алгоритм построения кода с минимальной избыточностью (алгоритм Хаффмена).
Алгоритм Фано построения префиксной схемы алфавитного кодирования.
Самокорректирующиеся коды. Алгоритм кодирования методом Хэмминга.
Правила суммы и произведения.
Комбинации без повторений. Формулы для их числа.
Комбинации с повторениями. Формулы для их числа.
Бином Ньютона. Свойства биномиальных коэффициентов.
Полиномиальная теорема.
Высказывание. Операции над высказываниями.
Формулы логики высказываний. Равносильные формулы логики высказываний. Виды формул логики высказываний.
Свойства операций над высказываниями.
Логическое следствие в логике высказываний.
Булевы функции от одного и двух аргументов. Свойства булевых функций.
Булевы функции от n переменных. Число булевых функций от n переменных.
Суперпозиция булевых функций. Представление булевых функций через конъюнкцию, дизъюнкцию и отрицание.
Совершенные дизъюнктивные и конъюнктивные нормальные формы. Способы их построения.
Полиномы Жегалкина. Способы их построения. Линейные функции.
Классы T0 и T1. Двойственные булевы функции. Монотонные функции.
Теорема о функциональной полноте.