Сборники тезисов • Информационные и интеллектуальные системы и технологии • Технологии программирования и искусственный интеллект
Сборник тезисов докладов конгресса молодых ученых. Электронное издание. – СПб: Университет ИТМО, 2015.
Разработка структуры данных для инкрементальной недоминирующей сортировки
УДК: 004.85
Аннотация:
Разработан новый алгоритм для инкрементальной недоминирующей сортировки двумерных точек. Структура данных, хранящая уровни недоминирования (ранги), основана на дереве Декартовых деревьев. Если есть N точек на M уровнях, время вставки составляет O(M (1 + log(N / M)) + log M log (N / log M)), то есть O(N) в худшем случае. Алгоритм может использоваться для эффективной реализации алгоритмов многокритериальной оптимизации (например, NSGA-II).Предложен метод генерации покрывающих наборов тестов для распределенных управляющих систем, представленных в стандарте IEC 61499. Метод основан на сведении поставленной задачи к более общей задаче генерации тестов покрытия для программного кода, а также на эволюционных вычислениях. Экспериментальное исследование метода на двух программных системах, известных из литературы, доказывает возможность его применения.