Аннотация программы учебной дисциплины«Дискретная математика и математическая логика и их приложения в информатике и компьютерных науках» Направление: 010100.62 «Математика» Профиль: Вычислительная математика и информатика Общее количество часов – 252 3, 8 семестр 2 экз. 1. Цели и задачи дисциплины. Целями освоения дисциплины "Дискретная математика" являются: формирование математической культуры студента, фундаментальная подготовка по основным разделам дискретной математики, овладение современным математическим аппаратом для дальнейшего использования при решении теоретических и прикладных задач. Целями освоения дисциплины "Математическая логика" являются: формирование логической и математической культуры студента, фундаментальная подготовка в области математической логики и теории алгоритмов, овладение современным математическим аппаратом для дальнейшего использования в приложениях. 2. Требования к уровню освоения содержания дисциплины.Процесс изучения дисциплины направлен на формирование следующих компетенций: способностью владеть культурой мышления, умение аргументировано и ясно строить устную и письменную речь (ОК-1), способность понимать и анализировать мировоззренческие, социально и личностно значимые философские проблемы (ОК - 3), способность работать с информацией в глобальных компьютерных сетях (ОК – 12), способность работы с информацией из различных источников, включая сетевые ресурсы сети Интернет, для решения профессиональных и социальных задач (ОК - 15), способность к интеллектуальному, культурному, нравственному и профессиональному саморазвитию, стремление к повышению своей квалификации и мастерства (ОК - 16); способность демонстрации общенаучных базовых знаний математики, понимание основных фактов, концепций, принципов, теорий (ПК - 1), способность приобретать новые научные и профессиональные знания, используя современные образовательные и информационные технологии (ПК - 2), способность понимать и применять в исследовательской и прикладной деятельности современный математический аппарат (ПК - 3), способность решать в составе коллектива решать задачи профессиональной деятельности (ПК - 4), способность критически переосмысливать накопленный опыт (ПК - 5), способность составлять и контролировать план выполняемой работы, планировать необходимые для выполнения работы ресурсы, оценивать результаты собственной работы (ПК - 12).В результате освоения данной дисциплины обучающийся должен: Знать: – основные понятия дискретной математики и математической логики, определения и свойства математических объектов, используемых в этих областях, формулировки утверждений, методы их доказательства, возможные сферы их приложений, основы построения математических моделей. Уметь: – решать задачи теоретического и прикладного характера из различных разделов дискретной математики и математической логики; – доказывать утверждения; строить модели объектов и понятий. Владеть: – математическим аппаратом дискретной математики, математической логики;– методами доказательства утверждений в этих областях; навыками алгоритмизации основных задач.3. Содержание дисциплины. Основные разделы.Выборки. Перестановки, сочетания, перестановки с повторениями, сочетания с повторениями. Биномиальные коэффициенты. Свойства биномиальных коэффициентов, биномиальная теорема. Полиномиальные коэффициенты, полиномиальная теорема. Разбиения Формулы обращения. Локально конечные частично упорядоченные множества. Метод включений и исключений. Оценки для числа элементов, не обладающих ни одним из n свойств. Формула для числа элементов, обладающих в точности m свойствами, 0 ≤ m ≤ n. Арифметическая функция Мёбиуса. Формула обращения Мёбиуса. Перечисление p-ичных циклических последовательностей длины n. Функция Эйлера φ(n); вычисление функции φ(n). Формула Гаусса (n = Σ φ(d), суммирование по всем d | n). Производящие функции. Примеры применения метода производящих функций для решения комбинаторных задач. Линейные рекуррентные соотношения с постоянными коэффициентами. Теорема о решении линейных рекуррентных соотношений. Числа Фибоначчи. Симметрические функции, элементарные симметрические функции, степенные суммы. Тождества Ньютона (связывающие элементарные симметрические функции и степенные суммы). Задача о расстановке скобок. Числа Каталана. Графы. Основные понятия. Способы представления графов. Перечисление графов на нумерованных вершинах. Верхняя оценка для числа неизоморфных графов с q ребрами. Эйлеровы циклы. Теорема Эйлера. Теорема Эйлера для ориентированных графов. Деревья и их свойства. Потоки в сетях. Максимальный поток. Минимальный разрез. Лемма о существовании максимального потока. в двудольных графах. Теорема Холла о паросочетаниях в двудольном графе. Частично упорядоченные множества. Элементы теории Рамсея. Теорема Рамсея (двуцветная раскраска). Верхние и нижние оценки для чисел N(p, q, 2). Побуквенное (алфавитное) кодирование. Разделимые коды. Конечные автоматы. Основные понятия. Способы задания автоматов. Представимые языки. Теорема Клини. Замкнутость семейства регулярных языков относительно теоретико-множественных операций. Примеры нерегулярных языков. Предмет математической логики. Вопросы оснований математики. Аксиоматическое построение элементарной геометрии, роль аксиомы о параллельных. Парадоксы теории множеств, семантические парадоксы. Формальный аксиоматический метод Гильберта, программа Гильберта. Роль теорем Гёделя о неполноте. Логика высказываний. Высказывания и логические связки. Формулы логики высказываний, понятие подформулы. Истинностные таблицы для логических связок и формул. Теорема о функциональной полноте. Выполнимые формулы, тавтологии, тождественно ложные формулы. Алгоритм распознавания выполнимости. Равносильность формул логики высказываний, связь с тождественной истинностью; важнейшие равносильности. Дизъюнктивные и конъюнктивные нормальные формы. Приведение формул логики высказываний к совершенной дизъюнктивной (конъюнктивной) нормальной форме. Исчисление высказываний. Аксиомы и правила вывода исчисления высказываний. Понятие вывода и выводимой формулы; примеры. Корректность исчисления высказываний. Выводимость из гипотез. Теорема о дедукции для исчисления высказываний. Теорема о полноте исчисления высказываний. Логика предикатов. Предикаты. Переменные и их области изменения. Кванторы. Языки первого порядка: термы, формулы, подформулы. Примеры языков первого порядка. Свободные и связанные вхождения переменных. Замкнутые формулы. Подстановка терма вместо переменной. Модели (алгебраические системы, интерпретации) для данного языка первого порядка. Истинность замкнутой формулы в данной модели. Предикаты, выразимые в данной модели. Равносильность формул языка первого порядка, важнейшие равносильности. Переименование связанных переменных. Операции подстановки и замены подформулы на равносильную. Приведение формулы к предварённой нормальной форме. Модель для данного множества замкнутых формул. Семантическое следование в логике первого порядка. Теория первого порядка, её аксиомы и теоремы. Теория с равенством, нормальная модель. Понятие выполнимой теории. Теорема о существовании нормальной модели выполнимой теории с равенством. Примеры теорий: теория частичных порядков, теория групп, теория полей, формальная арифметика, элементарная геометрия. Теоремы Тарского о полноте и разрешимости элементарной геометрии (без доказательства). Основные понятия теории алгоритмов. Пошаговый характер выполнения алгоритма. Функция, вычисляемая данным алгоритмом; область определения вычислимой функции. Вычисление словарных и числовых функций на машинах Тьюринга. Тезис Чёрча-Тьюринга. Разрешимые множества. Нумерация пар натуральных чисел. Нумерация множества слов в данном алфавите. Свойства объединения, пересечения и дополнения разрешимых множеств. Эквивалентные определения перечислимого множества. Теорема Поста. Теорема о графике вычислимой функции. Кодирование машин Тьюринга. Существование универсальной машины Тьюринга. Составитель: доцент кафедры МАиМ Кван Н.В.