Бакалавриат 2022/2023

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

Лучший по критерию «Новизна полученных знаний»

Статус: Курс обязательный (Фундаментальная и компьютерная лингвистика)

Направление: 45.03.03. Фундаментальная и прикладная лингвистика

Кто читает: Кафедра высшей математики

Где читается: Факультет гуманитарных наук

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

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

Охват аудитории: для своего кампуса

Преподаватели: Кочергин Вадим Васильевич, Михайлович Анна Витальевна

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

Кредиты: 4

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

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

Аннотация

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

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

• Целями освоения дисциплины «Дискретная математика» являются получение развёрнутого представления об основных разделах дискретной математики, развитие навыка строгих математических доказательств, изучение теоретических оснований и получение первичных практических навыков автоматической обработки текстов, общее развитие мышления, подготовка базы для последующих курсов математики.

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

• Умеет решать задачи из раздела "Элементы теории множеств".
• Умеет оперировать понятиями "множество" и операциями над множествами. Умеет строить взаимооднозначное соответствие между множествами или доказывать его отсутстсвие.
• Умеет применять метод математической индукции для решения задач
• Умеет применять комбинаторные методы для решения стандартных задач, а также комбинировать стандартные методы.
• Умеет составлять рекуррентные соотношения для соответствующих задач. Умеет решать рекуррентные соотношения.
• Умеет переводить целые и дробные числа между системами счисления с разными основаниями.

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

• Основы теории множеств.
• Метод математической индукции
• Комбинаторика
• Линейные рекуррентные последовательности.
• Системы счисления. Делимость.
• Функции алгебры логики.
• Предикаты.
• Графы.
• Кодирование.
• Регулярные языки и автоматы

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

• Работа на семинарах
  Оценивается активность работы на семинарах. Участие в обсуждениях, выступления у доски.
• Домашнее задание
  Текущее домашнее задание к каждому семинару. Письменные домашние задания, выданные и сдающиеся дистанционно. Для подтверждения оценки за письменное домашнее задание может быть проведена защита работы.
• Контрольная работа
  Письменная работа на 80 минут
• Экзамен
  Письменная работа на 120 минут.

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

• 2022/2023 учебный год 2 модуль
  0.2 * Домашнее задание + 0.25 * Работа на семинарах + 0.35 * Экзамен + 0.2 * Контрольная работа

Список литературы

Рекомендуемая основная литература

• Верещагин, Н. К. Лекции по математической логике и теории алгоритмов : учебное пособие / Н. К. Верещагин, А. Шень. — 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). — Режим доступа: для авториз. пользователей.
• Дискретная математика : курс лекций для студентов-механиков, Редькин, Н. П., 2006
• Задачи и упражнения по дискретной математике : учеб. пособие, Гаврилов, Г. П., 2005
• Лавров, И. А. Задачи по теории множеств, математической логике и теории алгоритмов : учебник / И. А. Лавров, Л. Л. Максимова. — 5-е изд., испр. — Москва : ФИЗМАТЛИТ, 2002. — 256 с. — ISBN 5-9221-0026-2. — Текст : электронный // Лань : электронно-библиотечная система. — URL: https://e.lanbook.com/book/2242 (дата обращения: 00.00.0000). — Режим доступа: для авториз. пользователей.

Рекомендуемая дополнительная литература

• Введение в дискретную математику : учеб. пособие для вузов, Яблонский, С. В., 1979
• Лекции по математической логике и теории алгоритмов. Ч.1: Начала теории множеств, Верещагин, Н. К., 2008
• Теория графов, Оре, О., 1980
• Теория графов, Харари, Ф., 2009

Авторы

• Кочергин Вадим Васильевич
• Михайлович Анна Витальевна