«ПРОГРАММА КОНФЕРЕНЦИИ СЕКЦИЯ I 16 апреля, вторник, 14:40 II учебный корпус, 6 этаж, ауд. 685 Кафедры : математической статистики, математической кибернетики, математических методов прогнозирования Сопредседатели : ...»

Тезисы конференции “Ломоносовские чтения” 2013

ПРОГРАММА КОНФЕРЕНЦИИ

СЕКЦИЯ I

16 апреля, вторник, 14:40

II учебный корпус, 6 этаж, ауд. 685

Кафедры : математической статистики, математической кибернетики,

математических методов прогнозирования

Сопредседатели : профессор КОРОЛЕВ Виктор Юрьевич, профессор АЛЕКСЕЕВ Валерий Борисович 1. Локализация невосполнимых областей головного мозга. — Доклад научного сотрудника Захаровой Т. В., аспиранта Хазиахметова М. Ш., аспиранта Драницыной М. А., студента Никифорова С. Ю., студента Гончаренко М. Б., студента Климова Г. А.

2. Вероятностно-статистические методы анализа и обработки томографических изображений. — Доклад доцента Шестакова О. В.

3. Моментные оценки скорости сходимости в центральной предельной теореме. — Доклад ассистента Шевцовой И. Г.

4. О пересечениях и объединениях предполных классов многозначной логики. — Доклад младшего научного сотрудника Нагорного А. С.

5. Оператор FE-замыкания в счетнозначной логике. — Доклад профессора Марченкова С. С., аспиранта Калининой И. С.

6. О сложности нахождения полиномов булевых функций. — Доклад доцента Селезневой С. Н.

7. Модели случайных частично упорядоченных множеств. — Доклад старшего научного сотрудника, доцента Гурова С. И.

–1– Тезисы конференции “Ломоносовские чтения”

СЕКЦИЯ II

16 апреля, вторник, 16: II учебный корпус, 5 этаж, ауд. Кафедра : исследования операций Председатель : профессор ВАСИН Александр Алексеевич 1. Асимптотическое решение одной сингулярно возмущенной нелинейной задачи диффузии. — Доклад профессора Белолипецкого А. А., аспиранта Малининой Е. А.

2. Модели формирования партий и участия в голосовании. — Доклад профессора Васина А. А., аспиранта Вартанова С. А., научного сотрудника Сосиной Ю. В.

3. Одна задача оптимизации выбора дивидендов. — Доклад доцента Денисова Д. В., аспиранта Некрасовой О. В.

4. Игровая задача распределения ресурсов при защите объекта. — Доклад доцента Морозова В. В., аспиранта Шалбузова К. Д.

5. Оптимизация потребления при управлении портфелем в модели процентной ставки Кокса–Ингер–Солла–Росса. — Доклад доцента Морозова В. В., аспиранта Бабина В. А.

6. Вето-голосование в коллективах с лидером. — Доклад профессора Новиковой Н. М., аспиранта Машечкина А. И.

7. Исследование равновесия в одной многошаговой игре двух лиц. — Доклад доцента Решетова В. Ю., аспиранта Зограбяна Г. А.

8. Моделирование движения капитала между секторами российской экономики и за границу. — Доклад ассистента Вржеща В. П.

СЕКЦИЯ III

17 апреля, среда, 14: II учебный корпус, 6 этаж, ауд. Кафедры : математической физики, автоматизации научных исследований Председатель : профессор ДЕНИСОВ Александр Михайлович 1. Математическое моделирование морских электромагнитных зондирований с движущимся приемником. — Доклад профессора Дмитриева В. И., старшего научного сотрудника Барашкова И. С.

2. Обратная задача для уравнения диффузии в сферически симметричном случае. — Доклад профессора Денисова А. М., доцента Соловьевой С. И.

–2– Тезисы конференции “Ломоносовские чтения” 3. Постановка и решение задач для волнового уравнения с комплексной скоростью. — Доклад профессора Баева А. В.

4. Численное решение трехмерной задачи Дирихле в неоднородной среде методом интегральных уравнений. — Доклад профессора Захарова Е. В., научного сотрудника Калинина А. В.

5. Нормальная форма бифуркации Андронова–Хопфа в одной модели оптической системы с запаздыванием. — Доклад профессора Разгулина А. В., аспиранта Романенко Т. Е.

6. Определение границы локальной неоднородности по измерениям акустического поля. — Доклад ассистента Головиной С. Г.

7. Суперкомпьютерное моделирование эволюции тороидальной плазмы. — Доклад профессора Зайцева Ф. С.

СЕКЦИЯ IV

18 апреля, четверг, 15: II учебный корпус, 6 этаж, ауд. Лаборатории : троичной информатики и компьютерной графики и мультимедиа Сопредседатели : профессор МАШЕЧКИН Игорь Вальерьевич, ведущий научный сотрудник РАМИЛЬ АЛЬВАРЕС Хосе 1. Троичная схемотехника — подходы и средства. — Доклад ведущего научного сотрудника, старшего научного сотрудника Маслова С. П.

2. Решение задачи определения оптимального набора способов выборочного изотопного мечения аминокислот в протеинах в целях отнесения пиков на двумерных спектрах ЯМР средствами троичной содержательной логики. — Доклад старшего научного сотрудника Владимировой Ю. С., научного сотрудника Института биоорганической химии им. академиков М. М. Шемякина и Ю. А. Овчинникова РАН (ИБХ) Дубинного М. А.

3. Сопрограммный механизм в ДССП для ТВМ. — Доклад старшего научного сотрудника Бурцева А. А.

4. Выделение и распознавание дорожных знаков. — Доклад научного сотрудника Конушина А. С., аспиранта Чигорина А. А.

5. Алгоритмы для автоматизации систем видеонаблюдения. — Доклад научного сотрудника Конушина А. С., аспиранта Кононова В. А., директора ООО “Технологии видеоанализа” Конушина В. С.

Тезисы конференции “Ломоносовские чтения”

СЕКЦИЯ V

Сопредседатели : академик ОСИПОВ Юрий Сергеевич, академик КРЯЖИМСКИЙ Аркадий Викторович 1. О методе программных пакетов как инструменте решения задач гарантирующего управления при неполной информации. — Доклад академика РАН Кряжимского А. В.

2. Принцип максимума Понтрягина для задачи оптимального управления с функционалом, заданным несобственным интегралом. — Доклад члена корреспондента РАН Асеева С. М.

3. О задаче глобальной нуль-управляемости для линейных нестационарных управляемых систем. — Доклад профессора Никольского М. С.

4. Дискретный метод с переменной метрикой для решения седловых задач. — Доклад ассистента Будака Б. А., аспирант Ничипорчук А. В.

5. Сильно гарантированные равновесия в конфликтных задачах при неопределенности и дуополия Бертрана при учете импорта. — Доклад профессора Жуковского В. И.

6. Оптимальные траектории в простейшей задаче о движении материальной точки с нелинейным сопротивлением и ограниченным расходом топлива. — Доклад профессора Дмитрука А. В., аспиранта Самыловского И. А.

7. Устойчивый метод решения задач квадратичной минимизации с неравномерно возмущенным оператором и ограничением на норму. — Доклад профессора Потапова М. М., студента Дряженкова+А. А., студента Иванова Д. А.

8. Исследование обобщённой задачи Чаплыгина. — Доклад доцента Киселёва Ю. Н., доцента Аввакумова С. Н.

9. Модели производства и планирование инфраструктур. — Доклад научого сотрудника Лукьяновой Л. Н.

10. Задача оптимального прохождения через область. — Доклад ассистента Смирнова А. И.

Тезисы конференции “Ломоносовские чтения”

СЕКЦИЯ VI

Кафедра : нелинейных динамических систем и процессов управления Председатель : профессор, член-корреспондент РАН 1. О задаче Коши для одного соболевского уравнения с квадратичной нелинейностью. — Доклад профессора Ильина А. В., аспиранта Аристова А. И.

2. Методы стабилизации объектов с запаздываниями. — Доклад доцента Фурсова А. С., аспиранта Миняева С. И.

3. Подходы к решению задач теории автоматического управления. — Доклад младшего научного сотрудника Капалина И. В.

4. Стабилизация биаффинных систем методом трансверсальных функций. — Доклад младшего научного сотрудника Гончарова О. И.

СЕКЦИЯ VII

Председатель : академик КУРЖАНСКИЙ Александр Борисович 1. Об аппроксимативном динамическом программировании для линейных управляемых систем с запаздыванием. — Доклад ассистента Вострикова И. В.

2. Эллипсоидальные аппроксимации трубок достижимости управляемых систем при неопределенности. — Доклад начальника отдела финансового моделирования Allied Testing LTD Гагаринова П. В.

3. Свойства множеств достижимости системы Лотка-Вольтерра. — Доклад начальника управления скоринга и аналитики ОАО АКБ Росбанка Простякова П. В., доцента Рублева И. В.

Тезисы конференции “Ломоносовские чтения”

СЕКЦИЯ VIII

Кафедра : вычислительных технологий и моделирования Председатель : профессор, член-корреспондент РАН 1. Нахождение оптимального маршрута судна, минимизирующего риск пересечения с траекторией другого объекта. — Доклад профессора Агошкова В. И., аспиранта Заячковского А. О.

2. Построение адаптивных сеток в задачах биомедицины. — Доклад научного сотрудника ИВМ РАН Данилова А. А., студента Юровой А. С.

3. Учет скважин произвольной формы в гидродинамических симуляторах. — Доклад научного сотрудника ИВМ РАН Никитина К. Д., студента Лутидзе Г. Н.

4. Повышение эффективности вычислительных алгоритмов в вихревых методах аэродинамики. — Доклад старшего научного сотрудника НИИ Парашютостроения Апаринова А. А., профессора Сетухи А. В.

5. Мультизарядовый метод задачи многих тел и его программная реализация. — Доклад доцента Оселедца И. В., аспиранта Михалева А. Ю.

СЕКЦИЯ IX

Кафедры : общей математики и функционального анализа и его применений Сопредседатели : академик ИЛЬИН Владимир Александрович, 1. Критерии принадлежности классам Lp и Wp при p 1 обобщенных решений волнового уравнения, определяемых при помощи интегрального тождества. — Доклад академика РАН Ильина В. А., ассистента Кулешова А. А.

2. Об одной задаче оптимального граничного управления колебаниями струны с нестационарным граничным условием. — Доклад академика РАН Моисеева Е. И., ассистента Холомеевой А. А.

3. Асимптотические формулы для фундаментальных решений системы Дирака с комплекснозначным суммируемым потенциалом. — Доклад доцента Садовничей И. В.

4. О задаче граничного управления для уравнения Клейна–Гордона–Фока с суммируемым потенциалом. — Доклад доцента Крицкова Л. В.

Тезисы конференции “Ломоносовские чтения” 5. О регуляризации решения обратной задачи для уравнения Лапласа. — Доклад академика НАН Узбекистана Алимова Ш. А., доцента Тихомирова В. В., аспиранта Очилова Н. Н.

6. Типы асимптотик решений дифференциальных уравнений с полиномиальными вырождениями в коэффициентах. — Доклад профессора Коровиной М. В.

7. Асимптотики решений дифференциальных уравнений с вырождениями в случае резонанса. — Доклад профессора Коровиной М. В., аспиранта Волнухина М. С.

8. Краевые двойственные задачи в оптимальном управлении. — Доклад доцента Хорошиловой Е. В.

СЕКЦИЯ X

автоматизации систем вычислительных комплексов, суперкомпьютеров и квантовой информатики и лаборатория вычислительного практикума и диалоговых систем профессор, член-корреспондент РАН ВОЕВОДИН Владимир Валентинович, профессор МАЛЬКОВСКИЙ Михаил Георгиевич 1. Признаки регулярности бесконтекстных L-графов. — Доклад старшего преподавателя Вылитка А. А., студента Касимовой А. А.

2. Метод сбалансированного выбора модулей распределенной вычислительной системы реального времени с учетом требований к ее надежности. — Доклад ассистента Волканова Д. Ю.

3. Восстановление алгоритма по композиции бинарных трасс. — Доклад академика РАН Иванникова В. П., старшего преподавателя Падаряна В. А., Соловьева М. А.

4. Моделирование волновых процессов в задачах сейсморазведки на суперкомпьютерах “Ломоносов” и BlueGene/P. — Доклад доцента Поповой Н. Н., магистра Бурцева А. П., ООО “Геолаб” Курина Е. А.

5. Создание таблиц шахматных 7-фигурных окончаний на суперкомпьютере: теория и практика. — Доклад научного сотрудника Захарова В. Б., ассистента Махнычева В. С.

6. Синтез курсов обучения в интеллектуальной обучающей системе. — Доклад научного сотрудника Громыко В. И., профессора философского факультета МГУ Казарян В. П., профессора кафедры высшей математики МГТУ им. Н. Э. Баумана Васильева Н. С., старшего преподавателя факультета гуманитарных и социальных наук

РУДН Симакина А. Г., главного специалиста ОАО банка “Возрождение” Аносова С. С.

Тезисы конференции “Ломоносовские чтения”

СЕКЦИЯ XI

Председатель : профессор ГУЛИН Алексей Владимирович 1. Математическое моделирование солитонных решений уравнения Гросса– Питаевского. — Доклад профессора Трофимова В. А., ведущего научного сотрудника Савенковой Н. П., аспиранта Лапонина В. С.

2. Стохастическое решение трехмерного нелинейного уравнения Колмогорова– Фоккера–Планка с использованием GPU. — Доклад доцента Богомолова С. В., аспиранта Гудича И. Г.

3. Квазиакустическая схема для уравнений Эйлера газовой динамики. — Доклад профессора Фаворского А. П., аспиранта Исакова В. А.

4. Развитие двумерных локальных возмущений в потоке слабопроводящего газа в магнитном поле. — Доклад профессора Фаворского А. П., аспиранта Галаниной А. М.

5. Тестирование симметрично-симплектических методов на решениях задачи Кеплера. — Доклад профессора Еленина Г. Г., студента Бакеева Р. Н.

6. Численное интегрирование зашумленных табличных данных. — Доклад доцента Терновского В. В.

7. О задаче на собственные значения для нелокального разностного оператора с комплексным параметром. — Доклад ассистента Мокина А. Ю.

Тезисы конференции “Ломоносовские чтения”

СЕКЦИЯ I

Кафедры математической статистики, математических методов прогнозирования

ЛОКАЛИЗАЦИЯ НЕВОСПОЛНИМЫХ ОБЛАСТЕЙ ГОЛОВНОГО МОЗГА

Захарова Татьяна Валерьевна, Хазиахметов Максим Шамилевич, Никифоров Семен Юрьевич, Гончаренко Мирослав Богданович, Драницына Маргарита Александровна, Климов Григорий Анатольевич Кафедра математической статистики, e-mail: [email protected], [email protected], [email protected], [email protected], [email protected], [email protected] Изучение электрических процессов, происходящих в головном мозге, было начато еще в середине 19 века, однако серьезных успехов в данной области удалось добиться лишь после того, как была изобретена магнитоэнцефалография. В 1968 году Девидом Коэном была записана первая магнитоэнцефалограмма, и уже через 10 лет по всему миру один за другим начали создаваться соответствующие исследовательские центры. В нашей стране Научно-образовательный центр нейрокогнитивных исследований открылся в 2008 году при Московском психолого-педагогическом университете (подробнее о методах МЭГ см. [1]).

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

Все эти методы характеризуются слабой устойчивостью, связанной с малым числом датчиков, формирующих магнитоэнцефалограмму, высоким уровнем шума в снимаемом сигнале (порядка 95%) и другими факторами. Один из методов, используемых в настоящее время, основан на т. н. опорных точках — моментах начала вызванной активности в головном мозге. Точность их локализации оказывает решающее влияние на результат работы метода. Существующие алгоритмы определения точек начала движения по оценке сотрудников МЭГ-центра не обладают достаточной точностью и однородностью разметки сигнала, зачастую заставляя прибегать к переразметке данных вручную, что, впрочем, так же не гарантирует как точность, так и однородность обработки, хотя и позволяет уменьшить число неверно распознанных и нераспознанных опорных точек.

Разработанный авторами метод определения опорных точек стал результатом предварительного исследования вероятностных характеристик различных сигналов телеметрии человека, в ходе которых были доказаны неоднородность участков МЭГ-сигнала между моментами начала движения, негауссовость распределения шума на миограмме и магнитоэнцефалограмме, а также установлены спектральные и энергетические особенности исследуемых сигналов. Был проведен сравнительный анализ алгоритма с аналогами, показавший его превосходство в точности, а также в меньшем числе ложных фиксаций и необнаружений опорных точек. При этом указанный результат был достигнут без последующей корректировки разметки сигнала специалистом. В настоящее время метод внедТезисы конференции “Ломоносовские чтения” рен в московском МЭГ-центре как часть процедуры локализации зоны моторной коры (подробнее сам метод и сопутствующие вопросы рассмотрены в [2]).

В настоящее время авторами ведутся работы по локализации зон активности головного мозга. В частности, разрабатывается новый метод решения обратной задачи:

где Yt — измерения датчиков МЭГ, L — оператор проекции (рассчитывается исходя из формулы Био–Савара–Лапласа, используя объемный каркас мозга пациента, полученный после МРТ), Jt — вектор активаций диполей и — шумовой вектор. Задача осложняется плохой определенностью матрицы L. В новом методе на основе информации, полученной из этой матрицы, поверхность мозга будет кластеризоваться на области со схожими характеристиками. Таким образом, сначала решение будет получено для областей, а позже будет итеративно уточнено (в [3, 4] дано подробное описание наиболее популярных методов решения обратной задачи МЭГ).

Авторы выражают благодарность сотрудникам московского МЭГ-центра и особенно Чаянову Н. В. за всестороннюю помощь, оказанную ими в ходе решения задачи.

1. Hamalainen M. S., Hari R., Ilmoniemi R. J., Knuutila J., Lounasmaa O. V.

Magnetoencephalography — theory, instrumentation, and applications to noninvasive studies of the working human brain // Rev. Mod. Phys. 1993. Vol. 65. P. 413–497.

2. Захарова Т. В., Никифоров С. Ю., Гончаренко М. Б., Драницына М. А., Климов Г. А., Хазиахметов М. Ш., Чаянов Н. В. Методы обработки сигналов для локализации невосполнимых областей головного мозга // Системы и средства информатики. 2012. Ч. 22, 3. Hamalainen M. S., Ilmoniemi R. J. Interpreting magnetic fields of the brain: minimum norm estimates // Biomedical engineering. 1994. Vol. 32. P. 35–42.

4. Friston K., Harrison L., Daunizeau J., Kiebel S., Phillips C., Trujillo-Barreto N., Henson R., Flandin G., Mattoutf J. Multiple sparse priors for the M/EEG inverse problem // NeuroImage. 2008. Vol. 39. P. 1104–1120.

ВЕРОЯТНОСТНО-СТАТИСТИЧЕСКИЕ МЕТОДЫ АНАЛИЗА И ОБРАБОТКИ

ТОМОГРАФИЧЕСКИХ ИЗОБРАЖЕНИЙ

Кафедра математической статистики, e-mail: [email protected] Томографические методы реконструкции характеристик поглощающих, излучающих и отражающих объектов и сред получили широкое распространение в самых разнообразных областях, включая медицину, биологию, физику плазмы, газовую динамику, геофизику, астрономию и радиолокацию. Различные виды томографических экспериментов имеют свои специфические особенности, что приводит к необходимости использования различных математических моделей для их описания. Среди этих моделей наиболее распространенными являются интегральные преобразования радоновского типа. Кроме того, в реальных экспериментах данные всегда регистрируются с некоторой погрешностью, которая возникает из-за несовершенства оборудования, фонового шума и других причин. Эти погрешности необходимо учитывать при построении и анализе статистической модели наблюдаемых данных [1].

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

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

Кроме случайности, обусловленной наличием шума, в томографических экспериментах может возникать случайность, связанная с особенностями самого объекта изучения.

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

1. Шестаков О. В. Вероятностные модели в томографии. — М. : МАКС Пресс, 2008.

2. Захарова Т. В., Шестаков О. В. Вейвлет-анализ и его приложения. — 2-е изд. перераб.

и доп. — М. : ИНФРА-М, 2011.

НЕКОТОРЫЕ МОМЕНТНЫЕ НЕРАВЕНСТВА ТЕОРИИ ВЕРОЯТНОСТЕЙ

Работа поддержана РФФИ (проекты 12–07–33063, 11–01–00515а и 11–07–00112a) и Министерством образования и науки РФ (грант MK–2256.2012.1).

Кафедра математической статистики, e-mail: [email protected] Пусть X — случайная величина (с.в.) с E|X|r < для некоторого положительного r. Обозначим Теорема 1. Если с.в. X является решетчатой с шагом h > 0 и 1 = 0, 2+ < для некоторого 0 < 1, то если, вдобавок, с.в. X имеет симметричное распределение, то Теорема 1 улучшает и обобщает хорошо известное неравенство Мизеса где 1. Esseen C.-G. A moment inequality with an application to the central limit theorem // Skand.

Aktuarietidskr. 1956. Vol. 39. P. 160–170.

2. Shevtsova I. Moment-type estimates with asymptotically optimal structure for the accuracy of the normal approximation // Annales Mathematicae et Informaticae. 2012. Vol. 39.

P. 241–307.

3. Shevtsova I. On the accuracy of the approximation of the complex exponent by the first terms of its Taylor expansion with applications [Electronic resource] // arXiv.org e-Print archive. 2013. URL: http://arxiv.org (access date: 16.04.2013), article-id arXiv:1301.2783 [math.PR].

О ПЕРЕСЕЧЕНИЯХ И ОБЪЕДИНЕНИЯХ ПРЕДПОЛНЫХ КЛАССОВ

МНОГОЗНАЧНОЙ ЛОГИКИ

Кафедра математической кибернетики, e-mail: [email protected] Пусть k — натуральное число, k 2, Ek = {0, 1,..., k 1}, Pk — множество всех конечноместных функций на Ek. Элементы множества Pk будем называть функциями k-значной логики, или k-значными функциями.

Замкнутый (относительно суперпозиции) класс H функций k-значной логики назовем предполным в Pk, если H = Pk, но для любой функции f Pk \ H замыкание множества H {f } совпадает с Pk.

Согласно теореме Кузнецова А. В. [1] при любом фиксированном k число предполных классов в Pk конечно. Усилиями Розенберга И. [2] и ряда других математиков при любом k 2 все предполные классы в Pk были найдены и охарактеризованы в терминах сохранения некоторых предикатов.

Пусть s, t 1 и s + t 3. Истинное включение где все Kim и Kjn суть предполные в Pk классы, назовем аксиомой вложения.

Аксиому вложения вида (1) назовем тупиковой, если после удаления любого Kim из левой части или Kjn из правой части она перестает быть аксиомой (т. е. соответствующее вложение становится ложным).

Очевидно, множество всех тупиковых аксиом вложения в Pk при любом k 2 является конечным.

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

Теорема 1 [3]. Существуют ровно 3602 тупиковых аксиомы вложения в P3.

Отметим также, что автором найдена базисная система аксиом вложения в P3, содержащая 123 аксиомы.

Приведем примеры задач, для решения которых можно использовать системы аксиом вложения.

1. Задача индивидуальной классификации k-значных функций. Обозначим через (k) количество предполных классов в Pk. Занумеруем эти классы в некотором порядке.

Характеристическим вектором функции f Pk назовем двоичный вектор (1 (f ), 2 (f ),..., (k) (f )) такой, что i (f ) = 1 тогда и только тогда, когда f принадлежит i-му предполному классу (i = 1, 2,..., (k)).

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

Теорема 2. Имеется ровно 406 попарно различных характеристических векторов функций трехзначной логики (их список вместе с примерами функций см. в [3]).

2. Задача построения решетки основных замкнутых классов в Pk. Множество всех замкнутых классов функций k-значной логики образует решетку по вложению, которая при любом k 3 является континуальной [4], что приводит к значительным трудностям при ее изучении.

Ввиду теоремы А. В. Кузнецова [1] о функциональной полноте в Pk всякий замкнутый класс из Pk, отличный от Pk, целиком содержится хотя бы в одном из предполных в Pk классов. Отсюда вытекает, в частности, что определяющие свойства предполных классов — предикаты, задающие предполные классы, — присутствуют во всех остальных замкнутых классах. Этот факт следует также из теории Галуа для алгебр Поста [5], согласно которой любой замкнутый класс можно задать подходящим множеством предикатов (может быть, бесконечным), среди которых обязательно присутствует хотя бы один из предикатов, задающих предполный класс.

Тезисы конференции “Ломоносовские чтения” Основными замкнутыми классами k-значной логики назовем сам класс Pk, все предполные классы, а также все замкнутые классы, которые представляют собой пересечения предполных в Pk классов.

Основные замкнутые классы образуют “каркас” решетки замкнутых классов в Pk, поскольку они определяются только “основными свойствами” класса Pk — свойствами, присутствующими во всех остальных замкнутых классах и отвечающими за решение проблемы полноты в классе Pk.

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

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

Для построения решетки основных замкнутых классов в Pk достаточно взять только те тупиковые аксиомы вложения вида (1), в которых t = 1.

Теорема 3 [3]. В трехзначной логике ровно 1505 основных замкнутых классов.

Автор выражает благодарность Вороненко А. А. за постановку задачи и Марченкову С. С. за ценные замечания.

1. Кузнецов А. В. О проблемах тождества и функциональной полноты для алгебраических систем // Труды 3-го Всесоюзного матем. съезда. Т. 2. М. : Изд-во АН СССР, 1956. С. 145–146.

2. Rosenberg I. G. La structure des fonctions de plusieurs variables sur un ensemble fini // C. R. Acad. Sci. Paris. Ser. A. B. 1965. Vol. 260. P. 3817–3819.

3. Нагорный А. С. О распределении трехзначных функций по предполным классам // Вестн. Моск. ун-та. Сер. 15. Вычисл. матем. и киберн. 2012. № 3. С. 45–52.

4. Янов Ю. И., Мучник А. А. О существовании k-значных замкнутых классов, не имеющих конечного базиса // ДАН СССР. 1959. Т. 127, № 1. С. 44–46.

5. Боднарчук В. Г., Калужнин В. А., Котов В. Н., Ромов Б. А. Теория Галуа для алгебр Поста. I, II // Киберн. 1969. № 3. С. 1–10 ; № 5. С. 1–9.

ОПЕРАТОР FE-ЗАМЫКАНИЯ В СЧЕТНОЗНАЧНОЙ ЛОГИКЕ

Калинина Инна Сергеевна, Марченков Сергей Серафимович Кафедра математической кибернетики, e-mail: [email protected], [email protected] Один из распространенных способов задания функций в математике использует в качестве инструмента системы функциональных уравнений. Функциональные уравнения определяются на основе функциональных и предметных переменных, а также различных функциональных и предметных констант. Большое число примеров функциональных уравнений можно найти в дискретной математике, в частности, в теории алгоритмов, теории автоматов и теории функций многозначной логики.

Системы функциональных уравнений являются удобным средством для задания операторов замыкания [1, 2]. В свою очередь, на основе операторов замыкания можно определить классификации различных множеств функций.

На основе системы функциональных уравнений на множестве функций счетнозначной логики определяется оператор FE-замыкания. Устанавливается, что всякий общерекурсивный оператор, заданный в формализме Эрбрана–Гёделя [3], можно представить ввиде оператора FE-замыкания. Доказывается совпадаение класса отношений, выразимых в языке FE, с классом 1 аналитической иерархии Клини [4]. Исследуются расширения оператора FE-замыкания с помощью нетривиальных однородных функций.

1. Марченков С. С. Оператор замыкания в многозначной логике, базирующийся на функциональных уравнениях // Дискретный анализ и исследование операций. 2010. № 4.

2. Марченков С. С. FE-классификация функций многозначной логики // Вестн. Моск.

ун-та. Сер. 15. Вычисл. матем. и киберн. 2011. № 2. С. 32–39.

3. Клини С. Введение в метаматематику. — М. : ИЛ, 1957.

4. Роджерс Х. Теория рекурсивных функций и эффективная вычислимость. — М. : Мир,

О СХЕМНОЙ СЛОЖНОСТИ НАХОЖДЕНИЯ ПОЛИНОМОВ БУЛЕВЫХ

ФУНКЦИЙ

Кафедра математической кибернетики, e-mail: [email protected] Настоящая работа относится к изучению схемной сложности линейных булевых (n, m)операторов в базисе {x y} из одного элемента сложения по модулю 2. Каждая линейный булев (n, m)-оператор может быть задан в виде Ax, где A — матрица из нулей и единиц размера m n, а x = (x1,..., xn ) — вектор переменных. Поэтому иногда схемная сложность таких операторов называется схемной сложностью матрицы A. Несмотря на простоту определения, линейными булевыми операторами задается ряд важных содержательных преобразований. Одно из них — преобразование вектора значений булевой функции от n переменных в вектор коэффициента ее полинома Жегалкина. Это преобразование называется преобразованием Мёбиуса µn. Оно задается матрицей An размера 2n 2n, определяемой рекурсивно:

Иногда эта матрица An называется матрицей Серпинского, или матрицей Паскаля по модулю два.

Базис {x y} не является полным, однако ситуация в нем принципиально иная, чем в неполном монотонном базисе из одного элемента дизъюнкции {x y}, ввиду наличия тождества x x = 0. Известно не так много оценок схемной сложности в базисе {x y} явно определенных матриц. В [1, 2] было показано, что при m log2 n сложность любой Работа поддержана РФФИ, гранты 12–01–00706-а, 13–01–00684-а, 13–01–958-а.

матрицы размера n m в базисе {x y} равна 2n o(n). В частности, сложность проверочной матрицы кода Хэмминга Hk размера k (2k 1) равна 2 · 2k 2k 2. Некоторой техникой из этой матрицы можно сконструировать матрицу размера nn, сложность которой в базисе {x y} равна 3n o(n) [1, 2]. В [3] доказано, что сложность булевой матрицы Адамара-Сильвестра размера 2k 2k в базисе {xy} равна O(2k ). В [4] построена матрица без прямоугольников размера n n, сложность которой в базисе {x y} равна 3n o(n).

Пусть B = {0, 1}. Множество B n, n 1, назовем n-мерным булевым кубом. На кубе B n при a1 b1,..., an bn. Отображение f : B n B называется булевой функцией от n переменных, n = 0, 1, 2,.... Множество всех булевых функций от n переменных обозначим как Bn. Вектором значений функции f Bn назовем вектор uf = (u0, u1,..., u2n 1 ) B 2, в котором uj = f (), где j = (aj1,..., ajn ) B n — такой набор, что j = n aji · 2ni, j = 0, 1,..., 2n 1. Каждая булева функция f (x1,..., xn ) может быть задана формулой вида где cf () = f ( ) B — коэффициенты, B n, xsi — степени, т. е. x1 = xi, x0 = 1, и сложение и умножение проводится по модулю 2. Это представление булевых функций называется полиномом Жегалкина, или алгебраической нормальной формой (АНФ). Вектор значений ucf булевой функции cf Bn называется вектором коэффициентов полинома функции f Bn. Преобразование вектора значений булевой функции от n переменных в вектор коэффициентов ее полинома является линейным булевым (2n, 2n )-операторм с матрицей An, т. е. для произвольной булевой функции f Bn верно ucf = An uf. Это преобразование вектора значений булевой функции в вектор коэффициентов ее полинома называется преобразованием Мёбиуса µn.

Сложностью L (y) линейного булева оператора y = Ax в базисе {x y} называется сложность минимальной схемы в базисе {x y}, реализующей этот оператор. Сложность L (y) обозначают также как L (A) и называют сложностью матрицы A в базисе {x y}.

Пользуясь представлением верным для произвольной булевой функции f (x1, x2,..., xn ) Bn, можно заключить, что L (µn ) 2L (µn1 )+2n1. Откуда получаем [5], что L (µn ) n·2n1 при n 1. Заметим, что модели схем с некоторым ограничением структуры в базисе {x y} доказана такая же нижняя оценка сложности преобразования Мёбиуса [6–10].

Мы доказываем следующие оценки.

Теорема 1. При n 1 верно L (µn ) 2 · 2n (n + 2).

Теорема 2. L (µ2 ) = 4.

Теорема 3. L (µ3 ) = 12.

1. Чашкин А. В. О сложности булевых матриц, графов и соответствующих им булевых функций // Дискретная математика. 1994. Т. 6, № 2. С. 43–73.

2. Interlando J. C., Byrne E., Rosenthal J. The uate uomplexity of uyndrome uecoding of Hamming uodes // Applications of Computer Algebra. Texas, 2004. P. 1–5.

3. Alon N., Karchmer M., Wigderson A. Linear circuits over GF(2) // SIAM J. Comput. 1990.

Vol. 19, N 6. P. 1064–1067.

4. Селезнева С. Н. О схемной сложности некоторых булевых матриц // Тихоновские чтения: Научная конференция. МГУ имени М. В. Ломоносова. Тезисы докладов. М. :

МАКС Пресс, 2012. С. 44–45.

5. Гаврилов Г. П., Сапоженко А. А. Сборник задач по дискретной математике. — М. :

Наука, 1977.

6. Kennes R. Computational aspects of the Mobius transformation of graphs // IEEE Transactions on Systems, Man, and Cybernetics. 1992. Vol. 22, N 2. P. 201–223.

7. Boyar J., Find M. C. Cancellation-free circuits: An approach for proving superlinear lower bounds for linear Boolean operators [Electronic resource] // arXiv.org e-Print arhive. 2012. URL: http://arxiv.org (access date: 16.04.2013), article-id arXiv:1207.5321 [cs.CC].

8. Selezneva S. N. Lower bound on the complexity of finding polynomials of Boolean functions in the class of circuits with separated variables // Computational Mathematics and Modeling. 2013. Vol. 24, N 1. P. 146–152.

МОДЕЛИ СЛУЧАЙНЫХ ЧАСТИЧНО УПОРЯДОЧЕННЫХ МНОЖЕСТВ

Кафедра математических методов прогнозирования, e-mail: [email protected] Частично упорядоченным (ч. у.) множеством называют пару P = (P, ), где P — непустое множество (носитель P), а — рефлексивное, антисимметричное и транзитивное однородное отношение на нем или (частичный) порядок в инфексной записи (все необходимые определения имеются, например, в [1]).

В ряде работ начиная с середины прошлого века П. Эрдёшем был предложен неконструктивный подход для доказательства существования математических объектов заданного вида названный вероятностным методом. Метод нашел широкое применение не только в комбинаторике, но и в других областях математики, таких как теория чисел, линейная алгебра, математический анализ, а также в компьютерных науках. Вероятностный метод активно использует такие утверждения как неравенство Маркова, оценки Чернова, локальная лемма Ловаса и др. Имеется фундаментальная монография, посвященная вероятностному методу [2].

Исследования по приложениям вероятностного методов для ч. у. множеств идут по двум направлениям. Первое связано с построением моделей случайных ч. у. (с. ч. у.) множеств, а второе концентрируется на адаптации вероятностного метода для изучения ч. у. множеств общего вида. В докладе в рамках первого направления рассматриваются различные модели частично упорядоченных (ч. у.) множеств. Вводятся необходимые понятия, определения структурных элементов, числовых характеристик ч. у. множеств и приводятся некоторые известные оценки их значений. Доклад представляет расширенный вариант собой обзора, сделанного на конференции КРОМШ-2012 [3].

В докладе рассмотрены различные модели ч. у. множеств и представлены результаты по определению их характеристик, полученные в рамках этих моделей: включены результаты, представленные в [4, 5], а также полученные в последнее время.

Тезисы конференции “Ломоносовские чтения” Модель случайного ч. у. множества есть семейство дискретных вероятностных пространств (n), элементами которых являются конечные ч. у. множества обычно (но не всегда) содержащие n элементов или, чаще, (n, s), где s — параметр пространства; обычно это значение вероятности некоторых событий, участвующих в определении пространства.

Случайный элемент пространства обычно обознается либо просто как P, либо P(n), либо Ps (n).

Если f — параметр ч. у. множества, то его значение f (P(n)) на элементе P(n) (n) есть случайная величина Fn. Обычно интересуются поведением случайной величины Fn при n. Целью здесь является получение результата в форме где (n) будет представлять собой верхнюю границу стандартного отклонения для Fn, а c() — константа или функция от. Если такая оценка получена, то говорят, что величина Fn плотно концентрируется около своего среднего. Обычно такие результаты получают используя неравенства Хёфдинга, Азумы, Талаграна и др. (см. [2]).

В докладе рассмотрены нижеперечисленные модели и приведены результаты по оценке параметров получаемых в них с. ч. у. множеств.

2-модель 2 (n, p) двудольных с. ч. у. множеств: для каждого натурального n составляют всевозможные ч. у. множества с минимальными элементами a1,..., an, максимальными элементами b1,..., bn и с вероятностью p, независящей от i, j {1,..., n} содержащие отношение ai < bj.

Здесь даны оценки размерности с. ч. у. множеств.

T-модель с. ч. у. множеств фиксированной размерности t приводится в двух вариантах.

Вариант A: генерируется t независимых случайных перестановок множества [n] и берется их пересечение. Вариант B: генерируется n случайных точек x = (x1,..., xt ) в единичном кубе [0, 1]t Rt, которые рассматриваются как элементы строящегося ч. у. множества, а порядок не нем есть пересечение естественных порядков по всем координатам: x y если xi yi для всех i = 1,..., t.

Даны оценки плотной концентрации высоты, ширины и числа линейных расширений с. ч. у. множеств.

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

U-модель U (n) составляют все помеченные n-элементные ч. у. множества, PU (n) есть результат равновероятного выбора элемента из него.

Даны оценки размерности с. ч. у. множеств и приведена теорема о “типичном” ч. у. множестве.

G-модель G (n, p). Рассматривается случайный граф с вершинами из [n] и имеющий с вероятностью p (независимой от наличия/отсутствия других дуг) дугу (i, j), если i < j.

Случайное ч. у. множество есть результат транзитивного замыкания рассмотренного графа.

Приводятся оценки размерности с. ч. у. множеств.

S-модель S (n, p). На начальном шаге P0 = {0}; на шагах n = 1, 2,... ч. у. множество Pn получается присоединением к Pn1 элемента n в предположении, что он содержит некоторые элементы Pn1 и проведении транзитивного замыкания (классическая последовательная модель роста).

Эта современная и наиболее сложная модель. Приводятся результаты [6].

Тезисы конференции “Ломоносовские чтения” 1. Гуров С. И. Булевы алгебры, упорядоченные множества, решетки: определения, свойства, примеры. — М. : КРАСАНД, 2012.

2. Алон Н., Дж. Спенсер. Вероятностный метод. — М : БИНОМ, 2007.

3. Гуров С. И. Случайные частично упорядоченные множества: модели и результаты // Intern. Conf. KROMSH-2012. Сборник тезисов. Simferopol : Taurida National V. Vernadsky University, 2012. С. 19.

4. Brightwell G. R. Models of random partial orders // Surveys in Combinatorics / ed. by K. Walker. Cambridge University Press, 1993. P. 53–83.

5. Winkler P. Random orders // Order. 1985. Vol. 1, Issue 4. P. 317–331.

6. Georgiou N. Random structures for partially ordered sets : thesis for Doctor of Philosophy. — London School of Economics and Political Science, 2003.

Тезисы конференции “Ломоносовские чтения”

СЕКЦИЯ II

ОДНА ЗАДАЧА ОПТИМИЗАЦИИ ВЫБОРА ДИВИДЕНДОВ

Денисов Дмитрий Витальевич, Некрасова Ольга Валерьевна Кафедра исследования операций, e-mail: [email protected], [email protected] Моделирование различных аспектов финансовой деятельности страховых компаний на данный момент представляет собой интенсивно развивающуюся область математических исследований с многочисленными практическими приложениями. Принимать решения приходится во всех областях деятельности компании — это и выбор стратегии перестрахования, и оптимальное распределение дивидендов, и возможные инвестиции как во внешний финансовый рынок, так и извне во внутренний баланс компании. Последствия принятия таких решений бывают очень весомы, поэтому все более актуальной становится потребность в разработке наиболее подробных и сложных моделей, методов и алгоритмов принятия решений, которые упрощали бы и, по возможности, формализовали бы этот процесс, тем самым придавая большую надежность и снижая влияние человеческого фактора.

В данной работе исследование вопроса оптимизации финансового состояния страховой компании построено путем последовательного усложнения и анализа дискретной модели, в которой s — начальный капитал, c — поток премий, поступающих в единицу времени по контрактам, заключенным в данной компании, Xt — случайные неотрицательные величины, характеризующие агрегированные размеры убытков за t-й период времени.

Резервы страховой компании в момент времени t 0 будут равны R(t):

По результатам работы страховой компании в случае закрытия t-го отчетного периода с успешными финансовыми показателями в начале следующего t+1 периода акционерами принимается решение о выборе стратегии дивидендных выплат. Если d(t) — размер дивидендных выплат в начале t + 1 периода по результатам финансового состояния компании на момент t, t 0, тогда резервы компании в момент времени t + 1:

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

С математической точки зрения стратегии перестрахования полностью определяются функциями дележа риска. Если X = Y + Z — страхуемый риск, то Y = g(X) — описывает часть риска, остающуюся у цедента, а Z = h(X) — риск, переданный на перестрахование.

Тезисы конференции “Ломоносовские чтения” Добавив в анализ модели возможность перестрахования, учитывая стоимость перестраховочной защиты, получим следующее уравнение для резервов компании с оставшейся у нее частью риска g(t) = g (Xt ):

Учитывая дополнительные ограничения на вероятность разорения компании, рассматривая ее деятельность на конечном горизонте планирования Tfin, в случае наличия возd можности выбора стратегии перестрахования и выплаты дивидендов, если re — момент разорения, то вероятность разорения:

Использование квантильного критерия Value-at-Risk требует предварительного выбора уровня доверительной вероятности, значение которого существенно влияет на решение задачи оптимизации. Квантильный критерий в нашем случае будет заключаться в нахождении параметров модели, при которых при заданном уровне 0 < 1 вероятность разорения заключена в доверительный интервал re (s).

Задача оптимизации выбора пары стратегий — перестрахования и выплат дивидендов, при которых суммарное дисконтированное значение выплаченных дивидендов на конечном горизонте планирования Tfin будет максимальным, с учетом ограничений на вероятность разорения:

xi, yi > 0.

Для исследования модели, запишем ее разностный аналог:

где k = {0, 1,... N }, 4 4 матрица A задана равенством и 4 вектора-столбца определены соотношениями:

Целью каждого игрока является максимизация функции выигрыша:

На основании теоремы 2.4.1 из [3], получено равновесное решение для двухшаговой игры.

На первом шаге:

На втором шаге:

Здесь для краткости записи введены переменные µ1, 1, i, которые зависят от коэффициентов модели (ai, bi, ci, i ).

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

1. Киселев Ю. Н., Решетов В. Ю., Аввакумов С. Н., Орлов М. В. Построение оптимального решения и множество достижимости в одной задаче распределения ресурсов // Проблемы оптимального управления. Вып. 2. М. : МАКС Пресс, 2007. C. 106–120.

2. Никольский М. С. Упрощенная игровая модель взаимодействия двух государств // Вестн. Моск. ун-та. Сер. 15. Вычисл. матем. и киберн. 2009. № 2. C. 14–20.

3. Жуковский В. И. Кудрявцев К. Н. Уравновешивание конфликтов и приложения. — М. :

Ленанд, 2012.

МОДЕЛИРОВАНИЕ ДВИЖЕНИЯ КАПИТАЛА В МОДЕЛИ

МЕЖВРЕМЕННОГО РАВНОВЕСИЯ ЭКОНОМИКИ РОССИИ

Кафедра исследования операций, e-mail: [email protected] Работа основана на трехпродуктовой модели межвременного равновесия экономики России, построенной в рамках подхода Системный анализ развивающейся экономики (САРЭ) [1].

В 2010 году была разработана концепция трехпродуктового нелинейного дезагрегирования основного макроэкономического баланса (ОМБ) по использованию [2]. Необходимость в данном подходе была продиктована наблюдающимся в статистике сильным расхождением в индексах цен основных компонент ОМБ. Успешное применение трехпродуктового подхода позволило создать трехпродуктовую модель межвременного равновесия экономики России [3]. Модель основана на замкнутой системе балансов материальных благ и финансовых инструментов. Равновесие на 11 рынках описывается взаимодействием двух групп макроагентов: массовые рациональные агенты (Производитель, Банк, Домохозяйство, Торговец, Собственник) и индивидуальные сценарные агенты (Государство, Центральный банк, Импортер, Экспортер).

Работа поддержана РФФИ, проекты №№12-01-00916-а (2011-2012), 12-01-31333, 12-01-31189; РГНФ, проект №11-02-00241а; ПФИ ОМН РАН №3, проект 3.14; ПФИ Президиум РАН №14, проект 109. Исследование осуществлено в рамках программы фундаментальных исследований НИУ ВШЭ в 2013 году. Расчеты выполнены на суперкомпьютере МВС-100К МСЦ РАН.

Тезисы конференции “Ломоносовские чтения” Тем не менее, одной из принципиальных проблем долгое время оставались ввоз и вывоз капитала. В работе [3] удавалось моделировать вывоз капитала за счет использования в модели рационального агента Собственник. Однако ввоз капитала, который играл существенную роль в экономическом развитии России в 00-х годах, приходилось задавать экзогенно. В данной работе описывается один подход к эндогенизированию ввоза капитала в российскую экономику с применением вариационного принципа.

1. Петров А. А., Поспелов И. Г., Шананин А. А. От Госплана к неэффективному рынку: Математический анализ эволюции российских экономических структур. Lewiston;

N.Y., USA : The Edvin Mellen Press. 1999.

2. Вржещ В. П., Поспелов И. Г., Хохлов М. А. Модельное дезагрегирование макроэкономической статистики // Экономический журнал Высшей школы экономики. 2010.

Т. 14, № 1. C. 88–104.

3. Андреев М. Ю., Вржещ В. П., Пильник Н. П., Поспелов И. Г., Хохлов М. А., Жукова А. А., Радионов С. А. Модель межвременного равновесия экономики России, основанная на дезагрегировании макроэкономического баланса // Труды семинара имени И. Г. Петровского. Вып. 29. М. : Изд-во МГУ. 2012. С. 41–143.

Тезисы конференции “Ломоносовские чтения”

СЕКЦИЯ III

автоматизации научных исследований

МАТЕМАТИЧЕСКОЕ МОДЕЛИРОВАНИЕ МОРСКИХ ЭЛЕКТРОМАГНИТНЫХ

ЗОНДИРОВАНИЙ С ДВИЖУЩИМСЯ ПРИЕМНИКОМ

Барашков Игорь Сергеевич, Дмитриев Владимир Иванович Кафедра математической физики, e-mail: [email protected], [email protected] В настоящее время важной задачей является исследование строения шельфа и обнаружение месторождений углеводородов в шельфовой зоне. Именно поэтому последнее время развиваются методы морских электромагнитных зондирований [1, 2]. При мобильном методе морских зондирований в качестве источника электромагнитного поля используется электрический кабель, который передвигается под поверхностью моря на заданной глубине, буксируемый судном, а вслед за ним на фиксированном расстоянии на той же глубине буксируется приемник электрического поля.

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

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

1. Дмитриев В. И., Барашков И. С. Математическое моделирование электромагнитных морских зондирований трехмерной неоднородной среды // Прикладная математика и информатика. № 38. М. : МАКС Пресс, 2011. С. 5–17.

2. Барашков И. С., Дмитриев В. И. Математическое моделирование морских электромагнитных зондирований с использованием принципа взаимности // Прикладная математика и информатика. № 40. М. : МАКС Пресс, 2012. С. 5–19.

3. Дмитриев В. И., Захаров Е. В. Метод интегральных уравнений в вычислительной электродинамике. — М. : МАКС Пресс, 2008.

ОБРАТНАЯ ЗАДАЧА ДЛЯ УРАВНЕНИЯ ДИФФУЗИИ В СФЕРИЧЕСКИ

СИММЕТРИЧНОМ СЛУЧАЕ

Денисов Александр Михайлович, Соловьева Светлана Ивановна Кафедра математической физики, e-mail: [email protected], [email protected] Рассматривается начально-краевая задача для функции u(r, t):

Обратная задача состоит в определении функций (r) и u(r, t) для r [a, b], t [0, T ], если для t [t1, t2 ] [0, T ] задана функция где R0 — постоянная, R0 > b.

Эту задачу можно рассматривать как линеаризованную постановку обратной задачи, возникающей при исследовании математических моделей возбуждения сердца [1].

Для поставленной обратной задачи исследуется единственность решения для различных значений i, i, i = 1, 2.

1. Денисов А. М., Калинин В. В. Обратная задача для математических моделей возбуждения сердца // Журн. вычисл. матем. и матем. физики. 2010. Т. 50, № 3. С. 539–543.

ПОСТАНОВКА И РЕШЕНИЕ ЗАДАЧ ДЛЯ ВОЛНОВОГО УРАВНЕНИЯ С

КОМПЛЕКСНОЙ СКОРОСТЬЮ

Кафедра математической физики, e-mail: [email protected] Целью работы является развитие предложенной в [1–2] математической модели распространения волн в гетерогенной изотропной среде, а также постановка и исследование соответствующих начальных и краевых задач. Кроме того, данная статья позволяет расширить круг традиционных математических моделей, используемых при решении практически важных обратных задач рассеяния волн.

Основным объектом рассмотрения является волновое уравнение с комплексной скоростью Работа выполнена при частичной поддержке РФФИ, проект 11-01- Тезисы конференции “Ломоносовские чтения” относительно комплексной функции w = p(r, t) + is(r, t), где p — первичное, s — вторичное поле — действительные функции, r — вектор (x, y, z) пространственных координат, t — физическое время, c = const > 0 — скорость в среде без включений, = const > 0 — относительная плотность неоднородностей.

Поскольку задача Коши для уравнения (1) оказывается некорректно поставленной, то в работе предложены и исследованы корректные постановки начальных и начально-краевых задач. Показано, что естественной постановкой задач для (1) является задача Дирихле.

В то же время, решения уравнения обладают волновыми свойствами. Так, имеет место дисперсия волн, справедлив принцип суперпозиции и имеет место разложение решения по плоским волнам.

Рассмотрим, в частности, начальную задачу для уравнения (1) в R3 :

Полагаем также, что функция w0 ограничена в R3.

Определение. Решением задачи (1–2) называется дважды непрерывно дифференцируемая по r R3, t > 0 комплексная функция, удовлетворяющая уравнению (1), непрерывная при t 0 и такая, что выполнено условие (2).

Справедлива следующая формула, определяющая решение начальной задачи:

где Mr [w0, ] — среднее значение функции w0 на поверхности сферы радиуса с центром в точке r.

Приведем без доказательства результат решения задачи для неоднородного уравнения при нулевом начальном условии и непрерывной функции f (r, t):

1. Баев А. В., Куценко Н. В., Файзуллин И. С. О затухании и рассеянии сейсмических волн в трещиноватых средах // Геофизика. 2007. № 2. С. 16–20.

2. Баев А. В. Математическое моделированния рассеяния акустических волн в трещиноватых средах // Журн. вычисл. матем. и матем. физики. 2012. Т. 52, № 9. С. 1676–1693.

ЧИСЛЕННОЕ РЕШЕНИЕ ТРЕХМЕРНОЙ ЗАДАЧИ ДИРИХЛЕ В

НЕОДНОРОДНЫХ СРЕДАХ МЕТОДОМ ГРАНИЧНЫХ ИНТЕГРАЛЬНЫХ

УРАВНЕНИЙ

Захаров Евгений Владимирович, Калинин Александр Викторович Кафедра математической физики, e-mail: [email protected], [email protected] Рассмотрим область в трехмерном пространстве, ограниченную достаточно гладкой поверхностью (поверхность Ляпунова). Поставим следующую задачу. Требуется найти Тезисы конференции “Ломоносовские чтения” функцию u(x) C 2 () C 1 (), такую, что где (x) C 1 () — известная положительная функция, определяющая коэффициент электропроводности в области, y(x) C() — заданная функция.

Задачу (1)–(2) можно рассматривать как обобщение трехмерной задачи Дирихле для уравнения Лапласа в кусочно-однородной среде [1]. Для решения задачи приведем выражение (1) к виду и построим следующую итерационную процедуру, в которой на каждом шаге будет решаться следующая задача Дирихле для уравнения Пуассона где и начальное приближение Для решения задачи (4)–(7) использовался метод граничных интегральных уравнений.

При формировании системы граничных интегральных уравнений объемный интеграл от функци bk (x) по области приводился к поверхностным интегралам по поверхности с использованием метод DRBEM [2].

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

1. Захаров Е. В., Калинин А. В. Численное решение трехмерной задачи Дирихле для уравнения Лапласа в кусочно-однородной среде методом граничных интегральных уравнений // Журн. вычисл. матем. и матем. физики. 2009. Т. 49, № 7.

2. Niku S. M., Brebbia C. A. Dual reciprocity boundary element formulation for potential problems with arbitrary distributed forces // Int. J. Eng. Analysis. 1998. Vol. 5, N 1.

НОРМАЛЬНЫЕ ФОРМЫ БИФУРКАЦИИ АНДРОНОВА–ХОПФА В

ОДНОЙ МОДЕЛИ ОПТИЧЕСКОЙ СИСТЕМЫ С ЗАПАЗДЫВАНИЕМ

Разгулин Александр Витальевич, Романенко Татьяна Евгеньевна Кафедра математической физики, e-mail: [email protected], [email protected] Рассматривается функционально-дифференциальное параболическое уравнение с запаздыванием и поворотом пространственного аргумента с периодическими граничными условиями где D > 0, T > 0, K > 0, (0, 1), [0, 2). Эта задача возникает при моделировании нелинейных оптических систем с нелокальной обратной связью в случае тонкой кольцевой апертуры [1]. В [2] установлено существование периодических решений этой системы, возникающих в случае бифуркации Андронова–Хопфа. В настоящей работе построена нормальная форма этой бифуркации. Особенность такого построения состоит в том, что получающаяся нормальная форма [3] для исходного уравнения (1) совпадает до членов третьего порядка с нормальной формой бифуркации Андронова–Хопфа для редуцированного ОДУ на соответствующем центральном многообразии [4], что позволяет судить об устойчивости найденных бифуркационных периодических решений.

1. Razgulin A. V. Finite-dimensional dynamics of distributed optical system with delayed feedback // Computers & Mathematics with Applications. 2000. Vol. 40, N 12.

P. 1405–1418.

2. Razgulin A. V., Romanenko T. E. An approach to the description of rotating waves in parabolic functional-differential equations with rotation of spatial arguments and time delay // The Sixth International Conference on Differential and Functional Differential Equations Moscow, 2011. P. 56–57.

3. Faria T. Normal forms for semilinear functional differential equations in Banach spaces and applications // Discrete and Continuous Dynamical Systems. Vol. 7. P. 155–176.

4. Minh N. V., Wu J. Invariant manifolds of partial functional differential equations // J. of Differential Equations. 2004. Vol. 198. P. 381–421.

ОПРЕДЕЛЕНИЕ ГРАНИЦЫ ЛОКАЛЬНОЙ НЕОДНОРОДНОСТИ ПО

ИЗМЕРЕНИЯМ АКУСТИЧЕСКОГО ПОЛЯ

Кафедра математической физики, e-mail: [email protected] Рассматривается обратная задача определения неизвестных характеристик рассеивающей неоднородности по наблюдениям скалярного волнового поля, возбуждаемого некоторым источником. Области S и P, где соответственно расположены источники и происходит измерение полей, рассеянных неоднородностью, не пересекаются с областьюю H, содержащей рассеиватель, и зависят от постановки эксперимента. Задача рассматривается в волновом приближении и решение ищется в трехмерном пространстве R3. Рассмотрена граничная задача для уравнения Гельмгольца с условиями сопряжения на границе неоднородности H для функции u(r, s, ) и ее нормальных производных, где n — внешняя нормаль к границе:

здесь — частота, функция (r s)f (t) описывает возмущение среды точечным источником, расположенным в точке s R3, [·] обозначает разрыв значений функций на границе раздела сред. Коэффициент k(r, ) содержит всю информацию о неоднородности [1]:

Предполагаем, что среда однородна вне сферы достаточно большого радиуса:

Обратная задача сводится к нахождению коэффициента k(r, ) во втором уравнении системы (1). Подобная постановка распространена в задачах зондирования. Обратная задача решалась в предположении, что плотность постоянна ((r) = 0 ) и известна везде в R3.

От дифференциальной задачи (1) перейдем к интегральным уравнениям для неизвестной функции и запишем их отдельно для r H и r R:

где функция (r) = c2 c2 (r), G(r, s, ) = 4|rs| exp( c0 |r s|) — функция Грина для уравнения Гельмгольца, u0 (r, s, ) = G(r, x, )f ()(x s)dx. Запишем систему (2) в операторном виде:

где интегральные операторы H и P определены следующим образом:

Рассмотрим абстрактный аналог системы (3) в виде операторного уравнения F (x) = 0, где x = — вектор неизвестных. Для его решения использован итеративно регуляризованный метод Ньютона–Гаусса [2], на каждом шаге которого минимизируется по x функционал:

где n — параметр регуляризации. Выпишем итерационный процесс:

здесь F2n = F2 (xn ).

При начальном приближении 0 = 0 из уравнения F1 (u, ) = 0 находим u(0 ) = u0, тогда из (3) следует что F2 (u0, 0) = U, подставляем в (4) и вычисляем 1 и т. д. Следует заметить, что первый шаг итерационного метода совпадает с решением обратной задачи в борновском приближении P u0 = U.

На рис. 1 приведены результаты расчетов, которые проводились на основе модельных данных прямой задачи с внесенной погрешностью. Источники располагались в точках:

(0, 0, 0), (200, 200, 0), измерения проводились на сетке приемников 25 25, покрывающих Рис. 1. Результаты расчетов: a) определяемая неоднородность, б) начальное приближение, в) результаты 1-й итерации (борновское приближение), г) результыты 10-й итерации.

область 800 800 при z = 0. Лоцируемая область размером 200 200 200 находилась на расстоянии 70 м., в ней имелась неоднородность 90 20 90, скорость c0 в среде отличалась от c внутри неоднородности на 15%, = 400 Гц.

1. Горюнов А. А., Сасковец А. В. Обратные задачи рассеяния в акустике. — М. : Изд-во 2. Бакушинский А. Б., Гончарский А. В. Итеративные методы решения некорректных задач. — М. : Наука, 1989.

3. Тихонов А. Н., Самарский А. А. Уравнения математической физики. — М., 1967.

4. Тихонов А. Н., Арсенин В. Я. Методы решения некорректных задач. — М. : Наука,

СУПЕРКОМПЬЮТЕРНОЕ МОДЕЛИРОВАНИЕ ЭВОЛЮЦИИ

ТОРОИДАЛЬНОЙ ПЛАЗМЫ

Кафедра автоматизации научных исследований, e-mail: [email protected] Создан комплекс новых математических моделей, численных методов и программного обеспечения для реалистического моделирования на суперкомпьютерах плазмы в установках токамак [1, 2]. Комплекс позволил решить ряд важнейших задач современного этапа проекта перехода к относительно безопасным электростанциям с практически неисчерпаемым источником энергии на основе систем с магнитным удержанием плазмы. Сложность исследований состояла в необходимости изучения трех-шестимерных нелинейных моделей процессов с сильно различающимися характерными временами. Большую роль в успешном проведении исследований сыграло наличие в МГУ современной уникальной суперкомпьютерной техники.

Разработана иерархия математических моделей, доступных для исследования на современной вычислительной технике: 1) общая самосогласованная модель эволюции тороидальной плазмы с учетом токов различной природы; 2) модели кинетических процессов разной степени детализации; 3) модели управления и оптимизации процессов в плазме;

4) модели обратных задачи диагностики плазмы: восстановление эволюции равновесия плазмы, восстановление функции распределения частиц, восстановление распределения источника излучения по видеоизображению; 5) феноменологические модели с использованием адаптивных подходов data mining.

Тезисы конференции “Ломоносовские чтения” Предложены и обоснованы новые последовательные и параллельные численные методы, включая методы для супер-ЭВМ: 1) методы решения задач для многомерных кинетических уравнений: схемы расщепления с весами, явные схемы локальных итераций, модификации метода Монте–Карло для шестимерных задач; 2) методы решения самосогласованной задачи эволюции равновесия плазмы; 3) методы управление формой, положением и полным током плазмы, профилем коэффициента запаса устойчивости; 4) методы решения обратных задач: реконструкция равновесия плазмы методом -сетей, метод решения двумерного интегрального уравнения Вольтерра 1-го рода в непрямоугольной области, алгоритм восстановления источника излучения по фотоизображению; 5) адаптация методов нейросетей, опорных векторов, скрытых моделей Маркова для аппроксимации моделей, оптимизации поискового вычислительного эксперимента, решения обратных задач, анализа и визуализации больших объемов многомерных данных вычислительного и натурного экспериментов, включая графические, видео и звуковые данные.

Внесен существенный вклад в создание уникального программного обеспечения (ПО) проблемы управляемого термоядерного синтеза (УТС): 1) специализированных кодов:

FPP-3D — решение многомерных кинетических задач; SCoPE — расчет самосогласованной эволюция равновесия, решение обратных задач диагностики плазмы; SDSS — восстановление по измерениям плотности тока в плазме, ее формы и положения; 2) кодов общего назначения: VIP — реконструкция границы плазмы по видео изображению, MAGDI — визуализация, кластеризация, статистическое исследование данных магнитных измерений и анализ корреляций с другими диагностическими данными, FIRe — восстановление пространственного распределения источника излучения по видео высокого разрешения, CLUNAVT — структурный анализ баз видео, графических и звуковых данных, NNTMM — моделирование, оптимизация и анализ данных с помощью нейросетей; 3) кодов для автоматизации разработки программного обеспечения, проведения и поддержки вычислительного эксперимента: UMB — генератор программ, позволяющий из набора модулей собрать расчетную программу для решения конкретных задач; SCoPEShell — система запуска, мониторинга и визуализации расчетов; TADISYS — проведение независимых вычислений на сети ЭВМ.

Коды FPP-3D, SCoPE, VIP и SCoPEShell внедрены и используются в Culham Centre for Fusion Energy, Великобритания. Эти коды по своим характеристикам существенно превосходят аналоги. Код UMB внедрен в Российском федеральном ядерном центре, Всероссийском научно-исследовательский институте экспериментальной физики (г. Саров). Коды SDSS, MAGDI, FIRe, CLUNAVT и NNTMM не имеют аналогов.

Развиты и применены к решению задач УТС современные информационные и программистские технологии: удаленное проведение вычислительного эксперимента, методы распределённых вычислений, пакетная технология, объектно-ориентированный подход.

Разработана и реализована система имитационного моделирования “Виртуальный токамак”, позволившая выйти на уровень комплексного решения задач УТС. Система обеспечивает проведение через Интернет в графическом режиме через стандартный Web-браузер вычислительного эксперимента с использованием локально поддерживаемого ПО, его накопление и совершенствование, унификацию интерфейса взаимодействия кодов, создание документации.

Новые модели, методы, информационные подходы и ПО обеспечили первенство в получении физических результатов, решении задач оптимизации, сжатия информации, аппроксимации, прогнозирования, распознавания образов, классификации, анализа размерТезисы конференции “Ломоносовские чтения” ности данных, выделения главных факторов.

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

1. Зайцев Ф. С. Математическое моделирование эволюции тороидальной плазмы. — 2-е издание. — М. : МАКС Пресс, 2011. 640 с.

2. Костомаров Д. П., Зайцев Ф. С., Шишкин А. Г., Степанов С. В., Сучков Е. П. Автоматизация проведения вычислений в программном комплексе “Виртуальный токамак” // Вестн. Моск. ун-та. Сер. 15. Вычисл. матем. и киберн. 2012. № 4. С. 7–10.

Тезисы конференции “Ломоносовские чтения”

СЕКЦИЯ IV

Лаборатории троичной информатики и компьютерной графики и мультимедиа

ТРОИЧНАЯ СХЕМОТЕХНИКА — ПОДХОДЫ И СРЕДСТВА

Лаборатория троичной информатики ВМК, e-mail: [email protected] В основе Троичной Схемотехники лежит осмысление опыта, полученного более 50-и лет тому назад при создании троичных ЭВМ “Сетунь” [5]. Элементная база этих машин основывалась на электромагнитной технике, посредством которой была реализована Троичная Пороговая Логика [6]. Впоследствии электромагнитную технику вытеснили интегральные полупроводниковые схемотехники.

В 2009–2012 гг. были созданы и запатентованы функциональные аналоги элементов и узлов “Сетуней”, реализуемые средствами интегральных технологий: Пороговый Элемент Троичной Логики (ПЭТЛ) [1] и Устройство Троичной Схемотехники (УТС) [2], состоящее из 3-х ПЭТЛ. Несмотря на то, что ПЭТЛ является аналогом логических элементов “Сетуней”, а в аппаратном отношении его прототипом стал элемент существующей ЭСЛ-схемотехники, напрямую использовать известные решения и инструментарий при проектировании троичных цифровых устройств не удается. Для этой цели потребовалась специальная Троичная Схемотехника (ТС) [3,4].

От существующих схемотехник ТС отличается подходами, приемами и изобразительными средствами. Она находится в стадии развития и постоянно пополняется. В докладе использование ТС демонстрируется на примерах нескольких троичных комбинационных схем: полусумматора, дешифраторов, мультиплексоров и демультиплексоров.

1. Маслов С. П. Пороговый элемент троичной логики и устройства на его основе. — Патент РФ на изобретение: RU № 2278469 C1.

2. Маслов С. П. Узел троичной схемотехники и дешифраторы-переключатели на его основе. — Патент РФ на изобретение: RU № 2461122 C1.

3. Маслов С. П. Об одной возможности реализации троичных цифровых устройств // Программные системы и инструменты : тематический сборник. № 12. М. : Изд-во факультета ВМиК МГУ, 2011. С. 222–227.

4. Маслов С. П. Троичная схемотехника // Программные системы и инструменты : тематический сборник. № 13. М. : Изд-во факультета ВМиК МГУ, 2012.

5. Брусенцов Н. П., Жоголев Е. А., Маслов С. П., Рамиль Альварес Х. Опыт создания троичных цифровых машин // Компьютеры в Европе. Прошлое, настоящее и будущее.

Киев : Феникс, 1998. С. 67–71.

6. Брусенцов Н. П. Пороговая реализация трехзначной логики электромагнитными средствами // Вычислительная техника и вопросы кибернетики. Вып. 9. М. : Изд-во Моск.

ун-та, 1972. С. 3–35.

РЕШЕНИЕ ЗАДАЧИ ОПРЕДЕЛЕНИЯ ОПТИМАЛЬНОГО НАБОРА

СПОСОБОВ ВЫБОРОЧНОГО ИЗОТОПНОГО МЕЧЕНИЯ АМИНОКИСЛОТ В

ПРОТЕИНАХ В ЦЕЛЯХ ОТНЕСЕНИЯ ПИКОВ НА ДВУМЕРНЫХ СПЕКТРАХ

ЯМР ПРИ ПОМОЩИ ТРОИЧНОЙ ЛОГИКИ

Владимирова Юлия Сергеевна1, Дубинный Максим Анатольевич Лаборатория троичной информатики ВМК, e-mail: [email protected] Институт биоорганической химии им. академиков М. М. Шемякина и Ю. А. Овчинни кова РАН (ИБХ), e-mail: [email protected] Метод ЯМР-спектроскопии позволяет рассчитывать пространственную структуру белков [1], изучать их динамику [2], а так же находить и разрабатывать лекарства, специфичные к белковым мишеням [3]. Для любого из этих приложений необходимо в первую очередь получить отнесение сигналов белковой молекулы в спектрах ЯМР, то есть установить резонансные частоты возможно большего числа атомных ядер в многомерных ЯМР спектрах изотопно-меченого (13 C/15 N) белка. Для решения данной задачи традиционно используются методы последовательного отнесения сигналов [4], но их применение к белкам большого молекулярного веса и к мембранным белкам наталкивается на значительные трудности.

Один из способов преодоления этих трудностей связан с бесклеточным синтезом белка [5] с использованием изотопно-меченых аминокислот. Пептидная связь, соединяющая два соседних аминокислотных остатка, включает в себя карбоксильную (CO) группу предыдущего остатка и амидную (NH) группу последующего остатка. Комбинирование немеченых/15 N/13 C меченых аминокислот (далее X/N/C) позволяет при помощи двух спектров 2D 15 N-HSQC и 2D 15 N/13 C-HN(CO) различить три возможных ситуации [6]: 1) в обоих спектрах нет сигнала, код “0”, соответствует ситуации, когда вторая аминокислота в паре мечена X или С; 2) сигнал наблюдается HSQC спектре и отсутствует в HN(CO) спектре, код “1”, соответствует ситуации, когда вторая аминокислота мечена N, а первая X или N и 3) сигнал есть в обоих спектрах HSQC и HN(CO), код “2”, соответствует ситуации, когда вторая аминокислота в паре мечена N, а первая — C.

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

алгоритм оперирует отношениями между особенностями пар. Для решения поставленной задачи в первую очередь требуется адекватное алгебраическое выражение отношений, имеющееся в методе индексов Льюиса Кэрролла [7], основанном на выражении посылок силлогистики Аристотеля в виде троичных алгебраических объектов [8]. Применение метода индексов для оперирования логическими отношениями позволяет для каждого белка последовательно строить уникальные, минимальные по длине троичные коды аминокислот без обращения к переборным методам.

1. Guerry P., Herrmann T. Advances in automated NMR protein structure determination // Q.

Rev. Biophys. 2011. Vol. 44. P. 257–309.

2. Osawa M., Takeuchi K., Ueda T., Nishida N., Shimada I. Functional dynamics of proteins revealed by solution NMR // Curr. Opin. Struct. Biol. 2012. Vol. 22. P. 660–669.

3. Wirmer-Bartoschek J., Bartoschek S. NMR in drug discovery on membrane proteins // Future Med. Chem. 2012. Vol. 4. P. 869–875.

4. Permi P. Aspects of coherence transfer in high molecular weight proteins // Annu. Reports Nmr Spectrosc / edited by Graham Webb. 2004. Vol. 53. P. 245–296.

5. Whittaker J. W. Cell-free protein synthesis: the state of the art // Biotechnol. Lett. 2013.

Vol. 35. P. 143–152.

6. Maslennikov I. et al. Membrane domain structures of three classes of histidine kinase receptors by cell-free expression and rapid NMR analysis // Proc. Natl. Acad. Sci. 2010.

Vol. 107. P. 10902–10907.

7. Кэрролл Л. Символическая логика. — Л. Кэрролл. История с узелками. — М. : Мир, 8. Брусенцов Н. П., Владимирова Ю. С. Аристотелева силлогистика в символической логике Льюиса Кэрролла. — М. : Фонд “Новое тысячелетие”, 2011.

СОПРОГРАММНЫЙ МЕХАНИЗМ В ДССП ДЛЯ ТВМ

Лаборатория троичной информатики ВМК, e-mail: [email protected] В 2010–2012 гг. в НИЛ троичной информатики ВМК МГУ созданы [1,2,3]: 1) ТВМ — программный имитатор троичной машины двухстековой архитектуры; 2) ДССП-ТВМ — кросссистема разработки программ для ТВМ на языке ДССП-Т; 3) ДССП/ТВМ — интерпретатор языка ДССП-Т, способный функционировать на ТВМ как резидентное ПО. Язык ДССП-Т был разработан как троичный вариант языка ДССП [4] с учетом возможности его обработки не только интерпретатором, но и кросс-компилятором. В настоящее время и сама ТВМ, и ДССП для неё продолжают развиваться. В представленной работе предложено дополнить язык ДССП-Т операциями сопрограммного механизма.

Сопрограммный механизм в качестве удобного способа структурирования сложных программ предложили использовать ещё Дал и Хоор в своей знаменитой статье “Иерархические структуры программ” [5, ч. 3]. Сначала он появился в языке Симула-67. Впоследствии он был включен Виртом в язык Модула-2 [6] и успешно использован при построении Тезисы конференции “Ломоносовские чтения” модулей-мониторов параллельных процессов и программ, управляющих одновременной работой нескольких внешних устройств.

Для ДССП [4] сопрограммный механизм был реализован сначала в версии ДССП-РВ (на PDP-11), затем в версии ДССП-32p (для Intel-x86), а впоследствии и для мобильной версии ДССП/С. На основе сопрограммного механизма в ДССП (и на языке ДССП!) созданы разнообразные мониторы параллельных процессов [7].

Реализация сопрограммного механизма в ДССП для ТВМ основывается на версии (3a) языка ДССП-Т, обеспечивающей средства построения новых типов данных [8], и выполнена с учётом особенностей архитектуры самой ТВМ и специфики исполнения операций ассемблерного ядра ДССП.

Основная операция {CX,CY} TRANSFER {CZ}, предусмотренная в ДССП для переключения с одной сопрограммы на другую, требует сохранения контекста текущей сопрограммы (CX) и восстановления контекста возобновляемой сопрограммы (CY), а CX, CY и CZ должны быть объявлены в ДССП-программе как переменные особого типа CONTEXT, например: CONTEXT VAR CA.

Тип CONTEXT определён в ДССП как структура, содержащая поля для хранения значений регистров-указателей (DSP, DSPL, DSPH) (CSP, CSPL, CSPH), характеризующих состояния стека данных и стека возвратов сопрограммы. Для переключения контекста ДССП-программы, исполняемой на ТВМ, оказывается достаточным сохранить в этих полях (и восстановить из таких же полей переменной другой сопрограммы) лишь значения этих регистров, что является еще одним преимуществом машин подобной двухстековой архитектуры.

С помощью сопрограммного механизма удалось значительно облегчить разработку в ДССП-ТВМ ряда программ. Примерами тому могут служить игровая программа угадывания девятеричного числа; и простой монитор, управляющий развитием квазипараллельных процессов, в котором предусмотрены операции запуска процессов с возможностью их задержки на заданное время или приостановки с целью возобновления другого процесса из их круговой очереди.

1. Сидоров С. А., Владимирова Ю. С. Троичная виртуальная машина // Программные системы и инструменты : тематический сборник. № 12. М. : Изд-во факультета ВМиК МГУ, 2011. С. 46–55.

2. Бурцев А. А., Рамиль Альварес Х. Кросс-система разработки программ на языке ДССП для троичной виртуальной машины // Программные системы и инструменты :

тематический сборник. № 12. М. : Изд-во факультета ВМиК МГУ, 2011. С. 183–193.

3. Бурцев А. А., Бурцев М. А. ДССП для троичной виртуальной машины // Труды НИИСИ РАН. Т. 2, № 1. М. : НИИСИ РАН. С. 73–82.

4. Бурцев А. А., Сидоров С. А. История создания и развития ДССП: от “Сетуни-70” до троичной виртуальной машины // Вторая Международная конференция “Развитие вычислительной техники и её программного обеспечения в России и странах бывшего СССР” (SORUCOM-2011). В. Новгород : НовГУ, 2011. C. 83–88.

5. Дал У., Дейкстра Э., Хоор К. Структур(ирован)ное программирование. — М. : Мир, 1975. Ч. 3. С. 209–217.

6. Вирт Н. Программирование на языке Модула-2. — М. : Мир, 1987. С. 137–150, 179–180.

7. Бурцев А. А., Шумаков М. Н. Сопрограммный механизм в ДССП как основа для построения мониторов параллельных процессов // Вопросы кибернетики / сб. статей под ред. В. Б. Бетелина. М., 1999. С. 45–63.

8. Бурцев А. А., Рамиль Альварес Х. Реализация средств объектно-ориентированного программирования в кросс-компиляторе языка ДССП-Т // Программные системы и инструменты : тематический сборник. № 13. М. : Изд-во факультета ВМК МГУ, 2012.

АЛГОРИТМЫ ДЛЯ АВТОМАТИЗАЦИИ СИСТЕМ ВИДЕОНАБЛЮДЕНИЯ

Конушин Антон Сергеевич1, Кононов Владимир Андреевич1, [email protected], [email protected] ООО ”Технологии видеоанализа”, e-mail: [email protected] Системы видеонаблюдения в настоящее время получили повсеместное распространение.

В одном Лондоне установлено до 500 000 камер видеонаблюдения. При этом их эффективность в настоящее время подвергается широкой критике. Данные видеонаблюдения используются в основном постфактум, уже после наступления какого-нибудь важного события, например, правонарушения. При этом для поиска нужных людей или объектов требуется просматривать многие сотни и тысячи часов видеозаписей. Возникает необходимость в автоматизации существующих систем видеонаблюдения, которая бы позволила существенно сократить время поиска людей и объектов в видеоархивах, и, потенциально, позволила бы распознавать события в реальном времени [1]. Для этого в первую очередь необходимо выделение, распознавание и аннотация движущихся объектов в видеопотоке.

Решение этих задач позволит при поиске оперировать не с массивом исходного видео, а с базой данных аннотированных объектов.

Алгоритмы распознавания объектов в видеопотоке можно разделить на несколько классов в зависимости от рассматриваемого сценария съемки, т. е. накладываемых ограничений на положение камеры наблюдения относительно объектов съемки. В докладе рассматриваются два сценария. В первом камера расположена на высоте 1.5–2.5 метра, и соотношение разрешения камеры и расстояния до наблюдаемых людей таково, что на изображении различимы отдельные черты лица. В этом сценарии для аннотации видеопотока можно применять алгоритмы распознавания и классификации человека по лицу [2]. Во втором сценарии может использоваться обычное расположение камер видеонаблюдения, при котором черты лица человека плохо различимы, поэтому аннотацию видеопотока можно проводить только по атрибутам всей фигуры человека, как, например, в [3]. Однако в этом сценарии фигуры людей видны в полный рост, поэтому можно использовать информацию о калибровке камеры и оценивать положение человека в сцене.

В докладе рассматриваются разработанные нами алгоритмы для выделения, сопровождения, классификации и аннотации объектов в видеопотоке для обоих указанных сценариев. Для методов распознавания и классификации изображений лиц приводятся результаты Работа выполнена при поддержке гранта Президента Российской Федерации для государственной поддержки молодых российских ученых — кандидатов наук МК-4644.2012.9 и гранта РФФИ 11-01-00957-а.

экспериментальной оцнеки на открытой эталонной коллекции изображений LFW [4], состоящей из более 13 000 фотографий, взятых из сети интернет. Для оценки алгоритмов выделения, сопровождения и поиска объектов в видеоархиве используются специально собранные и размеченных коллекции изображений и видеофрагментов.

1. Ramachandran U. et. al. Large-scale situation awareness with camera networks and multimodal sensing // Proceedings of IEEE. 2012. Vol. 100, N 4. P. 878– 2. Kumar N., Belhumeur P. N., Nayar S. K. FaceTracer: A search engine for large collections of images with faces // Proc. ECCV. 2008. P. 340–353.

3. Zheng W., Gong W., Xiang T. Person re-identification by probabilistic relative distance comparison // Proc. CVPR. 2011. P. 649–656.

4. Huang B, Ramesh M., Berg T., Learned-Miller E. Labeled faces in the wild: A database for studying face recognition in unconstrained environments // Technical report. University of Massachusetts, Amherst : October 2007. P. 07–49.

ВЫДЕЛЕНИЕ И РАСПОЗНАВАНИЕ ДОРОЖНЫХ ЗНАКОВ

Конушин Антон Сергеевич, Чигорин Александр Александрович Кафедра автоматизации систем вычислительных комплексов, e-mail: [email protected], [email protected] Выделение объектов на изображениях является одной из основных задач компьютерного зрения. Для ее решения наиболее широко используется метод “скользящего окна”. Изображение разбивается на множество пересекающихся прямоугольных областей, и к каждой независимо от остальных применяется бинарный классификатор. Для того, чтобы объект попал целиком в одну из областей, для изображения с разрешением в 1 мегапиксель необходимо обработать до 1 млн. областей. Поскольку в одном изображании обычно запечатлено от 0 до 10 объектов нужного класса, то задача классификации окон ассиметричная.

Поэтому доля ложноположительных ошибок классификатора должна быть менее 106, а при выделении объектов в видеополследовательностях менее 109.

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

В докладе будут рассмотрены разработанные нами алгоритмы выделения объектов на основе каскадов классификаторов [2]. При этом обучение алгоритмов распознавания предлагается проводить на синтических коллекциях изображений, для генерации которых предложен специальный алгоритм. Использование синтетических коллекций позволяет решить Работа выполнена при поддержке гранта РФФИ 12-01-33085.

Тезисы конференции “Ломоносовские чтения” проблему редко встречающихся типов знаков. Также предложена модификация каскадного алгоритма выделения объектов на основе многослойных нейросетей [3], позволяющая повысить точность распознавания при заданной доле ложноположительных ошибок.

1. Stallkamp J., Schlipsing M., Salmen J., Igel C. The german traffic sign recognition benchmark: A multi-class classification competition // Proc. Intern. Joint Conf. on Neural Networks. 2011. P. 1453– 2. Чигорин А. А., Конев А. А., Кривовязь Г. Р., Велижев А. Б., Конушин А. С. Распознавание знаков дорожного движения на изображениях, с обучением на синтетических данных // Сборник трудов научно-технической конференции “Техническое зрение в системах управления 2012” С. 165–169.

3. Sermanet P., Lecun Y. Traffic sign recognition with multi-scale convolutional networks // Proc. of Intern. Joint Conf. on Neural Networks. 2011. P. 2809–2813.

СЕКЦИЯ V

ПРИНЦИП МАКСИМУМА ПОНТРЯГИНА ДЛЯ ЗАДАЧИ ОПТИМАЛЬНОГО

УПРАВЛЕНИЯ С ФУНКЦИОНАЛОМ, ЗАДАННЫМ НЕСОБСТВЕННЫМ

ИНТЕГРАЛОМ

Математический институт им. В. А. Стеклова РАН, IIASA, e-mail: [email protected] Венский технический университет, Австрия, e-mail: [email protected] Рассмотрим следующую задачу оптимального управления (P ):

множество, U Rm — произвольное непустое множество, x0 G — заданное начальное состояние. Класс допустимых управлений в задаче (P ) состоит из всех измеримых (по Лебегу) локально ограниченных функций u : [0, ) U.

Предполагается выполненным следующее условие.

(A1) Функции f (t, x, u), f 0 (t, x, u) и их частные производные, fx (t, x, u), fx (t, x, u) измеримы по t для любых (x, u) G U, непрерывны по (x, u) при п.в. t [0, ) и локально ограничены.

Определение. Допустимое управление u (·), для которого соответствующая траектория x (·) определена на [0, ), называется локально слабо-обгоняющим в задача (P ), если существует такое > 0, что для любого допустимого u(·), удовлетворяющего неравенству meas{t 0 : u(t) = u (t)}, и такого, что соответствующая траектория x(·) определена на [0, ), и любого > 0 существует такая возрастающая положительная последовательность Ti, i, что Следующее условие играет центральную роль в получении полного варианта принципа максимума Понтрягина для локально слабо-обгоняющего допустимого управления u (·) в задаче (P ) при помощи классического метода игольчатых вариаций [1].

Работа первого автора выполнена при частичной финансовой поддержке РФФИ (проект N 13-01-00685-a) и ДРПННиТ (проект N 1.1348.2011).

Локальная ограниченность функции : [0, ) G U Rk означает, что для любого T > 0, любого компакта D G и любого ограниченного V U существует такое M 0, что (t, x, u) M при п. в.

(A2) Существует такие число > 0 и интегрируемая функция : [0, ) R1, что для имеет решение (в смысле Каратеодори) x(; ·) на [0, ) в G и Теорема. Пусть u (·) — локально слабо-обгоняющее управление в задаче (P ) и выполняется условие (A2). Тогда функция : [0, ) Rn, определенная равенством (локально) абсолютно непрерывна и удовлетворяет соотношениям принципа максимума в нормальной форме, т. е.

(i) функция (·) удовлетворяет сопряженной системе:

(ii) выполняется условие макисмума:

Здесь Z (t) — нормированная фундаментальная матрица сопряженной системы функция Гамильтона–Понтрягина для задачи (P ) в нормальной форме.

Данный результат аналогичен теореме 4 из [2], однако он получен при ослабленных предположениях на сходимость интегрального функционала полезности. Доказательство и обсуждение результата приведено в [3].

1. Понтрягин Л. С., Болтянский В. Г., Гамкрелидзе Р. В., Мищенко Е. Ф. Математическая теория оптимальных процессов. — М. : Физматгиз, 1961.