Отчет результаты научно-организационной деятельности утвержден Ученым Советом 20. 12. 2010 Омск 20 1 icon

Отчет результаты научно-организационной деятельности утвержден Ученым Советом 20. 12. 2010 Омск 20 1


Смотрите также:
Отчет результаты научно-организационной деятельности утвержден Ученым Советом 07. 12...
Отчет результаты научно-организационной деятельности утвержден Ученым Советом 22. 12...
Отчет результаты научно-организационной деятельности утвержден Ученым Советом 24. 12...
Отчет результаты научно-организационной деятельности в 2006 г. Утвержден Ученым Советом 20. 11...
Отчет о научно-исследовательской и научно-организационной деятельности за 2000 год...
Отчет о научной и научно-организационной деятельности Института геофизики Уро ран...
Отчет о нир за 2010 год Разработка научно исследовательских тем...
Отчет о результатах самообследования по состоянию на 01. 06...
Положение о декане факультета...
Годовой отчет за 2010 год Предварительно утвержден советом директоров ОАО «Завод «Навигатор»...
Правила приема студентов в алтгту в 2010 г. Общие положения...
Отчет о результатах самообследования деятельности...



Загрузка...
страницы:   1   2   3   4
скачать
Сибирское отделение Российской Академии наук

И Н С Т И Т У Т М А Т Е М А Т И К И им. С. Л. С о б о л е в а


О М С К И Й Ф И Л И А Л


УТВЕРЖДАЮ:

Директор д.ф-м.н., профессор

______________ В.А. Топчий

« » ______________2010 г.


ОТЧЕТ

РЕЗУЛЬТАТЫ НАУЧНО-ОРГАНИЗАЦИОННОЙ ДЕЯТЕЛЬНОСТИ


Утвержден Ученым Советом 20.12.2010


Омск - 2010


РЕФЕРАТ


Отчет содержит 31 стр. текста и 126 названий публикаций. В отчете представлены результаты фундаментальных и прикладных исследований и разработок, проведенных в 2010 г. Омским филиалом Института математики им. С.Л. Соболева СО РАН. Дана краткая информация о научно-организационной деятельности в СО РАН, в Омском регионе и в рамках международных контактов.


^ Ключевые слова: комбинаторная алгебра, теория вероятностей, математическое моделирование, начально-краевые задачи гидродинамики, методы оптимизации, информационные модели.


Директор д.ф.-м.н., профессор Валентин Алексеевич Топчий

т. (3812) 236567, admin@ofim.oscsbras.ru

Ученый секретарь Валентина Александровна Планкова

т. (3812) 247041, plankova@ofim.oscsbras.ru


http://ofim.okno.ru


ОГЛАВЛЕНИЕ

^ I. ВВЕДЕНИЕ 4

II. ИТОГИ НАУЧНЫХ ИССЛЕДОВАНИЙ 5

2.1. Важнейший научный результат 5

2.2. Научная работа лабораторий 7

III. НАУЧНО-ОРГАНИЗАЦИОННАЯ ДЕЯТЕЛЬНОСТЬ 14

3.1. Проекты, имеющие поддержку на международном, федеральном и региональном уровнях 14

3.2. Характеристика международных научных связей и совместной деятельности с зарубежными научными учреждениями 15

3.3. Участие в работе научных мероприятий 17

3.4. Работа в ВУЗах 19

3.5. Диссертационные советы 22

3.6. Список научных публикаций 23

^ IV. СПРАВОЧНАЯ ИНФОРМАЦИЯ 33

4.1. Основные количественные показатели 2010 г. 33

4.2. Участие в работе конференций, совещаний и т.д. 33

4.3. Научные публикации сотрудников по годам 33



^

I. ВВЕДЕНИЕ



Структурные подразделения



  • Лаборатория комбинаторных и вычислительных методов алгебры и логики

  • Лаборатория теоретико-вероятностных методов

  • Лаборатория математического моделирования в механике

  • Лаборатория методов преобразования и представления информации

  • Лаборатория дискретной оптимизации

  • Информационно-вычислительный центр



Основные задания к плану научно-исследовательских работ

Института математики им. С.Л. Соболева

Сибирского отделения Российской Академии наук


НИР ОФ ИМ СО РАН: ПСО № 328 от 19.11.09. 1.1.3.2. Развитие методов исследования стохастических моделей ансамблей частиц (2010-2012 гг., № гос. регистрации – 01201053357), руководитель – д.ф.-м.н. Топчий В.А., исп. – Перцев Н.В., Клоков С.А., Гольтяпин В.В., Пичугин Б.Ю., Зачатейский Д.Е., Планкова В.А.


НИР ИМ СО РАН: ПСО № 328 от 19.11.09. Актуальные проблемы алгебры (2010-2012 гг., № гос. регистрации – 01201051839), руководитель – чл.-к. РАН Мазуров В.Д., исп. – Ремесленников В.Н., Даниярова Э.Ю., Лопатин А.А., Берестовский В.Н., Носков Г.А., Рыбалов А.Н., Гичев В.М., Зубарева И.А., Шевляков А.Н.


НИР ОФ ИМ СО РАН: ПСО № 328 от 19.11.09. 1.3.1.3. Теория и приложения сплайн-функций и методы математического моделирования в механике сплошной среды, физике полупроводников и биологии (2010-2012 гг., № гос. регистрации – 01201051838), руководители – Блохин А.М., д.ф.-м.н. Фадеев С.И., исп. – Задорин А.И., Горелов Д.Н., Паничкин А.В., Зобнин А.И., Харина О.В.,


НИР ОФ ИМ СО РАН: ПСО № 328 от 19.11.09. 1.5.1.1. Математические методы распознавания образов и прогнозирования (2010-2012 гг., № гос. регистрации – 01201051843), руководитель – д.т.н. Загоруйко Н.Г., исп. – Зыкин С.В., Филимонов В.А., Чанышев О.Г., Пуртов А.М., Нартов Б.К., Чуканов С.Н., Маренко В.А., Терехов Л.С.


НИР ОФ ИМ СО РАН: ПСО № 328 от 19.11.09. 1.5.1.3. Алгоритмы дискретной оптимизации для задач исследования операций (2010-2012 гг., № гос. регистрации – 01201051848), руководители – Береснев В.Л., д.ф.-м.н. Э.Х. Гимади, исп. – Колоколов А.А., Адельшин А.В., Еремеев А.В., Забудский Г.Г., Заозерская Л.А., Леванова Т.В., Сервах В.В.

^

II. ИТОГИ НАУЧНЫХ ИССЛЕДОВАНИЙ




2.1. Важнейший научный результат




Автор результата – н.с., к.ф.-м.н. А.Н. Рыбалов.


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


Генерический подход к алгоритмическим проблемам – новое направление исследований, рассматривающее проблему не на всем множестве входных данных, а на подмножестве «почти всех» входов (генерическом множестве). Понятие «почти все» формализуется при помощи введения асимптотической плотности на множестве входов. Многие проблемы, вычислительно трудные в худшем случае, становятся легкими (разрешимыми за полиномиальное время), если рассматривать не все входы, а «почти все» входы (их асимптотическая плотность стремится к 1). Классическим примером такой проблемы является задача линейного программирования, для решения которой на практике применяется симплекс-метод, имеющий экспоненциальную сложность в худшем случае, но для большинства задач работающий за полиномиальное время. С другой стороны, существуют проблемы, которые остаются сложными даже на любом генерическом подмножестве. Например, такие проблемы известны в криптографии (проблема дискретного логарифма).

Арифметика Пресбургера является классической разрешимой теорией первого порядка. Ее фрагменты имеют многочисленные приложения в теории оптимизации и верификации программ. В 1974 г. Рабин и Фишер доказали, что эта теория имеет по крайней мере двойную экспоненциальную сложность в худшем случае, то есть на множестве всех формул. В то же время актуален вопрос об эффективных алгоритмах проверки истинности, которые хорошо бы работали для “почти всех” формул, т.е. на генерических множествах.

В данной работе (Rybalov, 2010) доказывается, что арифметика Пресбургера имеет по крайней мере экспоненциальную сложность на любом подмножестве формул, асимптотическая плотность которого экспоненциально быстро стремится к 1 (строго генерическом множестве). Этот результат является продолжением работы по исследованию генерической сложности классических алгоритмических проблем. Ранее было доказано (Rybalov 2007), что классическая проблема остановки остается неразрешимой на любом строго генерическом множестве. Установлено (Myasnikov, Rybalov, 2008), что любая неразрешимая теория первого порядка остается неразрешимой на любом строго генерическом множестве формул. Построен (Myasnikov, Rybalov, 2008) пример полугруппы с проблемой равенства, неразрешимой на любом генерическом множестве.


^ Результат соответствует мировому уровню исследований по теории алгоритмов и сложности вычислений.


Работа выполнена при поддержке РФФИ (проекты 10-01-00383 и 08-01-00067).


Результат опубликован:


  1. A. Rybalov. Generic complexity of Presburger Arithmetic // Theory of Computing Systems, Vol. 46, Num. 1, 2010, pp. 2-8.

  2. A. Rybalov. On the strongly generic undecidability of the Halting Problem // Theoretical Computer Science, Vol. 377, 2007, pp. 268-270.

  3. A. Myasnikov, A. Rybalov. Generic complexity of undecidable problems // Journal of Symbolic Logic, Vol. 73, No. 2, 2008, pp. 656-673.


Результат доложен на ежегодной научной сессии ОФ ИМ СО РАН 27 сентября 2010 г.









Скачать 480.01 Kb.
оставить комментарий
страница1/4
Дата05.11.2011
Размер480.01 Kb.
ТипОтчет, Образовательные материалы
Добавить документ в свой блог или на сайт

страницы:   1   2   3   4
Ваша оценка этого документа будет первой.
Ваша оценка:
Разместите кнопку на своём сайте или блоге:
rudocs.exdat.com

Загрузка...
База данных защищена авторским правом ©exdat 2000-2017
При копировании материала укажите ссылку
обратиться к администрации
Анализ
Справочники
Сценарии
Рефераты
Курсовые работы
Авторефераты
Программы
Методички
Документы
Понятия

опубликовать
Загрузка...
Документы

Рейтинг@Mail.ru
наверх