Важнейшие результаты за 2009 г.
1.1.1. Алгебра, теория чисел, математическая логика
Автор: Директор, академик Ю. Л. Ершов
Установлено, что экзистенционально замкнутые поля в классе счетных подполей классического кольца аделей являются так называемыми удивительными расширениями поля рациональных чисел.
[1] Ершов Ю. Л. О подполях кольца аделей // Алгебра и логика, 2009, 48, 6.
Автор: С.н.с., к.ф.-м.н. А. И. Стукачёв
Для полурешеток степеней моделей по определимости с операцией скачка, согласованной с естественными вложениями полурешеток тьюринговых степеней и степеней перечислимости, доказана теорема об обращении скачка.
[1] А. И. Стукачёв, О степенях представимости моделей. I // Алгебра и логика, 2007, т. 46, стр. 763-788.
[2] А. И. Стукачёв, О степенях представимости моделей. II // Алгебра и логика, 2008, т. 47, стр. 108-126.
[3] А. И. Стукачёв, Теорема об обращении скачка для полурешеток $\Sigma$-степеней // Сибирские электронные математические известия, 2009, т. 6, стр. 182-190.
Автор: В.н.с., д.ф.-м.н. Л. Л. Максимова
Завершена полная классификация суперинтуиционистских логик и расширений модальной логики Гжегорчика в соответствии с интерполяционными свойствами и свойствами неявной определимости.
[1] Л. Л. Максимова. Ограниченное интерполяционное свойство в суперинтуиционистских логиках // Алгебра и логика, 48, № 1 (2009), 54-89.
[2] L. Maksimova. Problem of restricted interpolation in superintuitionistic and some modal logics //Logic Journal of the IGPL, 2009; doi: 10.1093/jigpal/jzp040, 14 pp.
Автор: С.н.с., к.ф.-м.н. О. В. Кудинов, совместно с В. Л. Селивановым
Доказана биинтерпретируемость с арифметикой ряда структур гомоморфно упорядоченных размеченных деревьев и лесов, возникших при изучении начальных сегментов полурешетки Вэджа (для случая $k$-разбиений)
[1] Kudinov O. V., Selivanov V. L. Undecidability in the Homomorphic Quasiorder of Finite Labelled Forests // Journal of Logic and Computation, 17(6), 1135-1151 (2007)
[2] Kudinov O. V., Selivanov V. L., Zhukov A. V. Definability in the $h$-quasiorder of labeled forests // Annals of Pure and Applied Logic, 2009, 159(3): 318-332.
[3] Oleg V. Kudinov, Victor L. Selivanov Definability in the Infix Order on Words // Volker Diekert, Dirk Nowotka (Eds.): Proceedings of DLT 2009, Stuttgart, Germany, Lecture Notes in Computer Science, 2009, 5583, 454-465.
[4] Oleg V. Kudinov, Victor L. Selivanov A Gandy Theorem for Abstract Structures and Applications to First-Order Definability // K. Ambos-Spies, B. Lowe, W. Merkle (Eds.): Proceedings of CiE 2009, Heidelberg, Germany, Lecture Notes in Computer Science, 2009, 5635,290-299.
Автор: Зав.лабораторией, д.ф.-м.н. Е. А. Палютин
Получены необходимые и достаточные условия существования структурной теории для Фреше-замкнутых классов.
[1] Е. А.Палютин, Простые модели над нормальным базисным множеством, Сиб. электрон. матем. изв., 2007, 4, 596-604.
[2] Е. А. Палютин, Стабильные теории Фреше-степеней, Сиб. электрон. матем. известия, 2008, Т. 5 С. 699-707.
[3] Е. А. Палютин, Элиминация кванторов в фреше-замкнутых классах без интерпретации графов, Труды Международной научной конференции "Современные проблемы математики, информатики и управления" г. Алматы 2008 г. стр. 469.
[4] E. A. Palyutin, Non-commutative stable theories of Freshe-power are non-classificable, Алгебра и теория моделей, 7. Сборник трудов (Под ред. А. Г. Пинуса и С. В. Судоплатова). Новосибирск: изд-во НГТУ, 2009, 60-84.
[5] Е. А. Палютин, Интерпретация графов в некоммутативных теориях Фреше-степеней, Фундаментальная и прикладная математика, 2009, т. 15, N 5, С. 201-225.
[6] Международная конференция «Мальцевские чтения», Институт математики им. С. Л. Соболева СО РАН Новосибирск, 19-23 ноября 2008 г.
[7] Международная школа-семинар «Новые алгебро-логические методы решения систем уравнений в алгебраических системах», Омск, 16-22 августа 2009 г.
[8] Международная научная конференция «Вычислимость и модели», Восточно-Казахстанский государственный технический университет им. Д. Серикбаева, Усть-Каменогорск, Казахстан, 30 августа – 1 сентября 2009 г.
Авторы: Г.н.с., д.ф.-м.н. А. В. Васильев, н.с., к.ф.-м.н., М. А. Гречкосеева, зав.отделом, чл.-к. РАН В. Д. Мазуров
Доказано, что конечная простая группа и группа, имеющие одинаковый порядок и множество порядков элементов, изоморфны.
[1] Васильев А. В., Гречкосеева М. А., Мазуров В. Д. О конечных группах, изоспектральных простым симплектическим и ортогональным группам // Сиб. мат. журн. 2009. Т. 50, №6. С. 1223-1245.
[2] Васильев А. В., Гречкосеева М. А., Мазуров В. Д. Характеризация конечных простых групп их спектром и порядком // Алгебра и логика. 2009. Т. 49, №6.
Автор: Г.н.с., д.ф.-м.н. Н. С. Романовский
Доказана нётеровость по уравнениям произвольной жесткой разрешимой группы. Описаны координатные группы неприводимых алгебраических множеств над делимыми распавшимися жесткими группами.
[1] Н. С. Романовский «Делимые жесткие группы», Алгебра и логика, т.47, № 6, 2008, 762-776.
[2] Н. С. Романовский «Нетеровость по уравнениям жестких разрешимых групп», Алгебра и логика, т.48, № 2, 2009, 258- 279.
[3] Н. С. Романовский «Неприводимые алгебраические множества над распавшимися делимыми жесткими группами», Алгебра и логика, т.48, № 6, 2009, 721-747.
Автор: Н.с., к.ф.-м.н., А. А. Бутурлакин
Получено описание спектров всех конечных простых классических групп.
[1] Бутурлакин А. А., Гречкосеева А. А. Циклическое строение максимальных торов в конечных классических группах // Алгебра и логика. 2007. Т. 46, № 2. C. 129-156.
[2] Бутурлакин А. А. Спектры конечных линейных и унитарных групп // Алгебра и логика. 2008. Т. 47, № 2. C. 157-173.
[3] Бутурлакин А. А. Спектры конечных классических групп и изоспектральные простые группы // ИМ СО РАН. 2009. препринт № 232.
[4] Бутурлакин А. А. Спектры конечных симплектических и ортогональных групп // Мат. труды (в печати)
1.1.2. Геометрия и топология
Авторы: Г.н.с., д.ф.-м.н. А. Д. Медных, студент НГУ А. А. Колпаков
Разработан новый метод нахождения сферических структур на узлах и зацеплениях, и дано их описание.
[1] Колпаков А. А., Медных А. Д. Сферические структуры на торических узлах и зацеплениях // Сиб. мат. журн. 2009. Т. 50, N 5, С. 1083-1096.
Автор: Аспирант, Н. В. Абросимов
Решена известная проблема Зейделя об объемах неевклидовых тетраэдров.
[1] Абросимов Н. В. К решению проблемы Зейделя об объемах неевклидовых тетраэдров // Сиб. электрон. мат. изв. 2009. Т. 6. С. 211-218.
Автор: Г.н.с., д.ф.-м.н. С. С. Кутателадзе
Даны описания Парето-оптимальных решений многоцелевых задач выпуклой геометрии.
[1] Кутателадзе С.С. Многоцелевые задачи выпуклой геометрии // Сибирский мат. журн. 2009. Т. 50, № 5. С. 1123-1136
Автор: С.н.с., к.ф.-м.н., Я. В. Базайкин
Найдено условие представимости лоренцевых групп голономии псевдо-римановых многообразий.
[1] Я. В. Базайкин. Глобально гиперболические пространства со специальными группами голономии // Сибирский математический журнал. 2009. Том 50, № 4. С. 721-736.
Автор: В.н.с., д.ф.-м.н. В. П. Голубятников
Доказаны теоремы единственности восстановления слабо выпуклых тел по формам их круговых проекций, получены соответствующие оценки устойчивости. Установлены достаточные условия выпуклости плоской фигуры, однозначно определяемой двумя своими выпуклыми томографическими проекциями.
[1] СМЖ (в соавторстве с В. Ю. Ровенским), т.50, N 5, 2009, с. 1037-1049. SibAM, V. 19, N 2, 2009, 85-90.
1.1.3. Математический анализ
Автор: С.н.с., к.ф.-м.н. А. В. Грешнов
Доказано существование однородной нильпотентной аппроксимации для $C^1$-гладких векторных полей.
[1] Грешнов А. В. О применении методов группового анализа дифференциальных уравнений для некоторых систем $C^1$-гладких векторных полей // Сиб. Мат. журн. 2009. Т. 50, № 1. С. 47-62
Автор: С.н.с., д.ф.-м.н. М. В. Коробков
Найдены необходимые и достаточные условия однозначной определѐнности областей в евклидовых пространствах относительной метрикой границы, индуцированной внутренней метрикой области.
[1] Коробков М. В. Критерий однозначной определенности областей в евклидовых пространствах метрикой границы, индуцированной внутренней метрикой области // Математические труды, 2009, Т.12, No.2, С.52-96.
1.1.4. Дифференциальные уравнения и математическая физика
Авторы: Зав.лабораторией, д.ф.-м.н. А. М. Блохин, в.н.с., д.ф.-м.н. Д. Л. Ткачѐв
На линейном уровне исследована задача об обтекании бесконечного плоского клина сверхзвуковым стационарным потоком газа. Доказана асимптотическая устойчивость по Ляпунову стационарного решения в случае слабой ударной волны для финитных начальных данных. Тем самым дано обоснование известной гипотезы Куранта-Фридрихса.
[1] А. М. Блохин, Д. Л. Ткачев. Устойчивость сверхзвукового обтекания клина со слабой ударной волной // Мат. сборник, 2009, 200, №2, 3-30.
[2] Blokhin A. M., Tkachev D. L. Justification of the Courant-Friedrich’s hypothesis in the case of a weak shock. Part I. Presentation of solution to linear problem // Mathematical Analysis and Applications, 2009, Vol. 355. Pp.41-52.
Автор: В.н.с., д.ф.-м.н. Ю. Л. Трахинин
Доказана локальная по времени теорема существования и единственности в пространствах Соболева для уравнений газовой динамики с нулевым давлением на свободной границе "газ-вакуум" при условии, что плотность газа строго положительна на этой границе в начальный момент времени.
[1] Trakhinin Y. Local existence for the free boundary problem for nonrelativistic and relativistic compressible Euler equations with a vacuum boundary condition. Comm. Pure Appl. Math. 62 (2009), 1551-1594.
1.1.5. Теория вероятностей и математическая статистика
Авторы: Советник РАН, академик Боровков А. А., с.н.с., к.ф.-м.н. Рузанкин П. С.
Найдена аппроксимация для распределений, возникающих при изучении так называемых переходных явлений для случайных блужданий, порожденных суммами случайных величин, не имеющих математических ожиданий. Ранее аналогичные задачи исследовались лишь для конечных математических ожиданий. Полученные результаты позволяют найти асимптотику распределения времени ожидания в нагруженных системах обслуживания, у которых времена обслуживания имеют медленно убывающие на бесконечности распределения.
[1] А. А. Боровков, П. С. Рузанкин. Переходные явления для случайных блужданий при отсутствии математического ожидания скачков. Сибирский математический журнал, 2009, т. 50, № 5, с. 987-1009.
Авторы: В.н.с., д.ф.-м.н. Фосс С. Г., В.н.с., д.ф.-м.н. Коршунов Д. А.
Установлен ряд базовых свойств распределений, медленно убывающих на бесконечности. Эти распределения играют существенную роль при изучении стохастических моделей систем обслуживания и коммуникационных систем.
[1] S. Foss, D. Korshunov, Lower limits and equivalences for convolution tails. The Annals of Probability, 2007, V. 35, P. 366- 383.
[2] Д. Денисов, Д. Коршунов, С. Фосс, Нижние пределы для хвостов распределений случайно остановленных сумм. Теория вероятностей и ее применения, 2007, Т. 52, С. 794-802.
[3] D. Denisov, S. Foss, D. Korshunov, On lower limits and equivalences for distribution tails of randomly stopped sums. Bernoulli, 2008, V. 14, P. 391-404.
[4] D. Denisov, S. Foss, D. Korshunov, Asymptotics of randomly stopped sums in the presence of heavy tails. Accepted to "Bernoulli".
1.1.6. Вычислительная математика
Автор: Г.н.с., д.ф.-м.н. Кабанихин С. И.
Получены новые оценки скорости сходимости градиентных методов решения обратных и некорректных задач.
[1] Kabanikhin S. I. Conditional stability stopping rule for gradient methods applied to inverse and ill-posed problems. // J. of Inverse and Ill-Posed Problems, 2006. 14(8), 805-812.
[2] Kabanikhin S. I. Definitions and Examples of Inverse and Ill-Posed Problems. // J. Inv. Ill-Posed Problems. 2008. 16(4), 317- 357.
[3] Kabanikhin S. I. and Schieck M. Impact of conditional stability: сonvergence rates for general linear regularization methods // J. Inv. Ill-Posed Problems. 2008. 16(3), 267-282.
[4] Кабанихин С. И. Обратные и некорректные задачи. Сибирское научное издательство, 2009. 450 с. (второе издание).
1.1.7. Математическое моделирование
Автор: Г.н.с., д.ф.-м.н. В. М. Александров
Разработан метод оптимального по быстродействию управления в реальном времени линейными системами с возмущениями.
[1] Александров В. М. Последовательный синтез оптимального по быстродействию управления в реальном времени // Автоматика и телемеханика. 2008. № 8. С. 2-24.
[2] Александров В. М. Последовательный синтез оптимального по быстродействию управления линейными системами с возмущениями // Сибирский журнал вычислительной математики. 2008. Т. 11, № 3. С. 251-270.
[3] Александров В. М. Оптимальное по быстродействию управление в реальном времени линейными системами с возмущениями // Вестник НГУ. Серия: математика, механика, информатика. 2008. Т. 8, вып. 3. С. 3-25.
[4] Александров В. М. Особенности движения динамических систем с возмущениями в окрестности многообразий переключений // Автоматика и телемеханика. 2009. № 4. С. 58-77.
[5] Александров В. М. Численный метод решения линейной задачи минимизации расхода ресурсов // Сибирский журнал вычислительной математики. 2009. Т. 12, № 3. С. 247-267.
[6] Александров В. М. Оптимальное по быстродействию позиционно-программное управление линейными динамическими системами // Сибирские электронные математические известия. 2009. Т. 6. С. 385-439.
Автор: Г.н.с., д.ф.-м.н. В. А. Васильев
Найдена аксиоматизация обобщенного расширения Оуэна, как для конечных, так и для широкого класса бесконечных игр. Установлено, что для неатомических игр такая аксиоматизация совпадает с описанием мультипликативного продолжения Аумана-Шепли.
[1] Васильев В. А. Об одной аксиоматизации обобщенного расширения Оуэна. «Математическая Теория Игр и её Приложения», 2009, т.1, в.2, с. 3 - 13.
Автор: С.н.с., к.ф.-м.н. И. А. Быкадоров, совместно с С. Вианелло, Е. Моретти, С. Фунари, А. Эллеро (Италия)
Разработаны и исследованы модели для поиска оптимальной маркетинговой политики. Изучен специальный класс задач дробного оптимального управления, возникающих при анализе модели максимизации эффективности рекламных затрат.
[1] Bykadorov I., Ellero A., Moretti E., Vianello S. “The role of retailer’s performance in optimal wholesale price discount policies.” - European Journal of Operational Research, 2009, vol. 194, no. 2, p. 538–550.
[2] Bykadorov I., Ellero A., Funari S., Moretti E. “Dinkelbach Approach to Solving a Class of Fractional Optimal Control Problems.” – Journal of Optimization Theory and Applications, 2009, vol. 142, no. 1, p. 55–66.
1.1.10. Дискретная математика
Авторы: Зав. лабораторией, д.ф.-м.н. О. В. Бородин, вед. инж., А. О. Иванова, в.н.с., д.ф.-м.н., А. В. Косточка
Получены новые верхние оценки хроматического числа в задачах игровой раскраски, реберного разложения на лес и подграф для нескольких классов разреженных плоских графов. Опровергнута известная гипотеза (2002) о разбиении ребер плоского графа.
[1] O. V. Borodin, A. O. Ivanova, B. S. Stechkin, Decomposing a planar graph into a forest and a subgraph of restricted maximum degree, Siberian Electronic Math. Reports 4 (2007). 296-299.
[2] O. V. Borodin, A. O. Ivanova, A. V. Kostochka and N. N. Sheikh, Minimax degrees of quasiplane graphs without 4-faces, Siberian Electronic Math. Reports 4 (2007) 435-439.
[3] O. V. Borodin, A. V. Kostochka, N. N. Sheikh, and Gexin Yu, Decomposing a planar graph with girth nine into a forest and a matching, Europ. J. Combin., 29 (2008) 1235-1241.
[4] O. V. Borodin, A. O. Ivanova, A. V. Kostochka, N. N. Sheikh, Minimax degrees of quasiplanar graphs without short cycles other than triangles, Taiwanese J. of Math. 12 (2008), no. 4, 873-886.
[5] O. V. Borodin, A. V. Kostochka, N. N. Sheikh, and Gexin Yu, $M$-degrees of quadrangle-free planar graphs, J. of Graph Theory 60, 1, (2009) 80-85.
[6] O. V. Borodin, A. O. Ivanova, A. V. Kostochka, N. N. Sheikh, Planar graphs decomposable into a forest and a matching, Discrete Math. 309 (2009) 277-279.
[7] O. V. Borodin, A. O. Ivanova, A. V. Kostochka and N. N. Sheikh, Decompositions of quadrangle-free planar graphs, Discus. Math. Graph Theory 29 (2009) 87-99.
Авторы: С.н.с., к.ф.-м.н. С. В. Августинович, с.н.с., к.ф.-м.н. Д. С. Кротов
Доказано, что всякий двоичный код, исправляющий одну ошибку, может быть вложен в некоторый 1-совершенный код большей длины.
[1] S. V. Avgustinovich, D. S. Krotov. Embedding in a Perfect Code // J. Combin. Designs. 17(5) 2009, 419–423.
Автор: В.н.с., д.ф.-м.н. С. А. Малюгин
Построены несистематические совершенные коды над любым конечным полем.
[1] Малюгин С. А. О несистематических совершенных кодах над конечными полями // Дискрет. анализ и исслед. опер, 2009. Т.16, N 1. C. 44-63.
Авторы: С.н.с., к.ф.-м.н Агеев А. А ., в.н.с., д.ф.-м.н Гимади Э. Х., вед. инж. Курочкин А. А.
Обоснован полиномиальный точный алгоритм с улучшенной на порядок временной сложностью для решения задачи размещения с одинаковыми производственными мощностями предприятий на путевом графе.
[1] А. А. Агеев, Э. Х. Гимади, А. А. Курочкин. Полиномиальный алгоритм решения задачи размещения на цепи с одинаковыми ограничениями на объемы производства предприятий // Дискретный анализ и исследование операций. 2009. Т. 16, № 5, С. 3–18.
Авторы: С.н.с., к.ф.-м.н. Кононов А. В., в.н.с., д.ф.-м.н. Севастьянов С. В.
Получены структурные свойства оптимальных расписаний с прерываниями, позволившие обобщить большое число ранее известных результатов о сложности задач и закрывающие две ранее открытых проблемы о существовании оптимального расписания с конечным числом прерываний.
[1] Ph. Baptiste, J. Carlier, A. Kononov, M. Queyranne, S. Sevastyanov, and M. Sviridenko, Integrality Property in Preemptive Parallel Machine Scheduling, In: A. Frid a.o. (Eds.), Computer Science – Theory and Applications, 4th International Computer Science Symposium in Russia, CSA 2009, Novosibirsk, Russia, August 2009, Proceedings, Lecture Notes in Comp. Sci., 5675, Springer-Verlag, 2009, 38-46.
Автор: С.н.с., к.ф.-м.н. А. В. Еремеев (ОФ ИМ СО РАН)
Установлена полиномиальная разрешимость задачи оптимальной рекомбинации в генетических алгоритмах для задач упаковки и разбиения множества, простейшей задачи размещения производства, а также задач булевого линейного программирования, имеющих не более двух переменных в каждом ограничении.
[1] Borisovsky P., Dolgui A., Eremeev A. Genetic algorithms for a supply management problem: MIP-recombination vs greedy decoder // European Journal of Operational Research. Vol. 195 N 3, 2009, P. 770-779.
[2] Dolgui A., Eremeev A. and Guschinskaya O. MIP-based GRASP and genetic algorithm for balancing transfer lines // In: Matheuristics. Hybridizing Meta-heuristics and Mathematical Programming / Maniezzo, V., Stutzle, T., Voss, S. (eds.) Series Annals of Information Systems, Vol. 10, Springer, 2010, P. 189-208.
[3] Dolgui A., Eremeev A., Guschinskaya O. MIP-based heuristics for scheduling batch production with shifts // Book of Abstracts of GOR Workshop "Scheduling in the Process Industry", Bad Honnef, Germany, 2008. P. 8.
[4]Eremeev A. V. NP-hard cases of optimal recombination. Abstracts Collection of Dagstuhl Seminar 08051 "Theory of Evolutionary Algorithms", Dagstuhl, 2008, P.2.
[5] Eremeev A. V. On complexity of optimal recombination for binary representations of solutions // Evolutionary Computation, Vol. 16 N 1, 2008, P. 127-147.
[6] Еремеев А. В., Коваленко Ю. В. Приближенное решение одной задачи составления расписаний для многопродуктового производства // Материалы Всероссийской конференции "Проблемы оптимизации и экономические приложения". Омск, 2009. - С. 223.
1.1.11. Информационные системы
Авторы: С.н.с., д.т.н. Бериков В. Б., г.н.с., д.т.н. Г. С. Лбов
Разработаны методы кластерного анализа, основанные на коллективе (ансамбле) деревьев решений. Исследованы вероятностные свойства ансамбля. Методы применены в задаче сегментации спутниковых изображений.
[1] Бериков В. Б., Лбов Г. С. Выбор оптимальной сложности класса логических решающих функций в задачах распознавания образов // Доклады Академии наук. 2007. Том 417, N 1. C. 26-29.
[2] Лбов Г. С., Неделько В. М., Неделько С. В. Метод адаптивного поиска логической решающей функции. // Сибирский журнал индустриальной математики, 2009, т. ХII, № 3 (39). С. 66–74.
[3] Бериков В. Б. Кластерный анализ с использованием коллектива деревьев решений // Научный вестник НГТУ. 2009. № 3 (36). С.67-76.
[4] Berikov V. B. Construction of the ensemble of logical models in cluster analysis // D.-S. Huang et al. (Eds.) Emerging Intelligent Computing Technology and Applications. With aspects of artificial intelligence. ICIC 2009. Lecture Notes in Artificial Intelligence, LNAI 5755. Springer-Verlag: Berlin, Heidelberg. 2009. P. 581–590.
[5] Бериков В. Б. Построение ансамбля логических моделей в кластерном анализе // Математические методы распознавания образов: 14-я Всероссийская конференция. Владимирская обл., г. Суздаль. 21–26 сентября 2009 г.: Сборник докладов. – М.: Макс-Пресс, 2009. – С. 85-88.
[6] Пестунов И. А., Куликова Е. А., Бериков В. Б., Махатков И. Д. Сеточный алгоритм кластеризации с использованием ансамблевого подхода к принятию решений // Горный информационно-аналитический бюллетень. – 2009. - № 12. (принята в печать).
1.7.1. Физика элементарных частиц и фундаментальных взаимодействий
Авторы: Зав. лабораторией, д.ф.-м.н. Н. Н. Ачасов, в.н.с., д.ф.-м.н. А. А. Кожевников
Показана несостоятельность скрытой локальной симметрии при описании процесса множественного рождения пи-мезонов в электрон-позитронных столкновениях при низких энергиях.
[1] Н. Н. Ачасов и А. А. Кожевников, Письма в ЖЭТФ 88, 3 (2008).
[2] N. N. Achasov and A. A. Kozhevnikov, European Physical Journal A 38, 61 (2008).