Research Seminar "Theoretical Informatics"

2019/2020

Academic Year

RUS

Instruction in Russian

4

ECTS credits

Delivered at:

Big Data and Information Retrieval School

Course type:

Compulsory course

When:

1 year, 1-4 module

Instructors

Vyalyi, Michael

Milovanov, Alexey

Podolskii, Vladimir V.

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

Аннотация

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

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

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

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

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

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

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

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

• Домашнее задание.
• Устный экзамен
  "Экзамен проводится в устной форме (опрос по материалам курса). Экзамен проводится на платформе Zoom (https://zoom.us/). К экзамену необходимо подключиться ко времени начала экзамена. Компьютер студента должен удовлетворять требованиям: наличие рабочей камеры и микрофона, поддержка Zoom. Для участия в экзамене студент должен: явиться на экзамен, при ответе включить камеру и микрофон. Во время экзамена студентам запрещено пользоваться подсказками. Кратковременным нарушением связи во время экзамена считается нарушение связи менее 5 минут. Долговременным нарушением связи во время экзамена считается нарушение больше 5 минут. При долговременном нарушении связи студент не может продолжить участие в экзамене."

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

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

Список литературы

Рекомендуемая основная литература

• Arora, S., & Barak, B. (2009). Computational Complexity : A Modern Approach. Cambridge: Cambridge eText. Retrieved from http://search.ebscohost.com/login.aspx?direct=true&site=eds-live&db=edsebk&AN=304712

Рекомендуемая дополнительная литература

• Parameterized Complexity of Independent Set in H-free graphs. (2018). https://doi.org/10.4230/LIPIcs.CVIT.2016.23