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


Об отделе

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

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

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

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