ПРОГРАММА ЭКЗАМЕНА/ЗАЧЕТА
1. Множества и операции над ними. Мощность множества. Счетные и несчетные множества. Мощность континуума. Кардинальные числа. Сравнение мощностей. Теорема Кантора-Бернштейна. Шкала мощностей.
2. Функции и отношения, их свойства. Бинарные отношения. Отношение эквивалентности, фактор множество. Отношение частичного порядка. Решетки. Булевы решетки и булевы алгебры.
3. Функции алгебры логики. Суперпозиция функций. Функционально замкнутые классы. Булевы свойства логических операций. Эквивалентные преобразования формул. Дизъюнктивная и конъюнктивная нормальная формы. Разложение функции по компонентам. Совершенные нормальные формы. СДНФ и СКНФ. Двойственные функции. Теорема о суперпозиции двойственных функций. Принцип двойственности. Класс самодвойственных функций и его замкнутость относительно суперпозиции. Критерий самодвойственности. Лемма о несамодвойственной функции. Класс линейных функций и его замкнутость относительно суперпозиции. Многочлен Жегалкина. Лемма о нелинейной функции. Класс функций, сохраняющих константу. Класс монотонных функций и его замкнутость относительно суперпозиции. Лемма о немонотонной функции. Критерий монотонности по сокращенной ДНФ. Теорема Поста о функциональной полноте.
4. Графы, мультиграфы, псевдографы, орграфы. Изоморфизм графов. Способы задания графов. Обходы графов. Циклы Эйлера, Гамильтона, де Брейна. Деревья, их характеристика, каркасы (остовы). Циклы в графах. Линейное пространство подграфов данного графа. Подпространство четных подграфов. Фундаментальная система циклов. Циклический ранг графа. Двудольные графы м паросочетания. Системы различных представителей. Теорема Холла о совершенном паросочетании в двудольном графе. Планарные и плоские графы. Формула Эйлера для связного плоского графа. Графы 
и 
. Критерий планарности Понтрягина-Куратовского. Раскраска графов. Хроматическое число и хроматический класс. Двудольные и бихроматические графы. Верхняя и нижняя оценки для хроматического числа. Внутренне и внешне устойчивые множества вершин графа. Оптимальная раскраска вершин графа. Раскрашивание планарных графов. Теорема о пяти красках. Теорема о четырех красках. Потоки в транспортных сетях. Теорема Форда-Фалкерсона о максимальном потоке. Перечисление графов. Производящая функция для числа помеченных графов с p вершинами. Число помеченных графов с p вершинами и k ребрами. Теорема Кэли о числе помеченных деревьев с p вершинами. Матричная теорема Кирхгофа о деревьях. Графы и группы подстановок. Орбита группы подстановок. Лемма Бернсайда о числе орбит группы подстановок. Многочлен циклов (цикловый индекс). Теорема Пойа.
5. Рекуррентные уравнения. Порядок уравнения, частное и общее решение. Линейные рекуррентные уравнения (ЛРУ) однородные и неоднородные с переменными коэффициентами. Фундаментальная система решений. Общее решение однородного и неоднородного ЛРУ с помощью фундаментальной системы решений. Линейные рекуррентные уравнения однородные и неоднородные с постоянными коэффициентами, или стационарные ЛРУ (СЛРУ). Характеристический полином и характеристическое уравнение. Общее решение однородного и неоднородного СЛРУ. Частное решение неоднородного СЛРУ с правой частью – квазиполиномом.
6. Элементы комбинаторики. Размещения, перестановки, сочетания с повторами и без повторов. Правило суммы и правило произведения. Подсчет числа размещений, перестановок, сочетаний без повторов и с повторами. Число перестановок и размещений данной спецификации.
7. Производящие функции для комбинаторных конфигураций и их числа. Аппарат формальных степенных рядов. Производящие функции для сочетаний без повторений и с повторениями с ограничениями на число повторений. Сочетания с повторениями без ограничения на число повторений. Производящие функции для размещении с повторениями с ограничениями и без ограничений на число повторов.
8. Комбинаторно-логический аппарат. Формула включений и исключений.
9. Универсальные алгебры. Примеры универсальных алгебр. Операция суперпозиции. Алгебры, подалгебры, гомоморфизм и изоморфизм алгебр. Образы и прообразы алгебр при гомоморфизме. Конгруенции и фактор-алгебры. Теоремы о гомоморфизме. Каноническое отображение, ядерная эквивалентность и гомоморфизм.
10. Целые числа. Модульная арифметика. Сравнения. Индексы (логарифмы).
11. Полугруппы, примеры полугрупп. Подполугруппы, циклические полугруппы.
12. Группы, примеры групп, подгруппы, свойства групп. Циклическая группа и ее генератор. Смежные классы по подгруппе. Конечные группы и теорема Лагранжа. Нормальные подгруппы, фактор группы, теорема о гомоморфизме групп.
13. Кольца, примеры колец, делители нуля.
14. Поле, примеры полей. Характеристика поля. Конечные поля.