II. ИТОГИ НАУЧНЫХ ИССЛЕДОВАНИЙ
2.1. Важнейшие научные результаты
Первый результат:
Авторы: д. ф.-м. н. Ремесленников В.Н., к. ф.-м. н. Даниярова Э.Ю.
Сформулированы и доказаны четыре объединяющих теоремы в универсальной алгебраической геометрии для произвольных алгебраических систем, язык (сигнатура) которых может содержать как функциональные, так и предикатные символы.
Сформулированные теоремы позволяют изучать множества решений систем уравнений и их координатные алгебры для любой алгебраической системы как методами теории моделей, так и алгебраическими и геометро-топологическими методами.
Результат опубликован:
1. Даниярова Э.Ю., Мясников А.Г., Ремесленников В.Н. Универсальная алгебраическая геометрия // ДАН, 2011, том 439, №6, с. 730-732.
2. Daniyarova E., Miasnikov A., Remeslennikov V., Unification theorems in al-gebraic geometry, Algebra and Discrete Mathematics, 1 (2008), 80-112.
3. Daniyarova E., Myasnikov A., Remeslennikov V. Algebraic Geometry Over Algebraic Structures III: Equationally Noetherian Property and Compactness // Southeast Asian Bulletin of Mathematics (2011) 35, 35-68.
4. Даниярова Э.Ю., Мясников А.Г., Ремесленников В.Н. Алгебраическая геометрия над алгебраическими системами. IV. Эквациональные области и ко-области // Алгебра и логика, 49:6 (2010), 715–756.
Второй результат:
Авторы: д.ф.-м.н. Забудский Г.Г., аспирант Лагздин А.Ю.
Предложены и обоснованы полиномиальные алгоритмы решения квадратичной задачи о назначениях в теоретико-графовой постановке на древовидных сетях с минимаксным и минисуммным критериями для структуры связей в виде цепи, разработан и экспериментально исследован параллельный алгоритм динамического программирования для общей структуры связей.
Для квадратичной задачи о назначениях, играющей важную роль в теории и приложениях дискретной оптимизации, найдены новые полиномиально разрешимые случаи. В частности предложены и обоснованы алгоритмы полиномиальной трудоемкости для постановки указанной задачи на древовидных сетях при условии использования минимаксного и минисуммного критериев со структурой связей между вершинами в виде цепей. Для сетей более общей структуры разработан алгоритм динамического программирования с применением параллельных вычислений.
Результат опубликован:
Забудский Г.Г., Лагздин А.Ю. Полиномиальные алгоритмы решения квадратичной задачи о назначениях на сетях // Журнал вычислительной математики и математической физики. Т. 50. № 11. 2010. С. 2052–2059.
Забудский Г.Г., Лагздин А.Ю. Полиномиальные алгоритмы решения минимаксной квадратичной задачи на сетях // Дискретный анализ и исследование операций. Т. 18, № 4. 2011. С. 48–64.
Забудский Г.Г., Лагздин А.Ю. Алгоритм решения квадратичной задачи о назначениях с минимаксным критерием на дереве // Материалы VII Международной научно-технической конференции «Динамика систем, механизмов и машин» Омск, 2009. Т. 3. С. 23–27.
Забудский Г.Г., Лагздин А.Ю. Эффективные алгоритмы решения специальных случаев квадратичной задачи о назначениях на сетях // Доклады 8 Международной конференции «Интеллектуализация обработки информации ИОИ-2010». М.: МАКС Пресс, 2010. С. 255–257.
Забудский Г.Г. Анализ эффективности параллельного алгоритма динамического программирования для квадратичной задачи о назначениях на дереве// Информационный бюллетень Ассоциации математического программирования № 12, Екатеринбург, 2011.- С. 176.
Области применения
Размещение отделений больниц
Проектирование генеральных планов предприятий и планов цехов
Проектирование материнских плат
|
|
полиномиальные
алгоритмы
|
динамическое
программирование
| |
