Бакалавриат
2024/2025
Дискретная математика
Статус:
Курс обязательный (Фундаментальная и компьютерная лингвистика)
Направление:
45.03.03. Фундаментальная и прикладная лингвистика
Кто читает:
Кафедра высшей математики
Где читается:
Факультет гуманитарных наук
Когда читается:
1-й курс, 2-4 модуль
Формат изучения:
без онлайн-курса
Охват аудитории:
для своего кампуса
Преподаватели:
Михайлович Анна Витальевна
Язык:
русский
Кредиты:
4
Программа дисциплины
Аннотация
В данном курсе студенты познакомятся с понятиями дискретной математики как основой важной части математического аппарата теории вероятностей и математической статистики, исследования операций, дискретной оптимизации, компьютерных наук и других дисциплин, получат опыт анализа дискретных структур, развитие строгого логического мышления.
Цель освоения дисциплины
- Целями освоения дисциплины «Дискретная математика» являются получение развёрнутого представления об основных разделах дискретной математики, развитие навыка строгих математических доказательств, изучение теоретических оснований и получение первичных практических навыков автоматической обработки текстов, общее развитие мышления, подготовка базы для последующих курсов математики.
Планируемые результаты обучения
- Знает основные определения и алгоритмы на графах.
- Умеет решать задачи в рамках которых необходимо использовать графы.
- Знает основные понятия, методы и результаты теории булевых функций.
- Знает определение булевой функции. Может назвать все булевые функции одной переменной и основные булевые функции двух переменных (конъюнкция, дизъюнкция, импликация, эквивалентность, штрих Шеффера, стрелка Пирса)
- Умеет строить таблицы истинности булевых функций.
- Владеть основными понятиями теории булевых функций.
- Использовать булевы функции для формализации и решения логических задач.
- Умеет решать задачи из раздела "Элементы теории множеств".
- Умеет оперировать понятиями "множество" и операциями над множествами. Умеет строить взаимооднозначное соответствие между множествами или доказывать его отсутстсвие.
- Умеет применять метод математической индукции для решения задач
- Умеет применять комбинаторные методы для решения стандартных задач, а также комбинировать стандартные методы.
- Умеет составлять рекуррентные соотношения для соответствующих задач. Умеет решать рекуррентные соотношения.
- Умеет переводить целые и дробные числа между системами счисления с разными основаниями.
- Умение выделять в сложных в высказываниях логические связки. Умение строить отрицания высказываний.
- Воспроизводит алгоритм построения кода Хэмминга
- Воспроизводит алгоритм построения кода Хаффмана
- Анализирует коды, отличает префиксные коды, разделимые коды.
- Умеет строить автоматы для регулярных языков, умеет доказывать нерегулярность языков.
Содержание учебной дисциплины
- Основы теории множеств.
- Метод математической индукции
- Комбинаторика
- Линейные рекуррентные последовательности.
- Системы счисления. Делимость.
- Функции алгебры логики.
- Предикаты.
- Графы.
- Кодирование.
- Регулярные языки и автоматы
Элементы контроля
- Работа на занятиях
- Работа на занятиях
- Текущее домашнее задание
- Текущее домашнее задание
- Письменное домашнее задание
- Письменное домашнее задание
- Контрольная работа
- Экзамен
- Экзамен
Промежуточная аттестация
- 2024/2025 3rd module0.27 * Контрольная работа + 0.08 * Письменное домашнее задание + 0.27 * Работа на занятиях + 0.11 * Текущее домашнее задание + 0.27 * Экзамен
- 2024/2025 4th module0.05 * Письменное домашнее задание + 0.25 * Работа на занятиях + 0.1 * Текущее домашнее задание + 0.6 * Экзамен
Список литературы
Рекомендуемая основная литература
- Верещагин, Н. К. Лекции по математической логике и теории алгоритмов : учебное пособие / Н. К. Верещагин, А. Шень. — 3-е изд., стер. — Москва : МЦНМО, [б. г.]. — Часть 1 : Начала теории множеств — 2008. — 128 с. — ISBN 978-5-94057-321-0. — Текст : электронный // Лань : электронно-библиотечная система. — URL: https://e.lanbook.com/book/9306 (дата обращения: 00.00.0000). — Режим доступа: для авториз. пользователей.
- Виленкин, Н. Я. Рассказы о множествах : учебник / Н. Я. Виленкин. — 4-е изд., стер. — Москва : МЦНМО, 2007. — 152 с. — ISBN 978-5-94057-036-3. — Текст : электронный // Лань : электронно-библиотечная система. — URL: https://e.lanbook.com/book/9309 (дата обращения: 00.00.0000). — Режим доступа: для авториз. пользователей.
- Гаврилов, Г. П. Задачи и упражнения по дискретной математике : учебное пособие / Г. П. Гаврилов, А. А. Сапоженко. — 3-е изд., перераб. — Москва : ФИЗМАТЛИТ, 2009. — 416 с. — ISBN 978-5-9221-0477-7. — Текст : электронный // Лань : электронно-библиотечная система. — URL: https://e.lanbook.com/book/2157 (дата обращения: 00.00.0000). — Режим доступа: для авториз. пользователей.
- Гашков, С. Б. Дискретная математика : учебник и практикум для среднего профессионального образования / С. Б. Гашков, А. Б. Фролов. — 2-е изд., испр. и доп. — Москва : Издательство Юрайт, 2019. — 483 с. — (Профессиональное образование). — ISBN 978-5-534-11558-1. — Текст : электронный // Образовательная платформа Юрайт [сайт]. — URL: https://urait.ru/bcode/445631 (дата обращения: 28.08.2023).
- Дискретная математика : курс лекций для студентов-механиков, Редькин, Н. П., 2006
- Задачи и упражнения по дискретной математике : учеб. пособие, Гаврилов, Г. П., 2005
- Конспект лекций О.Б. Лупанова по курсу "Введение в математическую логику" : учебное пособие для вузов, Лупанов, О. Б., 2023
- Лавров, И. А. Задачи по теории множеств, математической логике и теории алгоритмов : учебник / И. А. Лавров, Л. Л. Максимова. — 5-е изд., испр. — Москва : ФИЗМАТЛИТ, 2002. — 256 с. — ISBN 5-9221-0026-2. — Текст : электронный // Лань : электронно-библиотечная система. — URL: https://e.lanbook.com/book/2242 (дата обращения: 00.00.0000). — Режим доступа: для авториз. пользователей.
- Марченков, С. С. Основы теории булевых функций : учебное пособие / С. С. Марченков. — Москва : ФИЗМАТЛИТ, 2014. — 136 с. — ISBN 978-5-9221-1562-9. — Текст : электронный // Лань : электронно-библиотечная система. — URL: https://e.lanbook.com/book/59714 (дата обращения: 00.00.0000). — Режим доступа: для авториз. пользователей.
- Редькин, Н. П. Дискретная математика : учебник / Н. П. Редькин. — Москва : ФИЗМАТЛИТ, 2009. — 264 с. — ISBN 978-5-9221-1093-8. — Текст : электронный // Лань : электронно-библиотечная система. — URL: https://e.lanbook.com/book/2293 (дата обращения: 00.00.0000). — Режим доступа: для авториз. пользователей.
- Редькин, Н. П. Дискретная математика / Н.П. Редькин. - Москва : ФИЗМАТЛИТ, 2009. - 264 с. ISBN 978-5-9221-1093-8, 700 экз. - Текст : электронный. - URL: https://znanium.com/catalog/product/208908
- Сорочан, С. В. Функции алгебры логики. Канонические виды булевых формул : учебно-методическое пособие / С. В. Сорочан. — Нижний Новгород : ННГУ им. Н. И. Лобачевского, 2023. — 41 с. — Текст : электронный // Лань : электронно-библиотечная система. — URL: https://e.lanbook.com/book/344945 (дата обращения: 00.00.0000). — Режим доступа: для авториз. пользователей.
Рекомендуемая дополнительная литература
- Введение в дискретную математику : учеб. пособие для вузов, Яблонский, С. В., 1979
- Дискретная математика и математические вопросы кибернетики. Т. 1: ., Васильев, Ю. Л., 1974
- Лекции по математической логике и теории алгоритмов. Ч.1: Начала теории множеств, Верещагин, Н. К., 2008
- Математическая теория формальных языков, Пентус, А. Е., 2006
- Пентус, А. Е. Математическая теория формальных языков : учебное пособие / А. Е. Пентус, М. Р. Пентус. — 2-е изд. — Москва : ИНТУИТ, 2016. — 218 с. — ISBN 5-9556-0062-0. — Текст : электронный // Лань : электронно-библиотечная система. — URL: https://e.lanbook.com/book/100633 (дата обращения: 00.00.0000). — Режим доступа: для авториз. пользователей.
- Теория графов, Оре, О., 1980
- Теория графов, Харари, Ф., 2009