Дискретная математика

Бакалавриат 2020/2021

Статус: Курс обязательный (Инфокоммуникационные технологии и системы связи)

Направление: 11.03.02. Инфокоммуникационные технологии и системы связи

Кто читает: Департамент прикладной математики

Где читается: Московский институт электроники и математики им. А.Н. Тихонова

Когда читается: 3-й курс, 1, 2 модуль

Формат изучения: без онлайн-курса

Преподаватели: Боголюбов Дмитрий Петрович, Славнов Сергей Андреевич

Язык: русский

Кредиты: 3

Контактные часы: 48

Полная версия программы учебной дисциплины

Аннотация

Настоящая дисциплина относится к базовой части профессионального цикла дисциплин образовательной программы "Инфокоммуникационные технологии и системы связи". Цели изучения дисциплины: знакомство с понятиями дискретной математики и теории графов; освоение основных приемов решения практических задач по темам дисциплины; развитие способности интерпретации формальных алгебраических структур, развитие четкого логического мышления. В результате освоения дисциплины студент должен: • Знать базовые понятия дисциплины • Понимать доказательства ключевых теорем курса • Иметь навыки использования математического аппарата дисциплины в дальнейшей учебной и профессиональной деятельности

Цель освоения дисциплины

Цель - знакомство с понятиями дискретной математики как основы значительной части теории информационных систем, освоение основных приемов решения практических задач по темам дисциплины и развитие навыков математического моделирования практических задач связанных с конечными множествами.

Планируемые результаты обучения

Знать основные понятия и законы теории множеств, уметь применять их при доказательстве равенств, содержащих операции над множествами
Знать основные понятия комбинаторики, уметь применять их при решении комбинаторных задач
Знать основные понятия и теоремы теории графов, уметь решать классические задачи на графах
Знать основы теории логики высказываний. Иметь навыки работы с формулами алгебры высказываний.Уметь формализовать рассуждение и проверить его правильность.
Знать основы теории логики предикатов 1-го порядка..Уметь формализовывать сложные суждения на языке логики предикатов. Уметь приводить формулу логики предикатов к нормальной форме.
Знать основы нечеткой теории множеств и нечеткой логики. Знать основы нечеткого логического вывода.

Содержание учебной дисциплины

Элементы теории множеств
Типы множеств, основные операции над множествами, законы и, способы доказательств в теории множеств, формула включений и исключений и ее применения.
Логика высказываний
Определение высказывания Операции над высказываниями. Алгебра высказываний Формулы логики высказываний. Равносильность формул Запись сложного высказывания в виде формулы логики высказываний Нормальные формы Тождественно-истинные и тождественно-ложные формулы. Проблема разрешимости Формализация рассуждений. Правильные рассуждения
Логика предикатов
Определение предиката. Кванторы. Формулы логики предикатов. Равносильность формул Приведенные и нормальные формулы Выражение суждения в виде формулы логики предикатов Интерпретация формулы логики предикатов в виде суждения. Выполнимость. Общезначимость
Нечеткая логика и теория множеств.
Нечеткие множества. Функции принадлежности. Алгебра нечетких множеств.Нечеткие высказывания Нечеткие предикаты. Нечеткий логический вывод.
Комбинаторные схемы
Определение чисел размещений, перестановок и сочетаний предметов без повторений и с повторениями, определение чисел упорядоченных и неупорядоченных разбиений конечных множеств, бином Ньютона и полиноминальная формула
Основы теории графов
Виды графов, связные графы и деревья, матрицы инцидентности, смежноси и весовые матрицы, построение остовных деревьев в связных графах, минимальное остовное дерево, определение остовных деревьев по матрице инцидентности, нахождение минимальных путей на ориентированных графах, мультиграфы и эйлеровы циклы
Конечные автоматы
Конечные автоматы. Определение. Диаграмма состояний. Детерминированные и недетерминированные КА. Операции над КА. Лемма о накачивании. Регулярные выражения и языки. Теорема Клини. Вопросы разрешимости автоматных языков.

Элементы контроля

Контрольная работа 2
Домашняя работа 2
Аудиторная работа
Контрольная работа 1
Домашняя работа 1
Аудиторная работа
Экзамен
письменный экзамен с прокторингом
самостоятельная работа 1
Самостоятельная работа 2

Промежуточная аттестация

Промежуточная аттестация (2 модуль)
0.15 * Контрольная работа 1 + 0.15 * Контрольная работа 2 + 0.15 * самостоятельная работа 1 + 0.15 * Самостоятельная работа 2 + 0.4 * Экзамен

Программа дисциплины