Мы используем cookie файлы.
Пользуясь сайтом, вы соглашаетесь с нашей Политикой конфиденциальности.

Номер договора
14.Z50.31.0030
Период реализации проекта
2014-2018

По данным на 30.01.2020

23
Количество специалистов
68
научных публикаций
Общая информация

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

Название проекта: Построение новых эффективных алгоритмов и доказательство трудности вычислительных задач



Цели и задачи

Направления исследований: Алгоритмы и теория сложности

Цель проекта: Решение фундаментальных вопросов современной математики и информатики: изучение сложности вычислительных задач


Практическое значение исследования

Научные результаты:

  • Улучшена нижняя оценка на размеры булевых схем. Эта оценка не только устанавливает новый мировой рекорд на размеры подобных схем, но и является первым (с 1984 года) улучшением известных нижних границ для одной из наиболее фундаментальных моделей вычислений.
  • Решены фундаментальные задачи о сложности вычислений гомоморфизмов графов и подграфов. Нахождение точных асимптотических оценок сложности для этих задач являлось одним из центральных открытых вопросов в области экспоненциальных алгоритмов.
  • Получены первые параметризованные алгоритмы для задачи о надстроке, которая является математической моделью задачи сборки генома.
  • Разработан метод доказательства теоремы об иерархии по времени для эвристических вычислений с помощью иерархии по времени моделирования распределений. Теоремы об иерархии по времени являются основным инструментом, используемым для решения важнейшей задачи теории сложности – разделения классов сложности.

Образование и подготовка кадров:

  • Проведены 3 международные студенческие школы: Студенческая научная школа по алгоритмам и теории сложности в 2014 году (80 участников), две студенческие школы “Recent Advances in Algorithms” в 2017 (70 участников) и в 2018 (50 участников) годах.
  • Защиты: 1 докторская диссертация, 4 кандидатских диссертации по направлению научного исследования.
  • Ежегодно в состав лаборатории принимаются 1-2 новых аспиранта, проходящих обучение в ПОМИ РАН под руководством членов научного коллектива. В настоящий момент в состав лаборатории входят 5 аспирантов, 7 кандидатов наук. Среди 5 докторов наук, входящих в состав лаборатории, один имеет звание академика РАН и один – член-корр. РАН.
  • Разработаны и проведены 12 курсов лекций по теоретической информатике для программ бакалавриата, магистратуры и аспирантуры, курсы повышения квалификации молодых специалистов. Программы магистратуры: «Анализ булевых функций», «Эффективные алгоритмы», «Теория сложности доказательств», «Параметризованные алгоритмы», «Теоретико-сложностные основы криптографии.», «Практическое программирование и анализ данных в специализированных средах», «Теория информации». Программы бакалавриата: «Математическая логика и теория алгоритмов» «Теория алгоритмов», «Основы дискретной математики и математической логики». Программы повышения квалификации: «Алгоритмы обработки потоковых данных», «Алгоритмы для NP- трудных задач». Курсы читались на базе Научно-образовательного центра нанотехнологий РАН (Россия), Санкт-Петербургского национального исследовательского Академического университета РАН (Россия), Казанского федерального университета (Россия), Научно-образовательного центра при ПОМИ РАН, Высшей школы экономики (Россия) и Санкт-Петербургского государственного университета (Россия).
  • Организованы регулярные курсы лекций специалистов в области алгоритмов и теоретической информатики для повышения квалификации научного коллектива, а также студентов, аспирантов и сотрудников сторонних организаций Санкт-Петербурга. Около 10 открытых курсов лекций проводятся каждый семестр на базе ПОМИ РАН (видеозаписи лекций опубликованы на сайте Computer Science Club).

Организационные и инфраструктурные преобразования:

На базе лаборатории сформирован некоммерческий научно-образовательный центр, в котором каждый год проводится около двадцати открытых курсов по теоретической информатике и программированию. Курсы читаются действующими учеными и практикующими специалистами. Видеозаписи и материалы всех курсов опубликованы в открытом доступе сайте Computer Science Club.

Другие результаты:

  • Организовано несколько крупных международных конференций по алгоритмам и теории сложности: Third St. Petersburg Days of Logic and Computability 2015, 11th International Computer Science Symposium in Russia 2016, 15th International Symposium on Experimental Algorithms 2016, Journées sur les Arithmétiques Faibles 2017, «Машинное обучение и анализ алгоритмов в Санкт-Петербурге 2017». Институт посетили более 200 ведущих российских и международных специалистов в области теории алгоритмов и компьютерных наук.
  • Сотрудники лаборатории являются руководителями более 10 проектов, получивших гранты, в том числе гранты Российского фонда фундаментальных исследований, Российского научного фонда, Совета по грантам Президента Российской Федерации и других бюджетных и коммерческих организаций.
  • Ежегодно сотрудники лаборатории заключают коммерческие контракты на проведение исследований и подготовку курсов лекций с такими организациями как Яндекс, Исследовательский центр Samsung, Huawei и др.
  • Члены научного коллектива регулярно выступают с докладами на международных симпозиумах и конференциях по всему миру.

Сотрудничество:

  • Университет Бергена (Норвегия), Институт математических наук Ченнаи (Индия), Варшавский университет (Польша), Калифорнийский университет в Сан-Диего (США), Университет Турку (Финляндия), Курантовский институт математических наук (США): совместные исследования и научные публикации.
  • Институт Ченнаи (Индия), Университет Бергена (Норвегия): разработаны новые эффективные алгоритмы для трудных задач на графах и строках.
  • Варшавский университет: получены новые условные нижние оценки для задач вложения графов.
  • Калифорнийский университет в Сан-Диего: записано две онлайн-специализации на международной платформе Coursera, на них в данный момент записаны более двухсот тысяч слушателей со всего мира.

Скрыть Показать полностью
Cygan M., Fomin F.V., Golovnev A., Kulikov A.S., Mihajlin I., Pachocki J., Socala A.
Tight Lower Bounds on Graph Embedding Problems. J. ACM 64(3), 18:1–18:22 (2017).
Kogan K., Nikolenko S.I., Eugster P., Shalimov A., Rottenstreich O.
Efficient FIB Representations on Distributed Platforms. IEEE Transactions on Networking. 25(6): 3309–3322 (2017).
Golovnev A., Kulikov A.S., Mihajlin I.
Families with Infants: Speeding Up Algorithms for NP-Hard Problems Using FFT. ACM Trans. Algorithms 12(3): 35:1–35:17 (2016).
Find M.G., Golovnev A., Hirsch E.A., Kulikov A.S.
A Better-Than-3n Lower Bound for the Circuit Complexity of an Explicit Function. IEEE 57th Annual Symposium on Foundations of Computer Science FOCS 89–98 (2016).
Abramovskaya T.V., Fomin F.V., Golovach P.A., Pilipczuk M.
How to hunt an invisible rabbit on a graph. European Journal of Combinatorics 52, Part A: 12–26 (2016).
Медиа
Вторник , 03.12.2019
Другие лаборатории и ученые
Лаборатория, принимающая организация
Область наук
Город
Приглашенный ученый
Период реализации проекта
Лаборатория «Гибридные методы моделирования и оптимизации в сложных системах»

Сибирский федеральный университет - (СФУ)

Компьютерные и информационные науки

Красноярск

Станимирович Предраг Стеван

Сербия

2022-2024

Лаборатория «Исследование сетевых технологий с ультра малой задержкой и сверхвысокой плотностью на основе широкого применения искусственного интеллекта для сетей 6G»

Санкт-Петербургский государственный университет телекоммуникаций им. проф. М. А. Бонч-Бруевича

Компьютерные и информационные науки

Санкт-Петербург

Абд Эль-Латиф Ахмед Абдельрахим

Египет

2022-2024

Лаборатория нелинейной и микроволновой фотоники

Ульяновский государственный университет - (УлГУ)

Компьютерные и информационные науки

Ульяновск

Тейлор Джеймс Рой

Великобритания, Ирландия

2021-2023