Магистратура
2019/2020
Математические основания компьютерной лингвистики
Лучший по критерию «Полезность курса для Вашей будущей карьеры»
Лучший по критерию «Полезность курса для расширения кругозора и разностороннего развития»
Лучший по критерию «Новизна полученных знаний»
Статус:
Курс по выбору (Компьютерная лингвистика)
Направление:
45.04.03. Фундаментальная и прикладная лингвистика
Кто читает:
Школа лингвистики
Где читается:
Факультет гуманитарных наук
Когда читается:
2-й курс, 1, 2 модуль
Формат изучения:
без онлайн-курса
Преподаватели:
Щуров Илья Валерьевич
Прогр. обучения:
Компьютерная лингвистика
Язык:
русский
Кредиты:
4
Контактные часы:
44
Программа дисциплины
Аннотация
Целями освоения дисциплины «Математические основания компьютерной лингвистики» являются - Знакомство студентов со следующими разделами: теория графов, конечные выражения и регулярные языки, теория информации, основы криптографии, необходимых для изучения прикладных дисциплин и дальнейшего практического применения. Формирование у слушателей ясного представления о базисных понятиях и методах данных разделов. - развитие логического мышления и умения оперировать абстрактными объектами, привитие навыков корректного употребления математических понятий и символов для выражения различных количественных и качественных отношений; - развитие навыка строгих математических рассуждений и доказательств. Изучение данной дисциплины базируется на знаниях и компетенциях, полученных при изучении следующих дисциплин: Математика (адаптационный курс), математические основы компьютерной лингвистики (1 курс).
Цель освоения дисциплины
- Цель данной дисциплины – научить студентов базовым математическим понятиям и определениям, необходимым для дальнейшего изучения прикладных математических дисциплин; научить их применять необходимый математический инструментарий при решении задач, использовать основные алгоритмы теории графов. Основные положения дисциплины должны быть использованы в дальнейшем при изучении следующих дисциплин: • Компьютерная лингвистика • Машинное обучение • Социальные сети
Планируемые результаты обучения
- Понимает основные положения теории графов, владеет методами построения графов
- Понимает устройство конечных автоматов и регулярных языков, умеет создать конечный автомат
- Владеет основными принципами теории информации, может применять их на практике
- Умеет писать код с исправлением ошибок
- Понимает и может применять на практике основы криптографии
Содержание учебной дисциплины
- Теория графов и основные алгоритмы теории графовПонятие ориентированного и неориентированного графа. Полный граф. Степень вершины графа. Подсчёт количества рёбер в графе. Изоморфизм графов. Понятие пути и цикла в графе, связные графы, сильно связные ориентированные графы. Дерево и подсчёт количества рёбер в дереве. Остовное дерево. Понятие планарного графа. Формула Эйлера для планарных графов. Таблица смежности данного графа, вычисление количества путей длины n по таблице смежности. Алгоритм Дейкстры поиска кратчайшего пути. Алгоритм Борувки. Алгоритм Чу-Лю-Эдмондса и его применение в лингвистических задачах.
- Конечные автоматы и регулярные языкиОпределение конечного автомата, примеры. Детерминированные и недетерминированные автоматы. Построение конечного автомата, проверяющего, содержится ли в строке данная подстрока. Определение формальной грамматики. Определение регулярного выражения. Построение регулярного выражения по словесному описанию грамматики. Связь с конечными автоматами. Построение конечного автомата, проверяющего соответствие строки данному регулярному выражению. Теорема Клини.
- Основы теории информацииКоличество информации. Принцип работы архиваторов. Невозможность создания архиватора, уменьшающего размер любого файла. Количество информации в текстах на разных языках. Энтропия.
- Основы теории информации(продолжение)Количество информации. Принцип работы архиваторов. Невозможность создания архиватора, уменьшающего размер любого файла. Количество информации в текстах на разных языках. Энтропия.
- Коды с исправлением ошибокПередача данных по ненадёжному каналу. Код с исправлением ошибок. Примеры кодов (код Хаффмана и код Хэминга).
- Основы криптографииАбсолютно стойкий шифр и область его практической применимости. Приемры шифров. Шифрование с открытым ключом: основные принципы. Пример: алгоритм RSA..
Элементы контроля
- домашние задания
- контрольная работаНа экзамене и при выполнении элементов текущего контроля студенты имеют право пользоваться любыми релевантными источниками информации.
- экзаменНа экзамене и при выполнении элементов текущего контроля студенты имеют право пользоваться любыми релевантными источниками информации.
