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