Geum.ru

Аннотация программы учебной дисциплины «Дискретная математика и математическая логика» Направление: 010100. 62 «Математика»

Вид материалаДокументы
Подобный материал:
Аннотация программы учебной дисциплины

«Дискретная математика и математическая логика»

Направление: 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). Побуквенное (алфавитное) кодирование. Разделимые коды. Конечные автоматы. Основные понятия. Способы задания автоматов. Представимые языки. Теорема Клини. Замкнутость семейства регулярных языков относительно теоретико-множественных операций. Примеры нерегулярных языков.

Предмет математической логики. Вопросы оснований математики. Аксиоматическое построение элементарной геометрии, роль аксиомы о параллельных. Парадоксы теории множеств, семантические парадоксы. Формальный аксиоматический метод Гильберта, программа Гильберта. Роль теорем Гёделя о неполноте.

Логика высказываний. Высказывания и логические связки. Формулы логики высказываний, понятие подформулы. Истинностные таблицы для логических связок и формул. Теорема о функциональной полноте. Выполнимые формулы, тавтологии, тождественно ложные формулы. Алгоритм распознавания выполнимости. Равносильность формул логики высказываний, связь с тождественной истинностью; важнейшие равносильности. Дизъюнктивные и конъюнктивные нормальные формы. Приведение формул логики высказываний к совершенной дизъюнктивной (конъюнктивной) нормальной форме. Исчисление высказываний. Аксиомы и правила вывода исчисления высказываний. Понятие вывода и выводимой формулы; примеры. Корректность исчисления высказываний. Выводимость из гипотез. Теорема о дедукции для исчисления высказываний. Теорема о полноте исчисления высказываний. Логика предикатов. Предикаты. Переменные и их области изменения. Кванторы. Языки первого порядка: термы, формулы, подформулы. Примеры языков первого порядка. Свободные и связанные вхождения переменных. Замкнутые формулы. Подстановка терма вместо переменной. Модели (алгебраические системы, интерпретации) для данного языка первого порядка. Истинность замкнутой формулы в данной модели. Предикаты, выразимые в данной модели. Равносильность формул языка первого порядка, важнейшие равносильности. Переименование связанных переменных. Операции подстановки и замены подформулы на равносильную. Приведение формулы к предварённой нормальной форме. Модель для данного множества замкнутых формул. Семантическое следование в логике первого порядка. Теория первого порядка, её аксиомы и теоремы. Теория с равенством, нормальная модель. Понятие выполнимой теории. Теорема о существовании нормальной модели выполнимой теории с равенством. Примеры теорий: теория частичных порядков, теория групп, теория полей, формальная арифметика, элементарная геометрия. Теоремы Тарского о полноте и разрешимости элементарной геометрии (без доказательства).

Основные понятия теории алгоритмов. Пошаговый характер выполнения алгоритма. Функция, вычисляемая данным алгоритмом; область определения вычислимой функции. Вычисление словарных и числовых функций на машинах Тьюринга. Тезис Чёрча-Тьюринга.

Разрешимые множества. Нумерация пар натуральных чисел. Нумерация множества слов в данном алфавите. Свойства объединения, пересечения и дополнения разрешимых множеств. Эквивалентные определения перечислимого множества. Теорема Поста. Теорема о графике вычислимой функции. Кодирование машин Тьюринга. Существование универсальной машины Тьюринга.


Составитель: доцент кафедры МАиМ Кван Н.В.