• A
  • A
  • A
  • АБВ
  • АБВ
  • АБВ
  • А
  • А
  • А
  • А
  • А
Обычная версия сайта

Математические основания компьютерной лингвистики

2020/2021
Учебный год
RUS
Обучение ведется на русском языке
8
Кредиты
Статус:
Курс обязательный
Когда читается:
1-й курс, 1-4 модуль

Преподаватель

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

Аннотация

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

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

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

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

  • Умеет анализировать функцию и строить график функций
  • Владеет простыми техниками интегрирования
  • Понимает и умеет использовать метод градиентного спуска
  • Умеет использовать формулу Байеса и формулу полной вероятности
  • Умеет использовать формулу Мувра-Лапласа
  • Умеет использовать центральную предельную теорему для решения задач
  • Понимает основные определения, касающиеся линейных пространств. Владеет методом Гаусса решения систем линейных уравнений. Работает с матрицами.
  • Умеет находить собственные векторы и собственные значение линейного оператора
  • Оценивает параметры линейной регрессии при помощи МНК
  • Понимает основные определения в теории графов, владеет алгоритмом Дейкстры и алгоритмом Чу-Лю-Эдмондса
  • Строит конечный автомат, проверяющий, содержится ли в строке данная подстрока. Владеет построением регулярного выражения по словесному описанию грамматики. Владеет построением конечного автомата, проверяющего соответствие строки данному регулярному выражению.
Содержание учебной дисциплины

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

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

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

  • неблокирующий Домашние задания
    Пересдача домашних заданий не предусмотрена. Домашние задания, сданные после срока, оцениваются так: опоздание в пределах двух часов – штраф 10% от полученной оценки, в пределах суток – штраф 20%, в пределах недели – штраф 50%. Если при проверке работ установлен факт нарушения академической этики, студент получает оценку «0» за данную работу. Работа студента, предоставившего свою работу для списывания, также аннулируется. Домашние задания, сданные через неделю после указанного срока и позже, не принимаются.
  • неблокирующий Контрольные работы
    Контрольная работа выполняется в режиме closed-book. Контрольная работа включает в себя письменное решение задач. Пересдача и переписывание контрольных работ с целью повышения оценки не предусмотрено. В случае пропуска контрольной работы по уважительной причине вес оценки переносится на экзаменационную работу.
  • неблокирующий Экзамен
    По общим правилам пересдачи экзамена, пропущенного по уважительной причине.
Промежуточная аттестация

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

  • Промежуточная аттестация (1 модуль)
    0.5 * Домашние задания + 0.5 * Контрольные работы
  • Промежуточная аттестация (4 модуль)
    0.26 * Домашние задания + 0.24 * Контрольные работы + 0.2 * Промежуточная аттестация (1 модуль) + 0.3 * Экзамен
Список литературы

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

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

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

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

  • Дискретная математика / Н.П. Редькин. - М.: ФИЗМАТЛИТ, 2009. - 264 с.: 60x90 1/16. (переплет) ISBN 978-5-9221-1093-8, 700 экз. - Режим доступа: http://znanium.com/catalog/product/208908