• A
  • A
  • A
  • АБB
  • АБB
  • АБB
  • А
  • А
  • А
  • А
  • А
Обычная версия сайта

Вопросы сложности в теоретической информатике

2020-2022
Подразделение: Факультет математики

Ход реализации проекта:
Проект направлен на исследование сложностных аспектов в ряде разделов теоретической информатики.
  • Исследование структурной сложности вычислений. Изучение сложности коммуникационных задач.
  • Исследование свойств количества взаимной информации в бесконечных двоичных последовательностях.
  • Изучение возможности дерандомизации задачи равенства нулю многочлена (Р1Т) в частных случаях.
  • Изучение схемной сложности булевых функций.
  • Изучение сложностных классов с оракулом, состоящим из слов большой колмогоровской сложности.
  • Изучение комбинаторных и спектральных свойств псевдослучайных графов.
  • Описание сложности кванторной задачи удовлетворения ограничениям.
  • Исследование равновесия Нэша в позиционных играх.
  • Исследование сложности алгоритмов для комбинаторных задач на графах.
  • Исследование структурных и сложностных свойств автоматных моделей вычислений.
  • Конструирование алгоритмов сжатия, удовлетворяющих условиям оптимальности в сильном смысле.
Коды по классификатору Elibrary:
27.41.41 Алгоритмы решения задач вычислительной и дискретной математики