ИСП РАН
Институт системного программирования Российской Академии Наук

Отдел «Теоретической информатики»

Об отделе

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

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

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

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

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