Кафедра математической логики и теории алгоритмов

Механико-математического факультета МГУ


Эффективные алгоритмы на словах и графах

Выпускник и профессор нашей кафедры, ученик В. А. Успенского Василий Александрович Любецкий, известный своими результатами в области теории моделей и теории множеств, работает также в Институте проблем передачи информации РАН, где заведует лабораторией математических методов и моделей в биоинформатике. Биоинформатика относится к числу наиболее перспективных, быстро развивающихся и дающих важные практические применения областей знания. Применение в ней методов математической логики и теории алгоритмов обусловило эффективность исследований В. А. Любецкого, упомянутых выше Ю. Л. Притыкина, Т. А. Стариковской, профессора Михаила Абрамовича Ройтберга, тоже нашего выпускника, работавшего в Институте математических проблем биологии — филиале Института прикладной математики им. М. В. Келдыша РАН.

Эффективные алгоритмы на словах — тема студенческой работы и кандидатской диссертации Татьяны Андреевны Стариковской, ученицы А. Л. Семенова и М. А. Бабенко. Студенткой она получила грант Аниты Борг, работала в Яндексе, ВШЭ, была постдоком в IRIF в Париже, работала в Бристольском университете; сейчас — в Высшей нормальной школе (Ecole normale superieure, Париж).

Задачами дискретной оптимизации занимаются В. А. Любецкий и выпускники нашей кафедры К. Ю. Горбунов, О. А. Зверков и др. Приведём пример их результата: фиксированы операции над графами; найден алгоритм с линейным временем работы, который преобразует этими операциями один данный граф в другой, тоже данный.

Построение эффективных алгоритмов на графах — тема исследований нашего выпускника, ученика Н. К. Верещагина Максима Александровича Бабенко, который сейчас заведует базовой кафедрой Яндекса в Высшей школе экономики