Научно-исследовательский семинар "Теоретическая информатика"

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

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

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

Статус: Курс по выбору (Прикладная математика и информатика)

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

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

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

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

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

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

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

Кредиты: 4

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

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

Аннотация

Целями освоения научно-исследовательского семинара «Теоретическая информатика» являются освоение студентами основ теоретической информатики, вычислительной логики и искусственного интеллекта, основным понятиям и методам дискретной математики, необходимым как в дальнейшем обучении, так и в работе по специальности. Это даст участникам семинара общее представление об указанных выше областях, а также позволит в дальнейшем заниматься более продвинутыми разделами этих областей. Курс организован в виде семинара, на котором планируются выступления как участников семинара, так и гостей факультета - ведущих специалистов в указанных выше областях науки.

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

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

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

Знание основных понятий и методов теоретической информатики, вычислительной логики и искусственного интеллекта
Умение самостоятельно осваивать новый материал по данным областям на основании учебных статей и научных статей
Навыки изложения и оформления научного материала по данным областям

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

Сложность вычислений
Классы сложности, соотношения между классами. Задачи, полные в основных классах сложности (P, NP, PSPACE).
Коммуникационная сложность
Детерминированная, недетерминированная и вероятностная модели коммуникации. Соответствующие меры коммуникационной сложности. Методы построения оценок коммуникационной сложности.
Сложность булевых схем
Оценки сложности ограниченных классов булевых схем.
Сложность пропозициональных доказательств
Системы пропозициональных доказательств. Нижние оценки. Сравнительная сила разных систем
Параметризованная сложность
Основные понятия параметризованной сложности. Классы параметризованной сложности. Примеры задач из класса FPT. Примеры задач, полных в классе W[1].

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

Домашнее задание
Устный экзамен
Экзамен проводится в устной форме с прокторингом в Zoom. Технические требования: web-камера, микрофон, наушники / колонки, Zoom.

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

Промежуточная аттестация (4 модуль)
0.3 * Домашнее задание + 0.7 * Устный экзамен

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