Генерация тестов для определения неэффективных решений олимпиадных задач по программированию с использованием эволюционных алгоритмов тема диссертации и автореферата по ВАК РФ 05.13.11, кандидат наук Буздалов Максим Викторович

• Буздалов Максим Викторович
• кандидат наук
• 2014

Оглавление диссертации кандидат наук Буздалов Максим Викторович

Введение

1. Олимпиады по программированию, эволюционные алгоритмы и поисковая инженерия программного обеспечения

1.1. Олимпиады по программированию

1.1.1. Термины и обозначения

1.1.2. Руководство по подготовке задач для Google Code Jam________22

1.1.3. Особенности архивов задач с проверяющей системой

1.1.4. Практика генерации тестов для олимпиадных задач по программированию

1.1.5. Вычислительная сложность задачи генерации тестов

1.2. Эволюционные алгоритмы

1.2.1. Термины и обозначения

1.2.2. (1 + 1)-эволюционный алгоритм

1.2.3. Генетические алгоритмы

1.2.4. «Классический» генетический алгоритм

1.2.5. Генетическое программирование

1.2.6. Эволюционные стратегии

1.3. Поисковая инженерия программного обеспечения

1.3.1. Обзор избранных работ по поисковому тестированию программного обеспечения

1.3.2. Альтернативные подходы

1.4. Задачи, решаемые в диссертационной работе

Выводы по главе

2. Метод генерации тестов для алгоритмов решения NP-трудных задач

на основе генетического алгоритма (на примере задачи о рюкзаке)

2.1. Задача о рюкзаке

2.2. Алгоритмы решения задачи о рюкзаке

2.2.1. Алгоритм slmpleßranch

2.2.2. Алгоритм ЕхрКмар

2.2.3. Алгоритм НаяоКмар

2.3. Генерация случайных тестов для задачи о рюкзаке

2.4. Описание генетического алгоритма

2.5. Экспериментальное исследование

2.5.1. Постановка экспериментального исследования

2.5.2. Результаты экспериментального исследования

2.5.3. Анализ случайных тестов

2.5.4. Сравнение генерации случайных тестов и генетического алгоритма

2.5.5. Сравнение частичных и полных решений

2.5.6. Анализ сложных тестов

Выводы по главе

3. Метод генерации тестов для алгоритмов решения графовых задач на основе генетического алгоритма (на примере задачи о поиске максимального потока)

3.1. Задача о поиске максимального потока

3.2. Алгоритмы решения задачи о поиске максимального потока

3.2.1. Алгоритм Форда-Фалкерсона с масштабированием пропускной способности

3.2.2. Алгоритм Эдмондса-Карпа

3.2.3. Алгоритм Эдмондса-Карпа с масштабированием пропускной способности

3.2.4. Алгоритм Диница

3.2.5. Неоптимальная реализация алгоритма Диница

3.2.6. Улучшенный алгоритм поиска кратчайших дополняющих путей

3.3. Генераторы тестов для задачи о поиске максимального потока

3.3.1. Генерация случайных графов

3.3.2. Генерация ациклических графов

3.3.3. Генератор транзитных решеток

3.3.4. Генератор случайных слоев

3.3.5. Генератор Черкасского и Гольдберга

3.3.6. Генератор «Washington»

3.3.7. Тесты Заде

3.4. Описание разработанного генетического алгоритма

3.5. Экспериментальное исследование

3.5.1. Выбор критерия для анализа результатов, наиболее точно отражающего время работы

3.5.2. Лучшие тесты и генераторы для каждого алгоритма поиска максимального потока

3.5.3. Средняя эффективность генераторов тестов

3.5.4. Другие наблюдения

Выводы по главе

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

4.1. Постановка задачи

4.2. Общий вид и верхняя оценка времени работы алгоритма выбора критериев оптимизации

4.3. Алгоритм с экспоненциальной стратегией перезапуска и его верхняя оценка времени работы

4.4. Пример входных данных, на которых верхняя оценка времени работы асимптотически достигается

4.5. Оптимальная экспоненциальная стратегия перезапуска

4.6. О необходимости перезапуска алгоритмов

Выводы по главе

5. Технология генерации тестов для определения неэффективных решений олимпиадных задач по программированию на основе эволюционных алгоритмов

5.1. Выбор неэффективного решения олимпиадной задачи для генерации тестов

5.2. Предварительный теоретический анализ задачи генерации тестов для выбранного решения

5.3. Построение представления теста для олимпиадной задачи в виде особи эволюционного алгоритма

5.4. Генерация случайных тестов

5.5. Построение оптимизируемых функций

5.6. Построение оператора мутации

5.7. Генерация тестов с помощью (1 + 1)-эволюционного алгоритма

5.8. Построение оператора скрещивания

5.9. Генерация тестов с помощью генетического алгоритма

5.10. Генерация тестов с помощью эволюционной стратегии

5.11. Проверка имеющихся решений олимпиадной задачи на сгенерированном тесте

5.12. Выбор подмножества сгенерированных тестов

Выводы по главе

6. Внедрение предложенной технологии при генерации тестов для задачи «Ships. Version 2»

6.1. Условие задачи

6.2. Применение технологии генерации тестов в 2009 году

6.2.1. Решение

6.2.2. Решение

6.2.3. Решение

6.2.4. Решение

6.2.5. Выбор подмножества сгенерированных тестов

6.3. Применение технологии генерации тестов в 2011 году

Выводы по главе

7. Внедрение предложенной технологии при генерации тестов для задачи

«Work for Robots»

7.1. Условие задачи

7.2. Авторское решение задачи

7.3. Неэффективные решения

7.4. Применение технологии генерации тестов

7.4.1. Решение с кешированием младших бит

7.4.2. Решение, использующее ассоциативный массив

7.4.3. Решение с использованием «большого массива»

7.5. Выбор подмножества сгенерированных тестов

Выводы по главе

Заключение

Список источников

Печатные издания на русском языке

Печатные издания на английском языке

Печатные издания на немецком языке

Ресурсы сети Интернет

Публикации автора по теме диссертации

Статьи в журналах из перечня ВАК

Публикации в рецензируемых изданиях, индексируемых Web of Science

или Scopus

Другие публикации

Приложение А. Некоторые решения задачи «Ships. Version 2»

А.1. Решение 2 558 302 (язык C++)

А.2. Решение 2 208 365 (язык Pascal)

А.3. Решение 2 072 705 (язык C++)

А.4. Решение 1700 736 (язык C++)

Введение диссертации (часть автореферата) на тему «Генерация тестов для определения неэффективных решений олимпиадных задач по программированию с использованием эволюционных алгоритмов»

ВВЕДЕНИЕ

Актуальность проблемы. В мире проводится большое число олимпиад и соревнований по программированию для школьников [129, 130], студентов [131—133] и всех желающих [134—138]. Олимпиады помогают выявить школьников и студентов, одаренных в области информатики и программирования [7], а IT-компаниям, в свою очередь, сформировать перечень кандидатов, среди которых они смогут найти способных и талантливых сотрудников.

Существуют работы, посвященные олимпиадам и соревнованиям по программированию, предназначенные главным образом для участников соревнований и для их тренеров [8, 9]. Методические аспекты олимпиад обсуждаются на некоторых конференциях, таких как, например, ISSEP (Informatics in Schools: Situation, Evolution and Perspectives). Журнал Olympiads in Informatics, публикуемый Институтом математики и информатики Вильнюсского университета, всецело посвящен различным аспектам олимпиад по программированию. Однако, в литературе было найдено крайне мало публикаций на тему того, как следует готовить задачи для олимпиад по программированию [10]. Информация на эту тему может быть найдена в виде методических рекомендаций на сайте олимпиад [139, 140] или разослана непосредственно будущим авторам задач, как это делают организаторы системы соревнований TopCoder [134].

Решение олимпиадной задачи по программированию — это, как правило, программа, которая читает входные данные, решает поставленную задачу и выводит ответ. При этом решение должно уложиться в ограничения на время работы и на объем используемой памяти, указанные в условии задачи.

Тест для олимпиадной задачи по программированию — это входные данные для задачи. В большинстве случаев тест хранится в виде текстового файла, удовлетворяющего определенному формату. Для одной задачи может быть один или несколько тестов. Тесты составляются жюри до начала со-

ревнования и, как правило, неизвестны участникам. Правильность ответа на каждом тесте проверяется программой, написанной жюри.

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

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

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

число N не превосходит 10000, а генерировать только такие тесты, в которых N ^ 1000. Это даст меньше шансов опытным участникам, так как они потратят лишнее время на реализацию эффективного решения, и даст преимущество неопытным участникам, которые будут пытаться наудачу посылать решения, возможно, неэффективные.

Одной из важнейших проблем при разработке олимпиадных задач по программированию является генерация тестов, на которых неэффективные решения превышали бы ограничения на время и память. Проблемы, подобные указанной, успешно решаются для определенных классов программ с использованием методов поисковой инженерии программного обеспечения [11], в частности, различных метаэвристик [1], включая эволюционные алгоритмы [12—14]. Однако, существующие методы, основанные на таких алгоритмах, имеют следующие недостатки:

— большинство методов [15—24] направлены на максимизацию покрытия кода тестами, а не на максимизацию времени работы кода;

— методы генерации тестов, направленные на максимизацию времени работы кода [25—34], разработаны для встраиваемых систем;

— методы, основанные на переборе возможных путей выполнения [35, 36], применимы только для кода без циклов и рекурсии, что не выполняется практически ни для одного решения олимпиадной задачи.

Поэтому проблема генерации тестов для определения неэффективных решений олимпиадных задач по программированию с использованием эволюционных алгоритмов является актуальной.

Целью работы является разработка методов и технологии генерации тестов для определения неэффективных решений олимпиадных задач по программированию с использованием эволюционных алгоритмов.

Основные задачи диссертационной работы состоят в следующем:

1. Показать целесообразность применения эволюционных алгоритмов для генерации тестов, определяющих неэффективные решения олимпиад-

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

2. Разработать алгоритм выбора из нескольких функций приспособленности функции, оптимальной по времени решения задачи оптимизации.

3. Разработать и внедрить технологию генерации тестов на основе эволюционных алгоритмов для определения неэффективных решений олим-пиадных задач по программированию на примере задач дискретной математики указанного класса.

Научная новизна. В работе получены следующие новые научные результаты, которые выносятся на защиту:

1. Метод генерации тестов для алгоритмов решения КР-трудных задач на основе генетического алгоритма (на примере задачи о рюкзаке). Показано, что разработанный метод с большим уровнем статистической значимости генерирует более сложные тесты, чем наилучшие методы случайной генерации тестов из известных на сегодняшний день.

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

3. Алгоритм выбора из нескольких функций приспособленности функции, оптимальной по времени решения задачи оптимизации. Показано, что данный алгоритм выбирает функцию приспособленности на каждой итерации эволюционного алгоритма, а также организует его перезапуск, таким образом, что математическое ожидание числа итераций эволю-

ционного алгоритма, необходимых для решения задачи оптимизации, меньше, чем 4K • min^ Tg, где K — число функций приспособленности, а Tg — математическое ожидание числа итераций эволюционного алгоритма при использовании функции приспособленности G.

Методы исследований. В работе используются методы дискретной математики, эволюционных вычислений, теории вероятностей и математической статистики.

Достоверность научных положений, выводов и практических рекомендаций, полученных в диссертации, подтверждается корректным обоснованием постановок задач, точной формулировкой критериев, результатами экспериментов по использованию предложенных в диссертации методов и их статистическим анализом.

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

Внедрение результатов работы. Дополнительные тесты, полученные с помощью методов, предложенных в диссертации, были внедрены в архив задач с проверяющей системой Timus Online Judge (функционирующий на базе Уральского федерального университета имени первого президента России Б. Н. Ельцина, г. Екатеринбург), используемый для подготовки к олимпиадам по программированию (задачи «Ships. Version 2» и «Work for Robots»).

Результаты диссертации были использованы в учебном процессе кафедры «Компьютерные технологии» Университета ИТМО при руководстве шестью бакалаврскими работами и одной магистерской диссертацией.

Апробация результатов работы. Основные результаты работы докладывались на следующих конференциях:

— Третья Всероссийская конференция «Нечеткие системы и мягкие вычисления» (2009, Волгоград);

— Всероссийская научная конференция по проблемам информатики СПИСОК (2011, 2012, 2013, 2014, Матмех СПбГУ);

— Genetic and Evolutionary Computation Conference (2011, Дублин, 2013, Амстердам);

— International Conference on Machine Learning and Applications (2012, Бока-Ратон, США, 2013, Майами, 2014, Детройт);

— IEEE Congress on Evolutionary Computation (2013, Канкун, Мексика);

— International Symposium on Search-Based Software Engineering (2013, Санкт-Петербург);

— International Conference on Soft Computing MENDEL (2014, Брно, Чехия);

— International Conference on Bio-Inspired Computing: Theories and Applications (2014, Вухан, Китай).

Личный вклад автора. Решение задач диссертации, разработанные методы, алгоритмы, технология и их реализация принадлежат лично автору.

Публикации. Основные результаты по теме диссертации изложены в 17 публикациях [152—168], две из которых изданы в журналах, рекомендованных ВАК [152, 153], девять — в изданиях, индексируемых в международных базах цитирования Web of Science [156, 160] и Scopus [154, 155, 157—159, 161, 162]. В работах, выполненных в соавторстве, авторство принадлежит соавторам в равных долях.

Свидетельства о регистрации программы для ЭВМ. Автором по теме диссертации получено три свидетельства о регистрации программы для ЭВМ:

1. № 2012610893 от 20 января 2012 года «Программное средство генерации тестовых данных для задачи о поиске максимального потока с использованием генетических алгоритмов», автор Буздалов М.В.;

2. № 2012619019 от 05 октября 2012 года «Программное средство исследования эволюционных алгоритмов для генерации покрывающего набора тестов», автор Буздалов М.В.;

3. № 2013610657 от 09 января 2013 года «Программное средство для исследования алгоритмов выбора оптимальной функции приспособленности», авторы Буздалов М.В., Буздалова А.С.

Участие в научно-исследовательских работах. Результаты диссертации были использованы при выполнении под руководством автора научно-исследовательской работы «Разработка методов автоматической генерации тестов на основе эволюционных алгоритмов» по Государственному контракту № 14.740.11.1430, 2011-2012 гг. Автор работы являлся победителем конкурса грантов Санкт-Петербурга для студентов, аспирантов, молодых ученых, молодых кандидатов наук 2011 г., тема проекта — «Генерация тестов для олимпиадных задач по теории графов с использованием эволюционных алгоритмов».

Объем и структура работы. Диссертация состоит из введения, семи глав, заключения и одного приложения. Объем диссертации составляет 204 страницы с девятью рисунками, 13 таблицами и пятью листингами. Список литературы содержит 168 наименований.

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

Во второй главе для КР-трудных задач на примере задачи о рюкзаке показывается целесообразность применения эволюционных алгоритмов для генерации тестов, определяющих неэффективные решения олимпиадных за-

дач по программированию. Задача о рюкзаке выбрана, так как она известна как «самая простая КР-трудная задача» [37] — многие решения этой задачи быстро работают на случайных тестах.

Рассматривается пять известных алгоритмов решения этой задачи, обладающих различной эффективностью. Предложен генетический алгоритм, позволяющий генерировать сложные тесты для таких алгоритмов. Приводятся результаты экспериментов, сравнивающих предложенный генетический алгоритм с известными методами генерации тестов, которые показывают, что генетический алгоритм генерирует более сложные тесты, в отдельных случаях — до 10 раз. При анализе тестов, сгенерированных генетическим алгоритмом, обнаружен новый класс тестов, сложных для переборных решений — тесты с двумя типами предметов.

В третьей главе для графовых задач на примере задачи о поиске максимального потока показывается целесообразность применения эволюционных алгоритмов для генерации тестов, определяющих неэффективные решения олимпиадных задач по программированию. Задача о поиске максимального потока выбрана ввиду того, что она обладает следующим свойством: тесты, сгенерированные случайным образом, редко бывают сложными, а оценки на время работы алгоритмов решений этой задачи могут существенно переоценивать их время работы.

Рассматривается шесть известных алгоритмов решения задачи о поиске максимального потока [38—42]. Предложен генетический алгоритм, позволяющий генерировать сложные тесты для указанных алгоритмов. Он сравнивается с семью известными генераторами тестов для алгоритмов решения задачи о максимальном потоке. По результатам экспериментальных исследований было установлено, что генерация тестов для различных алгоритмов поиска максимального потока наиболее эффективна при применении одной и той же конфигурации генетического алгоритма. Для некоторых алгоритмов,

таких как алгоритм Диница [40], генетический алгоритм генерирует примерно в четыре раза более сложные тесты, чем остальные методы.

В четвертой главе описывается разработанный автором алгоритм выбора оптимальной функции приспособленности, который назван SaRA (от англ. Switch-and-Restart Algorithm). Данный алгоритм направлен на решение проблемы выбора такой функции приспособленности из нескольких функций, которая приводит к нахождению хорошего теста за минимальное ожидаемое число итераций алгоритма оптимизации.

Пусть дана задача оптимизации, эволюционный алгоритм и K функций приспособленности, такие что математическое ожидание числа итераций эволюционного алгоритма, необходимых для решения указанной задачи оптимизации при использовании функции приспособленности G, составляет Tg. Разработанный алгоритм выбирает функцию приспособленности на каждой итерации эволюционного алгоритма, а также организует перезапуск этого алгоритма таким образом, что общее число итераций эволюционного алгоритма, необходимых для решения исходной задачи оптимизации, будет меньше 4K • minG Tg. При этом требуемый объем памяти равен соответствующей величине для используемого эволюционного алгоритма с добавлением лишь небольшой константы, что существенно меньше, чем при использовании параллельного запуска K эволюционных алгоритмов.

В пятой главе описывается технология генерации тестов для определения неэффективных решений олимпиадных задач по программированию на основе эволюционных алгоритмов. Предложенная технология состоит из 12 этапов. Она уменьшает влияние человеческого фактора на качество набора тестов в силу того, что чисто эвристический подход к построению тестов заменен использованием стандартной схемы, характерной для решения задач с помощью эволюционных алгоритмов.

В шестой главе описывается внедрение предложенной технологии при генерации тестов для задачи «Ships. Version 2» [141], расположенной в ар-

хиве задач с проверяющей системой Timus Online Judge [142], предназначенном для подготовки к олимпиадам по программированию. Данная задача является частным случаем задачи о мультирюкзаке, в котором сумма весов всех предметов равна сумме вместимостей всех рюкзаков. Указанный частный случай является NP-трудной задачей, что в совокупности с ограничениями, указанными в условии задачи, делают ее крайне трудной для решения. Однако в 2009 году по данной задаче на основании имевшихся на тот момент тестов 260 решений были признаны корректными по тестам. Применение технологии позволило признать все указанные решения неэффективными.

В седьмой главе описывается внедрение предложенной технологии при генерации тестов для задачи «Work for Robots» [143], расположенной в том же архиве задач, что и предыдущая задача. Данная задача состоит в подсчете числа клик в графе, и потому является #Р-полной, но в отличие от предыдущей задачи, у нее имеется корректное решение, основанное на динамическом программировании по подмножествам и идее «разделяй-и-властвуй». По состоянию на 2009 год администрацией сайта 86 решений было признано корректными по тестам. Однако кроме указанного корректного решения среди них было множество решений, основанных, главным образом, на идее перебора с возвратом. В результате применения технологии 45 из 86 решений были признаны неэффективными на новых тестах, которые были добавлены в архив.

В заключении сформулированы результаты, полученные в диссертации.

ГЛАВА 1. ОЛИМПИАДЫ ПО ПРОГРАММИРОВАНИЮ, ЭВОЛЮЦИОННЫЕ АЛГОРИТМЫ И ПОИСКОВАЯ ИНЖЕНЕРИЯ ПРОГРАММНОГО ОБЕСПЕЧЕНИЯ

В данной главе приводятся основные сведения об олимпиадах по программированию (раздел 1.1), в частности, о подготовке задач для олимпиад по программированию, об эволюционных алгоритмах (раздел 1.2), о поисковой инженерии программного обеспечения (раздел 1.3). В завершение главы (раздел 1.4) представлены и обоснованы задачи, решаемые в диссертационной работе.

1.1. Олимпиады по программированию

В мире проводится большое число олимпиад и соревнований по программированию для студентов [131, 132], для школьников [129, 130] и для всех желающих [133—138, 144]. Олимпиады помогают выявить школьников и студентов, одаренных в области информатики и программирования [7], а IT-компаниям, в свою очередь, сформировать перечень кандидатов, среди которых они смогут найти способных и талантливых сотрудников.

На указанных олимпиадах участникам предлагается решить одну или несколько задач. Обычно решением задачи является программа, написанная на одном из широко используемых языков программирования — например, на финале чемпионата мира по программированию разрешено использование языков C, C++ и Java [131], однако в некоторых соревнованиях требуется выслать лишь ответы, выдаваемые такой программой, на определенных тестовых данных [136], в некоторых случаях требуется также приложить саму программу [135].

Также распространены интернет-сервисы, предлагающие решать задачи с олимпиад по программированию в любое удобное время [137, 138, 142, 145—147], в том числе и в режиме эмуляции соревнования с виртуальным присутствием — в течение пяти часов участнику предлагается решать задачи с

определенного соревнования, при этом он может наблюдать положение реальных участников этого соревнования в тот момент, который соответствует времени, пройденному с начала «виртуального» соревнования.

Существуют работы, посвященные олимпиадам и соревнованиям по программированию, предназначенные главным образом для участников соревнований и для их тренеров [8, 9]. Методические аспекты олимпиад обсуждаются на некоторых конференциях, таких как ISSEP (Informatics in Schools: Situation, Evolution and Perspectives). Журнал Olympiade in Informatics, публикуемый Институтом математики и информатики Вильнюсского университета, всецело посвящен различным аспектам олимпиад по программированию. В работе С. Оршанского [2], чемпиона мира по программированию 2004 года, с точки зрения участника описано, как решаются олимпиадные задачи, а в статье И. Акишева [3], золотого медалиста чемпионата мира по программированию 2006 года, описан подход к эффективной командной работе на олимпиаде.

Однако, в литературе было найдено крайне мало публикаций на тему того, как следует подготавливать задачи для олимпиад по программированию [10]. Информация на эту тему может быть найдена в виде методических рекомендаций на сайтах олимпиад [139, 140] или разослана будущим авторам задач, как это делают организаторы системы соревнований TopCoder [134]. Наиболее старая публикация такого вида, известная автору диссертации, датирована 1988 годом [148]. По указанным причинам, информация о процессе подготовки задач будет приведена частично на основании опыта автора диссертации, являвшегося в 2006-2009 годах членом жюри интернет-олимпиад по информатике, проводимых Университетом ИТМО [130], в 2009 году ставшего чемпионом мира по программированию, а с 2010 года являющегося членом жюри Северо-Восточного полуфинала чемпионата мира по программированию [132] и одного из его четвертьфиналов, проходящих в Санкт-Петербурге.

1.1.1. Термины и обозначения

Решение олимпиадной задачи по программированию — это, как правило, программа, которая читает входные данные, решает поставленную задачу и выводит ответ. При этом решение должно уложиться в ограничения на время работы и на объем используемой памяти, указанные в условии задачи.

Тест для олимпиадной задачи по программированию — это набор входных данных, удовлетворяющий условию задачи (в частности, ограничениям, указанным в условии). В большинстве случаев тест хранится в виде текстового файла определенного формата. Решение олимпиадной задачи должно прочитать данные, содержащиеся в тесте, решить поставленную задачу для этих данных и вывести ответ. Правильность ответа проверяется программой, написанной жюри. Если для рассматриваемой задачи на каждый тест существует единственный правильный ответ, то программа проверяет совпадение ответа, выданного решением, и правильного ответа (например, сгенерированного решением жюри). Если правильных ответов несколько, то в условии задачи оговаривается критерий, на основании которого определяется правильность ответа, и проверяющая программа использует этот критерий (и, возможно, какой-либо правильный ответ, сгенерированный жюри).

На соревнованиях по программированию «классического» вида (International Collegiate Programming Contest (ICPC), проводимый Association for Computing Machinery (ACM) [131], International Olympiad in Informatics [129] до 2010 года) тесты, как правило, неизвестны участникам. Участники посылают на проверку в тестирующую систему решение задачи — программу, которая читает входные данные и выводит выходные данные. В тестирующей системе программа выполняется в специальном окружении («песочнице»), которое, как правило, пресекает попытки решения выполнить запрещенные действия (открытие файлов, кроме тех, которые указаны в условии, создание окон, выход в сеть, использование принтеров и т. п.), а

также прерывает выполнение программы при превышении ей ограничения на время работы или на объем используемой памяти (эти ограничения указаны в условии задачи). В соревнованиях последних лет типичным ограничением на время работы составляет от одной до пяти секунд, а ограничения на используемую память в последнее время выросли с 16-64 мегабайт до 256-512 мегабайт. В финале чемпионата мира по программированию используемая память как минимум с 2009 года ограничена только ресурсами компьютера.

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

Отметим, что в некоторых соревнованиях по программированию (например, Google Code Jam [135]) проверяющая система проверяет только ответы, сгенерированные решениями участников, при этом решения работают на компьютерах участников, а ответы пересылаются через Интернет. По причине того, что компьютеры участников могут иметь различные характеристики, при составлении задач приходится несколько изменить определение эффективного и неэффективного решения. В случае Google Code Jam, согласно руководству [139], эффективным решением является такое решение, которое на всех входных данных, удовлетворяющих условию задачи, находит корректный ответ не более чем за две минуты на компьютере с процессором тактовой частотой 2 ГГц, используя не более 256 мегабайт оперативной па-

Список литературы диссертационного исследования кандидат наук Буздалов Максим Викторович, 2014 год

СПИСОК ИСТОЧНИКОВ Печатные издания на русском языке

1. Скобцов Ю. А., Федоров Е. Е. Метаэвристики. — Донецк : Ноулидж, 2013. — 426 с.

2. Оршанский С. А. О решении олимпиадных задач по программированию формата ACM ICPC // Информатика. — 2006. — Т. 1. — С. 21—26.

3. Акишев И. Р. Об опыте участия в командных соревнованиях по программированию формата ACM // Информатика. — 2008. — Т. 19.

— С. 20—28.

4. Харари Ф. Теория графов. — М. : Едиториал УРСС, 2003. — 300 с.

5. Царев Ф. Н., Шалыто А. А. Применение генетического программирования для генерации автомата в задаче об «Умном муравье» // Труды IV Международной научно-практической конференции «Интегрированные модели и мягкие вычисления в искусственном интеллекте».

— М. : Физматлит, 2007. — С. 590—597.

6. Кормен Т., Лейзерсон Ч., Ривест Р. Алгоритмы. Построение и анализ. Второе издание. — М. : Издательский дом «Вильямс», 2005. — 1296 с.

Печатные издания на английском языке

7. Teaching Fundamentals Concepts of Informatics, 4th International Conference on Informatics in Secondary Schools - Evolution and Perspectives. Proceedings / ed. by J. Hromkovic, R. Kralovic, J. Vahrenhold.

— Springer, 2010. — (Lecture Notes in Computer Science ; 5941).

8. Skiena S. S., Revilla M. A. Programming Challenges: The Programming Contest Training Manual. — New York : Springer Verlag, 2003.

— 365 pp.

9. Halim S. Competitive Programming 3: The New Lower Bound of Programming Contests. — Lulu. — 447 pp.

10. Testing of Programs with Random Generated Test Cases / K. Manev, B. Yovcheva, M. Yankov, P. Petrov // Olympiads in Informatics. — 2010.

— Vol. 4. — Pp. 76-86.

11. Harman M., Mansouri S. A., Zhang Y. Search Based Software Engineering: A Comprehensive Analysis and Review of Trends, Technologies and Applications: tech. rep. / Department of Computer Science, King's College London. — 2009.

12. Holland J. P. Adaptation in Natural and Artificial Systems. — University of Michigan, 1975. — 211 pp.

13. Koza J. R. Genetic programming: on the programming of computers by means of natural selection. — Cambridge, MA, USA : MIT Press, 1992.

14. Mitchell M. An Introduction to Genetic Algorithms. — Cambridge, MA : MIT Press, 1996.

15. Tonella P. Evolutionary Testing of Classes // Proceedings of International Symposium on Software Testing and Analysis. — 2004.

— Pp. 119-128.

16. Offutt J., Abdurazik A. Generating Tests from UML specifications // Second International Conference on the Unified Modeling Language (UML99). — 1999. — Pp. 416-429.

17. Generating Test data from State based Specifications / J. Offutt, L. Shaoying, A. Abdurazik, P. Ammann // The Journal of Software Testing, Verification and Reliability. — 2003. — Vol. 1, no. 13. — Pp. 25-53.

18. Offutt J., Abdurazik A. Using UML Collaboration diagrams for static checking and test generation // Third International Conference on UML.

— UK, 2000.

19. Bousquet L. d., Martin H., Jezequel J. M. Conformance Testing from UML Specification Experience Report: tech. rep. — 2001.

20. Toth A., Varro D., Pataricca A. Model Level Automatic Test Generation for UML State-Charts // Sixth IEEE workshop on Design and Diagnostics of Electronic Circuits and System. — 2003.

21. Automating Software Testing Using Program Analysis / P. Godefroid, P. de Halleux, A. Nori, S. Rajamani, W. Schulte, N. Tillmann, M. Levin // IEEE Software. — 2008. — Vol. 25, no. 5. — Pp. 30-37.

22. Tillmann N., Halleux J. de Pex - White Box Test Generation for .NET // Tests And Proofs. Second International Conference. — 2008.

— Pp. 134-153.

23. Burnim J., Sen K. Heuristics for Scalable Dynamic Test Generation // Proceedings of the 23rd IEEE/ACM International Conference on Automated Software Engineering. — 2008. — Pp. 443-446.

24. Sen K, Marinov D, Agha G. CUTE: A Concolic Unit Testing Engine for C // SIGSOFT Software Engineering Notes. — New York, NY, USA, 2005. — Vol. 30, no. 5. — Pp. 263-272.

25. Alander J. T., Mantere T., Turunen P. Genetic Algorithm Based Software Testing // Artificial Neural Nets and Genetic Algorithms.

— Springer-Verlag, 1998. — Pp. 325-328.

26. Alander J. T., Mantere T., Moghadampour G. Testing Software Response Times Using a Genetic Algorithm // Proceedings of the 3rd Nordic Workshop on Genetic Algorithms and their Applications. — 1997.

— Pp. 293-298.

27. Gross H.-G. Measuring Evolutionary Testability of Real-Time Software: PhD thesis / Gross Hans-Gerhard. — University of Glamorgan, June 2000.

28. Gross H.-G., Jones B. F., Eyres D. E. Structural Performance Measure of Evolutionary Testing Applied to Worst-Case Timing of Real-Time Systems // IEEE Proceedings - Software. — 2000. — Vol. 147, no. 2.

— Pp. 25-30.

29. Gross H.-G. A Prediction System for Evolutionary Testability Applied to Dynamic Execution Time Analysis // Information and Software Technology. — 2001. — Vol. 43, no. 14. — Pp. 855-862.

30. Gross H.-G., Mayer N. Evolutionary Testing in Component-based RealTime System Construction // Proceedings of Genetic and Evolutionary Computation Conference. — 2002. — Pp. 207-214.

31. Gross H.-G., Mayer N. Search-based Execution-Time Verification in Object-Oriented and Component-Based Real-Time System Development // Proceedings of the 8th IEEE International Workshop on Object-Oriented Real-Time Dependable Systems. — 2003. — Pp. 113-120.

32. Tlili M., Wappler S., Sthamer H. Improving Evolutionary Real-Time Testing // Proceedings of Genetic and Evolutionary Computation Conference. — ACM, 2006. — Pp. 1917-1924.

33. Testing Real-Time Systems using Genetic Algorithms / J. Wegener, H. Sthamer, B. F. Jones, D. E. Eyres // Software Quality Journal. — 1997.

— Vol. 6, no. 2. — Pp. 127-135.

34. Wegener J., Mueller F. A Comparison of Static Analysis and Evolutionary Testing for the Verification of Timing Constraints // Real-Time Systems. — 2001. — Vol. 21, no. 3. — Pp. 241-268.

35. PathCrawler: Automatic Generation of Path Tests by Combining Static and Dynamic Analysis / N. Williams, B. Marre, P. Mouy, M. Roger // Lecture Notes in Computer Science. Vol. 3463. — 2005.

— Pp. 281-292.

36. Williams N., Roger M. Test Generation Strategies to Measure Worst-Case Execution Time // ICSE Workshop on Automation of Software Testing. — 2009. — Pp. 88-96.

37. Pisinger D. Algorithms for Knapsack Problems: PhD thesis / Pisinger David. — University of Copenhagen, Feb. 1995.

38. Ford Jr. L. R., Fulkerson D. R. Maximal flow through a network // Canadian Journal of Mathematics. — 1956. — Vol. 8. — Pp. 399-404.

39. Edmonds J., Karp R. M. Theoretical Improvements in Algorithmic Efficiency for Network Flow Problems // Journal of the ACM. — 1972.

— Vol. 19, no. 2. — Pp. 248-262.

40. Dinic E. A. Algorithm for solution of a problem of maximum flow in networks with power estimation // Soviet Math. Dokl. — 1970. — Vol. 11, no. 5. — Pp. 1277-1280.

41. Ahuja R. K., Magnanti T. L., Orlin J. B. Network Flows: Theory, Algorithms, and Applications. — Upper Saddle River, NJ, USA : Prentice-Hall, Inc., 1993.

42. Ahuja R. K., Orlin J. B. A Capacity Scaling Algorithm for the Constrained Maximum Flow Problem // Networks. — 1995. — Vol. 25, no. 2. — Pp. 89-98.

43. Rice H. G. Classes of Recursively Enumerable Sets and Their Decision Problems // Transactions of the American Mathematical Society.

— 1953. — Vol. 74, no. 2. — Pp. 358-366.

44. Mucherino A., Seref O. Monkey Search: A Novel Meta-Heuristic Search for Global Optimization // Data Mining, System Analysis and Optimization in Biomedicine, AIP Conference Proceedings. — 2007.

— Pp. 162-173.

45. Kirkpatrick S., Gelatt C. D., Vecchi M. P. Optimization by Simulated Annealing // Science. — 1983. — Vol. 220, no. 4598. — Pp. 671-680.

46. Boettcher S., Percus A. G. Extremal Optimization: Methods derived from co-evolution // Proceedings of the Genetic and Evolutionary Computation Conference. — 1999. — Pp. 825-832.

47. Geem Z. V., Kim J. H., Loganathan G. V. A new heuristic optimization algorithm: harmony search // Simulation. — 2001. — Vol. 76.

— Pp. 60-68.

48. Shah-Hosseini H. Principal component analysis by the galaxy-based search algorithm: a novel metaheuristic for continuous optimization // International Journal on Computation Science and Engineering.

— 2011. — Vol. 1/2. — Pp. 132-140.

49. Stutzle T. G., Hoos H. H. Analyzing the run-time behavior of iterated local search for the TSP // Proceedings of III Metaheuristic International Conference. — 1999. — Pp. 1-18.

50. Mladenovic N., Hansen P. Variable neighborhood search // Computers and Operations Research. — 1997. — Vol. 24, no. 11. — Pp. 1097-1100.

51. Feo T. A., Resende M. G. C. A probabilistic heuristic for a computationally difficult set covering problem // Operations Research Letters.

— 1989. — Vol. 8. — Pp. 67-71.

52. Voudouris C., Tsang E. P. K. Guided local search joins the elite in discrete optimization // Proceedings of DIMACS Workshop on Constraint Programming and Large Scale Discrete Optimization. — New Jersey : Rutgers, 1998. — Pp. 29-40.

53. Glover F. Tabu search methods for optimization // Feature Issue of European Journal on Operations Research. — 1998. — Vol. 106, no. 2.

— Pp. 110-115.

54. Battiti R., Tecchiolli G. The reactive tabu search // ORSA Journal on Computing. — 1994. — Vol. 6, no. 2. — Pp. 126-140.

55. Taillard E., Voss S. POPMUSIC: Partial optimization metaheuristic under special intensification conditions // Essays and surveys in meta-heuristics. — 2001. — Pp. 613-629.

56. Moscato P. On Evolution, Search, Optimization, Genetic Algorithms and Martial Arts: Towards Memetic Algorithms. — Pasadena : California Institute of Technology, 1989. — 101 pp.

57. Fogel L. J. Autonomous automata // Industrial Research. — 1962.

— Vol. 4. — Pp. 14-19.

58. Storn R., Price K. Differential Evolution - A Simple and Efficient Heuristic for Global Optimization over Continuous Spaces // Journal of Global Optimization. — 1997. — Vol. 11, no. 4. — Pp. 341-359.

59. Reynolds R. G. An Introduction to Cultural Algorithms // Proceedings of the 3rd Annual Conference on Evolutionary Programming. — 1994.

— Pp. 131-139.

60. Baluja S. Population-based incremental learning: A method for integrating genetic search based function optimization and competitive learning. — Pittsburgh, Pennsylvania : Carnegie Mellon University, 1994.

— 100 pp.

61. Syswerda G. Simulated crossover in genetic algorithms // Foundations of Genetic Algorithms. — 1993. — Vol. 2. — Pp. 239-255.

62. Muehlenbein H. The equation for response to selection and its use for prediction // Evolutionary Computation. — 1997. — Vol. 5, no. 3. — Pp. 303-346.

63. Pelikan M., Muehlenbein H. The Bivariate Marginal Distribution Algorithm // Advances in Soft Computing: Engineering Design and Manufacturing. — London : Springer, 1999. — Pp. 521-535.

64. Harik G. R., Lobo F. G., Goldberg D. E. The compact genetic algorithm // IEEE Transactions on Evolutionary Computation. — 1999. — Vol. 3, no. 4. — Pp. 287-297.

65. Harik G. R. Linkage Learning via Probabilistic Modeling in the Extended Compact Genetic Algorithm (ECGA). — Urbana : University of Illinois, 1999. — 19 pp.

66. Bonet J. S. de, Isbell C. L., Viola P. MIMIC: finding optima by estimating probability densities // Advances in Neural Information Processing Systems. — 1997. — Vol. 9. — Pp. 424-431.

67. Baluja S., Davies S. Using optimal dependency-trees for combinatorial optimization: learning the structure of the search space // Proceedings of the International Conference on Machine Learning. — 1997.

— Pp. 30-38.

68. Pelikan M., Goldberg D. E., Cantu-Paz E. Linkage Problem, Distribution Estimation, and Bayesian Networks // Evolutionary Computation.

— 2002. — Vol. 8, no. 3. — Pp. 311-341.

69. Shakya S., Santana R. An EDA based on local Markov property and Gibbs sampling // Proceedings of Genetic and Evolutionary Computation Conference. — 2008. — Pp. 475-476.

70. Eberhart R. C., Kennedy J. A new optimizer using particle swarm theory // Proceedings of the Sixth International Symposium on Micro Machine and Human Science. — 1995. — Pp. 39-43.

71. Li X. L., Shao Z. J., Qian J. X. An optimizing method based on autonomous animate: Fish swarm algorithm // Systems Engineering: Theory and Practice. — 2002. — Vol. 22. — Pp. 32-38.

72. Yang X. S., Deb S. Cuckoo search via Levy flights // Proceedings of World Congress on Nature and Biologically Inspired Computing. — 2009.

— Pp. 210-214.

73. Yang X. S. A New Metaheuristic Bat-Inspired Algorithm // Nature Inspired Cooperative Strategies for Optimization. — 2010. — Pp. 65-74.

74. Chu S. C., Tsai P. W., Pan J. S. Cat swarm optimization // Proceedings of the 9th Pacific Rim International Conference on Artificial Intelligence.

— 2006. — Pp. 854-858.

75. Eusuff M. M., Lansey K. E. Optimization of water distribution network design using the shuffled frog leaping algorithm // Journal of Water Resource Planning and Management. — 2003. — Vol. 129. — Pp. 210-225.

76. Dorigo M. The ant system: Optimization by colony of cooperating agents // IEEE Transactions on Systems, Man and Cybernetics. — 1996.

— Vol. 26, no. 1. — Pp. 1-13.

77. Dorigo M., Gambardella L. M. Ant Colony System: A Cooperative Learning Approach to the Traveling Salesman Problem // IEEE Transactions on Evolutionary Computation. — 1. — Vol. 1. — Pp. 53-66.

78. Yang X. S. Firefly algorithms for multimodal optimization // Stochastic Algorithms: Foundations and Applications. — 2009. — Pp. 169-178.

— (Lecture Notes in Computer Science ; 5792).

79. Krishnanand K. N., Ghose D. Detection of multiple source locations using a glowworm metaphor with applications to collective robotics // IEEE Swarm Intelligence Symposium. — 2005. — Pp. 84-91.

80. Basturk B., Karaboga D. An Artificial Bee Colony (ABC) Algoritmh for Numeric Function Optimization // IEEE Swarm Intelligence Symposium.

— 2006. — Pp. 10-15.

81. Pinto C., Runkler T. A., Sousa J. M. Wasp Swarm Algorithm for Dynamic MAX-SAT Problems // Proceedings of the 8th International Conference on Adaptive and Natural Computing Algorithms. Vol. 1. — 2007.

— Pp. 350-357.

82. Liu Y., Passino K. M. Biomimicry of Social Foraging Bacteria for Distributed Optimization // Journal of Optimization Theory and Applications. — 2002. — Vol. 115, no. 3. — Pp. 603-628.

83. Mehrabian A. R., Lucas C. A novel numerical optimization algorithm inspired from weed colonization // Ecological Informatics. — 2006. — Vol. 1. — Pp. 355-366.

84. Shah-Hosseini H. Problem Solving by Intelligent Water Drops // Proceedings of IEEE Congress on Evolutionary Computation. — 2007.

— Pp. 3226-3231.

85. Rabanal P., Rodrigues I., Rubio F. Using River Formation Dynamics to Design Heuristic Algorithms // Unconventional Computation. — 2007.

— Pp. 163-177. — (Lecture Notes in Computer Science ; 4618).

86. Rashedi E., Nezamabadi-pour H. A gravitational search algorithm // Information Sciences. — 2209. — Vol. 179, no. 13. — Pp. 2232-2248.

87. Birbil S., Fang S. An Electromagnetism-like Mechanism for Global Optimization // Journal of Global Optimization. — 2003. — Vol. 25.

— Pp. 263-282.

88. Kaveh A., Talatahari S. A novel heuristic optimization method: charged system search // Acta Mechanica. — 2010. — Vol. 213. — Pp. 267-289.

89. Bishop J. M. Stochastic Searching Networks // Proceedings of 1st IEEE Conference on Artificial Neural Networks. — 1989. — Pp. 329-331.

90. Erol O. K., Eksin I. A new optimization method: Big Bang-Big Crunch // Advances in Engineering Software. — 2006. — Vol. 37, no. 2.

— Pp. 106-111.

91. Castro L. N. de, Zuben F. J. von Learning and optimization using clonal selection principle // IEEE Transactions on Evolutionary Computation.

— 2002. — Vol. 6. — Pp. 239-251.

92. Self-Nonself Discrimination in a Computer / S. Forrest, A. S. Perelson, L. Allen, R. Cherukuri // Proceedings of the IEEE Symposium on Security and Privacy. — 1994. — Pp. 202-212.

93. Castro L. N. de, Zuben F. J. von An evolutionary immune network for data clustering // Proceedings of the 6th Brazilian Symposium on Neural Networks. — 2000. — Pp. 84-89.

94. Kelsey J., Timmis J. Immune Inspired Somatic Contiguous Hypermutation for Function Optimization // Proceedings of Genetic and Evolutionary Computation Conference. — 2003. — Pp. 207-218. — (Lecture Notes in Computer Science ; 2723).

95. Lucinska M., Wierzchon S. T. Hybrid Immune Algorithm for Multimodal Function Optimization // Recent Advances in Intelligent Information Systems. — 2009. — Pp. 301-313.

96. Aragon V. S., Esquivel S. C., Coello Coello C. A. Solving Constrained Optimization using a T-Cell Artificial Immune System // Inteligencia Artificial. — 2008. — Vol. 40. — Pp. 7-22.

97. Glover F. A Template for Scatter Search and Path Relinking // Proceedings of the 3rd European Conference on Artificial Evolution. — 1998.

— Pp. 3-54.

98. A Fast Elitist Multi-Objective Genetic Algorithm: NSGA-II / K. Deb, A. Pratap, S. Agarwal, T. Meyarivan // Transactions on Evolutionary Computation. — 2000. — Vol. 6. — Pp. 182-197.

99. Witt C. Optimizing Linear Functions with Randomized Search Heuristics - the Robustness of Mutation // Proceedings of the 29th Annual Symposium on Theoretical Aspects of Computer Science. — 2012.

— Pp. 420-431.

100. Bäck T., Hoffmeister F., Schwefel H.-P. A Survey of Evolution Strategies // Proceedings of the Fourth International Conference on Genetic Algorithms. — Morgan Kauffman, 1991. — Pp. 2-9.

101. Luke S. Essentials of Metaheuristics. — Lulu, 2009. — 253 pp.

102. Hansen N., Ostermeier A. Completely Derandomized Self-Adaptation in Evolution Strategies // Evolutionary Computation. — 2001. — Vol. 9.

— Pp. 159-195.

103. Hansen N., MUller S. D., Koumoutsakos P. Reducing the Time Complexity of the Derandomized Evolution Strategy with Covariance Matrix Adaptation (CMA-ES) // Evolutionary Computation. — 2003. — Vol. 11, no. 1. — Pp. 1-18.

104. Ros R., Hansen N. A Simple Modification in CMA-ES Achieving Linear Time and Space Complexity // Parallel Problem Solving from Nature X. — Springer, 2008. — Pp. 296-305. — (Lecture Notes in Computer Science ; 5199).

105. Langdon W. B., Harman M. Genetically Improving 50000 Lines of C++: Research Note RN/12/09: tech. rep. — 2012.

106. FloPSy - Search-Based Floating Point Constraint Solving for Symbolic Execution / K. Lakhotia, N. Tillmann, M. Harman, J. de Halleux // 22nd

IFIP International Conference on Testing Software and Systems. — 2010.

— Pp. 142-157.

107. Fitness-Guided Path Exploration in Dynamic Symbolic Execution / T. Xie, N. Tillmann, P. de Halleux, W. Schulte // Proceedings of the 39th Annual IEEE/IFIP International Conference on Dependable Systems and Networks (DSN 2009). — IEEE, 2009. — Pp. 359-368.

108. Garey M. R., Johnson D. S. Computers and Intractability: A Guide to the Theory of NP-Completeness. — New York, NY, USA : W. H. Freeman & Co., 1979. — 338 pp.

109. Bellman R. E. Dynamic Programming. — Princeton, NJ : Princeton University Press, 1957. — 342 pp.

110. Chvatal V. Hard Knapsack Problems // Operations Research. — 1980.

— Vol. 28, no. 6. — Pp. 1402-1411.

111. Nemhauser G., Ullmann Z. Discrete Dynamic Programming and Capital Allocation // Management Science. — 1969. — Vol. 15, no. 9.

— Pp. 494-505.

112. Dunn O. J. Multiple Comparisons Among Means // Journal of the American Statistical Association. — 1961. — Vol. 56, no. 293. — Pp. 52-64.

113. Goldberg A. V., Tarjan R. E. A New Approach to the Maximum Flow Problem // Proceedings of the Eighteenth Annual ACM Symposium on Theory of Computing. — New York, NY, USA : ACM, 1986.

— Pp. 136-146.

114. Zwick U. The smallest networks on which the Ford-Fulkerson maximum flow procedure may fail to terminate // Theoretical Computer Science.

— 1995. — Vol. 148, no. 1. — Pp. 165-170.

115. Goldfarb D., Grigoriadis M. D. A computational comparison of the Dinic and network simplex methods for maximum flow // Annals of Operations Research. — 1988. — Vol. 13, no. 1. — Pp. 81-123.

116. Zadeh N. Theoretical Efficiency of the Edmonds-Karp Algorithm for Computing Maximal Flows // Journal of the ACM. — 1972. — Vol. 19, no. 1. — Pp. 184-192.

117. Rice J. R. The algorithm selection problem // Advances in Computers.

— 1976. — Vol. 15. — Pp. 65-118.

118. Kotthoff L. Algorithm selection for combinatorial search problems: A survey //AI Magazine. — 2014.

119. Gomes C. P., Selman B. Algorithm portfolios // Artificial Intelligence.

— 2001. — Vol. 126, no. 1. — Pp. 43-62.

120. Yuen S. Y., Chow C. K., Zhang X. Which Algorithm Should I Choose at Any Point of the Search: An Evolutionary Portfolio Approach // Proceedings of the Genetic and Evolutionary Computation Conference.

— 2013. — Pp. 567-574.

121. Baudis P., Posik P. Online Black-Box Algorithm Portfolios for Continuous Optimization // Parallel Problem Solving from Nature XIII. — 2014.

— Pp. 40-49. — (Lecture Notes in Computer Science ; 8672).

122. Böttcher S., Doerr B., Neumann F. Optimal Fixed and Adaptive Mutation Rates for the LeadingOnes Problem // Parallel Problem Solving from Nature XI. — Springer, 2010. — Pp. 1-10. — (Lecture Notes in Computer Science ; 6238).

123. Karp R. Reducibility Among Combinatorial Problems //50 Years of Integer Programming 1958-2008. — 2010. — Pp. 219-241.

124. Raz R., Safra S. A sub-constant error-probability low-degree test, and a sub-constant error-probability PCP characterization of NP // Proceedings of the twenty-ninth annual ACM Symposium on Theory of Computing. — ACM, 1997. — Pp. 475-484.

125. Zhang L., Geng S. The Complexity of the 0/1 Multi-knapsack problem // Journal of Computer Science and Technology. — 1986. — Vol. 1, no. 1.

Печатные издания на немецком языке

126. Rechenberg I. Evolutionsstrategie: Optimierung technischer Systeme nach Prinzipien der biologischen Evolution. — Stuttgart: Fromman-Holzboorg Verlag, 1973.

127. Schwefel H.-P. Binäre Optimierung durch somatische Mutation: Techn. Ber. / Technical University of Berlin ; Medical University of Hannover. — Mai 1975.

128. Höfler A. Formoptimierung von Leichtbaufachwerken durch Einsatz einer Evolutionsstrategie: Diss. / Häfler A. — Technical University of Berlin, Juni 1976.

Ресурсы сети Интернет

129. International Olympiad in Informatics. — URL: http://www.ioinformatics.org.

130. Интернет-олимпиады по информатике. — URL: http://neerc.ifmo.ru/school/io/.

131. ACM International Collegiate Programming Contest. — URL: http://cm.baylor.edu/welcome.icpc.

132. Правила проведения Северо-западного полуфинала чемпионата мира по программированию. — URL: http://neerc.ifmo.ru/information/contest-rules.html.

133

134

135

136

137

138

139

140

141

142

143

144

145

146

147

148

Russian Code Cup. — URL: https://www.russiancodecup.ru/.

Programming Contests at TopCoder. — URL:

http://www.topcoder.com/1 c.

Google Code Jam. —URL: http://code.google.com/codejam.

Internet Problem Solving Contest. — URL: http://ipsc.ksp.sk/.

Codeforces. — URL: http://codeforces.ru.

CodeChef. —URL: http://www.codechef.com/.

Google Code Jam: Problem Preparation Guide. — URL: https://code.google.com/codej am/problem-preparation.html.

CodeChef: Test Generation Plan. — URL:

http://www.codechef.com/wiki/test-generation-plan.

Задача «Ships. Version 2» из архива задач Timus Online Judge. — URL: http://acm.timus.ru/problem.aspx?num=1394.

Timus Online Judge. Архив задач с проверяющей системой. — URL: http: //acm.timus . ru.

Задача «Work for Robots» из архива задач Timus Online Judge. — URL: http://acm.timus.ru/problem.aspx?num=1695.

Яндекс.Алгоритм. — URL: http://contest.yandex.ru/.

Архив задач и проверяющая система Саратовского государственного университета. — URL: http://acm.sgu.ru.

Sphere Online Judge. — URL: http://www.spoj .com.

UVa Online Judge. — URL: http://uva.onlinejudge.org.

Verhoeff T. Guidelines for Producing a

Programming-Contest Problem Set. — URL:

http://www.win.tue.nl/~wstomv/publications/guidelines.html.

149. R Core Team. R: A Language and Environment for Statistical Computing / R Foundation for Statistical Computing. — 2013. — URL: http://www.R-project.org/.

150. Генераторы тестов для алгоритмов решения задачи о максимальном потоке. — URL: http://www.informatik.uni-trier.de/~naeher/Professur/research.

151. Задача «Ships» из архива задач Timus Online Judge. — URL: http://acm.timus.ru/problem.aspx?num=1115.

ПУБЛИКАЦИИ АВТОРА ПО ТЕМЕ ДИССЕРТАЦИИ Статьи в журналах из перечня ВАК

152. Буздалов М. В. Генерация тестов для олимпиадных задач по программированию с использованием генетических алгоритмов // Научно-технический вестник СПбГУ ИТМО. - 2011. - 2(72). - С. 72-77.

153. Буздалов М. В. Генерация тестов для олимпиадных задач по теории графов с использованием эволюционных стратегий // Научно-технический вестник СПбГУ ИТМО. - 2011. - 6(76). - С. 123-127.

Публикации в рецензируемых изданиях, индексируемых Web of

Science или Scopus

154. Buzdalov M. Generation of Tests for Programming Challenge Tasks Using Evolution Algorithms // Proceedings of Genetic and Evolutionary Computation Conference Companion. — ACM, 2011. — Pp. 763-766.

155. Buzdalov M. Generation of Tests for Programming Challenge Tasks on Graph Theory using Evolution Strategy // Proceedings of the International Conference on Machine Learning and Applications. Vol. 2.

— IEEE Computer Society, 2012. — Pp. 62-65.

156. Buzdalov M., Buzdalova A. Adaptive Selection of Helper-Objectives for Test Case Generation // 2013 IEEE Congress on Evolutionary Computation. Vol. 1. — 2013. — Pp. 2245-2250.

157. Buzdalova A., Buzdalov M., Parfenov V. Generation of Tests for Programming Challenge Tasks Using Helper-Objectives // 5th International Symposium on Search-Based Software Engineering. — Springer, 2013.

— Pp. 300-305. — (Lecture Notes in Computer Science ; 8084).

158. Buzdalov M., Buzdalova A., Petrova I. Generation of Tests for Programming Challenge Tasks Using Multi-Objective Optimization // Proceedings of Genetic and Evolutionary Computation Conference Companion. — ACM, 2013. — Pp. 1655-1658.

159. Arkhipov V., Buzdalov M., Shalyto A. Worst-Case Execution Time Test Generation for Augmenting Path Maximum Flow Algorithms using Genetic Algorithms // Proceedings of the International Conference on Machine Learning and Applications. Vol. 2. — IEEE Computer Society, 2013. — Pp. 108-111.

160. Buzdalov M., Shalyto A. Worst-Case Execution Time Test Generation for Solutions of the Knapsack Problem using a Genetic Algorithm // Proceedings of 9th International Conference on Bio-inspired Computing: Theories and Applications. — Springer, 2014. — Pp. 1-10. — (Communications in Computer and Information Science ; 472).

161. Worst-Case Execution Time Test Generation using Genetic Algorithms with Automated Construction and Online Selection of Objectives / N. Kravtsov, M. Buzdalov, A. Buzdalova, A. Shalyto // Proceedings of 20th International Conference on Soft Computing MENDEL 2014. — Czech Republic, 2014. — Pp. 111-116.

162. Buzdalov M. A Switch-and-Restart Algorithm with Exponential Restart Strategy for Objective Selection and its Runtime Analysis // Proceedings of the International Conference on Machine Learning and Applications. Vol. 1. — IEEE Computer Society, 2014. — Pp. 112-117.

Другие публикации

163. Буздалов М. В. Применение генетических алгоритмов для определения неэффективных решений олимпиадных задач по программированию (на примере задачи о рюкзаке) // Труды Третьей Всероссийской

конференции «Нечеткие системы и мягкие вычисления». Т. 2. — 2009.

- С. 16—24.

164. Буздалов М. В. Генерация тестов для олимпиадных задач по программированию с использованием эволюционных стратегий // Материалы Второй межвузовской научной конференции по проблемам информатики СПИСОК. — 2011. — С. 336—338.

165. Буздалов М. В. Применение эволюционных алгоритмов для покрытия кода тестами // Материалы Всероссийской научной конференции по проблемам информатики СПИСОК. — 2012. — С. 404—408.

166. Буздалова А. С., Буздалов М. В. Использование вспомогательных функций приспособленности для тестирования решений олимпиадных задач по программированию // Материалы Всероссийской научной конференции по проблемам информатики СПИСОК. — 2013.

— С. 548—555.

167. Якорев В. О., Буздалов М. В. Генерация тестов для олимпиадных задач по программированию с помощью многокритериальных эволюционных алгоритмов // Материалы Всероссийской научной конференции по проблемам информатики СПИСОК. — 2013. — С. 571—573.

168. Буздалов М. В., Буздалова А. С. Асимптотически оптимальные алгоритмы для выбора вспомогательных критериев оптимизации // Материалы Всероссийской научной конференции по проблемам информатики СПИСОК. — 2014. — С. 324—329.

ПРИЛОЖЕНИЕ А. НЕКОТОРЫЕ РЕШЕНИЯ ЗАДАЧИ

«SHIPS. VERSION 2» А.1. Решение 2 558 302 (язык C++)

#include <iostream>

#include <algorithm>

#include <ctime>

#include <cstdio>

#include <cstdlib>

#include <cstring>

using namespace std ;

int n,m, a [102] ,c[12] , order [10 2] , path [ 1 000 2]; int ans [12] [102] , tot [12] , p [ 1 2 ] ; bool used [102] , can [10002];

inline void Print () {

for (int i =1; i<=m; i++) { printf("%d\n" , tot [ i ]) ; for (int j =0;j<tot [ i ] ; j++)

printf("%d " ,a[ans[i][j ]]) ; p r int f("\n") ;

}

exit (0) ;

}

inline void DP(int m) {

memset (can , 0 , s i z e o f ( can) ) ; can [ 0 ] = 1 ;

for (int i = 1; i <=n ; i ++) if (! used[order[i ] ]) { int j=order [ i ] ; for (int k=m; k>=a [ j ] ; k—)

if (! can [ k ] && can [ k—a [ j ]]) { can [k] = 1; path [k] = j ;

}

}

}

inline void Search(int k) {

if (k>m) Print () ; int s=0;

for (int i=k; i<=m; i++)

s=max( s , c [ i ]) ; DP(s);

for (int i=k; i<=m; i++) if (! can [ c [ i ] ] ) return; i n t now=p [ k ] ; tot [now] =0;

for (int i=c[k];i;i —=a [ path [ i ] ] )

ans [now] [ tot [now]++] = path [ i ] ; for (int i =0; i <t ot [now ] ; i++)

used [ ans [ now ] [ i ] ] = 1 ; Search (k+1) ;

for (int i =0; i <t ot [now ] ; i++) used [ ans [now] [ i ] ]=0;

}

int main () {

srand (time (0) ^19930130) ; scanf ("%d%d" ,&n,&m) ; for (int i = 1; i <=n ; i ++) scanf ("%d" ,&a [ i ]) ; for (int i =1; i<=m; i++) scanf ("%d" ,&c [ i ]) ;

for (int i = 1; i <=n ; i ++)

order [ i]= i ; for (int i =1; i<=m; i++)

P [ i]=i ; for (;;) {

for (int i =1; i < = 10000; i++) { int x=rand ()%n+1; int y=rand ()%n+1; swap(order[x],order[y]);

}

for (int i =1; i<=m; i++) { int x=rand ()%m+1; int y=rand ()%m+1;

swap(c[x],c[y]); swap(p[x],p[y]);

}

Search(1);

}

return 0;

}

А.2. Решение 2 208 365 (язык Pascal)

program aa; const

maxm = 10 + 2; maxn = 100 + 5; maxs = 10000; var

f : ar ray [ 0 .. maxn , 0 .. maxs ] of boolean; left : array [ 1 .. maxn] of longint ; row , idrow : array [ 1 .. maxm] of longint; ship , id , belong : array [ 1 .. maxn] of longint; i , j , k , tmp , n ,m: longint ; procedure Init ; begin

readln (n ,m) ;

for i: = 1 to n do readln ( ship [ i ]) ;

for i : = 1 to m do

begin

readln (row [ i ]) ; idrow [ i ]: = i ;

end ;

for i := 1 to m do

for j := i+1 to m do if row [ i ] <row [ j ] then begin

tmp: = row [ i ] ; row [ i ]: = row [ j ] ; row [ j ]: = tmp ;

tmp: = idrow [i ]; idrow [i]: = idrow[j ]; idrow [ j ]: = tmp;

end ;

for i := 1 to n do id [ i ]: = i ; end ;

procedure print ; begin

for i := 1 to m do begin

k:=0;

for j: = 1 to n do if idrow [ belong [ j ]]= i then

inc(k); writeln (k) ;

for j: = 1 to n do if idrow [ belong [ j ]]= i then

write ( ship [ j ], ' '); writeln ;

end ; halt ; end ;

procedure dfs ( x:longint ); var

i , tot : longint ; begin

if x=0 then Print ;

//dp

tot : = 0;k: = 0;

for i := 1 to n do if belong [ id [ i ]] =0 then begin

inc(tot) ; left [ tot] : = id [i ]; inc(k,ship[id [ i ] ]) ;

end ;

f [0 ,0]: = true ;

for i := 1 to tot do fillchar( f [ i ], k+1, false ); k:=0;

for i := 1 to tot do begin

for j := 0 to k do if f[i — 1,j] then begin

f[i ,j]: = true;f[i , j +s hip [ left [i]]]: = true;

end ;

inc(k,ship[left [i ] ] ) ;

end ; k:=0;

for i := 1 to x do begin

if not f [ tot , row [ i ] ] then exit; if not f[tot —1,row[i]] then inc(k);

end ;

i f k>1 then exit ; k := r ow [ x ] ;

for i := tot downto 1 do if not f[i — 1,k] then begin

belong [left [ i ] ] : = x ; dec( k,ship[ le ft [ i ] ] ) ;

end ;

dfs (x-1) ;

for i := 1 to n do if belong[i]=x then belong [ i ]: = 0; end ;

procedure Main; begin

f [0 ,0]: = true ; while true do begin

for i := 1 to n do begin

j : = random(n) +1; k: = random(n) +1;

tmp : = id[j ] ; id [j ]:=id [k] ; id [k]: = tmp;

end ; d f s (m) ;

end ; end ; begin

Init ; Main ;

end .

А.3. Решение 2 072 705 (язык C++)

#include <stdio.h> #include <stdlib.h> #include <memory. h> #include <time.h>

int N, M, tmp = 0;

int Rx [ 1 5 ] [ 2 ] , R [ 1 5 ] [ 2 ] , S[105], vis[105]; char valid [1 5] [20000] ;

int search(int x, int y){

if (clock () > 250000 && tmp < 1) return 0; if (clock () > 500000 && tmp < 2) return 0; if (R[x ] [0 ] == 0) {

memset ( v a l i d [ x + 1], 0, sizeof(int) * 301); valid [x + 1] [0] = 1; for (int i = 0; i < N; i ++){ if (vis[i] != —1) continue; for (int j = 300; j >= 0; j ——)

valid [x + 1] [j + S[i ]] |= valid [x + 1][j ];

}

for (int i = 0; i < M; i ++)

if (R[ i ] [ 0 ] <= 300 && ! valid [x + 1][R[i][0]]) return 0; return search(x + 1 , 0);

}

if (y >= N ||

(R[x ] [ 0 ] <= 300 && ! valid [x] [R[x] [0] ] ) || (R[x] [0] <= 19000 && ! valid [ 0 ] [R[x ] [ 0 ] ] ) ) return 0; i f ( x >= M — 1 ) {

for (int i = 0; i < N; i ++)

if ( vis [ i ] == —1) vis [ i ] = M — 1; for (int i = 0; i < M; i ++){ int p, count = 0; for (int j = 0; j < M; j ++) if (R[ j ] [ 1 ] == i) p = j; for (int j = 0; j <N; j ++) count += (vis [ j ] == p) ; printf("%d\n" , count); for (int j = 0; j < N; j ++)

if ( vis [ j ] == p) printf ("%d ", S [ j ]) ; p r int f("\n") ;

}

return 1;

}

while (S [y] > R[x ] [ 0 ] ) y ++; while (vis[y] != —1) y ++; i n t yx = y ;

while (S[yx] == S [y ]) yx ++; if (search(x, yx)) return 1;

R[x][0] -= S [ y ] ; vis [y] = x;

if (search(x, y + 1)) return 1; vis [y] = -1;

R[x][0] += S[y] ;

return 0;

}

int inline qCmp(void const * a, void const * b){ return *(int *)a — *(int *)b;

}

int inline qCmp2(void const * a, void const * b){ return *(int *)b — *(int *)a;

}

int main ( void ) {

memset(vis, 255, sizeof(vis)); scanf ("%d%d" , &N, &M) ;

for (int i = 0; i < N; i ++) scanf("%d" , &S [ i]) ;

for (int i = 0; i < M; i ++) scanf ("%d" , &Rx[i][0]);

for (int i = 0; i < M; i ++) Rx[i][1] = i;

memset(valid , 0, sizeof ( valid )) ;

valid [0] [0] = 1;

for (int i = 0; i < N; i ++)

for (int j = 19000; j >= 0; j —)

valid [0] [ j + S [ i ] ] |= valid [0] [ j ] ; memcpy(R, Rx, sizeof (Rx) ) ; qsort(S, N, sizeof (int), qCmp2) ; qsort(R, M, sizeof(int) * 2, qCmp) ; if (!search (0 , 0)){

memset(vis, 255, sizeof(vis)); memset(valid , 0, sizeof ( valid )) ;

valid [0] [0] = 1;

for (int i = 0; i < N; i ++)

for (int j = 19000; j >= 0; j —)