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

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

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

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

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

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

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

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

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

Кредиты: 4

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

Аннотация

В результате освоения дисциплины студент должен уметь применять изученные в рамках дисциплины методы к решению прикладных задач как математики, так и лингвистики. Изучение данной дисциплины базируется на знаниях и навыках, полученных в рамках школьного курса «Алгебра и начала анализа» (рекомендуемый минимальный балл ЕГЭ по математике: 70), а также предполагает наличие элементарных знаний по информатике.

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

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

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

а) формирование у студентов умений работать о основными понятиями и объектами комбинаторики, теории графов, математической логики, теории булевых функций, теории автоматов и грамматик, теории кодирования и других разделов дискретной математики; б) освоение методов, разобранных на занятиях, а также формирование умений их модифицировать и находить новые варианты решений;
в) формирование навыков формулировать задачи на языке математики в ситуациях, аналогичных изученным, а также находить решения этих задач; г) формирование у студентов умения ориентироваться в математических методах, применяемых для анализа естественных языков, анализа и синтеза языковых систем.

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

Математическая индукция
Принцип математической индукции. Рекурсивные алгоритмы и рекуррентные формулы. Задача о ханойской башне. Доказательство формул по индукции. Примеры некорректного применения принципа математической индукции.
Комбинаторика
Правила решения простейших комбинаторных задач: правило суммы, правило произведения. Формула включений-исключений. Подсчёт числа перестановок, числа размещений, числа сочетаний. Более сложные комбинаторные задачи. Связь различных определений биномиальных коэффициентов: треугольник Паскаля и бином Ньютона. Тождества с биномиальными коэффициентами. Доказательство тождеств при помощи различных определений биномиальных коэффициентов.
Дискретная теория вероятностей
Случайное событие, элементарный исход, вероятность. Примеры: бросание монеты и кубика, лотерея. Условная вероятность, независимость событий, формулы полной вероятности и Байеса.
Основы математической логики
Таблицы истинности. Составление логических формул по таблицам истинности. Тождества формальной логики. Дизъюнктивная нормальная форма. Понятие предиката. Область истинности и область осмысленности предиката. Кванторы существования и всеобщности. Построение отрицания к утверждению с кванторами. Понятие отношения. Выражение одних отношений через другие. Пример: отношения родства и свойства́.
Системы счисления
Примеры систем счисления: римская, вавилонская, n -ичные и другие. Позиционные системы счисления, их преимущества перед непозиционными. Перевод чисел из одной системы счисления в другую. Действия над числами в n -ичных системах счисления без перевода в десятичную. Запись дробных чисел в n -ичной системе счисления. Остаток от деления на n как последняя цифра в n -ичной записи.
Целые числа: делимость
Определение делителя, кратного. Деление с остатком. Признаки делимости в различных системах счисления. Использование соображений делимости при решении диофантовых уравнений и в комбинаторных задачах.
Алгоритм Евклида, НОД
Определение НОД и НОК. Простейшие свойства. Алгоритм Евклида и его преимущества перед алгоритмом, использующим разложение чисел на простые множители. Вычисление НОД больших чисел. Лемма Безу о линейном представлении НОД. Применение алгоритма Евклида для решения линейных диофантовых уравнений.
Теория графов
Понятие ориентированного и неориентированного графа. Полный граф. Степень вершины графа. Подсчёт количества рёбер в графе. Изоморфизм графов. Понятие пути и цикла в графе, связные графы, сильно связные ориентированные графы. Дерево и подсчёт количества рёбер в дереве. Остовное дерево. Понятие планарного графа. Формула Эйлера для планарных графов. Таблица смежности данного графа, вычисление количества путей длины n по таблице смежности.
Конечные автоматы
Определение конечного автомата, примеры. Построение конечного автомата, проверяющего, содержится ли в строке данная подстрока.
Регулярные выражения
Определение формальной грамматики. Определение регулярного выражения. Построение регулярного выражения по словесному описанию грамматики. Связь с конечными автоматами. Построение конечного автомата, проверяющего соответствие строки данному регулярному выражению.
Коды с исправлением ошибок
Передача данных по ненадёжному каналу. Код с исправлением ошибок. Примеры кодов. Оптимальные коды. Сферическая упаковка.
Основы криптографии
Абсолютно стойкий шифр и область его практической применимости. Шифрование в сети Internet. Криптографические протоколы. Шифрование с открытым ключом: основные принципы.

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

Домашние задания
Аудиторная работа
Контрольная работа
Экзаменационная работа

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

Промежуточная аттестация (2 модуль)
0.25 * Аудиторная работа + 0.2 * Домашние задания + 0.2 * Контрольная работа + 0.35 * Экзаменационная работа

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