МЕГАГРАНТЫ

Лаборатория алгоритмических методов

О лаборатории

Лаборатория создана в рамках гранта Правительства Российской Федерации, выделенного на конкурсной основе для государственной поддержки научных исследований, проводимых под руководством ведущих ученых в российских образовательных учреждениях высшего профессионального образования (постановление правительства №220 от 9 апреля 2010 года).

Ссылка на сайт лаборатории

№ договора:
14.Z50.31.0030

Наименование ВУЗа:

ФГБУН «САНКТ-ПЕТЕРБУРГСКОЕ ОТДЕЛЕНИЕ МАТЕМАТИЧЕСКОГО ИНСТИТУТА ИМ. В.А. СТЕКЛОВА РОССИЙСКОЙ АКАДЕМИИ НАУК»

Области научных исследований:
КОМПЬЮТЕРНЫЕ И ИНФОРМАЦИОННЫЕ НАУКИ

Цель проекта: Создание новых подходов разработки и анализа алгоритмов для NP-трудных задач.

Исследование NP-трудных задач интересно как с практической, так и с теоретической точек зрения. Для многих таких задач неизвестны даже алгоритмы, работающие быстрее полного перебора.
Построение эффективных алгоритмов является одной из фундаментальных задач современной информатики.
Алгоритмы находят применение в поисковых системах, биоинформатике, анализе данных, обработке изображений и многих других областях.
К сожалению, для решения ряда практических задач, таких как задачи составления расписаний, сегментации изображений или сборки генома, несмотря на усилия большого числа исследователей, эффективных алгоритмов до сих пор не найдено.
За последние 40 лет сложилась стройная математическая теория вычислительной сложности, объясняющая отсутствие эффективных алгоритмов для подобных задач. Основой этой теории является понятие NP-полноты.
NP-полная задача — это задача из класса NP, к которой можно свести любую другую задачу из этого класса за полиномиальное время. Выяснилось, что многие алгоритмические задачи тесно связаны между собой в следующем смысле: существование эффективного (заканчивающие работу за полиномиальное от длины входа число операций) алгоритма для любой из этих задач влечет за собой существование эффективного алгоритма для всех этих задач.
Таким образом, NP-полные задачи образуют в некотором смысле подмножество «типовых» задач в классе NP: если для какой-то из них найден «полиномиально быстрый» алгоритм решения, то и любая другая задача из класса NP может быть решена так же «быстро».
Однако ни построить такой алгоритм для хотя бы одной из этих задач, ни доказать отсутствие такого алгоритма ученым пока не удается. Созданием новых подходов к разработке и анализу алгоритмов для NP-трудных задач и занимается коллектив этой уникальной лаборатории.

 

Ведущий учёный

img02 

ФИО:Фомин Федор Владимирович

 

Ученые степень и звание:
КАНДИДАТ ФИЗИКО-МАТЕМАТИЧЕСКИХ НАУК

Занимаемая должность:

ПРОФЕССОР УНИВЕРСИТЕТА БЕРГЕНА (НОРВЕГИЯ)

Области научных интересов:

Теоретическая информатика: анализ и дизайн алгоритмов, параметризованная сложность и алгоритмы для труднорешаемых задач.

Научные достижения:

Создатель теории биразмерных задач.
Автор метода Measure & Conque для анализа экспоненциальных алгоритмов. Также развивает субэкспоненциальные алгоритмы.
Создатель новых кернелизационных алгоритмов.
Автор (совместно с Д. Кратчем) первого и единственного на данный момент учебника по точным алгоритмам для NP-трудных задач*.

Научное признание: 

Член программных комитетов международных конференций, включая наиболее престижные конференции по алгоритмам SODA, ICALP, ESA.
Председатель программного комитета ведущих конференций по алгоритмам ICALP, SWAT и по параметризованной сложности IPEC.
Редактор журналов SIAM Journal on Discrete Mathematics, Algorithmica и Information and Computation.

Back to top