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

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

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

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

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

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

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

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

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

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

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

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

Кредиты: 5

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

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

Аннотация

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

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

Освоение основ теоретической информатики. Освоение основ вычислительной логики и искусственного интеллекта. Освоение методов дискретной математики, используемых в теоретической информатике.

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

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

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

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

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

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

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

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

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