Генерация тестов для олимпиадных задач по теории графов с использованием эволюционных алгоритмов

© 2011, М.В. Буздалов

Санкт-Петербургский национальный исследовательский университет информационных технологий, механики и оптики

Полный текст работы
Презентация

Аннотация

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

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

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