Математика для лингвистов

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

Лучший по критерию «Полезность курса для Вашей будущей карьеры»

Лучший по критерию «Полезность курса для расширения кругозора и разностороннего развития»

Лучший по критерию «Новизна полученных знаний»

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

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

Кто читает: Школа лингвистики

Где читается: Факультет гуманитарных наук

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

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

Преподаватели: Клышинский Эдуард Станиславович, Сериков Олег Алексеевич

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

Кредиты: 3

Контактные часы: 28

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

Аннотация

В рамках курса "Математика для лингвистов" предполагается ознакомить студентов с дополнительными элементами дискретной математики, которые могут быть полезны при работе в рамках математического и компьютерного моделирования языка.

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

Целью освоения дисциплины является привитие базовых знаний и навыков в области алгоритмов на графах.

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

Знать методы представления графа. Уметь представлять графы в виде списков и словарей в ЯП Питон. Владеть теоретическим аппаратом обработки графов.
Владеть методами хранения информации в виде дерева
Владеть основами оценки сложности алгоритмов. Знать основные классы сложности алгоритмов. Уметь определять вычислительную сложность алгоритма.
Владеть алгоритмами поиска пути на графе. Знать типы графов и их основные метрики. Уметь рассчитывать метрики связности графов с использованием библиотек Python.
Владеть методами анализа текстов на естественном и формальном зыках. Знать варианты представления конечных автоматов. Уметь применять методы разбора текстов на практике.

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

Методы представления деревьев и графов
Понятия графа и дерева. Хранение дерева в языке Питон. Хранение графов — матрица смежности, матрица переходов, собственно граф. Степень вершины. Вычислительная сложность против сложности разработки. Обход дерева. Польская запись. Представление в виде дерева арифметических выражений и синтаксических деревьев. Формат CONLL как вариант хранения дерева.
Вычислительная сложность алгоритмов.
Алгоритм сортировки сложности N2 (пузырек, вставками, гномья). Понятие вычислительной сложности алгоритма. Алгоритмы сортировки сложности N*log N. Алгоритм прямого поиска, алгоритм поиска делением пополам. Сложность вставки в очередь, стек, список. Сложность задачи расстановки ферзей (только взять какую-нибудь матрицу из лингвистики, типа оценки гнездования предложения).
Хранение данных в деревьях.
Двоичное дерево. Балансировка деревьев. Суффиксное дерево. Алгоритм Укконена. Реализация Т9 на суффиксном дереве. B-деревья.
Граф социальной сети. Методы поиска в графе.
Гипотеза «мир тесен». Поиск клик в графе. Метрики кластерности в графе. Граф связи между соседними словами в тексте. Метрики центральности на таком графе. Понятие графа случайного графа, социальной сети. Генерация случайного графа из различных распределений. Поиск кратчайшего пути между двумя вершинами — поиск в ширину против поиска в глубину. Представление графом произвольной сетки. Алгоритмы поиска пути Дейкстры, Беллмана-Форда, Ли (волновые). Метод Флойда-Уоршела. Поиск подграфа в графе (прямой поиск, использование ограничений, использование списка вершин). Поиск остовного графа. Поиск компонент связности в графе. Алгоритм Хиршберга для вычисления расстояния Левенштейна.
Конечные автоматы. Контекстно-свободные грамматики.
Регулярные выражения. Конечные автоматы. Представление регулярного выражения в виде недетерминированного конечного автомата. Представление НКА в ДКА. Морфологический словарь в форме ДКА. Бэкусовские нормальные формы. Контекстно-свободные грамматики. Представление КС-грамматики в виде графа. Разбор с помощью МП-автомата. LR/LL-грамматики.

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

Домашние задания
Коллоквиум
Экзамен

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

Промежуточная аттестация (1 модуль)
0.5 * Домашние задания + 0.2 * Коллоквиум + 0.3 * Экзамен

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