Методы теоретической информатики

Магистратура 2020/2021

Статус: Курс по выбору (Науки о данных)

Направление: 01.04.02. Прикладная математика и информатика

Кто читает: Департамент больших данных и информационного поиска

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

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

Охват аудитории: для своего кампуса

Преподаватели: Вялый Михаил Николаевич, Милованов Алексей Сергеевич, Подольский Владимир Владимирович

Прогр. обучения: Науки о данных

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

Кредиты: 6

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

Аннотация

Учебная дисциплина «Методы теоретической информатики» предназначена для обучения студентов специальности «Теоретическая информатика» основным приемам и методам решения и анализа задач в этой области. Среди всего разнообразия методов теоретической информатики для изучения в данной дисциплине выбраны те, которые наиболее активно используются в современных исследованиях по актуальным направлениям теоретической информатики.

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

Основная цель освоения дисциплины «Методы теоретической информатики» обучить студентов основным методам и техникам, используемым в исследованиях по теоретической информатике.
Для достижения основной цели предполагается развить у студентов умение формулировать задачи теоретической информатики.
Для достижения основной цели предполагается развить у студентов умение решать задачи методами теоретической информатики.
Для достижения основной цели требуется обеспечить знание студентами основных определений и фактов рассматриваемых в курсе разделов математики и теоретической информатики.
Для достижения основной цели требуется обеспечить владение студентами основными методами теоретической информатики.
Для достижения основной цели предполагается развить у студентов навыки перехода от обсуждения содержательных задач к их математическим формулировкам и дальнейшего анализа сформулированных математических задач.

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

Умение решать задачи, используя методы анализа Фурье над конечными полями.
Умение решать задачи, используя вероятностный метод.
Умение применять полиномиальный метод при решении задач.
Умение строить и анализировать приближенные алгоритмы, основанные на выпуклых релаксациях задач комбинаторной оптимизации.

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

Анализ Фурье над конечными полями
Базовые понятия анализа Фурье, его приложения в различных разделах теоретической информатики.
Вероятностные методы
Неравенство Чернова и его применения. Обобщение на зависимые случайные величины.
Полиномиальный метод
Представление булевых функций многочленами, приложения в сложности разрешающих деревьев, сложности булевых схем, коммуникационной сложности.
Применение методов линейного и выпуклого программирования для решения задач комбинаторной оптимизации
Примеры ЛП и SDP релаксаций задач комбинаторного программирования. Приближенные алгоритмы их решения.

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

Домашнее задание
Коллоквиум
Оценка за дисциплину выставляется в соответствии с формулой оценивания от всех пройденных элементов контроля. Экзамен не проводится.
Контрольная работа

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

Промежуточная аттестация (3 модуль)
0.35 * Домашнее задание + 0.5 * Коллоквиум + 0.15 * Контрольная работа

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