• A
  • A
  • A
  • АБB
  • АБB
  • АБB
  • А
  • А
  • А
  • А
  • А
Обычная версия сайта
Магистратура 2018/2019

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

Лучший по критерию «Полезность курса для Вашей будущей карьеры»
Лучший по критерию «Полезность курса для расширения кругозора и разностороннего развития»
Лучший по критерию «Новизна полученных знаний»
Статус: Курс обязательный (Компьютерная лингвистика)
Направление: 45.04.03. Фундаментальная и прикладная лингвистика
Когда читается: 2-й курс, 1, 2 модуль
Формат изучения: без онлайн-курса
Прогр. обучения: Компьютерная лингвистика
Язык: русский
Кредиты: 3

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

Аннотация

Целями освоения дисциплины «Математические основания компьютерной лингвистики» являются - Знакомство студентов со следующими разделами: теория графов, конечные выражения и регулярные языки, теория информации, основы криптографии, необходимых для изучения прикладных дисциплин и дальнейшего практического применения. Формирование у слушателей ясного представления о базисных понятиях и методах данных разделов. - развитие логического мышления и умения оперировать абстрактными объектами, привитие навыков корректного употребления математических понятий и символов для выражения различных количественных и качественных отношений; - развитие навыка строгих математических рассуждений и доказательств. Изучение данной дисциплины базируется на знаниях и компетенциях, полученных при изучении следующих дисциплин: Математика (адаптационный курс), математические основы компьютерной лингвистики (1 курс).
Цель освоения дисциплины

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

  • Цель данной дисциплины – научить студентов базовым математическим понятиям и определениям, необходимым для дальнейшего изучения прикладных математических дисциплин; научить их применять необходимый математический инструментарий при решении задач, использовать основные алгоритмы теории графов. Основные положения дисциплины должны быть использованы в дальнейшем при изучении следующих дисциплин: • Компьютерная лингвистика • Машинное обучение • Социальные сети
Планируемые результаты обучения

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

  • Понимает основные положения теории графов, владеет методами построения графов
  • Понимает устройство конечных автоматов и регулярных языков, умеет создать конечный автомат
  • Владеет основными принципами теории информации, может применять их на практике
  • Умеет писать код с исправлением ошибок
  • Понимает и может применять на практике основы криптографии
Содержание учебной дисциплины

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

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

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

  • неблокирующий домашние задания
  • неблокирующий контрольная работа
    На экзамене и при выполнении элементов текущего контроля студенты имеют право пользоваться любыми релевантными источниками информации.
  • неблокирующий экзамен
    На экзамене и при выполнении элементов текущего контроля студенты имеют право пользоваться любыми релевантными источниками информации.
Промежуточная аттестация

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

  • Промежуточная аттестация (2 модуль)
    0.23 * домашние задания + 0.17 * контрольная работа + 0.6 * экзамен
Список литературы

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

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

  • Задачи и упражнения по дискретной математике : учеб. пособие, Гаврилов, Г. П., Сапоженко, А. А., 2005

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

  • Графы и их применение, Оре, О., Головиной, Л. И., 2006