СПЕЦИАЛЬНЫЕ ГЛАВЫ МАТЕМАТИКИ: ВОПРОСЫ К ЗАЧЕТУ 1) Возможности програмы GAP для работы с группами и подстановками. 2) Возможности програмы GAP для работы с кольцами, полями, множествами, многочленами и бинарными отношениями. 3) Булевы функции. Теорема о числе всех булевых функций от $n$ переменных. ``Элементарные'' булевы функции. 4) Формулы. Свойства конъюнкции, дизъюнкции и отрицания. 5) Теорема о разложении булевой функции по переменным. СДНФ и СКНФ. 6) ДНФ. Проблема минимизации ДНФ. Полиномы Жегалкина. 7) Полнота и замкнутость функциональных систем. Некоторые полные системы булевых функций. 8) Графы и их основные характеристики. Матрицы смежности и инцидентности. 9) Маршруты. Эйлеровы и гамильтоновы циклы. Деревья. Оценка числа деревьев. 10) Изоморфизм графов. Реализация графов на плоскости и в пространстве. 11) Поиск кратчайшего пути на графе. 12) Машина Тьюринга. Тезис Тьюринга. Вычислительная сила языков программирования. 13) Вычислительная сложность алгоритмов. Полиномиальные и экспоненциальные алгоритмы. Труднорешаемые задачи. Задача коммивояжера. 14) Недетерминированная машина Тьюринга. Классы P, E и NP. Типовые задачи класса NP. Теорема Кука. NP-сложные задачи. NP-полнота. 15) Возможности программы Reduce.