Доказано, что всякая центрированная функция (сумма значений в каждом шаре радиуса 1 равна нулю), заданная на дискретном пространстве с метрикой Хэмминга, состоящем из всех вершин n-мерного единичного куба, может быть восстановлена внутри произвольной сферы по ее значениям на этой сфере.
Для широкого класса задач теории расписаний, в которых допускается прерывание операций, получен ряд общих результатов, касающихся существования и структурных свойств оптимальных решений. Доказана теорема о структуре оптимального решения задач в случае целевых функций вида суммы или максимума конечного числа кусочно-линейных функций, зависящих от моментов завершения операций. Установлены полиномиальные верхние оценки на число прерываний в оптимальном расписании.
Получена верхняя оценка аддитивной сложности слова, зависящая только от кратностей вхождения подслов фиксированной длины и достижимая на наиболее сложных словах.
Разработаны точные и приближенные алгоритмы с гарантированными оценками точности для задачи двухуровневого программирования с ограничениями общего вида на верхнем уровне и с задачей о многовариантном ранце на нижнем уровне.
Для задачи календарного планирования с ограниченными ресурсами разработан новый алгоритм локального поиска, основанный на идее чередующихся окрестностей.
Охарактеризованы равномерно рекуррентные бесконечные слова, имеющие линейно растущую арифметическую сложность.
Дано полное описание фасет многогранника Вебера. Предложен новый подход к сравнительному анализу взвешенных дележей Шепли и вероятностных значений кооперативных игр, основанный на полученной характеризации d-распределений Вебера.
Найдены оценки качества получаемых решений для эволюционных методов типа алгоритма случайного поиска с пересчетом при неудачном шаге, а также условия, при которых эти методы оказываются наилучшими в классе эволюционных алгоритмов.
Предложено формальное описание синтаксиса языка машин состояний UML и его операционной семантики. Определено подмножество этого языка, допускающее эффективное построение. Разработан и реализован алгоритм трансляции спецификаций UML в исполняемый код на языке Java.
|
