• A
  • A
  • A
  • АБB
  • АБB
  • АБB
  • А
  • А
  • А
  • А
  • А
Обычная версия сайта
Бакалавриат 2020/2021

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

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

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

Аннотация

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

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

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

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

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

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

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

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

  • неблокирующий Домашние задания
  • неблокирующий Коллоквиум
  • неблокирующий Экзамен
Промежуточная аттестация

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

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

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

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

  • Python 3, Прохоренок, Н. А., Дронов, В. А., 2016
  • Изучаем Python, Лутц, М., Киселева, А., 2014
  • Классическая теория компиляторов : учеб. пособие, Карпов, В. Э., 2002
  • Комбинаторика и теория графов. Ч.1: ., Григорьев, Б. В., 2005
  • Компиляторы : принципы, технологии и инструментарий : пер. с англ., Ахо, А. В., 2019
  • Математическая теория формальных языков, Пентус, А. Е., Пентус, М. Р., 2006
  • Структуры данных и алгоритмы, Ахо, А. В., Хопкрофт, Д. Э., 2010
  • Теория графов, Омельченко, А. В., 2018
  • Теория графов, Омельченко, А.В., 2018
  • Теория графов, Харари, Ф., Козырева, В. П., 2003

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

  • Python и анализ данных, Маккинли, У., Слинкина, А. А., 2015
  • Статистическая механика : энтропия, параметры порядка, теория сложности, Сетна, Дж. П., Тамм, М. В., 2013
  • Теория сложности и проектирование систем управления, Солодовников, В. В., Тумаркин, В. И., 1990