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


Об отделе

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

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

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

Члены коллектива читают несколько курсов для студентов (МФТИ и МГУ им. М.В. Ломоносова):

  • сложность комбинаторных алгоритмов,
  • распределенные алгоритмы,
  • математическая логика,
  • математическая криптография,
  • теоретические основы численного анализа,
  • эффективные алгоритмы,
  • решетки, алгоритмы и современная криптография.