УНИВЕРСИТЕТ ИТМО
Кафедра «Технологии программирования»

Только через мой труп...

Когда я в свое время спросил Максима Буздалова, о чем он хочет писать диссертацию, он ответил: «О тестировании программ». В силу того, что предполагалось мое научное руководство, я сказал: «Только через мой труп» – и пояснил: «Если бы эту задачу можно было решить, то в каждой компании не было бы своих методик тестирования, а каждый программист не проводил бы тестирование по-своему». Вместо этого я предложил провести это исследование для какого-либо класса программ, а так как Максим – чемпион мира по спортивному программированию, то, по моему мнению, этот класс – олимпиадные задачи.

Оказалось, что этот класс задач не проще класса всех задач, так как в одной из книг по олимпиадному программированию я прочел, что существует 23 класса олимпиадных задач (задачи по геометрии, задачи на графах и т.д.).

В результате Максим написал диссертацию на тему: «Генерация тестов для определения неэффективных решений олимпиадных задач по программированию с использованием эволюционных алгоритмов» (http://is.ifmo.ru/disser/buzdalov-synopsis.pdf). Даже после такого сужения тема все еще была очень широкой, и исследования Максима свелись к созданию тестов для двух классов очень сложных задач, для которых тестов, кроме случайных, до сих пор никто предложить не мог.

В результате Максим, в частности, создал «метод генерации тестов для алгоритмов решения NP-трудных задач на основе генетического алгоритма (на примере задачи о рюкзаке). При этом было показано, что разработанный метод с большим уровнем статистической значимости генерирует более сложные тесты, чем наилучшие методы случайной генерации тестов из известных на сегодняшний день», а также «метод генерации тестов для алгоритмов решения графовых задач на основе генетического алгоритма (на примере задачи о поиске максимального потока). При этом было показано, что разработанный метод генерирует более сложные тесты, чем метод случайной генерации тестов, а также большинство известных методов генерации тестов для указанной задачи. Для некоторых алгоритмов, например для алгоритма Диница, тесты, построенные генетическим алгоритмом, превосходили тесты, построенные другими методами, в несколько раз по времени работы».

История решения первой задачи была весьма интересной. До того как Максим взялся за ее решение, было известно 256 решений, полученных за пять лет, в том числе и чемпионами мира по спортивному программированию. Сначала Максим так усилил тесты, что «убил» (по времени решения задачи) половину решений, он продолжал исследования и за день до защиты бакалаврской работы оставалось всего четыре «правильных» решения, а в день защиты их не осталось совсем! Через некоторое время снова появились «правильные» решения, которые со временем Максимом были «убиты». Это «соревнование» продолжается до сих пор.

Если раньше многие задачи в олимпиадном программировании появлялись из адаптации научных публикаций, то в диссертации Максима, чуть ли не впервые в мире, на основе анализа некоторых классов олимпиадных задач были получены научные результаты!

Скоро Максим защитит докторскую диссертацию, тему которой мы придумали вместе. Во всех университетах мира на программистских специальностях преподают курс «Алгоритмы и структуры данных». В теме Максима будет еще три слова: «для эволюционных вычислений». Надеюсь, что и этот курс со временем будут читать в университетах, если и не во всех, то во многих. Пока мы начали с Университета ИТМО.

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

16.02.2020

P.S. Выше я на всякий случай написал, что тему докторской диссертации Макса мы придумали вместе. Это весьма странное утверждение, так как у нас по этому поводу мозгового штурма не было. Мне казалось, что это название придумано мною, но из дипломатических соображений написал, как указано выше. До публикации в сети я показал текст Максиму. Его письмо начиналось фразой, которая не предвещала ничего хорошего: «Вот ведь труп раскопали...». А еще в письме была фраза: «Про «вместе» я, кстати, не очень-то помню – кажется, я просто рассказал Вам про это название, и Вы «загорелись». Последнее свидетельствует о том, что правдивое написание истории невозможно – прошло всего несколько лет и нас всего двое, а мы имеем прямо противоположные воспоминания по описываемому факту. А если бы прошло значительно больше времени, а в событии участвовало на много больше народа?