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