 |
|
Цикл дисциплин предметной подготовки
Математическая логика
Алгебра высказываний. Нормальные формы. Совершенные нормальные формы. Теорема существования и единственности совершенных нормальных форм. Логическое следствие. Прямая и обратная теоремы, противоположная и обратная теоремы; закон контрапозиции. Методы математических доказательств. Применение алгебры высказываний к описанию релейно-контактных схем. Исчисление высказываний. Формулы исчисления высказываний. Аксиомы исчисления высказывания и правила вывода. Теорема дедукции и ее применение. Исследования системы аксиом исчисления высказываний; их непротиворечивость и полнота. Логика предикатов. Формулы логики предикатов и их классификация. Приведенная форма для формул логики предикатов. Предваренная нормативная форма. Проблема разрешения в логике предикатов. Применение логики предикатов. Строение математических теорем. Методы доказательства теорем. Исчисление предикатов. Непротиворечивость исчисления предикатов. Теорема Геделя о полноте исчисления предикатов.
Дискретная математика
Рекуррентные соотношения. Способы решения рекуррентных соотношений. Суммы и рекуррентности. Целочисленные функции x, x, mod. Бином Ньютона. Биномиальные коэффициенты. Основные тождества с биномиальными коэффициентами. Полиномиальная формула. Введение в асимптотические методы. Асимптотические решения рекуррентных соотношений. Формула суммирования Эйлера. Основные комбинаторные конфигурации. Метод включения-исключения. Основные понятия теории графов. Связные графы. Изоморфизм графов. Эйлеровы и гамильтоновы графы. Деревья. Паросочетания, независимые множества и клики. Пленарные графы. Теорема Эйлера и ее следствия. Непланарность графов К5 и Кз,з. Раскраска вершин и ребер графа. Двудольные графы. Теорема Кенига. Раскрашиваемость вершин планарного графа пятью красками. Гипотеза четырех красок.
Элементы абстрактной и компьютерной алгебры
Понятие группы, кольца, поля, булевой алгебры. Алгебры, алгебраические системы. Теория делимости в кольце целых чисел. Кольца классов вычетов. Поле комплексных чисел. Подгруппы. Смежные классы по подгруппе, факторгруппы. Подкольца. Идеалы кольца, факторкольца. Кольцо многочленов от одной переменной, теория делимости. Многочлены от нескольких переменных. Расширения полей, алгебраические и конечные расширения. Конечные поля. Первоначальное представление о теории кодирования. Представление символьных данных в компьютере. Алгоритмы символьных преобразований (числа, многочлены, выражения, дифференцирование, интегрирование).
Теория алгоритмов
Понятие вычислимой функции. Разрешимые и перечислимые множества. График вычислимой функции. Формальная теория вычислимости (частично рекурсивные функции, регистровые машины, машины Тьюринга). Тезис Чёрча. Конечные и бесконечные машины. Понятие программы. Эффективная нумерация программ. Теорема о параметризации. Существование универсальной программы. Компьютер фон Неймана. Диагональный метод. Пример невычислимой функции. Проблема останова. Примеры неразрешимых и неперечислимых множеств. Алгоритмическая сводимость проблем. Примеры алгоритмически неразрешимых проблем в математике и информатике. Эффективные операции над вычислимыми функциями. Теорема о неподвижной точке. Общее понятие исчисления. Грамматики. Языки, иерархия языков по Хомскому. Языки и машины. Основные меры сложности вычисления. Основы теории NР-полноты. Применение теории NР-полноты для анализа сложности проблем. Приложения теории алгоритмов в информатике.