Теоретическая информатика

С 2022 года набор на специализацию не осуществляется!

Кураторы специализации:

Подольский Владимир Владимирович

Вялый Михаил Николаевич

Теоретическая информатика (Theoretical Computer Science) — это раздел науки, посвященный изучению теоретических основ компьютерных наук. Коротко говоря, по научным методам и подходам теоретическая информатика является разделом математики, при этом мотивировка задач происходит из Computer Science.

Основными разделами теоретической информатики являются теория алгоритмов, теория вычислимости, сложность вычислений, теория информации, теория кодирования. Отметим, однако, что этими разделами содержание теоретической информатики не исчерпываются, есть много других важных областей в этой науке. Знание основ теоретической информатики необходимо как исследователям, работающим в области компьютерных наук, так и высококвалифицированным специалистам в IT-индустрии.

Во время обучения на специализации можно будет познакомиться с основами теоретической информатики и попробовать себя в научной деятельности в этом направлении. Научно-исследовательская и проектная работа будет проводиться на базе международной лаборатории теоретической информатики НИУ ВШЭ.

Обязательные курсы специализации

• Theory of Computing (на английском языке)

Не всегда практическая задача, связанная с применением компьютеров, имеет чёткую математическую постановку. И даже если такая постановка есть, может оказаться, что в принципе не существует алгоритма, который решает соответствующую математическую задачу (она, как говорят, может быть алгоритмически неразрешимой). Наконец, задача может быть хотя и алгоритмически разрешимой, но вычислительно сложной - порой настолько, что с практической точки зрения она ничем не лучше алгоритмически неразрешимой. 
Теория вычислений как раз и занимается такими вопросами. Общая теория вычислимости позволяет понять, является ли задача алгоритмически разрешимой (и классифицирует алгоритмически неразрешимые задачи). Теория сложности вычислений изучает, прежде всего, класс "реально разрешимых задач", который в первом приближении отождествляется с полиномиально разрешимыми задачами. К сожалению, центральная проблема (P=NP) остаётся нерешённой, но тем не менее удаётся получить множество интересных условных результатов (в предположении трудности этой или близких задач, некоторые другие задачи являются трудными). 

Можно исследовать и более сложные ситуации, чем задачи разрешения: вместо того, чтобы узнавать, обладает ли исходное данное желаемым свойством, можно рассматривать интерактивный протокол, когда два участника обмениваются сообщениями (и имеют те или иные цели). Например, можно анализировать сложность игр, или сложность интерактивных доказательств (когда один участник должен убедить другого, что исходное данное обладает некоторым свойством), или криптографические задачи (когда два участника должны обменяться информацией, но так, чтобы внешний наблюдатель с ограниченными вычислительными ресурсами ничего не узнал), и так далее. 

Чтобы преодолеть барьер, связанный с P=NP, можно рассматривать некоторые ограниченные классы алгоритмов или специальные модели вычислений. Скажем, легко (и важно!) проанализировать, какие задачи могут быть решены алгоритмами без внешней памяти (конечные автоматы) - они соответствуют так называемым регулярным выражениям. Или, напротив, можно исследовать только какой-то один аспект вычислений - например, количество битов, которыми обмениваются участники (считая, что сами вычисления нам ничего не стоят, а трудность представляет лишь

передача битов). 

В целом, теория сложности вычислений расставляет (пусть не всегда и не везде) ориентиры для программиста - позволяя ему лучше рассчитать свои силы и понять, чего в принципе можно достичь и чего достичь нельзя

• Алгоритмы и структуры данных

Существующий курс совместной специализации "Анализ Интернет-данных". 

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

В этом курсе планируется рассказать об основных методах, техниках и приемах, использующихся в различных разделах теоретической информатики. В частности, планируется обсудить вероятностные методы и применения неравенства Чернова, анализ Фурье над конечными полями, полиномиальные методы в работе с булевыми функциями, методы теории матриц и спектральные методы, методы линейного программирования. Во второй части курса планируется разобрать базовые комбинаторные методы и приемы с приложениями в теоретической информатике.