• A
  • A
  • A
  • АБB
  • АБB
  • АБB
  • А
  • А
  • А
  • А
  • А
Обычная версия сайта
Бакалавриат 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 * Экзаменационная работа
Список литературы

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

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

  • Алексеев В.Е., Таланов В.А. - Графы и алгоритмы - Национальный Открытый Университет "ИНТУИТ" - 2016 - 153с. - ISBN: 5-9556-0066-3 - Текст электронный // ЭБС ЛАНЬ - URL: https://e.lanbook.com/book/100593

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

  • Дискретная математика : курс лекций для студентов-механиков, Редькин, Н. П., 2006
  • Клековкин Г. А., Коннова Л. П., Коннов В. В. - ГЕОМЕТРИЧЕСКАЯ ТЕОРИЯ ГРАФОВ 2-е изд., испр. и доп. Учебное пособие для академического бакалавриата - М.:Издательство Юрайт - 2019 - 240с. - ISBN: 978-5-534-04812-4 - Текст электронный // ЭБС ЮРАЙТ - URL: https://urait.ru/book/geometricheskaya-teoriya-grafov-438693