Раздел 1. Множества и отношения
Тема 1. Введение в дисциплину. Множества и способы их задания Понятие множества. Способы задания множеств. Характеристические функции. Конечные и счетные множества. Диаграммы Эйлера-Венна. Собственное и несобственное подмножества. Операции над множествами. Законы алгебры множеств. Мощность множества. Формула включений и исключений. Тема 2. Кортежи и прямое произведение множеств Кортежи и прямое произведение множеств. Операции над кортежами, комбинаторика. Проекция. Тема 3. Отношения, соответствия и отображения Отношения: отношение эквивалентности, отношение порядка. Бинарные отношения, матрица бинарного отношения. Способы задания бинарных отношений. Соответствия и отображения. Композиция бинарных отношений. График. Раздел 2. Элементы математической логики Тема 4. Высказывания Основные понятия. Определения. Основные логические операции. Таблицы истинности. Формулы алгебры высказываний. Эквивалентность формул. Элементы теории доказательств: принцип математической индукции, принцип двойственности, система натурального вывода, прямоеобратное рассуждение. Принцип математической индукции. Тема 5. Предикаты и кванторы Предикаты. Кванторы. Исчисление предикатов. Диаграммы Эйлера. Тема 6. Булевы функции Двоичная арифметика. Булевы функции. Реализация булевых функций формулами. СДНФ и СКНФ. Карта Карно.Полные системы булевых функций. Важнейшие замкнутые классы булевых функций. Теорема Поста о полноте. Двойственность булевых функций. Тема 7. Минимизация булевых функций Задача минимизации булевых функций. Постановка задачи минимизации в классе ДНФ. Построение сокращенной ДНФ: геометрический метод, метод Квайна-Мак-Класки, метод Блейка. Поиск минимальных ДНФ. Тема 8. Элементы теории алгоритмов Понятие алгоритма. Вычислимые функции. Примитивно-рекурсивные функции.Частично-рекурсивные функции. Машина Тьюринга.Понятие сложности алгоритма. Раздел 3. Элементы комбинаторики Тема 9. Комбинаторика Правила суммы и произведения. Принцип включения и исключения. Размещения и перестановки. Сочетания. Бином Ньютона. Биномиальные коэффициенты для отрицательных и дробных показателей. Свойства биномиальных коэффициентов. Тема 10. Рекурсия Рекуррентные соотношения. Возвратные последовательности. Числа Фибоначчи. Приемы вычисления сумм. Числа Каталана. Случайное блуждание. Раздел 4. Элементы теории графов
|
