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

Об отделе

Отдел существует со времени образования ИСП РАН в 1994 году. Сотрудники ведут научную работу в различных областях математики и теоретической информатики. В частности, это комбинаторика, сложность алгоритмов, вероятностные методы, математическая логика и теория алгоритмов, формальные методы анализа программ, логическое программирование, математическая криптография.

Главные направления исследований:

• Сложность вычислений, разработка и анализ алгоритмов, в том числе разработка и исследование эффективных алгоритмов решения вычислительно сложных (в частности, NP-трудных) задач. Современные подходы к их решению включают:
  • разработку вероятностных алгоритмов;
  • разработку приближённых алгоритмов с оценками точности;
  • оценки порогов неаппроксимируемости;
  • анализ сложности в среднем;
  • разработку различных эвристик (генетические алгоритмы, локальный поиск и т.п.).
• Теоретические основы обеспечения информационной безопасности, в том числе теория обфускации программ, теоретические основы криптографии, вычисления над зашифрованными данными.
• Гомоморфное шифрование.

Сотрудники отдела читают ряд курсов для студентов МФТИ и ВМК МГУ.