Проект Федеральной целевой программы "Интеграция" (раздел 4.1 "Издание научной и учебной литературы в области фундаментальных наук, в том числе серии учебников и учебных пособий") "Подготовка и издание справочника программиста по алгоритмам обработки сводимых графов".
Организации - соисполнители проекта: НГУ, ИСИ СО РАН
Координатор - д.ф.-м.н., профессор В.Н.Касьянов (ИСИ СО РАН)

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

Подготовлена рукопись книги "Сводимые графы и граф-модели в программировании" объемом в 20 п.л. Книга состоит из 11 глав, образующих две части, и предназначена для широкого круга специалистов, использующих методы теории графов при решении своих задач, в первую очередь, для системных и прикладных программистов, а также для специалистов по САПР, конструкторов СБИС и т.д. Книга может быть использована в качестве учебного пособия студентами высших учебных заведений, аспирантами и преподавателями, читающими соответствующие курсы.

Проект по программе "Информатизация России" "Разработка набора инструментов для компонентно-ориентированного программирования в рамках модели СОМ в системе XDS" (шифр проекта 037.01.178.27.1-98).
N гос. Регистрации 01980004928.
Ответственный исполнитель – к.ф.-м.н. Кузьминов Т.В. (ИСИ СО РАН)

Разработаны требования по модификации трансляторов XDS для автоматического порождения структур данных СОМ и модифицировано внутреннее представление системы XDS, разработаны прототип транслятора XIDL и рабочая версия библиотеки автоматической поддержки требований СОМ, осуществлен перенос описания стандартных СОМ-интерфейсов в среду XDS.

Kouzminov T.V. XDS–COM – A COM binding for Oberon–2 and Modula–2 // Joint Bull. of NCC and IIS. Ser. Comput. Sci. – 1998. – N 8. – P.39–56.

Научно-исследовательский проект "Качественные свойства и инвариантные решения уравнений механики сред с существенн нелинейной реологией".

Научный руководитель проекта – академик Ю.И. Шокин .
Ответственные исполнители – д.ф.-м.н., профессор Ю.Н. Григорьев (ИВТ СО РАН), в.н.с., профессор С.В. Мелешко (ИТПМ СО РАН)

Выведены некоторые новые фактор-уравнения для инвариантных решений кинетического уравнения Больцмана с одной независимой инвариантной переменной.

Григорьев Ю.Н., Мелешко С.В. Групповой анализ уравнений Больцмана релаксирующего многокомпонентного газа // Доклады РАН.. –1998. –N 4. –С. 459-462.

Проект "Диаспора НГУ".
Ответственный исполнитель – к.ф.-м.н. Бульонков М.А. (ИСИ СО РАН)

Целью проекта являлось создание базы данных о выпускниках университета и обеспечение удаленного доступа к ней средствами Интернет. Актуальность такой задачи объясняется тем, что в настоящее время данные о выпускниках имеются либо в разрозненном и неполном виде, либо слабо доступны. Наличие средств сбора, структуризации и поддержание актуальности информации в сочетанием со средствами удаленного доступа к ней позволило бы, во-первых, упростить и активизировать общение между выпускниками НГУ, во-вторых, повысить уровень взаимодействия выпускников с НГУ, и, наконец, способствовать улучшению имиджа университета и расширению его связей.

Разработанная система предоставляет средства для систематизации информации о выпускниках НГУ и для ее просмотра как на основе структурных связей, так и с помощью контекстного поиска. Система не ограничивается внутренними структурами и взаимосвязями НГУ и включает в себя понятия из его окружения, как, например, институты СО РАН. Предусмотрены средства отображения информации на английском языке или, по крайней мере, латиницей. Учитывается также введенная в НГУ двухступенчатая система образования, т.е. тот факт, что студент может выпускаться дважды из университета - со званием бакалавра и со званием магистра.

Доступ к базе данных обеспечивается как из WWW просмотрщика MS Internet Explorer (версии 4.0 и выше), так и через отдельную программу, работающую в среде Windows 95/NT. Общая архитектура системы представлена на рисунке.

Рис. 27. Общая архитектура системы.

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

По метеорологическим данным из архива Реанализа Национальных центров прогноза окружающей среды США и Национального центра атмосферных исследований США (NCEP/NCAR) построены траектории для каждого сезона областей воздействия на картину загрязнения в пунктах мониторинга сибирского атмосферного аэрозоля. На основе построения десятисуточных обратных траекторий проведена оценка характерных для каждого сезона областей воздействия на картину загрязнения в пунктах мониторинга. На рисунках 28,29 приведены области влияния для теплого и холодного периодов (цифрами обозначены номера месяцев), которые показывают, что в теплый период изменение состояния атмосферы Пуровского района носит региональный характер, а в холодный - глобальный.

Рис.28. Обратные траектории, построенные по климатическим данным о ветре для г. Самбург (для периода "май-август").

Рис.29. Обратные траектории, построенные по климатическим данным о ветре для г. Самбург (для периода "январь-апрель").

Куценогий К.П., Ривин Г.С. Мониторинг, база данных и математическое моделирование переноса аэрозолей в Сибири // Вычислительные технологии - 1998. - Т. 3, N 5. С. 51 - 62.

Ривин Г.С., Воронина П.В. Математическое моделирование для оценки областей воздействия мощных выбросов загрязняющих веществ в атмосферу // Доклады Первой Международной конференция "Цифровая обработка информации и управление в чрезвычайных ситуациях" (22-25 сентября 1998 г., Минск), том 2. Минск. - 1998. - С. 215-220.

Ривин Г.С., Воронина П.В. Перенос аэрозоля в атмосфере: имитационные эксперименты // Оптика атмосферы и океана. - 1998. - N 7. - С. 741 - 746.

Ривин Г.С., Климова Е.Г., Куликов А.И. Оценка влияния климатических метеоусловий на картину распространения аэрозолей в Сибирском регионе // Оптика атмосферы и океана. - 1998. - N 6. - С. 561 - 566.

Klimova E.G., Rivin G.S. Inverse traces for the passive pollutants // Preprints of the 23rd NATO/CCMS International Technical Meeting on Air Pollution Modellimg and its Aplication, September 28 – October 2, 1998, Varna, Bulgaria. - P. 163 - 167.

Rivin G.S., Klimova E.G. Inverse traces for the passive pollutants: numerical experiments with Reanalysis data. Research activities in atmospheric and oceanic modelling // Research activities in atmospheric and oceanic modelling. - 1998. - WMO/TD-No. 865. - P. 2.31-2.32.

Rivin G.S., Voronina P.V. Transport of aerosols in Siberian region: imitative experiments // Research activities in atmospheric and oceanic modelling. - 1998. - WMO/TD-No. 865. - P. 5.42-5.43.

Интеграционный проект СО РАН N 30. "Исследование и моделирование глобальных и региональных изменений климата, трансформации и переноса загрязняющих примесей в атмосфере Сибири".

В рамках проекта исследуются возможности применения конечноэлементных алгоритмов для численного моделирования задач о динамике волн на поверхности жидкости. Выполнена постановка задачи в рамках одной из нелинейно-дисперсионных моделей мелкой воды, разработан гибридный алгоритм, включающий отдельные компоненты методов конечных элементов и конечных объемов, для решения соответствующих систем линейных уравнений используется пакет ЛИНПАР.

Проведена разработка алгоритма усвоения метеорологических данных, основанного на динамико-стохастическом подходе, предложена схема субоптимального алгоритма Калмана и проведены численные эксперименты по исследованию его свойств. Эксперименты показали эффективность разработанного алгоритма.

Klimova E.G. Asymptotic properties of the data assimilation algorithm based on the Kalman filter // Research activities in atmospheric and oceanic modelling. - 1998. - WMO/TD-No. 865. - P. 1.31-1.32.

Rivin G.S., Klimova E.G. Assimilation system, atmospherical modelling and ecological problems for the Siberian region using NCEP reanalysis data // Procedings of the First WCRP International Conference on Reanalysis, Silver Spring, Maryland, 27 - 31 0ctober, 1997. - 1998. - WMO/TD-No. 876. - P. 398 -401.

Выполнено подробное исследование ряда математических моделей, используемых для описания близких по характеру явлений в задачах длинноволновой гидродинамики. Основное внимание сосредоточено на моделях из работ Перегрина (1967), Железняка, Пелиновского (1985), Кима, Райда, Витакера (1988) и Федотовой, Пашковой (1997), а также рассмотрены линейная, линейная дисперсионная и нелинейная модели мелкой воды.

Главным объектом исследования являются материалы по лабораторным экспериментам, предложенные Международной рабочей группой по изучению наката волн на берег, а также результаты экспериментальных исследований, описанные в работе Seabra-Santos, Renouard & Temperville (1987). Эти данные были использованы для содержательного тестирования моделей и алгоритмов волновой гидродинамики. Сравнение полученных численных результатов с экспериментальными исследованиями позволили плодотворно обсудить вопросы адекватности описания физического процесса в рамках различных моделей мелкой воды, сформулировать критерии оценки результатов и описать собственно качественные и количественные особенности каждой из рассмотренных моделей.

Chubarov L B. , Shkuropatskii D. A. Nonlinear-Dispersive Shallow-water Models of High Order Approximation // International Journal of Computational Fluid Dynamics. –1998 . –V.10. –N 2. –P. 91-100.

Shokin Yu.I., Chubarov L.B., Fedotova Z.I., Pashkova V. Yu., Shkuropatskii D.A. Comparative analysis of hydrodynamic models of tsunami waves on a solution of the problems about of waves interaction with model obstacles // Abstracts of the 7th International Conference on Natural and Man-Made Hazards, May 17-22, 1998. Chania, Greece. - 998. –p.141.

Молодежный проект СО РАН "Иерархическое моделирование пространственных трансзвуковых течений адаптивными методами".

Обладатель гранта - к.ф.-м.н., доцент В.Б. Карамышев (ИВТ СО РАН).

Предложена эффективная технология решения задач трансзвуковой аэродинамики, сочетающая в себе адаптивную многосеточную стратегию [South J., Brandt А., 1977] и алгоритм ускорения сходимости внутренних итераций [А.Г.Слепцов, 1989]. В качестве базового итерационного процесса решения нелинейной системы конечно-разностных уравнений используется упрощенный метод Ньютона. Полученная линейная система решается итерациями по Зейделю (верхней релаксацией для дозвуковых течений). Известно, что для больших, плохо обусловленных систем сеточных уравнений, получаемых для расчета трехмерных сверхкритических течений, релаксационные методы утрачивают свою эффективность. Однако применение к ним алгоритма ускорения итераций позволило построить простой в реализации и быстро сходящийся итерационный процесс. Особенностью предложенной технологии является явная реализация всех вычислений, что делает ее привлекательной при использовании неструктурированных сеток, а также при компьютерном моделировании течений на ЭВМ параллельной архитектуры.

Построенная вычислительная схема была использована для численного исследования трансзвукового обтекания эллипсоидов вращения. На рис.30 представлены результаты расчетов на трех вложенных сетках при Многосеточная технология, с алгоритмом ускорения итераций, позволила сократить время получения приближенного решения на порядок. Аналогичный расчет был получен на адаптивной к скачку уплотнения последовательности сеток (рис. 31). По точности приближенное решение соответствует расчету на регулярной равномерной сетке, содержащей 80x80x80 узлов, а вычислительные затраты сопоставимы с обычным многосеточным моделированием. на трех сетках, содержащих 10x10x10, 19 x 19 x 19 и 37x37x37 узлов.

Рис. 30. Сверхкритический режим обтекания эллипсоида идеальным газом. Распределение давления на, полученное на самой мелкой сетке 37x37x34.

Рис. 31. Топология вложенных сеток: общая композиция и ее составные части (20x20x20, 30x19x38, 52x19x74)

Karamyshev V.B., Kukartseva O. V. Application of a local multigrid method to 3D transonic flow calculations // Proceedings of The Sixth Japan-Russia Joint Symposium on Conputational Fluid Dynamics, Nagoya University, Nagoya, Japan. –1998. –p. 19-22.

Обладатель гранта – к. ф.-м. н. С.П. Шарый (ИВТ СО РАН).

"Алгебраический подход" – это общий метод решения различных задач приближенного оценивания множеств решений интервальных систем уравнений, который заключается в замене исходной задачи оценивания на вспомогательную задачу нахождения алгебраического решения некоторого специального интервального уравнения (так называемого уравнения в дуализациях). Редуцированная задача является, по существу, традиционной общематематической задачей нахождения решения некоторого уравнения и далее может быть сведена, например, к решению обычных конечномерных систем уравнений в евклидовых пространствах. Впервые алгебраический подход был предложен автором в начале 90-х годов для нахождения внутренних оценок различных множеств решений интервальных линейных систем и зарекомендовал себя как исключительно эффективная вычислительная методика. Впоследствии алгебраический подход был адаптирован для внутреннего оценивания множеств решений некоторых классов нелинейных уравнений.

Основным содержанием работ по заявленному проекту стало развитие различных аспектов алгебраического подхода к внешнему оцениванию обобщенных множеств решений интервальных линейных систем уравнений. Напомним, что за этой абстрактной математической постановкой стоит важная практическая задача анализа чувствительности линейных управляемых систем в интервальной остановке.

Ранее (на конец 1997-го года) в этом направлении был решён лишь круг вопросов, связанных с применением алгебраического подхода к задачам внутреннего интервального оценивания различных множеств решений интервальных систем уравнений, а также проработано внешнее оценивание с помощью алгебраического подхода для очень частного случая объединённого множества решений интервальных линейных систем.

За прошедшее время конкретными результатами по проекту являются:

• развитие методики сведения исходной задачи к уравнению в дуализациях, исследование достаточных условий его разрешимости, единственности решения, разработка практических алгоритмов для численного нахождения уравнения в дуализациях;
• развитие интервального метода Гаусса-Зейделя для внешнего интервального оценивания обобщенных множеств решений интервальных линейных систем (до сих пор он широко использовался в вычислительной практике только для оценивания объединённых множеств решений);
• теоретическое исследование сходимости обобщенного метода Гаусса-Зейделя и выбора его начального приближения;

• для интервальных линейных систем с М-матрицами доказана сходимость метода к оптимальному интервальному решению;

• развитие конструкции предобуславливания интервальных линейных систем, расширяющей сферу применимости алгебраического подхода и других методик внешнего оценивания различных множеств решений интервальных систем уравнений (с систем, имеющих H-матрицу до систем с любыми строго регулярными матрицами).

Обладатель гранта – к.ф.-м.н. Тарасюк И.В. (ИСИ СО РАН).

Для временных сетей Петри с видимыми переходами введен и исследован ряд временных, не-временных и региональных эквивалентностей.

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

Обладатель гранта - к.ф.-м.н. Устименко А.П. (ИСИ СО РАН)

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

В оглавление

Webmaster Обратная связь

© 1999 Institute of Computational Technologies SB RAS, Novosibirsk
    Last update: Tuesday, 01-Jun-1999 17:25:00 NOVST