Geum.ru

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

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

«Дискретная математика и математическая логика и их приложения в информатике и компьютерных науках»

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

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

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

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

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


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