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

Материалы по математике, 2017-18 учебный год
Перейти к: навигация, поиск
  • Курс ведёт Илья Щуров

Темы курса

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

Задачи

  1. Дан неориентированный граф: G = <V, E>, V={a, b, c, d}, E={{a,b}, {b, c}, {c, d}, {d, a}, {a, с}}. Построить этот граф на плоскости. Найти матрицу смежности и матрицу инцидентности. Построить граф, матрица смежности которого равна исходной матрице смежности, возведённой в квадрат. Объяснить связь с исходным графом.
  2. Существует ли граф со степенями вершин 1, 2, 2, 2, 3, 3, 3?
  3. Васин кот всегда чихает перед дождём. Сегодня кот чихнул. Значит, завтра будет дождь, подумал Вася. Прав ли он? Объяснить, что здесь произошло с точки зрения алгебры логики. Какую ошибку совершил Вася?
  4. Петя написал такое условие: if not (a == b and not (c == d and not (d == e or e == f) and g == h)): print("That's fine"). Как записать это условие без скобок?
  5. Записать с помощью кванторов утверждение: все члены последовательности an с чётными номерами нечётны. (Использовать операцию «деления с остатком» запрещено.)
  6. Доказать, что 10n + 10 = O(n) при n стремящемся к бесконечности.
  7. Доказать, что O(n) есть также O(n^2) при n стремсящемся к бесконечности.
  8. Найти энтропию случайной величины со следующим распределением: P(x=0)=1/2, P(x=1)=1/4, P(x=2)=1/8, P(x=3)=1/8.
  9. Пусть имеется источник последовательностей из букв A, B, C, D, который каждый раз генерирует очередную букву в соответствии с распределением из предыдущей задачи (0 соответствует A, 1 соответствует B и т.д.). Построить код Хаффмана для таких последовательностей. Какова средняя длина кодового слова будет получаться при использовании этого кода? Закодировать последовательность ABBAAACD полученным кодом.
  10. Закодировать с помощью (7,4)-кода Хэмминга какую-нибудь последовательность из 8 бит. Испортить в ней случайный бит. Передать другому студенту. Расшифровать и сравнить с исходной последовательностью.
  11. Найти предел функции (x^2+x)/(2x^2+100x+1) при x стремсящемся к бесконечности.
  12. Найти предел функции (x^2+x)/(x^2-x) при x стремящемся к 1.
  13. Найти производную функции x(x^2+1)/(x+2).
  14. Построить линии уровня функции f(x, y)=x^2 + y. Найти градиент этой функции. Взять несколько точек и отложить от них вектор градиента, посчитанный в этой точке. Как связаны векторы градиента и линии уровня?
  15. Найти матрицу такой игры: Петя и Вася одновременно называют по целому числу от 1 до 4 (включительно), затем считают их произведение. Если произведение оказывается чётным, то Вася отдаёт Пете столько рублей, чему равно это произведение, а если нечётное, то наоборот, Петя отдаёт Васе число рублей, равное произведению. Найти доминирующие стратегии игроков в этой игре, если они есть. Найти равновесие Нэша.

ДЗ