• A
  • A
  • A
  • ABC
  • ABC
  • ABC
  • А
  • А
  • А
  • А
  • А
Regular version of the site

Research Seminar "Theoretical Informatics 2"

2020/2021
Academic Year
RUS
Instruction in Russian
5
ECTS credits
Course type:
Elective course
When:
4 year, 1-3 module

Instructors


Milovanov, Alexey


Podolskii, Vladimir V.

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

Аннотация

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

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

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

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

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

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

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

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

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

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

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

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

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

  • Boolean function complexity : advances and frontiers, Jukna, S., 2012
  • Communication complexity, Kushilevitz, E., 2006
  • Computational complexity : a modern approach, Arora, S., 2010
  • Introduction to the theory of computation, Sipser, M., 2013

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

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