WWW.MASH.DOBROTA.BIZ
БЕСПЛАТНАЯ  ИНТЕРНЕТ  БИБЛИОТЕКА - онлайн публикации
 

«Оптимальный метод перераспределения общей памяти для двухприоритетной очереди, представленной в виде двух последовательных циклических FIFO-очередей Аксенова Е. А., Соколов А. В. ...»

417

Секция Информатика и прикладные исследования

Оптимальный метод перераспределения общей памяти

для двухприоритетной очереди, представленной в виде

двух последовательных циклических FIFO-очередей

Аксенова Е. А., Соколов А. В .

(Петрозаводск, Институт прикладных математических

исследований КарНЦ РАН, Петрозаводский государственный

универстет)

aksenova@krc.kareia.ru, avs@krc.karelia.ru

Во многих приложениях используется структура данных, в которой основными операциями являются вставка элемента и удаление элемента с наибольшим приоритетом. Такую структуру данных называют приоритетной очередью. Основными методами реализации приоритетной очереди являются упорядоченные и неупорядоченные списки, массивы, бинарные деревья, пирамиды [1]–[3]. Эти методы сравниваются с точки зрения стоимости (времени) выполнения основных операций. В работах [4]–[7] предлагались математические модели для последовательного циклического и связанного способов представления очередей и решались задачи оптимального начального распределения памяти для разных критериев оптимальности .

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



Рассмотрим очередь с двумя приоритетами, расположенную памяти размера единиц.

Будем считать, что время дискретно, и в 418 Интеллектуальные системы и компьютерные науки каждый момент времени происходит одна из следующих операций:

– вставить элемент с приоритетом с вероятностью ( = 1, 2),

– удалить элемент с наибольшим приоритетом с вероятностью,

– найти элемент с наибольшим приоритетом с вероятностью, где 1 + 2 + + = 1 .

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

Выделим первой FIFO-очереди единиц памяти, тогда для второй останется единиц. Обозначим текущие длины очередей 1 и 2 .

В качестве математической модели рассмотрим случайное блуждание по целочисленной решетке в прямоугольной области на плоскости 0 1 +1, 0 2 +1. Блуждание начинается в точке 1 = 0, 2 = 0. Переполнению первой FIFO-очереди соответствуют точки на прямой 1 = + 1, переполнению второй точки на прямой 2 = + 1. Прямые 1 = 1 и 2 = 1 отражающие экраны, то есть при исключении элемента из пустой очереди работа не завершается .



Требуется оптимально перераспределить свободную память между FIFO-очередями после переполнения одной из них. То есть, при попытке включения элемента в заполненную FIFO-очередь, когда (или 2 = ), требуется определить новую область блуждания 0 1 + 1, 0 2 + 1, то есть такое значение, где (или ), чтобы время до следующего переполнения какой-либо FIFO-очереди было максимальным. Этот процесс перераспределения можно продолжать до полного исчерпания свободной памяти. Такой подход оправдан, если при переполнении одной из FIFO-очередей, в области памяти, выделенной для других очередей, есть достаточно свободной памяти. В алгоритме Гарвика [1] для Секция Информатика и прикладные исследования работы с последовательными стеками и очередями при переполнении какой-либо структуры данных приблизительно 10% свободной памяти делится поровну между структурами данных, а оставшиеся 90% делятся пропорционально росту размеров структур данных с момента предыдущего распределения памяти .

Математическая постановка задачи сводится к решению задачи нелинейного целочисленного программирования, с критерием оптимальности, заданным алгоритмически. Случайное блуждание по целочисленной решетке будем рассматривать как конечную однородную поглощающую цепь Маркова с матрицей вероятностей переходов P [8]. Для решения задачи требуется матрица вероятностей переходов из невозвратных состояний в невозвратные ( подматрица матрицы ). Вводится нумерация состояний Марковской цепи, это позволяет определить структуру матрицы для любого размера памяти и любого значения. Среднее время работы до переполнения = ( )1 .

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

Алгоритм:

–  –  –

6) Для каждого значения суммируем элементы матрицы в строке, соответствующей рассматриваемому состоянию ( 1 = или 2 = );

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

Шаги 5–7 можно повторять до полного исчерпания свободной памяти (если перед каждым новым прераспределением текущее значение обозначить как ) .

Вычисление критерия оптимальности в данной задаче является очень ресурсоемким за счет обращения матрицы ( ) большого = ( )1 = размера. Матрицу можно представить в виде 2 +... =. Для данной задачи такое представление ++ =0 матрицы дает выигрыш в размере памяти для вычислений. Поскольку для алгоритма важна сумма элементов в определенной строке матрицы N, то запись в виде суммы ряда позволяет вычислять элементы конкретной строки, не вычисляя остальных элементов матрицы .





Работа выполнена при финансовой поддержке РФФИ, грант 09–01–00330 .

Список литературы

[1] Кнут Д. Искусство программирования для ЭВМ. М.: Вильямс, 2001 .

[2] Седжвик Р. Фундаментальные алгоритмы на С++. К.: Диасофт, 2001 .

[3] Боллапрагада В., Мэрфи К., Уайт Р. Структура операционной системы Cisco IOS. М.: Вильямс, 2002 .

[4] Аксенова Е. А., Соколов А. В. Некоторые задачи оптимального управления FIFO-очередями // Труды Второй Всероссийской научной конференции Методы и средства обработки информации. М.: Изд. отдел ВМК МГУ им. М. В. Ломоносова, 2005 .

С. 318–322 .

Секция Информатика и прикладные исследования [5] Аксенова Е. А. Оптимальное управление FIFO-очередями на бесконечном времени // Межвузовский сборник Стохастическая оптимизация в информатике. СПб: Изд-во С.-Петербургского унта, 2006. С. 71–76 .

[6] Аксенова Е. А., Драц А. В., Соколов А. В. Об оптимальном управлении FIFO-очередями на бесконечном времени // Обозрение прикладной и промышленной математики. 2009. Т. 16. Вып. 3 .

С. 401–415 .

[7] Аксенова Е. А., Драц А. В., Соколов А. В. Оптимальное управление FIFO-очередями на бесконечном времени // Информационно-управляющие системы. 2009. № 6. С. 46–54 .

[8] Кемени Дж., Снелл Дж. Конечные цепи Маркова. М.: Наука, 1970 .

422 Интеллектуальные системы и компьютерные науки

–  –  –

В работе рассмотрены математические методы краткосрочного прогнозирования .

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

Прогнозирование стоимости акций на следующих дней Сформирован портфель из акций пяти различных компаний. Известна динамика изменения курса этих акций стоимость акций за определённый период времени: дней. Требуется оценить стоимость акции каждой компании в период с ( +1)-го по ( + )-ый день. В работе представлены три подхода, позволяющие решить поставленную задачу .

Метод с предиктором .

Данный метод является методом линейного прогнозирования, аналогичным методу наименьших квадратов (МНК).

В его основе лежит решение следующей задачи на минимум:

(1) min где матрица, каждая строка которой составлена из пяти временных рядов (по количеству типов акций) одинаковой длины, элементами (уровнями) которых являются стоимости акций, следующая строка получается сдвигом предыдущей на один шаг вперёд (таким образом, что в каждой следющей строке кроме первой используется пять новых значений относительно предыдущей), предсказывающая матрица или предиктор, матрица, каждая строка которой состоит из 5 значений стоимостей акций, опережающих значения в Секция Информатика и прикладные исследования соответствующей строке матрицы на число шагов от 1 до. Проще говоря, при умножении одной строки матрицы на предиктор появятся 5 будущих значений стоимостей акций, составляющих матрицу .

Вероятностный аналог данного метода рассмотрен в [2] .

Метод, минимизирующий среднеквадратичное отклонение .

Пусть матрица размера 5, каждая из пяти строк которой (по числу типов акций) представляет собой временной ряд длины, вектор, составленный из цен акций, опережающих соответствующие значения в на один шаг (на один день). Введём векторы : и :5 такие, что преобразование + было как можно ближе в среднеквадратичном к.

Таким образом, необходимо решить следующую задачу:

+ 2 min (2) 1, = +1 Требуется решить задачу на минимум (2) и найти,, если известны вектор и матрица .

Анализ методов .

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

424 Интеллектуальные системы и компьютерные науки

–  –  –

при должным образом выбранном 0, где гильбертово пространство функций на [, ] с абсолютно непрерывной 1 производной и суммируемых в квадрате производной:

()2 (4) ( )() Решением этой задачи также является сплайн, называемый сглаживающим, его гладкость тем выше, чем меньше .

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

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

Секция Информатика и прикладные исследования

–  –  –

Таблица 1. Значения ( ) для каждого метода .

Параметр = 2 .

МП метод с предиктором, ММСК метод, минимизирующий с.к .

отклонение, МС метод, использующий сглаживающие сплайны, МБ метод Брауна, МХ метод Хольта .

Судя по полученным результатам, не следует ожидать улучшения качества прогноза без учёта модели данных. Если модель известна приближённо, то можно поставить задачу оптимального предсказания. Приведём пример модели данных, в которых предсказание на основе обучения невозможно. Рассмотрим двоичное представление 426 Интеллектуальные системы и компьютерные науки

–  –  –

[1] Бокс Дж., Дженкинс Г. Анализ временных рядов: прогноз и управление. 1974 .

[2] Цыплаков А. Введение в прогнозирование в классических моделях временных рядов // Квантиль. № 1. С. 3–19 .

[3] Лукашин Ю. П. Адаптивные методы краткосрочного прогнозирования временных рядов. М.: Финансы и статистика, 2003 .

[4] Дегтярёв К. Прогнозирование валютных котировок с использованием модифицированного стационарного метода, основанного на нечетких временных рядах .

Секция Информатика и прикладные исследования Конфликты между методами математики и механики и техногенные катастрофы Величенко В. В. (Москва, Институт машиноведения РАН, МГУ им. М. В. Ломоносова) vlad.velichenko@mail.ru Рассматриваются технические и теоретические проблемы техногенных катастроф. Детально анализируются конфликты между методами математики и механики, приводящие при их формально правильном использовании к ошибочным выводам .

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

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

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

Единственная надежда на создание этих новых областей науки и техники сегодняшние студенты. Им автор и адресует эту статью, которую можно считать введением в эту новую специальность. Специальность эта заключается в борьбе со страшным противником, и 428 Интеллектуальные системы и компьютерные науки автор говорит о нем неприкрашенную правду. Но рассказать студентам, почему именно утонули такие знаменитые океанские корабли, как Титаник и Конкордия, и почему упали такие знаменитые космические корабли, как Челленджер и Фобос, в этой статье невозможно не хватит места, и требуются предварительные специальные знания. Мы расскажем здесь о вещах более доступных, уже отчасти известных студентам, и еще более важных .

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

Материал этой статьи почти элементарный, доступен студентам 2–3 курсов, но затрагивает фундаментальные вопросы математики, механики и техники .

1. Технические и теоретические проблемы техногенных катастроф

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

Эти причины лежат на поверхности. Глубже лежат причины менее очевидные. Например, когда уважаемые ученые под давлением государственной необходимости, а на самом деле примитивного экономического поощрения, обоснованно продлевают сроки ресурсов уже отработавших свой регламент опасных установок и производств, в том числе и таких, как атомные электростанции. Богатую питательную среду для роста катастроф культивируют экономика и политика. Авиационные корпорации в погоне за прибылью соревнуются в изготовлении огромных самолетов, и в непредсказуемой атмосфере, запечатанные в этих ненадежных гигантах сотни (в последних моделях почти тысяча) пассажиров загадывают итог каждого рейса: пронесет не пронесет. Конкурирующие автомобильные магнаты рекламируют и производят автомобили все большей, ничем и никем не обоснованной и не ограниченной мощности, и обыватель, получив в свои руки ракету на колесах, становится убийцей на большой дороге, и самоубийцей. Физика создает энергостанции все большей мощности обещания будущих глобальных катастроф. Ученые обсуждают на конгрессах негативные последствия потепления климата нашей планеты а техника судорожно тратит остатки природных ресурсов на ее нагрев. Военные техника и наука занимаются профессиональным производством катастроф вообще не задумываясь об их последствиях. Правители получили в свои руки оружие, способное на любом расстоянии от их безопасных кабинетов поразить любую цель, и превращают слабые страны в руины, разрушая тем самым и свою будущую безопасность. Эти причины предмет для исследований прокуроров и геополитиков .

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

Вместе с тем, она является одной из главных:

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

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

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

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

Ошибки проектирования и расчетов ведут к авариям и катастрофам объектов, но одновременно разрушают эти проекты и расчеты .

Имея в виду эти две деструктивных характеристики, их можно назвать катастрофами проектов и катастрофами расчетных методов .

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

Секция Информатика и прикладные исследования Эти вопросы должны быть предметом специального изучения профессиональных математиков и механиков. Но для них они представляют только теоретический интерес, тогда как в прикладных областях, в руках инженеров, они непосредственно ведут к реальным катастрофам. Эти прикладные области в условиях современных требований совершенствования и интенсификации техники чрезвычайно сложны, требуют обширных и глубоких специальных знаний, и умения владеть многими экспериментальными и теоретическими инструментами. Среди прочих, конечно, математикой и классической механикой самыми надежными средствами науки, веками проверенными практикой. Перечислениям имен ученых, разработавших мощные инструменты математики и механики, и их достижениям посвящены энциклопедии, и мы тоже будем ссылаться на гениев этих наук Галилея, Ньютона, Лагранжа, Эйлера [1]–[3], [4]. Но наша цель здесь другая: не продемонстрировать еще раз замечательные возможности этих инструментов математики и механики, а, наоборот, указать на катастрофические конфликты между этими безупречными науками .

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

Здесь критика стала вообще неуместной, как в храме, или на кладбище .

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

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



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

То есть ищет то, что лежит под фонарем, а не то, что нужно .

Техника за 250 лет после трудов Лагранжа опутала Землю сетью железных дорог и авиалиний, разъединила материки и соединила океаны каналами, достигла планет, а теоретическая механика все та же Ньютонова и Лагранжева. Выдающиеся успехи самой передовой отрасли техники космонавтики обеспечены теорией движения одной материальной точки Ньютона и теорией движения одного Секция Информатика и прикладные исследования твердого тела Эйлера трехвековой давности! И это на фоне гигантских успехов, достигнутых за это время другими науками .

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

Приведенные пессимистичные оценки автор в равной степени относит и к себе. Тема настоящей статьи является фрагментом общей проблемы Моделирование и управление катастрофами с целью минимизации наносимого ими ущерба [5]–[10]. Катастрофы свирепствуют с нарастающей силой, а мы все еще разрабатываем проект будущей общей теории катастроф, конструируя детали инструментов для исследования сложных и рваных динамических процессов [11]– [18]. Некоторые попытки приложений этих инструментов в аварийной и катастрофической динамике летательных и космических аппаратов [19]–[23], и в задачах управления катастрофами человеческого организма [24]–[28] оказались относительно успешными. Однако в анализе катастрофического развала и возможностей стабилизации экономики [29]–[31] научные рекомендации остаются благими пожеланиями. А в проблеме автоматизации управления катастрофами, где требуются мгновенные и жесткие решения, которые неспособен принять эмоциональный человек в момент внезапной опасности, сделаны лишь первые шаги [32]–[38] .

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

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

434 Интеллектуальные системы и компьютерные науки Представленный в настоящей статье фрагмент этой объемной темы особенный. Все указанные выше работы посвящены решению задач моделирования и управления уже возникшими катастрофами;

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

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

В свете сказанного, мы далее будем параллельно обсуждать технические катастрофы, и их причины проектно-расчетные и теоретические катастрофы .

2. Технические и проектно-расчетные катастрофы

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

Приведем несколько примеров. Часть их общеизвестна, часть взята из личных наблюдений автора .

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

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

Вблизи берега Новороссийской бухты, в 1961 г. встретились и не разминулись два корабля пассажирский лайнер Адмирал Нахимов (немецкой постройки) и некий сухогруз. Лайнер ушел на дно с сотнями пассажиров. Капитаны судов, не согласовавших свои курсы, остались невредимыми и получили по 15 лет тюрьмы. Настоящая причина катастрофы задержка отправления пассажирского корабля в ожидании высокопоставленного чиновника не афишировалась .

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

Автор не успел закончить эту статью, а услужливая статистика предоставила ему еще один пример ровно через сто лет после Титаника, в январе 2012 г. еще более огромный и представительный лайнер с тысячей кают Коста Конкордия сел на риф в Средиземном море и лег на борт, раздавив часть пассажиров .

Это очевидные причины произошедших катастроф. Но! Если бы корпуса всех этих судов были спроектированы правильно, все эти очевидные причины не привели бы к гибели кораблей! Очевидно, что для огромных кораблей Титаника и Новороссийска полученные ими пробоины были бы всего лишь неприятным случаем, если бы их корпуса были спроектированы с минимальной грамотностью. Кто же должен сидеть в тюрьме в ответе за тысячи погибших людей? Капитаны, или проектировщики? Которые уже в проектах заложили те самые мины замедленного действия, которые должны были взорваться и заполнить водой трюмы этих заранее обреченных кораблей. Те мины, которые ждали только внешних обстоятельств, заИнтеллектуальные системы и компьютерные науки пустивших в действие их взрыватели. Между тем, проектировщиков никто не думал судить и сажать в тюрьму .

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

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

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

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

2. Замечательный проект дирижабля воздушной подводной лодки завершился катастрофами и умер. Но катастрофический Секция Информатика и прикладные исследования проект летательного аппарата тяжелее воздуха продолжает жить в самолетах и вертолетах. А каждый такой аппарат обязан упасть!

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

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

4. Уравнения движения современных сложных технических объектов сложные. Современная вычислительная техника позволяет их решить, но никакая вычислительная техника не позволяет их исследовать. Для этого требуется знать всё о всех траекториях объекта, а компьютер может вычислить только некоторые из них. Практика подсказала выход: линеаризовать нелинейные уравнения! Но их все равно оказывается слишком много, и умельцы в КБ научились их грамотно сокращать, выбрасывая те, которые кажутся им несущественными. И в авиационном КБ забыли об исходной задаче динамики реальных летательных аппаратов: вместо этого создана научная школа дальнейшего упрощения тех уже линеаризованных уравнений, которые никакого отношения к реальным самолетам и вертолетам не имеют. И летают нелинейные самолеты и вертолеты под управлением беспринципно упрощенных линейных систем ручного управления и автопилотов. А аварийные комиссии ищут ошибки управления пилота, которому в руки дали штурвал не реального самолета, а его выдуманной фанерной имитации .

Виноваты ли в этом расчетчики, у которых нет необходимых математических инструментов для исследования нелинейных систем?

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

5. Существует международный научно-технический проект тросовых космических систем, состоящий в создании систем космических аппаратов, связанных тросами, и двигающихся на значительном расстоянии друг от друга. Проект сулит значительные выгоды: победу над невесомостью за счет вращения связки, возможность выработки электрической энергии за счет движения в космических магнитных полях, и другие. Но даже собрать тросовую систему в неинерциальном поле Земли существующими методами невозможно: наши расчеты показали, что выпускаемые тросы вовсе не хотят направляться к предназначенным им целям, а наматываются бабушкиными клубками на выпускающий их аппарат [21]! А гипотетическая тросовая система, отбирающая энергию из магнитного поля Земли, тормозится пропорционально отбираемой энергии, и должна упасть, как детская игрушка, у которой кончилась батарейка .

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

Перечисление этих но требует отдельной статьи. Упоминание о матрицах означает линеаризацию, а компьютерная программа использование численных методов. Итого в докладе специалиста присутствует четыре объекта: 1 реальный объект, 2 его нелинейная математическая модель, 3 его линеаризованная математическая модель, 4 результаты расчетов с использованием компьютерной программы. Докладчик убеждает аудиторию, что он изучил объект 1, но показывает ей объект 4. А дистанция от первого до четвертого объекта огромна!

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

Например, все численные методы разрушают физические характеристики механических объектов. Численный метод либо отбирает механическую энергию из модели системы, либо, наоборот, добавляет ее .

Значит, можно не долететь до цели, можно перелететь. Но попасть в цель с помощью таких расчетов нельзя!

А стандартная компьютерная программа кем она изготовлена?

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

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

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

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

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

440 Интеллектуальные системы и компьютерные науки Теорема неизбежности катастроф. При увеличении срока эксплуатации любой исправный технический объект должен потерпеть катастрофу .

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

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

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

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

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

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

3. Краткая история вечных конфликтов между матема- тикой и механикой

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

Первый конфликт механики с математикой возник в первый день ее рождения. Знаменитый греческий историк Плутарх (45–127 н.

э.) свидетельствует:

Механика, предмет искания и прославления, есть изобретение Евдокса (408–355 до н. э.) и Архита (428–365 до н. э.). Они хотели некоторым образом иллюстрировать геометрию (дать геометрии внешнюю прикраску) и основать на чувственных и материальных предметах теоремы, которые трудно решить помощью рассуждений и научных доказательств. Но скоро Платон (428–348 до н. э.) в негодовании стал упрекать их, что они портят геометрию, лишают ее достоинства, обращают ее в беглого раба, заставляя ее от изучения бестелесных и умственных вещей переходить к чувственным предметам и прибегать, кроме рассуждений, к помощи тел, рабски изготовленных работою руки .

442 Интеллектуальные системы и компьютерные науки С тех пор конфликты между математикой и механикой, и конфликты в математике и механике, традиционны, и происходят на всех уровнях, от философских оснований и общетеоретических построений, до интерпретации конкретных расчетов. Примерами могут служить конфликт между теорией дифференциальных уравнений и механикой в трактовке уравнений связей в механических системах [3], знаменитая многовековая скандальная дискуссия о принципе наименьшего действия [39]–[44], или обвинения известного в свое время геометра Пуансо [45] против гениального математика и механика Лагранжа в незнании последним основ геометрии! Но все они относятся к обсуждению ошибок, которые рано или поздно, иногда через века после смерти насмерть спорящих оппонентов, исправляются. Принцип наименьшего действия, покрывший в свое время позором его создателя Мопертюи [39], через 250 лет был реабилитирован в нашей работе [42]–[44] с помощью современной теории управления, о возникновении которой через будущие века спорщики того времени не могли и подозревать. Конфликт между теорией дифференциальных уравнений и механикой Лагранж своевременно разрешил, введя в механическую систему реакции связей [3], которых не существует в теории дифференциальных уравнений. Но обвинения Пуансо Лагранж не мог опровергнуть, потому что они появились после его смерти. И скандальная статья Пуансо [45] путешествует по времени и пространству вместе со всеми переизданиями гениального трактата Лагранжа [3] на всех языках в качестве его приложения, попала и в Россию в русском переводе. Этот заочный спор имеет отношение к теме настоящей статьи к криволинейным пространствам с косоугольными ненормированными координатными базисами, в которых существует аналитическая механика, но о которых не знал ее создатель Лагранж, и о которых не мог подозревать его критик Пуансо .

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

Секция Информатика и прикладные исследования

4. Скрытые конфликты между корректными методами математики и механики

Механика математическая наука, но в отличие от других наук, пользующихся математическими методами, она неразрывно срослась с математикой, фактически превратилась в раздел математики. Галилей первым сделал попытку ее аксиоматического построения [1] .

Ньютон, по существу, превратил механику в теорию дифференциальных уравнений [2]. Лагранж, создавая аналитическую механику, поставил и практически реализовал цель сделать ее новой отраслью анализа [3]. В последующем все теории механики развивались как теории преобразований уравнений движения и поиска их первых и полных интегралов. В том числе, к поиску интегралов уравнений движения сводятся достижения теории Солнечной системы Ньютона [2], все общие и частные достижения аналитической механики Лагранжа [3], и теории движения твердого тела Эйлера [4]. Используя точные методы математики, все различные теории механики, безотносительно к различиям в их формализме, демонстрируют полное совпадение своих результатов во всех теоретических и прикладных исследованиях и задачах. Это считается непреложным фактом, не подлежащим обсуждению в той же мере, в какой не подлежит обсуждению незыблемость методов математики. В результате все теории механики и все методы математики во всех исследованиях используются совместно, как инструменты единой мастерской .

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

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

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

Руководства по механике учат нас, как нужно делать, мы же говорим о том, как не нужно делать. С точки зрения последнего, и первое переходит из одномерного измерения это правильно в многоправильно?2 мерное пространство это Один из коллег указал автору, что его статья будет только запутывать студентов, и окажется вредной для их несформировавшегося еще профессионального сознания. Автор, со своей стороны, убежден, что формирование сознания студентов самоуверенными профессионалами, которые наводнили мир своими опасными изделиями бесперспективно. Если это сознание не изменить, стремительный рост катастроф победить не удастся. Образование студентам, разумеется, необходимо, но обязательно критическое, к чему и призывает эта статья. Науку всегда двигали вперед не отличники-зубрилы, а плохие ученики с несформировавшимся еще профессиональным сознанием, плохо заучившие наизусть старые истины, и поэтому вынужденные создавать новое знание .

Родителей студентов о вреде нашей статьи мы предупредили. А что касается самих студентов, то 50-летний опыт преподавания автора в МФТИ и МГУ, во Владивостокском и зарубежных университетах показал, что им интереснее всеСекция Информатика и прикладные исследования Метод изложения этих вопросов мы выбираем самый простой обсуждаем их с помощью примеров, большей частью элементарных .

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

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

го то, что вредно, и не разрешается. Так стоит ли продолжать вдалбливать им нудные математику и механику, или лучше рассказывать им захватывающие страшилки по Эдгару По, к сожалению, выплеснувшиеся из его книжек в нашу действительность? Не вернуться ли от скучного, многократно переписанного под разными фамилиями одного и того же учебника механики к механическим поэмам, гимнам, молитвам Галилея, Ньютона, Эйлера, Мопертюи? Чтобы воспитать у студентов (простите за гуманитарный термин) художественный вкус, позволяющий различить музыку Бетховена в научных и богословских трактатах Ньютона и Мопертюи, и Моцарта в математических симфониях Лагранжа!

Чем еще может привлечь наука в наше меркантильное время, как не красотой .

446 Интеллектуальные системы и компьютерные науки

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

Эдгар По. Убийство на улице Морг Любой механический объект является механической системой .

Мы рассмотрим в качестве такой системы простейший фундаментальный объект механики, основной предмет исследований Галилея, Ньютона и Лагранжа [1]–[3] материальную точку. Заставим ее играть серьезную роль механической системы, будем наблюдать за ее поведением в этом качестве, задавать ей серьезные системные вопросы, и критически оценивать ее ответы, относя их к ответственности той теории, которую эта точка в контексте этой теории будет представлять. В качестве декораций возьмем вторую в истории механики (после рычага) теоретическую задачу Галилея о движении по наклонной плоскости [1]. Галилей с ее помощью открыл все законы классической механики, известные нашей цивилизации, но сама эта задача все еще не утратила своего познавательного значения. Задача эта элементарная, но посмотрим, является ли она простой .

Задача 1. Составить уравнения движения материальной точки, движущейся под действием силы тяжести по неподвижной гладкой прямой спице, отклоненной от вертикали на 45 .

Решение. Исходные математические уравнения этой задачи, очевидно, можно записать так:

А) = 0, Б), В) = (, ) = + = 0, = const. (1) = Поручим решить эту задачу математику, и механику. Это демонстрационный пример, и мы намеренно попросим участвовать в его анализе математика-формалиста, не знакомого с теоретической механикой .

Секция Информатика и прикладные исследования

5.1. Беспомощность методов теории дифференциальных уравнений в механике Приступив к решению Задачи 1, математик-теоретик уже при виде ее системы трех уравнений (1) вернет их Галилею, как некорректные: уравнение В) должно быть интегралом уравнений А) и Б), чего, очевидно, быть не может .

Это наблюдение математика является важным общим фактом механики:

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

5.2. Конфликт между методами теории дифференциальных уравнений и теоретической механики Для механика противоречий в системе уравнений (1) нет: уравнение В) описывает механическую связь, которая воздействует на уравнения А) и Б) дополнительной силой своей реакции. Сила реакции в этой задаче одним уравнением связи В) определена быть не может. Следует использовать дополнительное условие ее гладкости .

Это условие требует, чтобы сила реакции связи была к ней ортогональной .

Чтобы избежать вычисления силы реакции косой связи В), подкованный в математике механик предпочтет упростить уравнение этой связи, выровняв ее с помощью преобразования системы уравнений (1) к новым переменным

–  –  –

Никаких рекомендаций и инструкций о правилах преобразований уравнений движения, отличных от правил корректных преобразований дифференциальных уравнений, в теоретической механике нет, поэтому будем обращаться с уравнениями (3-1) и (3-2) как с уравнениями обычных задач механики .

Связь (1В) превратилась после преобразований (2) в связь (3-1В), (3-2В), и стала здесь горизонтальной, а сила реакции этой гладкой связи, в соответствии с рис. 1 и 2, вертикальной .

Эта сила реакции связи (3-1В) и (3-2В) войдет, следовательно, только в уравнения (3-1А) и (3-2А) для координаты, и уравнения (3-1) и (3-2) с учетом этой силы запишутся, соответственно, в виде А) +, Б), В) = 0; (4-1) = = А) +, Б) = 0, В) = 0. (4-2) = Единственными решениями алгебраических уравнений (4-1) и (4-2) относительно их переменных,, и,, являются

–  –  –

Преобразование решений (5), обратное к (2), дает два решения

Задачи 1:

(6-1) =, =, = ;

(6-2) = 0, = 0, = .

Два разных решения элементарной Задачи 1, полученные правильными вычислениями, вызывают вопросы. Читатель может (и должен) Секция Информатика и прикладные исследования искать арифметические и методические ошибки в приведенных вычислениях. В этом ему поможет и то очевидное обстоятельство, что оба эти решения вздор.

Мы же ограничимся следующим выводом:

Предупреждение 2. Формальное преобразование уравнений движения механических систем методами теории дифференциальных уравнений недопустимо .

Негативное утверждение ускользает от прямой ответственности .

Его нельзя схватить за руку, проверив его доказательство оно же отсутствует! Это всего лишь разрушающий пример. Но, раз здесь что-то не так, подозрение падает не только на достопочтенные методы математики и механики, на которые жаждет бросить тень автор этой статьи, но и на самого автора. Это и является нашей целью вызвать у читателя подозрения. Поможем ему: возможно, в приведенных примерах виноваты не математика и механика, а автор этой статьи, который неверно понял и применил метод Лагранжа замены механической связи ее силой реакции? Чтобы разрешить этот вопрос, следует обратиться к самому компетентному арбитру к самому Лагранжу. Кстати, наткнемся еще на один конфликт в этом безупречном семействе точных наук .

–  –  –

Приравнивая в этих уравнениях множители при независимых дифференциалах переменных к нулю, и добавляя для определения лишИнтеллектуальные системы и компьютерные науки них переменных 1 и последние уравнение (3-1), (3-2), получаем две системы уравнений (8-1) + + = 0, + = 0, = 0;

(8-2) + + = 0, = 0, = 0 .

Уравнения Лагранжа (8-1) и (8-2) при 1 =, 2 = совпадают с уравнениями механика (4-1) и (4-2), и он, следовательно, ни в чем не ошибся. Но эти уравнения Лагранжа приводят к тем же разным решениям (6-1) и (6-2). Следовательно, вину за их абсурдность теперь можно снять с автора этой статьи, и обоснованно отнести на счет методов математики и механики, теперь аналитической механики Лагранжа .

Читатель по-прежнему может (и мы ему это советуем) не доверять автору.

Мы же подытожим наше элементарное исследование следующим предупреждением:

Предупреждение 3. Формальное преобразование уравнений движения методами теории дифференциальных уравнений в аналитической механике недопустимо .

5.4. Высший арбитраж Ньютона Обратимся к высшему авторитету в Механике Ньютону. Уравнения движения материальной точки Ньютона единственное, что надежно знают студенты. Поэтому приведем решение Задачи 1, полученное студентом .

Студент нарисовал линию движения точки и, в соответствии с рис. 3, разложил вектор вертикальной силы тяжести на ортогональную и касательную к этой линии составляющие, обе величины / 2 .

Затем он уничтожил ортогональную компоненту по третьему Закону Ньютона реакцией опоры. Повторно разложив оставшуюся касательную компоненту силы на горизонтальную и вертикальную составляющие в соответствии с Рис. 4, в результате он получил

–  –  –

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

5.5. Решение Задачи 1 методами аналитической механики Лагранжа Попросим Лагранжа решить Задачу 1 без математических усовершенствований механика, который ввел преобразования (2), но, чтобы избежать разночтений, сделать это путем того же предварительного преобразования переменных (2) .

Рассмотрим для краткости случай (2б). Лагранж не пользуется методами теории дифференциальных уравнений (как будто он уже прочел наше Предупреждение 3!), а производит преобразования переменных в уравнениях движения собственными методами, с помощью своей универсальной Общей формулы динамики [3].

Ее нужно записать для исходных уравнений (1), и затем произвести в ней преобразования (2б):

–  –  –

Извлекая из (10), при произвольных независимых виртуальных перемещениях и, два уравнения, и добавляя к ним уравнение связи = 0, получаем систему уравнений (11) 2 = 0, ( ) + + = 0, = 0, решение которой дает результат совпадающий с решением студента (9):

<

–  –  –

Легко проверить, что к этому же результату (9), (12) приводят уравнения Лагранжа I рода, и уравнения Лагранжа II рода, при использовании в качестве обобщенной координаты в этой одностепенной задаче как любой из координат,,так и. К этим же уравнениям (9), (12) приводят наши матричные уравнения [46]–[48] в декартовых, и в обобщенных координатах .

Комментарии. Результаты студента (9) и Лагранжа (12) верные, а результаты механика (6) ошибочные, хотя никаких математических нарушений при их получении нет! И правильность его вычислений даже была выше подтверждена Лагранжем! Это парадокс, и причина этого парадокса заключается, очевидно, не в вычислительных ошибках.

Она в конфликте методов математики и механики:

преобразование (2) уравнений (1) недопустимо! Этот факт, уже отмеченный выше в Предупреждениях 2 и 3, оказывается общим для всех методов механики, и отличать ее отдельные разделы уже не обязательно:

Предупреждение 4. Формальное преобразование дифференциальных уравнений движения механики методами теории дифференциальных уравнений недопустимо .

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

Секция Информатика и прикладные исследования

5.6. Конфликт между методами преобразования уравнений в теории дифференциальных уравнений и в аналитической механике Лагранжа Преобразования (2) системы уравнений (1) в системы уравнений (3) было произведено по всем правилам теории дифференциальных уравнений: они невырожденные, взаимно однозначные, и сохраняют порядок дифференциальных уравнений .

Лагранж простыми приемами этой математической теории пренебрег, и преобразование (2) системы уравнений (1) в систему уравнений (11) производит сложным, странным и загадочным образом: он собирает все старые уравнения (1) в единственное уравнение (10), и из этого единственного уравнения получает новую систему уравнений (11)! Глубоко развитая и подробно изученная теория дифференциальных уравнений такого фокуса не знает! В ней уравнения можно складывать, но, сложив два уравнения, одно из слагаемых обязательно нужно сохранить, и нельзя потерять ни одной производной! А Лагранж, волшебник математических превращений, показывает нам открытые карты одной масти, собирает их в одну колоду, на наших глазах ее тасует, и раскладывает перед нами карты другой масти!

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

Потому что последние, как показывают Предупреждения 2–4, для преобразований дифференциальных уравнений механики непригодны. Здесь применимы только методы преобразований Лагранжа!

Предупреждение 5. Для преобразования уравнений движения механических систем в механике могут быть использованы только методы Лагранжа .

К числу этих методов, помимо использующих Общую формулу динамики Лагранжа, относятся методы преобразования переменных 454 Интеллектуальные системы и компьютерные науки в функциях Лагранжа и Гамильтона. Последние присутствуют в активном арсенале аналитической механики [3], [4] .

Взаимоотношения Предупреждения 5 с методами преобразования уравнений аналитической механики в теории Гамильтона для обыкновенных дифференциальных уравнений и в теории ГамильтонаЯкоби для уравнений в частных производных мы предоставляем обдумать читателю .

6. Примеры конфликтов между методами аналитической и теоретической механики

Продолжим обсуждать простые примеры, теперь примеры конфликтов разных методов механики между собой .

Рассмотрим замечательную методическую задачу Галилея с еще одной стороны .

Задача 2. Составить уравнения движения в Задаче 1 в полярных координатах .

Решение. В этой задаче два этапа: первый состоит в преобразовании ее исходных уравнений, второй в исключении уравнения связи .

Выполним первый этап методом теоретической механики, а второй методом аналитической механики .

6.1. Преобразования уравнений движения методами теоретической механики

–  –  –

6.2. Решение преобразованных уравнений методами аналитической механики На втором этапе записываем для уравнений (13) Общую формулу динамики Лагранжа ( 2 + sin ) + ( + 2 + cos ) + + sin ) + ] = 0. (14) + [ (cos Расщепление уравнения (14) при независимых и дает два уравнения ( 2 + sin ) + (cos + sin ) = 0, (15) ( + 2 + cos ) + (cos sin ) = 0 .

Решать уравнения (15) не потребуется. Они некорректны: множитель Лагранжа должен принимать в них одинаковое значение разной размерности!

Комментарий. Решение указанных двух этапов одним методом, как теоретической, так и аналитической механики, приведет, как легко проверить, к правильному результату. В абсурдности формул (15) виновато смешение разных методов .

Предупреждение 6. Методы теоретической механики для использования в алгоритмах аналитической механики непригодны .

Здесь действует также Предупреждение 5 .

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

А они, в силу нашего примера, в целом заведомо несовместимы. И выбор частных случаев совместимости должен быть основан на общем теоретическом анализе: примеры могут опровергать, но не могут сказать ничего позитивного. В нашу задачу такой обширный анализ не входит. Предупреждение 6, всего лишь, предупреждает. И если указанный анализ будет когда-либо проведен, он это Предупреждение только уточнит, но не опровергнет: пример Задачи 2 этого не позволит .

456 Интеллектуальные системы и компьютерные науки

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

Задача 3. Составить уравнения движения груза, переносимого на тросовой подвеске вертолетом .

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

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

Выпишем их для вертолета (вращение в системе главных осей инерции тела,,, координаты поворота углы Эйлера,, ; координаты центра масс в, в, в в системе неподвижных осей,, ):

–  –  –

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

–  –  –

Попросим решить Задачу 3 нашего студента, который решал Задачу 1, но теперь уже окончил ВУЗ и стал инженером. Наш пример методический, и нашего инженера мы попросим сыграть две методические роли расчетчика из КБ и младшего научного сотрудника из НИИ .

7.1. Инженерный расчет, основанный на методах теоретической механики В КБ традиционно используются теоретическая механика и общие методы математики. Аналитическая механика считается развлечением теоретиков из университетов .

Использование уравнения троса (18) позволяет исключить из уравнений вертолета (16-1), (16-2) и груза (17) одну из их координат .

Например, координату вертолета. Ее можно исключить из (16-1) с помощью самого уравнения (18), а ее производные и, соответственно, с помощью производных этого уравнения

–  –  –

переменной и ее производных, трех уравнений центра масс вертолета (16-2) и трех уравнений груза (17) .

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

Комментарии. Инженеру в его расчетной работе можно помочь .

Редукцию системы уравнений (16-1) можно провести отбрасыванием не только ее последнего уравнения, но и любого другого. Можно также исключить одну из координат системы уравнений (16-2), или (17). В итоге можно получить не одну, а 9 редуцированных систем и, соответственно, 9 решений Задачи 3!

Мы предоставляем эти расширенные возможности инженерурасчетчику, а он, в свою очередь конструктору вертолета. Что посоветовать конструктору какую ему из этих 9 систем уравнений движения механической системы вертолет-груз выбрать, чтобы заказать не ее основе систему управления вертолетом?

Попросим ответить читателя, а сами пока посетим НИИ .

7.2. Научный расчет, основанный на методах аналитической механики В современном НИИ для решения Задачи 3 естественно воспользоваться методами аналитической механики. Общая формула динамики Лагранжа для уравнений (16-1), (16-2), (17) с механической связью (18) записывается в виде

–  –  –

Расчленение уравнения (21) на множители при независимых виртуальных дифференциалах приводит к 9 уравнениям Секция Информатика и прикладные исследования

–  –  –

к которым следует добавить еще уравнение связи (20) .

Выражения (16-1), (16-2), (17), которые должны быть подставлены в (22), и уравнение (20) линейны по вторым производным всех 9 координат системы вертолет-груз, и решение этой линейной системы 10 уравнений (22), (20) относительно 10 переменных в, в, в,,,, г, г, г и дает искомое решение Задачи 3 .

Работа завершена, и подробные вычисления наш инженер м.н.с .

из НИИ может изложить в научном отчете, и использовать их в кандидатской диссертации, теперь по физико-математическим наукам .

Комментарии. Можно обсуждать достоинства и недостатки представленных инженерного и научного методов: первый приводит к дифференциальным уравнениям движения 16 порядка, второй к уравнениям 18 порядка. И разных решений теперь еще больше к 9 решениям КБ можно добавить решение НИИ. Теперь у конструктора вертолета выбор необходимых уравнений движения для заказа системы управления еще больше. Только это выбор вида катастрофы, который неизбежно потерпит вертолет в первом же полете. Потому что все эти уравнения ошибочные. Точнее, они не имеют никакого отношения к истинным уравнениям движения системы вертолетгруз .

Пока читатель объяснит конструктору вертолета, какие именно ошибки допустили его помощники расчетчик из КБ и м.н.с. из НИИ, автор пояснит, что приведенные сценарии решения Задачи 3 взяты им из личного опыта общения с работниками КБ и сотрудниками НИИ. И приведет дословно свой диалог с еще одним действующим лицом этой научно-технической драмы, слишком часто завершающейся трагедией, с вертолетчиком, переносившим трансформаторы и опоры электропередач над бездорожьем тайги .

460 Интеллектуальные системы и компьютерные науки

7.3. Диалог автора с пилотом вертолета об эффективных методах механики Автор: Как ведет себя груз в полете?

Пилот: Болтается .

Автор: Какие маневры вы предпринимали, чтобы уменьшить колебания груза при сильной болтанке?

Пилот: Рубил трос!

7.4. Разбор несостоявшихся полетов Ошибки инженерного решения .

На вздорность инженерного решения 6.1 указывает Предупреждение 1: уравнение связи (18) не является первым интегралом системы уравнений (16-1), (16-2), (17) и не может быть использовано в этом качестве для понижения ее порядка. Это независимо подтверждает алгебра. Общее число уравнений (16-1), (16-2), (17) и (20) равно 10, а неизвестных,,, в, в, в, г, г, г в этих уравнениях 9. Очевидно, что эти уравнения совместными быть не могут, и поэтому любые их преобразования бессмысленны. Таким образом, не заглядывая в конкретные расчеты нашего инженера из КБ, мы убеждаемся, что его отчет блеф .

К каким последствиям приведет использование его вздорного решения на практике очевидно. Кем является в этом случае наш расчетчик, очевидно тоже террористом! Но он в этом не виноват. В ВУЗе он был отличником, усердно изучал курс механики и, одновременно, курс дифференциальных уравнений, на котором ему рассказали, что любое конечное соотношение между переменными системы дифференциальных уравнений можно (и нужно!) немедленно использовать для понижения ее порядка. В результате в нашей задаче, обладая хорошей математической подготовкой, он сделал все правильно с точки зрении теории дифференциальных уравнений. Но пятерка по этому математическому предмету оказывается двойкой по механике! И виноватым оказывается не этот невольный террорист, а конфликт между математикой и механикой!

Ошибки научного решения .

Обнаружить ошибки в научном решении 6.2 труднее. Здесь наш м.н.с. тоже оказался в банде техногенных террористов, но настояСекция Информатика и прикладные исследования щим заказчиком этого преступления оказывается вредитель, надежно скрывшийся под профессорской мантией! Вот что говорят о нем в научных изданиях: Выдающийся ученый, создавший капитальный труд, по обилию материала, полноте и строгости изложения представляющий собой по существу энциклопедию знаний в области классической механики.... Этот, действительно выдающийся труд замечательного французского ученого П. Аппеля [49] содержит безобидное утверждение, что уравнения движения твердого тела Эйлера являются уравнениями Лагранжа ([49], п. 443, стр. 283)! Это утверждение, полученное на основании красивой, но неполной и потому ошибочной аналогии, широко растиражировано в многочисленных современных отечественных учебниках. Но безобидное в энциклопедии по механике начала прошлого века, с появлением современных сложных технических систем связанных тел, требующих использования методов множителей Лагранжа, оно становится орудием математического терроризма.

Мы специально подчеркнем это в следующем предупреждении:

Предупреждение 7. Уравнения движения твердого тела Эйлера уравнениями Лагранжа не являются .

Но почему следует называть терроризмом всего лишь разницу в названиях разных видов уравнений движения? Сам Лагранж утверждает [3], что его метод множителей является универсальным, и пришел в механику из анализа, где он используется повсеместно. Представляется очевидным, что его, следовательно, можно использовать в любых уравнениях движения теоретической и аналитической механики, и что наш математически подкованный м.н.с. вполне грамотно применил его для уравнений движения вертолета в форме Эйлера (16-1) .

Попробуем разобраться по существу. Однако здесь следует обращаться уже не к анализу, а к геометрии. Уравнения (21) и (22), вполне респектабельные с точки зрения формальных методов аналитической механики и математики, с геометрической точки зрения бессмысленны. Они уравнивают между собой два 9-мерных вектора. Одним является вектор, составленный из левых частей уравнений движения 462 Интеллектуальные системы и компьютерные науки (16-1), (16-2) и (17), а вторым градиент уравнения троса (18) по координатам этих уравнений. Но это векторы разных пространств!

В частности, три значения,, первого вектора составляют компоненты трехмерного вектора, разложенного по осям связанной с телом подвижной системы координат Эйлера,,. А соответствующие им три значения /, /, / составляют вектор, разложенный по ортам 0, 0, 0 системы координат, которой Эйлер никогда не пользовался. Это трехгранник, орты которого являются локальными касательными к криволинейной координатной сетке углов Эйлера,, подпространства, которому в 9-мерном пространстве этой задачи принадлежит точка прикрепления троса (18) к вертолету .

Эти разные пространства с разными системами координат конфликтуют, не позволяют складывать свои векторы и, следовательно, запрещают писать как уравнение (21), так и уравнения (22) .

Этот запрет оказывается общим, и ведет к неустранимому конфликту между методами Лагранжа и Эйлера. Векторы разных систем координат, разумеется, можно перепроектировать. Но перепроектирование вектора /, /, / из системы координат 0, 0, 0 в систему координат,, уничтожает метод множителей Лагранжа. В свою очередь, перепроектирование уравнений вращения Эйлера,, из системы координат,, в систему координат 0, 0, 0 уничтожает их как уравнения Эйлера: общая геометрическая теория преобразований уравнений движения [46]–[47] показывает, что такое перепроектирование превращает их в уравнения Лагранжа .

7.5. Почему же иногда благополучно летают вертолеты с грузом?

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

7.6. Конфликт между методами Лагранжа и Эйлера Но где же здесь наука? Спустимся на землю, и подытожим сказанное. В динамике связанных тел можно пользоваться теорией ЭйСекция Информатика и прикладные исследования лера но без метода множителей Лагранжа. При желании в механических системах со связями пользоваться методом множителей Лагранжа, уравнения движения тел тоже следует записывать в форме Лагранжа. Пример приведен в [46]–[47] .

Предупреждение 8. Теория уравнений движения твердого тела Эйлера и метод множителей Лагранжа несовместимы .

Ряд фундаментальных руководств по механике, не приводя при этом обоснований, в общем, следуют Предупреждениям 7 и 8. Например, в руководстве Г. К. Суслова [4] при использовании уравнений движения Эйлера множители Лагранжа заимствуются из уравнений движения Лагранжа. Э. Дж. Раус [50] составляет уравнения движения несвободного тела с множителями Лагранжа только в форме Лагранжа .

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

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

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

464 Интеллектуальные системы и компьютерные науки Наши тривиальные примеры бросают тень даже на общие законы движения механики. Эти законы устанавливаются путем формального преобразования уравнений движения элементов системы, а Предупреждение 2 на основе примера Задачи 1 утверждает, что это может привести к абсурду. Теория твердого тела Эйлера повсеместно используется без ограничений, но такие ограничения, как показывают Предупреждения 6 и 7, существуют, и должны учитываться. О современном состоянии этих теорий можно сказать, что они получены в результате правдоподобных рассуждений, отчасти проверенных впоследствии экспериментом и практикой, отчасти так и оставшихся правдоподобными .

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

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

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

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

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

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

Для молодых читателей есть образцы, с которых нужно брать пример это Галилеей, Ньютон, Лагранж, и наши соотечественники М. В. Келдыш, М. А. Лаврентьев, Л. С. Понтрягин. Выдающиеся математики, они показали, как именно нужно использовать математику для решения содержательных проблем и задач механики и техники .

Список литературы

[1] Галилей Г. Избранные труды. М.: Наука, 1964 .

[2] Ньютон И. Математические начала натуральной философии // Собрание трудов академика А. Н. Крылова. Т. 7. М.–Л., 1936 .

[3] Лагранж Ж. Аналитическая механика. М.–Л.: Гостехиздат, 1950 .

[4] Суслов Г. К. Теоретическая механика. М.–Л.: Гостехиздат, 1944 .

466 Интеллектуальные системы и компьютерные науки [5] Величенко В. В. К проблеме управления катастрофами // ДАН. 1996. Т. 349. № 6. С. 732–735 .

[6] Величенко В. В. Управление дискретно-непрерывными моделями катастроф // ДАН. 1996. Т. 350. № 1. С. 9–11 .

[7] Величенко В. В. К проблеме управления катастрофами // Безопасность России. Раздел 1. М., 1998. С. 379–382 .

[8] Величенко В. В. Математическая оболочка для моделирования и управления в типовых сценариях техногенных аварий и катастроф // Science. Вып. 3. М.: ИМАШ РАН, 1999. С. 112–113 .

[9] Velichenko V. V. Catastrophe Control Problem // Proceedings of First FLINS’94 Intern. Workshop on Fuzzy Logic and Intelligent Technology in Nuclear Science. Belgium, Mol: World Scientic,

1994. P. 117–121 .

[10] Velichenko V. V. Variational Analysis and Control of Catastrophic Dynamical Systems // Nonlinear Analysis, Theory, Methods & Applications. Oxford, England: Elsevier Science Ltd, 1997. Vol. 30 .

No. 4. P. 2065–2067 .

[11] Величенко В. В. О задачах оптимального управления для уравнений с разрывными правыми частями // Автоматика и телемеханика. 1966. № 7. С. 20–30 .

[12] Величенко В. В. Численный метод решения задач оптимального управления // ЖВМ и МФ. 1966. Т. 6. № 4. С. 636–647 .

[13] Величенко В. В. Оптимальное управление составными системами // ДАН СССР. 1967. Т. 176. № 4. С. 754–756 .

[14] Величенко В. В. Об инвариантности разрывных систем // Автоматика и телемеханика. 1973. № 8. С. 155–160 .

[15] Величенко В. В. Задачи оптимального управления с промежуточными условиями // Исследование операций. ВЦ АН СССР,

1974. Вып. 4. С. 126–145 .

[16] Величенко В. В. Сильно нелинейные динамические системы:

ударная динамика механических систем с односторонними связями // Межд. Конгресс Нелинейный анализ и его приложения .

Тез. докл. М., 1998. С. 107 .

Секция Информатика и прикладные исследования [17] Величенко В. В. Матричная теория удара в механических системах с переменным составом связей // 8-й Всероссийский съезд по теоретической и прикладной механике. Аннотации докладов .

Пермь, 2001. С. 149–150 .

[18] Величенко В. В. Механика трансформирующихся систем // ДАН. 2003. Т. 388. № 6. С. 757–760 .

[19] Величенко В. В., Сыромятников В. С. и др. Синтез управления стыковкой космических аппаратов на основе принципа максимальной скорости сближения в метрике расстояний между фазовыми траекториями // Межд. Конгресс Нелинейный анализ и его приложения. Тез. докл. М., 1998. С. 83 .

[20] Величенко В. В. Ударная динамика штатных и аварийных стыковок космических кораблей и станций // Труды XII Байкальской междун. конф. Иркутск, 2001. Т. 6. С. 62–67 .

[21] Величенко В. В., Сыромятников В. С. и др. Управление динамикой развертывания космической тросовой системы // 2-я Межд .

конф. Устойчивость и управление для нелинейных трансформирующихся систем. Тез. докл. М., 2000. С. 64 .

[22] Величенко В. В., Валуев А. М. О задаче синтеза траекторий полета самолета в трансформирующейся воздушной обстановке // 2-я Межд. конфер. Устойчивость и управление для нелинейных трансформирующихся систем. Тез. докл. М., 2000. С. 62 .

[23] Величенко В. В., Козьминых В. А. Управление возвратом воздушно-космического аппарата в атмосферу // 2-я Межд. конфер .

Устойчивость и управление для нелинейных трансформирующихся систем. Тез. докл. М., 2000. С. 63 .

[24] Величенко В. В., Притыкин Д. А. Искусственный интеллект и социальная динамика ВИЧ-инфицированной иммунной системы человека // Интеллектуальные системы. 2001. Т. 6. Вып. 1–4 .

С. 5–24 .

[25] Величенко В. В., Притыкин Д. А. Численные методы оптимального управления динамикой ВИЧ-инфекции // Известия РАН .

Теория и системы управления. 2006. № 6. С. 53–64 .

468 Интеллектуальные системы и компьютерные науки [26] Величенко В. В., Притыкин Д. А. Управление лечением СПИДа // Автоматика и телемеханика. 2006. № 6. С. 166–185 .

[27] Величенко В. В. К проблеме компьютерного интеллекта: решение задачи на выживание, предложенное и реализованное компьютером // XV Межд. конф. Проблемы теоретической кибернетики. Казань, 2008. С. 14 .

[28] Величенко В. В., Притыкин Д. А. Возможности искусственного интеллекта и компьютерных технологий в построении программ лечения сложных иммунных заболеваний // Журнал фундаментальной и прикладной математики. 2010. Т. 15. Вып. 5 .

[29] Величенко В. В. Принципы технического интеллекта в проблеме управления сложными экономическими системами // Интеллектуальные системы. 1997. Т. 2. Вып. 1. С. 5–34 .

[30] Величенко В. В. Принципы и методы современной теории управления в задачах стабилизации и развития экономики // Новая парадигма развития России. Комплексные исследования проблем устойчивого развития / Ред. В. А. Коптюг. М.: Academia,

1999. С. 322–328, 436–442 .

[31] Величенко В. В. Интеллектуальные ресурсы в проблеме предотвращения стратегической экономической катастрофы России // Моделирование и управление процессами регионального развития. М.: Физматлит, 2001. С. 351–392 .

[32] Величенко В. В. Технический интеллект // Интеллектуальные системы. 1996. Т. 1. Вып. 1. С. 5–18 .

[33] Величенко В. В. К методологии интеллекта. Творчество Компьютера // Сб. трудов 2-й Межд. научн. конф. Философские проблемы математики. М.: МГУ, 2009 .

[34] Величенко В. В. Интеллектуальный компьютер теоретик механики. Компьютерные методы в машиноведении // Сборник лекций Межд. научной школы для молодых ученых Компьютерные методы анализа инженерных задач механики 2009. М.:

ИМАШ РАН, 2009. С. 12–19 .

Секция Информатика и прикладные исследования [35] Величенко В. В. Математическое конструирование нейросетевых вычислителей // Сборник докладов научно-технического семинара Кибернетические системы. Ч. 2. М., 1999. С. 29–32 .

[36] Velichenko V. V. Neural Computer’s Educational Levels: from Intuition to Formal Mathematics // YU-INFO 99 Symposium. Yugoslavia, Kapaonic, 1999. P. 1–7 .

[37] Величенко В. В. Нейровычислительные алгоритмы интегрирования обыкновенных дифференциальных уравнений // V Всерос .

конф. Нейрокомпьютеры и их применение. Сборник докладов. М., 1999. С. 211–216 .

[38] Величенко В. В. Интуитивные и формализованные методы в нейроматематике. Нейрокомпьютерное интегрирование дифференциальных уравнений // Нейрокомпьютеры: разработка и применение. 2001. № 2. С. 9–29 .

[39] Мопертюи П. Законы движения и покоя, выведенные из метафизического принципа // Вариационные принципы механики / под ред. Л. С. Полака. М.: Физматгиз, 1959. С. 41–55 .

[40] Якоби К. Лекции по динамике. Общетехническая литература .

Л.–М., 1936 .

[41] Полак Л. С. Вариационные принципы механики, их развитие и применения в физике. М.: Физматгиз, 1960 .

[42] Величенко В. В. О достаточных условиях оптимальности для многолистных полей экстремалей // ДАН СССР. 1976. Т. 226 .

№ 4. С. 757–760 .

[43] Величенко В. В. Минимальная интерпретация принципа наименьшего действия // ДАН СССР. 1979. Т. 248. № 3 .

С. 553–556 .

[44] Величенко В. В. Об условиях абсолютной минимальности в принципе наименьшего действия // Устойчивость движения, аналитическая механика, управление движением. М., 1981 .

С. 100–109 .

[45] Пуансо. Об основном положении Аналитической механики Лагранжа / Приложение к [3]. С. 307–318 .

470 Интеллектуальные системы и компьютерные науки [46] Величенко В. В. Матрицы, геометрия, механика и ЭВМ. М.:

МФТИ, 1984 .

[47] Величенко В. В. Матрично-геометрические методы в механике с приложениями к задачам робототехники. М.: Наука, 1988 .

[48] Величенко В. В. Матричная механика: возвращение к основаниям Ньютона // Проблемы машиноведения. Сборник трудов .

М.: ИМАШ РАН, 2008. С. 134–138 .

[49] Аппель П. Теоретическая механика. Т. 2. Динамика системы .

Аналитическая механика. М.: Физматгиз, 1960 .

[50] Раус Э. Дж. Динамика системы твердых тел. Т. I. М.: Наука, 1983 .

[51] Тарасенко Ф. П. Четыре типа связей в моделировании реальности // Труды XIII Межд. конф. Проблемы управления и моделирования в сложных системах. Самара, 2011. С. 110–114 .

Секция Информатика и прикладные исследования ЦЛП-формулировка для совмещенной задачи выбора и планирования инструкций в генераторе кода Вьюкова Н. И., Галатенко В. А., Самборский С. В .

(Москва, Научно-исследовательский институт системных исследований РАН) niva@niisi.msk.ru, galat@niisi.msk.ru, sambor@niisi.msk.ru Введение Фаза генерации кода в современных оптимизирующих компиляторах включает последовательное выполнение выбора инструкций, планирования инструкций и распределения регистров. Поскольку эти задачи взаимосвязаны, результат их последовательного решения может быть неоптимальным .

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

Метод отложенного выбора инструкций Рассмотрим основные моменты предлагаемого метода, который получил название генерация кода с отложенным выбором инструкций [1]. Входными данными для генератора кода служат грамматика, описывающая систему команд целевого процессора, и дерево (или лес деревьев), задающее входной линейный участок.

Далее мы будем использовать следующий простой пример грамматики:

–  –  –

Здесь нетерминальный символ M соответствует памяти, R регистр. Терминальный символ x соответствует некоторой арифметической инструкции процессора, а r описывает значение в памяти или константу. Целые константы, заданные через двоеточия после правил, описывают латентность соответствующих машинных команд .

Пример входного дерева для выражения ( ) ( ) показан на рисунке .

Индексы задают нумерацию узлов дерева. Каждому узлу сопоставляется множество виртуальных регистров: V1, M1 для узла 1, V2, M2 для узла 2, и т. д., исходя из того, что результат подвыражения в узле может быть вычислен либо в регистре (R ), либо в ячейке памяти (M ) .

Генерация кода состоит из двух шагов: 1) первичный выбор инструкций и 2) планирование с окончательным выбором инструкций .

Мы используем модификацию известного метода BURG [2], одного из декларативных методов выбора команд, обзор которых можно найти в [3]. Алгоритм BURG основан на методах синтаксического разбора, где командам процессора соответствуют правила вывода в некоторой контекстно-свободной грамматике (без однозначности разбора). Применение правила имеет определенную цену; цена дерева разбора сумма цен примененных правил, что позволяет находить оптимальный разбор методом динамического программирования .

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

Для нашего примера будут сгенерировано множество команд ( ):

–  –  –

Команды вида M =R и R =M обычно являются избыточными .

Но в условиях дефицита регистров планировщик может включить их в расписание для реализации спиллинга .

Окончательный выбор инструкций выполняется во время планирования. Формулировка ЦЛП-задачи планирования с выбором команд в целом аналогична [4]; отличия касаются методов подсчета числа требуемых регистров и требования об однократности выполнения каждой входной команды. Здесь оно заменяется требованием о необходимости выполнения подмножества команд из, достаточного для вычисления входного выражения .

В формулировке ЦЛП-задачи используются константы и .

задает число тактов, за которое должна выполниться программа. На стадии планирования последовательно делаются попытки составить расписание, укладывающееся в =, + 1,.. .

тактов, пока решение ЦЛП-задачи не закончится успешно. Константа указывает число доступных физических регистров .

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

Не выталкивая регистры в память, нельзя вычислить выражение ( )( ) менее, чем на 3 регистрах (не меняя заданный скобками порядок операций). Попробуем решить построенную ЦЛП задачу 474 Интеллектуальные системы и компьютерные науки

–  –  –

Легко видеть, что сгенерированный код действительно использует всего два физических регистра. Это достигается за счет того, что на шестом такте содержимое регистра R5 сохраняется в память (и замещается значением переменной B), а на такте 8 загружается обратно. Таким образом, полностью автоматически выбран регистр для спиллинга и сгенерирован спилл-код .

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

Обычно эти преобразования реализуются в компиляторах по отдельности, и редко полностью. Часто реализуется единственное преобразование без которого нельзя обойтись (спиллинг). При этом нет гарантии, что будет оптимально выбран регистр для выталкивания в память. В предлагаемом подходе все управление регистрами происходит комплексно и гарантировано оптимальным образом .

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

Список литературы [1] Вьюкова Н. И. Генерация кода с отложенным выбором инструкций. М.: НИИСИ РАН, 2010. С. 80–96 .

[2] Fraser C. W., Henry R. R., Proebsting T. A. BURG Fast optimal instruction selection and tree parsing // SIGPLAN Notices. 1992 .

27. 4. P. 68–76 .

[3] Вьюкова Н. И., Галатенко В. А., Самборский С. В. К проблеме выбора машинных инструкций в генераторах кода. М.: НИИСИ РАН, 2009. С. 3–31 .

[4] Самборский С. В. Формулировка задачи планирования линейных и циклических участков кода // Программные продукты и системы. 2007. 3 (79). С. 12–16 .

476 Интеллектуальные системы и компьютерные науки

–  –  –

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

а) б) Рис. 1. поле зрения, распределение интесивности потока, падающего на, строка сенсоров. a) выходной сигнал строки сенсоров, б) выходной сигнал строки сенсоров, покрывающей всё поле зрения, и состоящей из сенсоров, размеры которых равны шагу перемещения строки сенсоров .

Определим геометрическую разрешающую способность строки сенсоров как размер светочувствительного элемента. Чем меньше размер сенсора, тем выше геометрическая разрешающая способность строки сенсоров. При регистрации сигнала будем перемещать сроку сенсоров по полю зрения c шагом, меньшим чем размер сенсора, и фиксировать сигнал. Зарегистрированный сигнал методами матемаСекция Информатика и прикладные исследования тической редукции можно свести к виду, свойственному выходному сигналу (рис. 1б)) строки сенсоров, покрывающей всё поле зрения, и состоящей из сенсоров, размеры которых равны шагу перемещения строки сенсоров. Таким образом решается задача сверхразрешения восстанавливается вариация интенсивности потока до размера, фиксированного шагом перемещения строки сенсоров по полю зрения. Такая система регистрации обладает так же робастностью. Представим, что один из сенсоров строки вышел из строя .

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

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

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

Данная система регистрации описывается следующей схемой измерений:

.. .

. =. +., (1).. .

где и независимые случайные векторы с математическим ожиданием равным нулю и ковариационными операторами и соответcтвенно. Вектор моделирует распределение интенсивности светового потока, падающего на поле зрения. оператор, моделирующий отклик матрицы сенсоров на световой поток в каждом акте 478 Интеллектуальные системы и компьютерные науки

–  –  –

( 1 ) (4) = 1 +, 2+

–  –  –

Рис. 2. Изображение, полученное статической матрицей сенсоров, покрывающей всё поле зрения .

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

Рисунки 4a),б) демонстрируют робастность описанной выше системы регистрации изображений. Изображение на рисунке 4a)было получено методом математической редукции сигнала, зарегестрированного стопроцентно работающей матрицей, а на рисунке 4б) матрицей, часть сенсоров которой вышли из строя .

Секция Информатика и прикладные исследования

–  –  –

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

Список литературы

[1] Ярбус А. Л. Роль движений глаз в процессе зрения. М.: Наука, 1965 .

[2] Демидов В. Е. Построение оценок. М.: Наука, 2008 .

[3] Пытьев Ю. П. Методы математического моделирования измерительно-вычислительных систем. М.: ФИЗМАТЛИТ, 2011 .

480 Интеллектуальные системы и компьютерные науки

–  –  –

Рассмотрим систему заданий = { 1, 2,..., }, на которой отношение частичного порядка задано графом =,, в котором есть дуга = (, ) тогда и только тогда, когда. Если то выполнение задания может быть начато только после завершения задания. Задано время выполнения каждого задания ( ), которое будем считать целым .

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

Алгоритм решения задачи 1 рассмотрен в [3], ниже рассмотрим задачу 2. Общей подзадачей этих двух задач будет задача построения допустимого расписания при заданном числе процессоров и общем времени выполнения .

Построить расписание, значит найти для каждого задания время начала выполнения задания ( ) и номер процессора ( ), на котором оно выполняется. Длиной расписания называется величина = max{ ( ) + ( ) } .

Требуется определить минимальное число процессоров при котором существует расписание заданной длины .

Секция Информатика и прикладные исследования Алгоритм нахождения минимального числа процессоров Пусть минимальное количество процессоров. Определим интервал (, ] такой, что. Нижняя оценка значения целевой функции в данной задаче ( ) = =1 ( )/. Поэтому положим = ( ) 1. В качестве верхней оценки возьмем = .

Тогда (, ] .

–  –  –

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

Для каждого задания определяется раннее время начала выполнения задания ( ), и позднее время начала задания ( ) .

Возможное время простоя процессоров = =1 ( ) .

Для частичного решения = ( 1, 2,..., ) известно время освобождения процессоров после выполнения заданий, включенных в частичное решение, [1 : ] и ( ) = min{ [ ] 1 : } .

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

Основным способом сокращения перебора будет как можно более раннее установление недопустимости частичного решения .

482 Интеллектуальные системы и компьютерные науки

–  –  –

1) Проверить для всех заданий, выполнение условия 1. Если / оно не выполнено, то := и перейти к п.6 .

2) Если не выполнено условие 2, то перейти к п.6 .

3) Если не выполнено условие 3, то перейти к п.5 .

4) Выбрать задание 0, и добавить к частичному решению. := + 1. Если =, то конец алгоритма, иначе перейти к п.1 .

5) Аннулировать список заданий, запрещенных на -ом уровне перебора := .

6) Если = 0, то конец алгоритма. Шаг назад: от частичного решения = 1 вернуться к решению 1. Задание перевести во множество и := 1 .

7) Если выполнено условие 4, то запретить группу заданий, если выполнено условие 5, то сделать еще один шаг назад. Перейти к п.1 .

Если = 0, то допустимого расписания не существует, если =, то получили допустимое расписание =, с длиной .

Приближенный алгоритм Для уточнения верхней оценки числа процессоров можно применить приближенный алгоритм. Определим минимально возможное количество процессоров и будем строить допустимое расписание заданной длины, проверяя на каждом шаге выполнение условий 1 и 2 допустимости расписания. Если будет установлено, что частичное расписание недопустимо, то увеличим число процессоров на единицу и начнем построение расписания сначала уже для большего числа процессоров .

Вычислительный эксперимент подтвердил работоспособность алгоритмов .

Список литературы [1] Теория расписаний и вычислительные машины / Под ред. Коффмана Э. Г. M.: Наука, 1984. (Computer and job-shop Scheduling theory / ed. by E. G. Coman, J.) 484 Интеллектуальные системы и компьютерные науки [2] Ullman J. D. NP-complete scheduling problems // Journal Comput .

System Sci. 1975. 10. P. 384–393 .

[3] Григорьева Н. С. Алгоритм ветвей и границ построения расписания для многопроцессорной системы // Вестник СПбГУ .

Сер. 10. 2009. Вып. 1. С. 44–55 .

[4] Fernandez E., Bussell B. Bounds the number of processors and time for multiprocessor optimal schedules // IEEE Trans. on Computers .

1973. P. 745–751 .

Секция Информатика и прикладные исследования

–  –  –

Введение При дешифрировании изображений часто используются геометрические признаки. При этом обязательным этапом дешифрирования является получение проекций объектов (сегментация) .

В 1988 г. в работе [1] предложен новый подход к задаче поиска границ, названный методом активных контуров (или методом змей ) .

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

Граница выявляется методом последовательных приближений .

Вслед за этой публикацией разными авторами был предложен ряд модификаций и новых методов на основе идеи активных контуров [2–7] .

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

–  –  –

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

486 Интеллектуальные системы и компьютерные науки

–  –  –

На рис. 1 представлен пример движения активного контура по изображению размера 60 60 пикселов. Объект (крест) имеет размер 40 40 пикселов и расположен в центре изображения. Здесь и далее значения энергетической яркости точек объекта и фона имеют нормальное распределение со стандартным отклонением 20 и средним значением 60 (фон) и 140 (объект). В качестве начального приближения для метода выбрана окружность (рис. 1, а). На рис. 1 (б,в,г) показаны положения контура после 1000, 3000 и 5000 итераций соответственно. На последующих итерациях значительного изменения в положении контура не наблюдалось .

2. Результаты экспериментов Важным достоинством подхода является учет замкнутости границы и ограничение кривизны. Кроме того, найденная проекция автоматически получается односвязной. В настоящее время часто используется задание границы с помощью множества уровня (level-set), Секция Информатика и прикладные исследования позволяющее искать объекты с многосвязными проекциями (см., например, [9]) .

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

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

В качестве начальных приближений были выбраны окружности, раса) б) в) г) д) Рис. 2. Зависимость результата сегментации от выбора начального приближения. = 0.005, = 0.00005, = 1.0 .

положенные в центре изображения, с диаметром 54 пиксела (б) и 48 пикселов (г). Результаты сегментации представлены соответственно на рис. 2, (в, д). Как можно видеть, они существенно отличаются. Методы из более поздних работ, например, GVF [3], позволяют уменьшить зависимость результата от начального приближения .

Рис. 3. Зависимость результата сегментации от выбора значений коэффициентов и. = 1, 0 .

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

Описанные недостатки проявляются и в случае объектов более простых форм (например, квадрат) .

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

–  –  –

[1] Kass M., Witkin A., Terzopoulos D. Snakes: Active contour models // Int. J. Comput. Vis. 1988. № 1. С. 321–331 .

[2] Cohen L. D. On active contours models and balloons // Computer Vision, Graphics, and Image Processing: Image Understanding .

1991. 53 (2). С. 211–218 .

[3] Xu C., Prince J. L. Gradient vector ow: A new external force for snakes // IEEE Proc. Conf. on Comp. Vis. Patt. Recog. (CVPR’97) .

1997. С. 66–71 .

[4] Williams D. J., Shah M. A fast algorithm for active contours and curvature estimation // CVGIP: Image Underst. 1992. 55 (1) .

С. 14–26 .

[5] Amini A. A., Weymouth T. E., Jain R. C. Using dynamic programming for solving variational problems in vision // IEEE Transactions on pattern analysis and machine intelligence. 1990. Vol. 12. № 9 .

С. 855–867 .

Секция Информатика и прикладные исследования [6] Melonakos J., Pichon E., Angenent S., Tannenbaum A. Finsler Active Contours // IEEE Transactions on Pattern Analysis and Machine Intelligence. 2008. Vol. 30. № 3. С. 412–423 .

[7] Caselles V., Kimmel R., Sapiro G. Geodesic active contours // International journal of computer vision. 1997. Vol. 22. № 1 .

С. 61–79 .

[8] Эльсгольц Л. Э. Дифференциальные уравнения и вариационное исчисление. М.: Наука, 1965 .

[9] Chan T. F., Vese L. A. Active Contours Without Edges // IEEE Trans .

on Image Processing. 2001. № 2. С. 266–277 .

490 Интеллектуальные системы и компьютерные науки

–  –  –

Из-за высокой вычислительной трудоемкости, а также возможности распараллеливания вычислительных процессов, присущей алгоритмам дискретной оптимизации (ДО), разработка параллельных алгоритмов для решения задач ДО представляет значительный интерес. Параллельные вычислительные системы обладают возможностями параллельного использования большого числа процессоров для обработки информации. Разумное использование вычислительного потенциала посредством распараллеливания вычислительного процесса существенно ускоряет решение практически важных задач ДО большой размерности. Современные достижения параллельных методов комбинаторной оптимизации описаны в [1]. Декомпозиционные алгоритмы ДО являются первоочередными кандидатами для параллелизации [2, с. 225, 257] .

Для решения задач ДО с помощью декомпозиционных методов представляют интерес системы с распределенной памятью. Параллельное программное обеспечение (ПО) для этих систем использует явную декомпозицию решаемой задачи на подзадачи и назначение их процессорам, а также быструю коммуникационную сеть, обеспечивающую синхронный обмен данными между процессорами. Наиболее типичной архитектурой является Беовульф кластер, важные свойства которого: однородность, коммуникационная сеть типа всесо-всеми, отсутствие общей памяти и отсутствие глобальных часов для синхронизации вычислений. В такой архитектуре все процессы передачи сообщений и синхронизации должны осуществляться с помощью явного обмена сообщениями между процессорами, используя message-passing протокол. Программирование для системы с распределенной памятью осуществляется с помощью стандартного языка высокого уровня типа C++ или Fortran с явной передачей соСекция Информатика и прикладные исследования общений.

Имеются два стандартных API для передачи сообщений:

Message-Passing Interface (MPI) и Parallel Virtual Machine (PVM) .

Остановимся на вопросах разработки ПО для параллельных алгоритмов решения задач ДО. SYMPHONY [3] это параллельная система ПО для решения задач смешанного целочисленного линейного программирования (СЦЛП), подобная COIN/BCP [4]. COIN/BCP и SYMPHONY объединены в новом решателе ALPS [5]. Кроме того, существуют такие параллельные решатели, как PUBB [6], PPBBLib [7] и PICO [8]. PARINO [9] и FATCOP [10] параллельные решатели общего назначения для решения задач СЦЛП, причем FATCOP предназначен для грид-систем. ParaLEX [11] это параллельное расширение решателя CPLEX для задач СЦЛП, предназначенное для работы в распределенной вычислительной среде. Более современной системой является программная система CHiPPS (COIN-OR High Performance Parallel Search), созданная для параллелизации поисковых алгоритмов на дереве [12] .

При параллельной реализации локального элиминационного алгоритма (ЛЭА) [13] предпочтительны методы top-down, работающие с макрографами потоков данных, так как структура графа потоков данных известна (элиминационное дерево или древовидная декомпозиция). Высокая вычислительная сложность, один из основных недостатков ЛЭА, может быть снижена с помощью параллельных вычислений. ЛЭА основан на использовании элиминационного дерева, которое обладает необходимой информацией о зависимости между данными в задаче ДО. Высота элиминационного дерева представляет собой (грубую) меру вычислительной работы по параллельной элиминации. Элиминационное дерево управляет процессом элиминации переменных и блоков переменных и указывает потоки данных, а также характеризует возможности распараллеливания при решении задачи ДО с помощью ЛЭА. В случае вычислительных машин с распределенной памятью после построения элиминационного дерева далее необходимо решить задачу отображения переменных на процессоры .

Основными целями этого отображения являются хорошая балансировка нагрузки и низкая межпроцессорная коммуникация, причём они могут конфликтовать друг с другом. При параллельной реализации блочного ЛЭА используемый граф потоков данных является 492 Интеллектуальные системы и компьютерные науки деревом, которое должно обрабатываться от листьев к корню. Когда для вершины дерева найдено частичное решение, множество промежуточных данных передается в родительскую вершину. Как только промежуточная информация от всех вершин-потомков собрана в родительской вершине, она используется при решении соответствующей родительской вершине задачи ДО. Таким образом, независимые ветви дерева могут обрабатываться параллельно; будем называть этот тип параллельности (древовидной) параллельностью первого типа. В общем случае, он может быть использован более эффективно в нижней части дерева, нежели вблизи ее корневой вершины. Второй тип параллельности соответствует параллельным задачам для одного блока. При этом используется парадигма Master-Worker, в которой имеются два различных типа процессоров: мастер-процессор и рабочие процессоры. При этом управление алгоритмом осуществляется мастер-процессором: он разбивает задачу на отдельные подзадачи и назначает их для решения рабочим процессорам, учитывая взаимосвязи между ними. Такая парадигма особенно полезна, когда задача разбита на легко решаемые подзадачи, а также при слабой взаимосвязи между этими подзадачами. Мастер-процессор выбирается в начале решения пакета задач, соответствующих блоку древовидной декомпозиции. Далее, рабочие процессоры выбираются мастером динамически из списка процессоров-кандидатов, используя критерий хорошей балансировки нагрузки .

Грид-компьютинг (или метакомпьютинг) в общем описывает параллельные вычисления на географически распределенной и гетерогенной платформе [14]. При этом могут использоваться рабочие станции с общей памятью, узлы кластеров ПК, кластеры и суперкомпьютеры. Потенциал грид-компьютинга [14] используется в настоящее время в ДО лишь частично. Декомпозиционные алгоритмы решения задач дискретной оптимизации (включая ЛЭА) хорошо подходят для грид-платформ .

При разработке параллельных версий ЛЭА представляется перспективным использование грид-компьютинга с использованием интерфейса Condor, а также технология PVM .

Секция Информатика и прикладные исследования Список литературы [1] Ferreira A., Pardalos P. (eds.) Solving Combinatorial Optimization Problems in Parallel: Methods and Techniques // LNCS 1054. Stateof-the-Art Surveys. Springer-Verlag, 1996 .

[2] Bertsekas D. P., Tsitsiklis J. N. Parallel and Distributed Computation: Numerical Methods. Englewood Clis: Prentice-Hall, 1989 .

[3] Ralphs T. K., Ladanyi L., Salzman M. J. Parallel branch, cut and price for large-scale discrete optimization // Mathematical Programming. 2003. B. 98. P. 253–280 .

[4] Ralphs T. K., Ladanyi L. COIN/BCP User’s Guide. 2001. URL:

http://www.coin-or.org (дата обращения 30.07.2011) .

[5] Ralphs T. K., Ladanyi L., Saltzman M. J. A library hierarchy for implementing scalable parallel search algorithms // Journal of Supercomputing. 2004. V. 28 (2). P. 215–234 .

[6] Shinano Y., Higaki M., Hirabayashi R. Control schemas in a generalized utility for parallel branch and bound // Proc. of the 1997 Eleventh International Parallel Processing Symposium. Los Alamitos: IEEE, Computer Society Press, 1997 .

[7] Tschoke S., Polzer T. Portable parallel branch-and-bound library PPBBLib user manual. Department of computer science, Univ. of Paderborn, 1996 .

[8] Eckstein J., Phillips C. A., Hart W. E. PICO: An Object-Oriented Framework for Parallel Branch and Bound / RUTCOR Research Report 40–2000. Rutgers University, Piscataway, 2000 .

[9] Linderoth J. T. Topics in Parallel Integer Optimization / Ph.D .

Dissertation. Georgia Institute of Technology School of Industrial and Systems Engineering, 1998 .

[10] Chen Q., Ferris M. C., Linderoth J. T. Fatcop 2.0: Advanced features in an opportunistic mixed integer programming solver // Annals of Operations Research. 2001. V. 103. P. 17–32 .

[11] Shinano Y., Fujie T. ParaLEX: A parallel extension for the CPLEX mixed integer optimizer // Recent Advances in Parallel Virtual 494 Интеллектуальные системы и компьютерные науки Machine and Message Passing Interface / F. Cappello, T. Herault, J. Dongarra (eds.) Springer, 2007. P. 97–106 .

[12] Xu Y., Ralphs T. K., Ladanyi L., Saltzman M. J. Computational experience with a software framework for parallel integer programming // The INFORMS Journal on Computing. 2009 .

V. 21. P. 383–397 .

[13] Щербина О. А. Локальные элиминационные алгоритмы решения разреженных дискретных задач // Журнал вычислительной математики и математической физики. 2008. Т. 48. № 1 .

С. 161–177 .

[14] Foster I., Kesselman C. (eds). The Grid: Blueprint for a New Computing Infrastructure. San Francisco: Morgan Kaufmann Publishers Inc., 1998 .

Секция Информатика и прикладные исследования

–  –  –

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

Метод В работе исследовалась фоновая электрическая активность мозга, то есть испытуемый сидел в кресле с закрытыми глазами в расслабленном состоянии. Было обследовано шестнадцать людей с БП 1-ой стадии по шкале Хен-Яра (ХЯ) [5], четырнадцать людей со 2-ой стадией, восемь людей 2,5–3 стадией, и одиннадцать здоровых испыИнтеллектуальные системы и компьютерные науки туемых. ЭЭГ записывалась с электродов со стандартным расположением 10x20 с референтными электродами на ушах. Оцифрованные записи ЭЭГ были обработаны фильтром Баттерворта 4-ого порядка для удаления частот 50, 75 и 100 Гц, а также частот ниже 1 Гц.

Исследование частотно-временной динамики электрической активности проводилось с помощью вейвлет преобразования ЭЭГ:

В качестве материнской функции используется комплексный вей-влет Морле:

где, Fb = Fc = 1 .

Вейвлет спектрограмма (рис. 1) состоит из временных серий вспышек, расположенных в различных частотных диапазонах тета, альфа, бета и др. Суть метода заключается в том, что исследуется распределение локальных максимумов вспышек вейвлет преобразования по частоте и времени. В качестве примера на Рис. 1 представлено вейвлет преобразование сигнала в центральном отведении C3 здорового испытуемого 27 лет. Для нахождения местоположения вспышек на плоскости частота время делается две проекции вейвлет преобразования одна на плоскость частота амплитуда, другая на плоскость время амплитуда. С помощью первой проекции выделяются частотные диапазоны хребтов вейвлет спектрограмм. Далее, в каждом из диапазонов частот вейвлет спектрограмма проецируется на плоскость время амплитуда. Это необходимо для того, чтобы вспышки высоких амплитуд одного хребта не перекрывали вспышки других диапазонов. Далее вычисляются координаты положения всех вспышек. Таким образом, задача поиска локальных максимумов вейвлет-преобразования на плоскости частота время сводится к поиску локальных максимумов в двух плоскостях время амплитуда и частота амплитуда .

Секция Информатика и прикладные исследования Рис. 1. Вейвлет спектрограмма ЭЭГ здорового испытуемого с отведения C3 в полосе частот 1–25 Гц .

В результате, получены 2 координаты локальных максимумов и значения их амплитуд. На рис. 2 представлены положения локальных максимумов на плоскости время частота с симметричных пар отведений C3 (в виде крестиков) и C4 (в виде ноликов), отвечающих за моторику, здорового испытуемого и пациента с заболеванием Паркинсона на 1-ой стадии .

–  –  –

Рис. 2. а). Испытуемый К. (здоровый человек, 27 лет), б) Испытуемый Е. (пациент на 1-ой стадии БП, 29 лет) X отведение C3, O отведение C4 .

498 Интеллектуальные системы и компьютерные науки Для анализа динамики изменения частоты доминирующего ритма во времени в каждой полосе частот 0,5 Гц суммируются амплитуды локальных максимумов вспышек в окне 16 секунд и сдвигом окна на 16 секунд на всем временном интервале продолжительностью 240 секунд. Соответствующие гистограммы распределений частот вспышек с симметричных пар отведений ЭЭГ отображаются на одном графике (рис. 3) .

а) б) Рис. 3 .

Из рис. 3 видно, что у здорового человека вспышки распределены в узком диапазоне частот от 9 до 11 Гц. На ранней стадии паркинсонизма происходит увеличение частоты основного ритма в левом полушарии (X), уширение диапазона частот и проявляется межполушарная асимметрия электрической активности .

Заключение

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

Работа поддержана Программой Президиума РАН Фундаментальные науки медицине Список литературы [1] Stoers D., Bosboom J. L. W., Dejen J. B., Wolters E. C., Berendse H. W., Stam C. J. Slowing of oscillatory brain activity is a stable characteristic of Parkinson’s disease without dementia // Brain. 2007. 130. P. 1847–1860 .

[2] Soikkeli R., Partenen J., Soininen H., Paakkonen A., Riekkenen P. Sr .

Slowing of EEG in Parkinson’s disease // EEG Clin. Neurophysiol .

1991. 79. P. 159–165 .

[3] Вейн А. М., Голубев В. Л., Яхно Н. Н. Паркинсонизм с позиций функционально-неврологического анализа // Паркинсонизм: Вопросы клиники, патогенеза и лечения. M., 1974. C. 57–65 .

[4] Голубев В. Л., Левин Я. И., Вейн А. М. Болезнь Паркинсона и синдром паркинсонизма. М.: МЕДпресс, 1999 .

[5] Movement Disorder Society Task Force on Rating cales for PD. Unied Parkinson’s disease rating scale: status and recommendations // Mov. Disord. 2003. 18. P. 738–750 .

500 Интеллектуальные системы и компьютерные науки Модель информационно-поискового сайта филиала МГУ Осокин В. В. (Москва, МГУ им. М. В. Ломоносова) osvic@mail.ru Ставится задача построения универсальной информационно-поисковой системы, на базе которой можно реализовать веб-сайт любого филиала МГУ, факультета или кафедры. Система должна включать в себя объекты разных типов, таких как, например, сотрудник, студент, курс, практикум и т. д. В дальнейшем будем называть такие объекты сущностями. Система должна обеспечивать авторизированным пользователям интерфейс добавления произвольных типов сущностей с произвольными полями. Также система должна обеспечивать авторизированным пользователям интерфейс добавления произвольных сущностей введенных в систему типов .

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

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

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

Еще одним объектом системы является так называемый виджет .

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

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

В реализации системы возможность неограниченного добавления сущностей, отношений, типов сущностей и типов отношений достигается путем применения NOSQL СУБД MongoDB. В отличие от стандартных реляционных SQL СУБД, в MongoDB вместо таблиц используются коллекции, а вместо строк таблиц документы, причем структура документа не определяется коллекцией. Другими словами, каждый документ может иметь свои уникальные поля. При этом даже поля, присутствующие лишь в некоторых документах, можно индексировать. В результате, мы получаем единое хранилище сущностей и отношений, оптимизированное для поиска в нем .

Среди других используемых в системе технологий стоит выделить серверный язык php (фреймворк YII) и клиентский язык JavaScript (библиотека jQuery) .

Один из первых сайтов, реализованных в рамках системы сайт ташкентского филиала МГУ http://uz.msu.ru .

502 Интеллектуальные системы и компьютерные науки

–  –  –

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

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

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

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

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

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

Второй прием состоит в связывании образов друг с другом также по воле субъекта .

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

Предлагаемая нами модель гипертекстовой (гипермедиа) организации историко-исследовательской информации несколько отличается от классического представления о гипертексте. В ее основе лежат следующие понятия: информационный объект (ИО), образ ИО, объект гипертекста (ОГТ), ассоциация и связь .

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

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

Образ ИО, дополненный уникальным идентификатором его и указателем на ИО (уникальным идентификатором ИО), к которому этот образ относится, называется объектом гипертекста. ОГТ выступают в качестве узлов гипертекстовой сети и играют роль представителей ИО в гипертексте. С одним ИО может быть связано несколько ОГТ (один первичный, а остальные вторичные), представляюИнтеллектуальные системы и компьютерные науки

–  –  –

В множество операций входит 15 операций трех типов:

– операции формирования гипертекста, которыми определяются изменения состояния -структуры;

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

– операции выделения части гипертекстовой структуры в соответствии с заданными условиями .

506 Интеллектуальные системы и компьютерные науки Примером информационной системы для исторических исследований, в которой организация информации основывается на представленной выше -модели, может служить созданная автором система Просис [1, 2] .

–  –  –

[1] Гутнов Д. А., Перевертень В. А. Российские историки XVIII – начала XX вв.: проект и информационная система // Круг идей:

новое в исторической информатике. Труды I конференции Ассоциации История и компьютер. М., 1994. С. 39–50 .

[2] Гутнов Д. А., Перевертень В. А. Просопографическая информационная система Просис : версия 2.0 // Информационный бюллетень Ассоциации История и компьютер. М., 1994. № 10 .

С. 17–18 .

Секция Информатика и прикладные исследования

–  –  –

Рассмотрены методы математического моделирования неполного и недостоверного знания модели ( ) объекта исследования, выраженного в форме субъективных суждений модельера-исследователя (м.-и.) о возможных значениях неизвестного параметра. Математическая модель неизвестного параметра определена как неопределенный элемент (н. э.), характеризующий (как неопределенная высказывательная переменная) субъективные суждения м.-и. об истинности каждого значения значениями мер правдоподобия P равенства = и доверия Be неравенства = .

Предисловие

Вероятностные и возможностные методы применяются при моделировании многих аспектов как неясности и неопределенности, отражающих неполноту и недостоверность информации, так и случайности, нечеткости и неточности, относящихся к её содержанию. Модель случайности и нечеткости обычно считается вероятностной или возможностной, а неясность и неопределенность ассоциируются с неполным знанием последней, но моделируются, как правило, вербально [1, 2, 3]. Обычно неполное знание вероятностной (,, Pr(; )) или возможностной (, ( ), P(; )) моделей обусловлено их зависимостью от неизвестного параметра. В научной, инженерной и прочей исследовательской и творческой деятельности невозможно исключить использование неполной, противоречивой и недостоверной информации, ассоциированной с опытными фактами, с практикой их использования и с полученными знаниями. В работе рассмотрен метод математического моделирования подобной информации о возможных значениях неизвестного параметра, выраженной в форме субъективных суждений [4, 5] .

508 Интеллектуальные системы и компьютерные науки Существо метода иллюстрирует конструкция неопределенного случайного элемента, заданного на произведении пространств: вероятностного (,, Pr(; )), известного с точностью до значения и моделирующего неопределенный объект исследования, и пространства (, ( ), P, Be ) с мерами правдоподобия P и доверия Be, моделирующего неопределенный элемент (н. э.), характеризующий субъективные суждения исследователя об истинности каждого значения параметра значениями мер правдоподобия P ( = ) и доверия Be ( = ) .

В работе показано, как такая модель н. э. позволяет вычислить правдоподобие и доверие любых суждений исследователя о любых свойствах объекта, обусловленных его моделью (,, Pr(; )), .

Неопределенный элемент. Меры правдоподобия P и доверия Be Пусть семейство моделей ( ),, неопределенная модель объекта исследования. Модель неизвестного параметра неопределенный элемент (н. э.), характеризующий субъективные суждения исследователя об истинности каждого значения значениями мер правдоподобия P ( = ) и доверия Be ( = ) .

В модели (, ( ), P, Be ) н. э. меры правдоподобия P () :

( ) и доверия Be () : ( ), где и суть шкалы их значений, определены равенствами

–  –  –

значения правдоподобия равенства = и доверия неравенства =,. Функции () : [0, 1] и () : [0, 1] Секция Информатика и прикладные исследования распределения правдоподобий и доверий значений н. э.. Определения (1), (2) и их содержательная интерпретация суть следствия условий:

Модельер-исследователь может, основываясь на своих неполных и недостоверных априорных знаниях свойств объекта, считать значениями н. э. и предложить его модель (, ( ), P, Be ), указав в (2), насколько, по его мнению, относительно правдоподобны равенства =,, и насколько следует относительно доверять неравенствам =,, где относительно означает, что в (, ( ), P, Be )

1) численные значения P ( ) и Be ( ), ( ), в (1), отличные от нуля и единицы, не могут быть содержательно истолкованы, а существенна лишь их упорядоченность,

2) меры P () и P () (Be () и Be ()) считаются эквивалентными, если () ( ) (P ( )) = P ( ) ( () ( ) (Be ( )) = Be ( )), где группа непрерывных, строго монотонных функций () : [0, 1] [0, 1], (0) = 0, (1) = 1, def с групповой операцией, ( ) = ( ( )), [0, 1] .

Условия 1), 2) в терминах свойств шкал и, означают, что класс определяет группу автоморфизмов шкал = ([0, 1],, +, ) ([0, 1],, max, min) и = ([0, 1],, +, ) ([0, 1],, min, max) значений мер P () : ( ) и Be () : ( ), то есть () в шкалах и : ([0, 1]) = [0, 1],, [0, 1] ( ) ( ), ( ) ( ), и ( ) = ( ) ( ), где символ любой из операций: сложения +, + и умножения, .

Равенства + = = max{, }, = + = min{, },, [0, 1], следуют из требований [3] непрерывности и коммутативности операции как отображения [0, 1]2 [0, 1] и свойств нейтральных элементов 0 и 1 шкал и и группы : [0, 1] + 0 = 0 = 1 = +1 =, + 1 = 1 = 1 и 0 = +0 = 0 .

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

–  –  –

Оптимальные значения н. э .

Иногда н. э., в частности, E, удобнее охарактеризовать не распределениями E () и E (), а указав его, в известном смысле, оптимальное значение. В таком случае исследователь должен построить семейство пространств (L, (L), P (, ), Be (, )), (, ) (0, )2, в котором значение E, его оценка, L пространство элементарных потерь, (L) класс всех подмножеств L, P (, ), Be (, ) суть переходные правдоподобие и доверие для пространств ((0, )2, ((0, )2 )), (L, (L)), и для каждого (0, ) Секция Информатика и прикладные исследования

–  –  –

Автор признателен Ю. М. Нагорному, рассчитавшему зависимости на рис. 2 и подготовившему электронный вариант рукописи .

516 Интеллектуальные системы и компьютерные науки

–  –  –

[1] Пытьев Ю. П. Методы математического моделирования измерительно-вычислительных систем. М.: Физматлит, 2011 (третье издание) .

[2] Дюбуа Д., Прад А. Теория возможностей. М.: Радио и связь, 1990 .

[3] Пытьев Ю. П. Возможность как альтернатива вероятности. М.:

Физматлит, 2011 (второе издание) .

[4] Пытьев Ю. П. Неопределенные нечеткие модели и их применения // Интеллектуальные системы. 2004. Т. 8. Вып. 1–4 .

С. 147–310 .

[5] Пытьев Ю. П. Эмпирическое восстановление мер возможности и правдоподобия возможности в моделях экспертных решений // Автоматика и телемеханика. 2010. № 3. С. 131–146 .

Секция Информатика и прикладные исследования

–  –  –

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

Математическая часть этой задачи может быть сформулирована следующим образом. Имеется реализация функции ( ), сопоставляющая каждому неотрицательному значению соответствующее ему значение функции. При этом известно, что аналитически функция ( ) представима в виде () ( )= () + =1 ( попарно различные положительные константы, представляющие собой константы Михаэлиса входящих в раствор ферментов, положительные константы, характеризующие максимальную скорость реакции для чистого раствора отдельного фермента), но параметры, и неизвестны. Химически это соответствует моИнтеллектуальные системы и компьютерные науки

–  –  –

() где .

= Следует отметить, что вместо стандартного (экспоненциального) преобразования Фурье возможно (без изменения дальнейшей сути метода) и применение косинус-преобразования .

Секция Информатика и прикладные исследования Далее осуществляется комплексно-аналитическое продолжение функции ( ) с луча [0; +) действительной прямой на квадрант Re 0, Im 0 комплексной плоскости. Такое продолжение осуществимо в силу аналитичности функций во всей комплексной плоскости. Комплексно-аналитического продолжение может быть реализовано на основе стандартных конечно-разностных схем и определения комплексной производной или же эквивалентных комплексной дифференцируемости условий Коши Римана: оценки производных могут осуществляться рассмотрением горизонтальных приращений, а затем, на основе рассмотрения вертикальных приращений, могут быть восстановлены значения функции на следующем уровне сетки .

После комплексно-аналитического продолжения осуществляется переход к функции действительного переменного ( ): ( ) = Re ( ) ( 0). Аналитически функция ( ) представляет собой сумму () cos( ) .

=1 Наконец, для оценки характеристик присутствующих в растворе ферментов используются базовые факты теории почти периодических функций (см., например, [4], [5, Доп.: Почти периодические функции]) .

На пространстве почти почти периодических функций определено скалярное произведение (, ) = lim ()(), и система {cos( )} 0 является ортогональной относительно этого скалярного произведения .

Соответственно, для оценки количества ферментов и их характеристик функция ( ) разлагается по системе {cos( )} 0 или, иными словами, строится функция ( ) = ( ( ), cos( )) ( 0) .

Функция ( ) отлична от нуля лишь в точках ( = 1, 2,..., ), причем () ( )= .

520 Интеллектуальные системы и компьютерные науки Таким образом, число слагаемых (число ферментов) совпадает с числом точек, в которых функция ( ) совершает скачек (принимает ненулевое значение), и каждая такая точка позволяет восстановить () () () () = 2 ( ) ) .

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

Следует отметить, что для определения каталитической активности ферментов вместо интегрального преобразования Фурье в качестве интегрального преобразования может использоваться обратное преобразование Лапласа (см., например, [3, Гл. VIII, § 6]). В этом случае интегральное преобразование осуществляется после комплексноаналитического продолжения .

Работа выполнена в рамках Проекта по развитию пост-геномных исследований и технологий Разработка и реализация математических методов для определения каталитической активности ферментов в сложных биологических растворах (в соответствии с приказом ректора МГУ имени М. В. Ломоносова № 484 от 25 мая 2011 года) .

Секция Информатика и прикладные исследования

Список литературы

[1] Яковлев В. А. Кинетика ферментативного катализа. М., 1965 .

[2] Уэбб Л. Ингибиторы ферментов и метаболизма. М., 1966 .

[3] Колмогоров А. Н., Фомин С. В. Элементы теории функций и функционального анализа. М., 1976 .

[4] Левитан Б. М. Почти-периодические функции. М., 1953 .

[5] Демидович Б. П. Лекции по математической теории устойчивости. М., 1967 .

522 Интеллектуальные системы и компьютерные науки

–  –  –

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

К настоящему времени для визуальной информации (изображения, видео-поток без звука) и аудио-информации, а также для объединения этих видов информации (видео-поток со звуком) разработана и активно используется формальная база, включающая четкие стандарты и позволяющая строго говорить об обработке, хранении, воспроизведении и анализе такого рода данных и в аналоговом, и в цифровом форматах. В этой связи ограничимся лишь упоминанием цифровых стандартов JPEG/JPEG 2000 (см., например, [1]), MP3 (MPEG-1/2 Audio Layer 3, см., например, [2], [3]) и MPEG-2 (см., например, [4]). Для тактильной же информации до последнего времени не было разработано ни формальной модели, ни устройств, обеспечивающих получение и воспроизведение такого рода информации .

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

Тактильный механорецептор представляет собой круговой цилиндр с диаметром основания 10–20 мм, на одном из оснований которого расположена рабочая головка электронная таблетка, соСекция Информатика и прикладные исследования держащая датчики давления и обеспечивающая регулярное снятие показателей датчиков (в текущей реализации 100 раз в секунду) и передачу этих показателей управляющей станции. Дополнительно механорецептор может быть оборудован системой, позволяющей точно определять текущее положение и ориентацию этого прибора .

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

В настоящее время механорецептор успешно проходит клинические испытания .

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

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

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

Объективизация тактильных данных. Переход от субъективного описания тактильных характеристик ткани ( мягкая, умеренно жесткая и т. п.) к объективным данным обеспечивает возможность сопоставления результатов различных тактильных исследований, в частности, дает возможность объективно оценивать динамику изменений .

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

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

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

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

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

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

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

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

Работа выполнена в рамках комплексного проекта 2010–218–01– 345 Министерства образования и науки РФ Организация производства медицинских и биологических устройств с тактильными возможностями .

Список литературы

[1] Taubman D. S., Marcellin M. W. JPEG2000: image compression

fundamentals, standards, and practice. Norwell, Massachusetts:

Kluwer Academic Publishers, 2004 .

[2] Brandenburg K.-H., Stoll G. et al. ISO-MPEG-1 Audio: A Generic Standard for Coding of High Quality Digital Audio // JAES. 1994 .

42 (10). P. 780–792 .

[3] Information Technology: Generic coding of Moving pictures and associated audio Audio Part International standard ISO/IEC 13818-3. 1995 .

[4] Watkinson J. MPEG 2. Oxford: Focal Press, 1999 .

[5] Садовничий В. А., Буданов В. М., Соколов М. Э. и др. Математические задачи и методы в тактильной диагностике. М.: МАКС Пресс, 2008 .

526 Интеллектуальные системы и компьютерные науки

–  –  –

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

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

Однако после появления специального устройства (тактильного механорецептора), используемого в хирургии, в том числе, при проведении эндоскопических операций, появилась возможность говорить об объективных, численно измеряемых тактильных данных: результатом исследования, основанного на использовании тактильного механорецептора, является поле давлений (, ), снимаемое с датчиков рабочей головки механорецептора в процессе исследования .

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

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

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

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

Эти требования делают невозможным использование для автоматизации диагностики ряда стандартных методов решения задач классификации. Так, применение экспертных систем (см., например, [1], [2]) не дает возможности эффективно использовать экспериментальные данные, а также требует регулярного обновления банка правил в ручном режиме. Применение нейронных сетей (см., например, [3], [4]), наоборот, затрудняет использование экспертных данных, а также не удовлетворяет требованию о формальной обоснованности вывода. Классификация на основе тестов (см., например, [5]) также приводит к невозможности эффективного сочетания экспертных знаний и экспериментальных данных: при автоматическом создании набора тестов не могут быть эффективно использованы экспертные знаИнтеллектуальные системы и компьютерные науки ния (а также нарушается требования о формальной обоснованности вывода), а при неавтоматическом создании набора тестов возникает сложность учета экспериментальных данных (и возникает необходимость регулярного обновления набора тестов в ручном режиме) .

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

Основные шаги разработанного метода автоматизации диагностики заключаются в следующем .

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

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

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

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

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

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

Работа выполнена в рамках комплексного проекта 2010–218–01– 345 Министерства образования и науки РФ Организация производства медицинских и биологических устройств с тактильными возможностями .

Список литературы [1] Джексон П. Введение в экспертные системы. 3-е издание.

М.:

Изд. дом Вильямс, 2001 .

530 Интеллектуальные системы и компьютерные науки [2] Джарратано Дж., Райли Г. Экспертные системы: принципы разработки и программирование. М.: Изд. дом Вильямс, 2007 .

[3] Уоссерман Ф. Нейрокомпьютерная техника. Теория и практика .

М.: Мир, 1992 .

[4] Псиола В. В. Обзор основных нейросетевых моделей // Интеллектуальные системы. 1999. Т. 4. Вып. 3–4 .

[5] Кудрявцев В. Б., Андреев А. Е., Гасанов Э. Э. Теория тестового распознавания. М.: Физматлит, 2007 .

[6] Мандель И. Д. Кластерный анализ. М.: Финансы и статистика, 1988 .

[7] Айвазян С. А., Бухштабер В. М., Енюков И. С., Мешалкин Л. Д .

Прикладная статистика. Классификация и снижение размерности. М.: Финансы и статистика, 1989 .

Секция Информатика и прикладные исследования Алгоритмы упорядочивания переменных в локальном элиминационном алгоритме Свириденко А. В., Щербина О. А .

(Симферополь, Таврический национальный университет им. В. И. Вернадского) oleks.sviridenko@gmail.com, oshcherbina@gmail.com Для решения разреженных задач дискретной оптимизации (ДО) путем вычисления глобальной информации с помощью локальных вычислений на основе анализа окрестностей элементов задачи [1] может быть использован класс локальных элиминационных алгоритмов (ЛЭА) [2] .

Анализ публикаций, посвященных этой проблеме, позволяет сделать вывод, что в настоящее время экспериментальное исследование поведения алгоритма несериального динамического программирования (НСДП) [3, 4], являющегося локальным алгоритмом элиминации переменных, не проводилось .

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

Нерешенным является вопрос экспериментального исследования поведения алгоритма НСДП в зависимости от использования алгоритма упорядочивания переменных .

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

Рассмотрим разреженную задачу ДО, структура которой задается графом взаимосвязей переменных [3, 4]. В графе взаимосвязей задачи ДО вершины соответствуют переменным, причем две вершины соединяются ребром, если соответствующие переменные имеются 532 Интеллектуальные системы и компьютерные науки в одном и том же ограничении или/и в одном компоненте целевой функции .

Алгоритм НСДП может быть кратко записан так:

1) Перенумеровать переменные согласно порядку (в данном случае : { 1,..., }) .

2) Для = 1,..., исключить, изменяя граф взаимосвязей путем добавления ребер для превращения окрестности исключаемой вершины в клику .

Алгоритм минимальной степени MD В алгоритме минимальной степени (minimum degree (MD)) выбирается вершина графа с минимальной степенью. Далее строится граф, получаемый путем создания клики из вершины и ее соседей с последующим удалением и инцидентных ей ребер. Рекурсивно из с помощью эвристики создается хордальный суперграф. И, наконец, получают связный суперграф из, путем добавления и инцидентных ей ребер из к. Будучи алгоритмом локальной минимизации, алгоритм MD не всегда дает упорядочение с минимальным пополнением для графа в целом. Для получения упорядочения при помощи алгоритма минимальной степени MD в данной работе была выбрана функция minimum_degree_ordering() из библиотеки BOOST [5] .

Алгоритм рекурсивного разбиения ND Алгоритм рекурсивного разбиения ND [6] находит сепаратор, то есть множество вершин, разделяющее граф на две части и, помещая в упорядочении последним. Алгоритм применяется рекуррентно к частям графа и, пока их размеры не станут меньше, чем некоторое пороговое значение. Для вычисления упорядочения с помощью алгоритма рекурсивного разбиения ND в настоящей работе использовалась функция METIS_EdgeND() библиотеки Metis [7] .

Алгоритм MCS В [8] был предложен алгоритм MCS (Maximum Cardinality Search поиск по максимальной степени). MCS на некотором графе производит за время ( + ) полное упорядочение множества Секция Информатика и прикладные исследования вершин следующим образом. Из произвольной вершины, выбирается любая, еще не пронумерованная вершина, смежная максимальному числу уже пронумерованных вершин. MCS упорядочение было получено при помощи пакета CHOMPACK [9] .

Алгоритм Minimum Fill-in Эвристика минимального пополнения (Minimum Fill-in) [10] работает практически так же, как и описанная выше эвристика минимальной степени MD, с той лишь разницей, что здесь на каждом шаге выбирается такая вершина, чтобы число добавляемых к ней ребер, необходимых для получения клики, было минимальным .

Алгоритм Lex-BFS Rose, Tarjan, и Lueker [11] предложили алгоритм, вычисляющий хорошую элиминационную последовательность за линейное время, который был назван лексикографическим поиском в ширину (LexBFS). Суть данного метода заключается в следующем. Вершины нумеруются от до 1 (нумерация фиксирует позиции переменных) в упорядочении. Далее, для каждой вершины создается метка, содержащая множество чисел, записанных по убыванию. Таким образом вершины могут быть лексикографически упорядочены согласно их меткам .

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

Описание множества тестовых задач Тестовые задачи ДО генерировались на основе уже существующих гиперграфов из библиотеки задач удовлетворения ограничений [12]. Для построения ограничения бралось очередное гиперребро гиперграфа из библиотеки [12], содержащее множество переменных, входящих в строящееся ограничение. Далее с помощью 534 Интеллектуальные системы и компьютерные науки процедуры, использующей датчик случайных чисел, строились коэффициенты при соответствующих переменных, тогда левая часть

-го ограничения имела вид. Правая часть -го ограничения имеет вид, где случайное число из интервала (0, 1). Коэффициенты целевой функции max. также строились =1 с помощью процедуры, использующей датчик случайных чисел. Далее для каждой тестовой задачи ДО строился соответствующий граф взаимосвязей. Для каждого графа взаимосвязей применялись алгоритмы упорядочивания MD, ND, MCS, MIN-FILL и LEX-BFS, после чего задачи ДО решались с помощью алгоритма НСДП с соответствующими найденными упорядочениями .

Анализ результатов вычислительного эксперимента Для проведения вычислительного эксперимента были взяты пять групп тестовых задач: ’dubois’, ’bridge’, ’adder’, ’pret’ и ’NewSystem’ из библиотеки [7], содержащие 33 тестовые задачи. Все вычисления были проведены на базе процессора Intel Core 2 Duo @ 2.66 GHz, 2 GB ОЗУ и операционной системы Linux, версия ядра 2.6.35-24-generic .

Согласно результатам вычислительного эксперимента, на множестве тестовых задач для алгоритма ND минимальное время работы алгоритма НСДП было достигнуто 0 раз (0%), для MD 2 раза (6,0%), LEX-BFS 3 раза (9,1%), MCS 9 раз (27,3%) и MIN-FILL 19 раз (57,6%) .

Список литературы

[1] Журавлев Ю. И. Избранные научные труды. М.: Магистр, 1998 .

[2] Щербина О. А. Локальные элиминационные алгоритмы решения разреженных дискретных задач // Журнал вычислительной математики и математической физики. 2008. Т. 48. № 1 .

С. 161–177 .

[3] Bertele U., Brioschi F. Nonserial Dynamic Programming. New York: Academic Press, 1972 .

Секция Информатика и прикладные исследования [4] Щербина О. А. О несериальной модификации локального алгоритма декомпозиции задач дискретной оптимизации // Динамические системы. 2005. Вып. 19. С. 179–190 .

[5] BOOST, minimum degree ordering algorithm .

URL: http://www.boost.org [6] George J. A. Nested dissection of a regular nite element mesh // SIAM J. Numer. Anal. 1973. V. 10. P. 345–367 .

[7] Karypis G., Kumar V. MeTiS a software package for partitioning unstructured graphs, partitioning meshes, and computing ll-reducing orderings of sparse matrices. Version 4. University of Minnesota, 1998 .

[8] Tarjan R. E., Yannakakis M. Simple linear-time algorithms to test chordality of graphs, test acyclity of hypergraphs, and selectively reduce acyclic hypergraphs // SIAM J. Comput. 1984. V. 13 .

P. 566–579 .

[9] CHOMPACK, maximum cardinality ordering algorithm. URL:

http://abel.ee.ucla.edu/chompack/ [10] Jgou P., Ndiaye S. N., Terrioux C. Computing and exploiting e tree-decompositions for (Max-)CSP // Proceedings of the 11th International Conference on Principles and Practice of Constraint Programming (CP-2005). 2005. P. 777–781 .

[11] Rose D., Tarjan R., Lueker G. Algorithmic aspects of vertex elimination on graphs // SIAM J. on Computing. 1976. V. 5 .

P. 266–283 .

[12] Musliu N., Samer M., Ganzow T., Gottlob G. A csp hypergraph library. Technical Report. DBAI–TR–2005–50. Technische Universitt Wien, 2005 .

a 536 Интеллектуальные системы и компьютерные науки Достаточное условие эффективной разрешимости задачи Open shop в терминах суммарной нагрузки Севастьянов С. В., Черных И. Д. (Новосибирск, ИМ СО РАН) seva@math.nsc.ru, idchern@math.nsc.ru

–  –  –

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

В статье [3] рассматриваются достаточные условия нормальности входов, описываемые в терминах неравномерности нагрузок машин, и описываются соответствующие (достаточно широкие) эффективно-нормальные классы. Целью данной работы является выявление эффективно-нормальных классов, описываемых в терминах ограничений на суммарную нагрузку .

.

( ) = { ( ) ( )}. Для Рассмотрим класс входов каждого 3 исследуем, при каком наибольшем значении класс ( ) является нормальным, то есть найдем наиболее широкие нормальные классы вида ( ). Заметим, что для случая = 2 такая постановка вопроса неинтересна, поскольку множество всех входов 2 является эффективно-нормальным классом [1] .

В дальнейшем будем пользоваться следующими преобразованиями входов .

Определение. Будем говорить, что вход получен из входа с помощью склеивания множества машин, если ( ) = ( ) и ( ) = ( ) { }, где = .

Заметим, что допустимое расписание для склеенного входа можно интерпретировать как допустимое расписание такой же длины для исходного входа. Справедлива следующая Лемма. Для любого 3и 2 класс ( ) не является нормальным .

Доказательство. Рассмотрим следующий вход с четырьмя работами. Работа 1 имеет три операции на машинах 1, 2 и 3 длительности 1/3, операции на остальных машинах нулевые. Каждая из работ, = 2, 3, 4, имеет единственную ненулевую операцию длительности 1/3 + на машине 1. Для этого входа = 2 + 3. Докажем, что он не является нормальным. Предположим обратное, что для этого входа существует расписание длины. Поскольку 1 =, операции работы 1 выполняются в этом расписании одна за другой, без промежуточных ожиданий. При этом одна из них выполняется (на некоторой машине ) в интервале [1/3, 2/3]. Ясно 538 Интеллектуальные системы и компьютерные науки однако, что ненулевую операцию работы +1 невозможно выполнить на этой же машине ни в одном из оставшихся свободных интервалов [0, 1/3], [2/3, 1], что означает невозможность выполнения совокупности работ в интервале [0, ]. Полученное противоречие доказывает лемму .

.

Рассмотрим объединение классов ( ) = ( ). Справедлива следующая Теорема. (2) является эффективно-нормальным классом .

Доказательство. Рассмотрим вход (2). В силу симметричности понятий машина/работа в системе open shop, без ограничения общности можем считать, что ( ) = 1 ( ). Поскольку ( ) 2 ( ), справедливо ( ) ( ). Проведем склеивание множества машин = { 2,..., }. Поскольку 1 ( ) = 1 ( ) = ( ), 2 ( ) ( ), а длины работ нового входа совпадают с длинами соответствующих работ из, имеем ( ) = ( ) .

Поскольку 2, оптимальное расписание длины ( ) может быть построено алгоритмом Гонзалеза-Сани [1] за время, линейное от числа работ. Это расписание можно интерпретировать как допустимое расписание длины ( ) для исходного входа .

Заметим, что в силу леммы и теоремы любой нормальный класс вида ( ) является подмножеством (2), то есть для любого 3 наиболее широким нормальным классом вида ( ) является (2) .

Работа выполнена при финансовой поддержке РФФИ, грант № 08–01–00370 .

Список литературы

[1] Gonzalez T., Sahni S. Open shop scheduling to minimize nish time // J. Assoc. Comp. Math. 1976. 23. P. 665–679 .

[2] Williamson D. P. et al. Short shop schedules // Oper. Res. 1997 .

V. 45. N. 2. P. 288–294 .

[3] Kononov A., Sevastianov S., Tchernykh I. When dierence in machine loads leads to ecient scheduling in open shops // Annals of Oper .

Res. 1999. 92. P. 211–239 .

Секция Информатика и прикладные исследования

–  –  –

1. Введение Системы линейных уравнений = с симметричной положительно определенной матрицей возникают при численном решении задач математической физики. Для решения систем такого рода применяют разложение Холецкого вида, где верхнетреугольная матрица. Тогда решение исходной системы эквивалентно решению двух систем: =. Классический алгоритм =, нахождения разложения, предложенный в [1], последовательно формирует элементы новой строки, начиная с первой, и использует при этом значения в найденных строках. Такой подход не обладает параллелизмом, так как независимый расчет строк приведет к некорректному результату. Однако, если матрица является разреженной, то некоторые строки могут не зависеть от значений предыдущих строк, и выделение независимых друг от друга групп позволяет организовать параллельный расчет. В [2] дано определение дерева исключения матрицы, как отражения ее структуры разреженности, определяющей зависимость между строками, и сформулированы теоремы, позволяющие сконструировать параллельный алгоритм нахождения разложения по известному дереву исключения. Задача построения дерева исключения совпадает по сложности с задачей определения портрета матрицы [3], при этом вид полученного дерева может не допускать эффективного распараллеливания. В этом случае предлагается предварительно переупорядочивать матрицу с помощью алгоритмов [1], в ходе выполнения которых дерево исключения матрицы становится известным и хорошо сбалансированным. К таким алгоритмам относят методы семейства вложенных сечений. В данной статье рассматривается параллельная схема общего вида для решеИнтеллектуальные системы и компьютерные науки ния поставленной задачи, позволяющая достичь ускорения log2, где число независимых вычислителей .

2. Связь дерева исключения с переупорядочиванием матрицы Пусть ( ) = (, ) граф матрицы. Деревом исключения называется дерево, чье множество вершин совпадает с, а ребро (, ) существует тогда и только тогда, когда = min{ : = 0 & } .

Таким образом, является родителем, если первый недиагональный элемент строки располагается в столбце. Такое определение дает понятие зависимости между строками. Если вершина является предком вершины, то значения в строке должны быть вычислены после значений в строке, так как зависят от них. Ресурсом для получения ускорения является параллельное вычисление строк, соотвествующие вершины которых не являются по отношению к друг другу предком или потомком. При этом, чем меньше высота дерева исключения при заданном количестве вершин, тем более высокое ускорение можно получить. Переупорядочивание матрицы методом вложенных сечений дает бинарное дерево исключения [4], причем настройка параметров алгоритма позволяет получать сбалансированность между поддеревьями одного уровня. Другим критерием при выборе алгоритма переупорядочивания является заполнение, возникающее в матрице, так как при решении большеразмерных систем сохранение разреженности более важная задача, чем распараллеливание. В статье приведены результаты, демонстрирующие, что для типовых задач, возникающих на практике, метод вложенных сечений дает не худшее заполнение, чем другие известные алгоритмы [1] .

3. Программная реализация На основе приведенных рассуждений предлагается программная реализация, основанная на предварительном переупорядочивании исходной матрицы методом вложенных сечений. Итогом переупорядочивания является матрица перестановок и дерево исключения. В силу эквивалентости задач определения дерева исключения и символической факторизации будем считать, что портрет матрицы является известным. Для дальнейшего параллельного выполнения необходиСекция Информатика и прикладные исследования мо сделать разбиение дерева исключения. Один из способов разбиения выделение поддеревьев одинаковой высоты. Высота поддеревьев эвристический параметр, влияющий на балансировку между потоками, и его оптимальное значение зависит от конфигурации вычислительной системы. Для матриц с порядком от 50000 до 1000000 рекомендуется выбирать его в диапазоне от 50 до 100. Между поддеревьями необходимо установить отношение предок потомок, и каждое поддерево связать с задачей. Под задачей понимается атомарный набор операций, который будет последовательно выполняться на одном вычислителе для всех вершин поддерева, ей соотвестветствующего .

Пример задачи:

1) Для всех потомков текущего поддерева запустить параллельное выполнение соотвествующих задач .

2) Синхронизировать окончание выполнения порожденных задач .

3) Для каждой вершины поддерева выполнить шаги вычислительной фазы .

Запуск параллельного алгоритма инициализирует задача, соотвествующая корневому поддереву. Данная схема подходит для численой факторизации и решения системы = при обходе вершин от листьев поддерева к корню. Решение системы = соотвествует схеме с последовательностью шагов 3, 1, 2 и обратным порядком обхода вершин в поддереве для шага 3 .

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

Название CM RCM King Sloan ND shallow_water2 0,00656 0,00656 0,00739 0,00654 0,00063 parabolic_fem 0,00163 0,00163 0,00163 0,00163 0,00019 tmt_sym 0,00242 0,00236 0,00266 0,00225 0,00018 thermomech_dM 0,00181 0,0017 0,00178 0,00512 0,00045 542 Интеллектуальные системы и компьютерные науки где CM прямой алгоритм Катхилл Макки, RCM обратный алгоритм Катхилл Макки, King алгоритм Кинга, Sloan алгоритм Слоуна, ND метод вложенных сечений .

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

Результаты решения СЛАУ на 8 потоках показывают ускорение, близкое к теоретически возможному:

Название 1 2 shallow_water2 81920 1,65 2,62 930 100 parabolic_fem 525825 1,84 2,83 2826 75 tmt_sym 726713 1,62 2,59 3932 100 thermomech_dM 204316 2,79 3,16 1293 50 где порядок матрицы, 1 ускорение численной факторизации, ускорение при решении систем, высота дерева исключения, высота поддеревьев в разбиении .

Список литературы

[1] Писсанецки С. Технология разреженных матриц. М.: Мир,

1988. C. 76–79, 115, 163 .

[2] Heggerness P. Minimizing ll-in size and elimination tree height in parallel Cholesky factorization. Bergen: Department of Informatics University of Bergen, 1992. P. 15–17 .

[3] Van Grondelle J. Symbolic Sparse Cholesky Factorization Using Elimination Trees. Utrecht: Department of Mathematics Utrecht University, 1999. P. 3–6 .

[4] Сафонова Я. Ю. Использование графовых моделей при распараллеливании метода Холецкого при решении разреженных симметричных СЛАУ // Материалы XVI международной конференции Проблемы теоретической кибернетики. Нижний Новгород: Издво ННГУ, 2011. C. 426–430 .

Секция Информатика и прикладные исследования Формализация задачи поиска объектов на векторной сцене Фофанов В. Б., Жизневский А. Н .

(Казань, Казанский (Приволжский) Федеральный Университет) viatcheslav.fofanov@ksu.ru, write2aracon@mail.ru Введение Поиску на сцене объектов определенного вида по ее изображению посвящено довольно большое количество публикаций. Предлагаемые в них методы являются, как правило, эвристическими. В настоящей работе излагаются формализация и решение этой задачи в рамках теоретико-вероятностного подхода. При этом предполагается, что объекты являются пятнами, а исходной информацией о сцене служит набор ее изображений. Поиск объектов предлагается проводить в три этапа. На первом определяются квадратные фрагменты сцены, названные зонами интереса. Каждая зона содержит один объект и его окружение (фон). На втором этапе (сегментации) проводится классификация пикселей зоны интереса на два класса. Пиксели, оказавшиеся в классе с именем объект, используются на третьем этапе для вычисления геометрических признаков объекта и принятия окончательного решения о его присутствии на сцене .

1. Модель сцены Пусть (,, ) вероятностное пространство, = {0, 1,..., множество из = объектов и конечное подмножество на целочисленной решетке 2. Назовем объектом сцены с проекцией семейство = ( ) векторных случайных величин = ( )1, определенных на (,, ) и принимающих значения в Y =. Изображением объекта будет называться семейство x = (x ) из Y. Объект считается заданным, если на множестве Y его изображений задано распределение вероятностей Y = ( Y (x ))x Y. Совокупность объектов назовем векторной сценой, если их проекции попарно не пересекаются, а их сумма равна 2. Таким образом, сцена является векторным случайным полем 544 Интеллектуальные системы и компьютерные науки ( ) 2. В частном случае, когда случайные величины являются скалярными, сцена также будет называться скалярной. В качестве изображения x = (x ) 2 сцены естественно рассматривать реализации (выборочные поверхности) случайного поля. Существование указанных сцен вытекает из следующей теоремы .

Теорема 1. Пусть на 2 задано разбиение, состоящее из конечных попарно непересекающихся подмножеств, называемых проекциями, и пусть каждой проекции 2 поставлено в соответствие распределение вероятностей Y на множестве Y .

Тогда существует вероятностное пространство (,, ) и векторная сцена ( ) 2 такая, что { : ( )=x }= (x ) Y для любой проекции и любого x Y. Кроме того, если и проекции разных объектов, то для любых и случайные величины и независимы .

Далее предполагается, что каждый объект является фрагментом однородного случайного поля с вектором средних значений m Y, для которого выполняются условия эргодической теоремы Слуцкого. Это позволяет использовать среднее арифметическое значение x = 1 x, вычисленное по изображению объекта x в качестве статистической оценки для m .

–  –  –

Математические модели экономических процессов Черемных Ю. Н. (Москва, МГУ им. М. В. Ломоносова) Содержательные области и проблематика экономико-математического моделирования исторически формировались постепенно: проблемы ценообразования в различных рыночных структурах (от чистой конкуренции до чистой монополии), рационального поведения потребителя на рынке, максимизации прибыли, спроса и предложения, относящиеся традиционно к микроэкономике. К макроэкономике относятся вопросы, связанные со статикой и динамикой инвестиций, процентной ставки, безработицы и валового национального продукта. Отдельно следует отметить проблему рыночного равновесия (на микро- и макроэкономическом уровнях). Cюда необходимо добавить вопросы структуризации данных и их преобразования в модельную информацию, анализа влияния отдельных факторов на поведения ключевых экономических показателей (предмет математической статистики и эконометрики), совокупность задач, связанных с операциями на финансовых рынках (то eсть на рынках ценных бумаг и финансовых услуг) .

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

Теория систем линейных алгебраических уравнений основной инструмент анализа статической межотраслевой модели, предложенной в 1930-e гг. американским экономистом В. В. Леонтьевым (Премия по экономике имени Нобеля, 1973). Cтатическая межотраслевая модель (модель затраты выпуск) представляет собой развитие идеи межотраслевого описания национальной экономики Советской России, реализованной группой советских экономистов в середине 1920-х гг .

Метод неопределенных множителей, опубликованный французским математиком Ж. Л. Лагранжем на рубеже 18–19 вв., активно использовался и используется экономистами для решения разнообИнтеллектуальные системы и компьютерные науки разных задач в основном микроэкономики: задачи рационального поведения потребителя на рынке, задача рационального распределения ограниченных ресурсов и задача издержек при фиксированном объеме выпускаемой продукции. B этих задачах множитель Ж. Л. Лагранжа имеет глубокий экономический смысл. В теории потребления он связывает величину дохода потребителя с уровнем полезности, в теории производства лимит на ресурсы с объемом выпускаемой продукции .

Линейное программирование возникло под давлением экономической проблематики (проблема рационального использования ограниченных ресурсов) и было отмечено Премией по экономике имени Нобеля, которую получили советский математик Л. В. Канторович и американский математик Т. Купманс. На основе симплексного метода, предложенного американским математиком Дж. Данцигом, и на базе использования ЭВМ было решено большое число оптимизационных задач с экономическим и военным содержанием .

Линейное программирование долгое время представляло собой интенсивно развивающуюся область прикладной матемaтики (нелинейное программирование) .

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

Положения теории оптимального управления находят активное применение в решении и анализе многих задач макроэкономики .

Для решения широких классов разнообразных экономических задач интенсивно применяются разделы теории вероятностей и математической статистики .

Следует отметить, что примерно до середины 20 в. уровень применения математики в экономических исследованиях заметно отставал от аналогичного уровня применения математики в естественнонаучных областях. После публикации в 1954 г. журналом Эконометрика cтатьи Существование равновесия в конкурентной экономике американского экономиста К. Эрроу (лауреат Премии по экономике имени Нобеля (1972) и французского математика Ж. Дебре Секция Информатика и прикладные исследования (лауреат Премии по экономике имени Нобеля (1983) ситуация заметно изменилась благодаря высокому математическому уровню статьи К. Эрроу и Ж. Дебре. Уровень был вполне сопоставим с математическим уровнем самых продвинутых статей естественно-научного профиля. Добавим, что Ж. Дебре был членом группы Н. Бурбаки, работавшей во Франции после окончания Второй мировой войны .

Исторически первой монографией экономико-математического содержания была работа Исследования математических принципов теории богатства французского математика А. Курно (1838) .

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

Позднее, в 1950 г., американский математик Дж. Нэш (лауреат Премии по экономике имени Нобеля, 1994) предложил понятие равновесия некооперативной игры конечного числа игроков, которое позже получило его имя и которое обобщает равновесие А. Курно .

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

Вопрос формулировался так:

существуют ли такие цены (называемые ценами равновесия), ориентируясь на которые каждая фирма и каждый потребитель решают задачу максимизации и при этом не будет дефицита ни по одному продукту. Полное положительное решение этой задачи К. Эрроу и Ж. Дебре (как уже отмечалось выше) опубликовали в 1954 г. Они 550 Интеллектуальные системы и компьютерные науки использовали теорему о неподвижной точке точечно-множественного отображения японского математика Ш. Какутани, опубликованную в 1941 г .

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

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

В 1958 г. в книге Линейное программирование и экономический анализ трех американских авторов Дорфман Р., Сэмуэльсон П .

(лауреат Премии по экономике имени Нобеля, 1970), Солоу Р. (лауреат Премии по экономике имени Нобеля, 1987) было описано магистральное свойство оптимальных траекторий валовых выпусков и цен, суть которого состояла в том, что в случае продолжительного временного промежутка модели ее оптимальная траектория выпусков (для оптимальной траектории цен ситуация аналогична) состоит из трех участков. Первый участок это отрезок оптимальной траектории, который приближается к траектории максимального постоянного пропорционального роста, расположенной на луче, называемом магистралью; второй участок это отрезок оптимальной траектории, который близок (в смысле углового расстояния) к траектории максимального постоянного пропорционального роста; третий участок это отрезок оптимальной траектории, который может отойти от траектории максимального постоянного пропорционального роста. Основные характеристики траектории максимального постоянного пропорционального роста (темп роста и структура) определяются технологическим множеством модели, то есть эндогенно. ТеоСекция Информатика и прикладные исследования ретическое значение магистрального свойства состоит в том, что в случае продолжительного временного горизонта модели оптимум достигается через максимальный постоянный пропорциональный рост, практическое значение магистрального свойства в том, что оно позволяет дать рациональное решение проблемы хвоста и проблемы сглаживания оптимальной траектории .

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

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

Список литературы [1] Экономико математический энциклопедический словарь.

M.:

Большая Российская энциклопедия, Изд. дом ИНФРА-М, 2003 .

552 Интеллектуальные системы и компьютерные науки

–  –  –

Рассматриваемая задача обобщает две классические задачи дискретной оптимизации: метрическую задачу комивояжера и задачу Open Shop с прерываниями. Имеется работ 1,...,, каждая из которых должна быть обработана каждой из машин 1,..., в произвольном порядке. Операция обработки работы машиной занимает единиц времени. Операцию можно прерывать в любой момент времени и возобновить ее выполнение позднее. Работы расположены в вершинах транспортной сети, описываемой реберновзвешенным графом =,, расстояние между вершинами и обозначается через. Множество работ, расположенных в вершине, обозначим через. Одна из вершин является базой; изначально все машины находятся в базе и должны вернуться туда после выполнения всех своих операций. Машины передвигаются с единичной скоростью. Требуется составить допустимое расписание, минимизирующее время возвращения всех машин на базу после выполнения всех операций. Задача рассматривается в двух постановках: с заданной базой или с выбираемой базой, обозначаемых соответственно max и max .

, Задача является NP-трудной в сильном смысле даже в случае = 1 (в этом случае она эквивалентна метрической задаче комивояжера). Двухмашинная задача является полиномиально разрешимой в случае, когда транспортная сеть состоит из двух вершин [1]. Алгоритмическая сложность двухмашинной задачи на треугольнике является открытым вопросом. Двухвершинная задача с нефиксированным числом машин является NP-трудной в сильном смысле [1]. Целью данной работы является описание полиномиально-разрешимых подклассов задач max и max .

2 2, Секция Информатика и прикладные исследования

–  –  –

2 (1) .

/ 1

–  –  –

« ©« « © © 1,... 11 12 13

–  –  –

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

–  –  –

и такое расписание с не более чем одним прерыванием может быть найдено за время ( + ) .

Доказательство этой теоремы аналогично доказательству теоремы 1 .

Работа выполнена при финансовой поддержке РФФИ, грант № 08–01–00370 .

–  –  –

[1] Пяткин А. В., Черных И. Д. Задача открытого типа с маршрутизацией и разрешением прерываний на двухвершинной сети // Материалы IV Всероссийской конференции Проблемы оптимизации и экономические приложения. Омск, 29.06–4.07.09. С. 158 .






Похожие работы:

«82 УДК 621.438:536.38 М А ТЕ М А Т И Ч ЕС К О Е М О Д Е Л И Р О В А Н И Е П Р О Ц Е С С А О БРА ЗО В А Н И Я О К С И ДА А ЗО ТА В К А М ЕРА Х С Г О РА Н И Я А В И А Ц И О Н Н Ы Х Д В И ГА Т Е Л Е Й И Э Н Е Р Г Е Т И Ч Е С К И Х У С ТА Н О В О К Куценко Ю.Г. ОАО "Авиадвигатель", г....»

«Журнал для тех, для кого информатика – любимый школьный предмет Выпуск № 1, май 2016 г. Уважаемые коллеги! Интернет-журнал "Мир информатики", первый выпуск которого вы читаете, предназначен для учащихся. В нем...»

«Системы счисления ПОЗИЦИОННЫЕ СИСТЕМЫ СЧИСЛЕНИЯ Известно множество способов представления чисел. В любом случае число изображается символом или группой символов (словом) некоторого алфавита. Будем называть такие симво...»

«Агальцов Алексей Дмитриевич Исследование задач обращения и характеризации для обобщённого преобразования Радона и оператора Дирихле–Неймана 01.01.02 Дифференциальные уравнения, динамические системы и оптимальное управлени...»

«0715197 ^^ НИИ ТОЧНЫХ ПРИБОРОВ НАПРАВЛЕНИЯ ДЕЯТЕЛЬНОСТИ И ПРОИЗВОДИМАЯ ПРОДУКЦИЯ Генеральный директор главный конструктор Шишаное Анатолий Васильевич Рад приветствовать Вас на страницах каталога Научно-исследовательского инс...»

«Всероссийские олимпиады по информатике: 1989 – 1991 г.г. Всероссийские олимпиады школьников по информатике с 1989 года по 1991 год являлись республиканским этапом Всесоюзной олимпиады. Поскольку после распада СССР статус этих олимпиад изм...»

«ВСЕРОССИЙСКАЯ ОЛИМПИАДА ШКОЛЬНИКОВ 2013-2014 гг. МУНИЦИПАЛЬНЫЙ ЭТАП ИНФОРМАТИКА 9-11 КЛАСС Задача A. ЛЛШ Имя входного файла: stdin Имя выходного файла: stdout Ограничение по времени: 1 сек...»

«Лекция 4. Функциональные стили русского литературного языка. Общая характеристика. Морфологические и синтаксические средства.Домашнее задание: Выполняется до 13 недели занятий. Проанализируйте текст научного стиля (приблизительно 500 сло...»

«LinkMaster SKU: KWP-LNKMS0-PRD Обзор продукта LinkMaster обеспечивает соединение и передачу данных между OPC серверами, и таким образом служит в качестве универсального моста для OPC систем. LinkMaster, действует и как OPC сервер, и как DDE сервер, позволяя соединить мостом устаревшие систем...»

«ОТЗЫВ официального оппонента на диссертационную работу Свалова Андрея Владимировича “ВЛИЯНИЕ РАЗМЕРНОГО И СТРУКТУРНОГО ФАКТОРОВ НА МАГНЕТИЗМ МНОГОСЛОЙНЫХ ПЛЕНОК НА ОСНОВЕ 3dи 4/-МЕТАЛЛОВ, представленную на соис...»

«Беспроводные микрофонные системы Руководство пользователя Состав системы Все системы включают в себя: 1x приёмник PAW-260 1х передатчик 2х батареи типа "АА" 1х аудио кабель 1х блок питания 1х руководство пользователя Система для вокалиста включает в себя: Микрофон-передатчик PAH-172 Система нагрудного / голо...»

«IV. Запоминающие устройства ЗУ классифицируют: 1) по месторасположению по отношению к вычислительному устройству:а) внешние ЗУ, б) внутренние ЗУ;2) по назначению:а) сверхоперативные ЗУ (СОЗУ) – имеют бы...»

«Категорная модель модального лямбда-исчисления, основанного на интуиционистской эпистемической логике. Категорная модель модального лямбда-исчисления, основанного на интуиционистской эпистемической логике. Даня Рогозин Март, 2018 Категорная модель мо...»

«Инструкция по охране труда 2018 г.1. Общие требования охраны труда 1.1. Настоящая инструкция устанавливает требования безопасности труда при выполнении должностных обязанностей учебно-вспомогательным пе...»

«Объекты для проведения практических занятий Кабинет №19 Жалюзи 4 информатика Колонки Genius 1 Подставка для цветов 1 Стол демонстрационный под аудиторную доску 1 Тумба 1 Стол ученический 1 "Введение в информатику" 12 таблиц 1 Стеллажи для обуви 1 Стол журнальный 1 Стол преподавателя 1 Сканер HP Scanjet 3...»

«Вестник БГУ. Сер. 1. 2014. № 2 УДК 539.1.08;539.12.08 А. и. СыТОВ ПРИМЕНЕНИЕ ИЗОГНУТОГО КРИСТАЛЛА ДЛя ВЫВОДА ПРОТОННОГО ПУчКА ИЗ НАКОПИТЕЛьНОГО КОЛьЦА Обсуждаются методы реализации новых идей в области управления высокоэнергетичными пучками при помощи изогнутых кристаллов с использованием эффекта...»

«СЕРИЯ 10 ВЕСТНИК ВЫПУСК 4 ПРИКЛАДНАЯ МАТЕМАТИКА САНКТ-ПЕТЕРБУРГСКОГО ДЕКАБРЬ ИНФОРМАТИКА УНИВЕРСИТЕТА ПРОЦЕССЫ УПРАВЛЕНИЯ Научно-теоретический журнал Издается с августа 1946 года СОДЕРЖАНИЕ Прикладная математика Ампилова Н. Б., Терентьев С. В. О применении интервальной арифметики пр...»

«Российский государственный гуманитарный университет Russian State University for the Humanities RSUH/RGGU BULLETIN № 2 (8) Academic Journal Series: Records Management and Archival Studies. Computer Science. Data Protection and Information Security Moscow ВЕСТНИК РГГУ № 2...»

«ДОГОВОР № 81257 на централизованное обслуживание контрольно-кассовой техники и средств вычислительной, пишущей и копировально-множительной техники г. Тула "" марта 2015 г. Общество с ограниченной ответственностью "Автодор-Платные Дороги" (ООО "...»

«Приложение к свидетельству № 66489 Лист № 1 об утверждении типа средств измерений Всего листов 4 ОПИСАНИЕ ТИПА СРЕДСТВА ИЗМЕРЕНИЙ Адаптеры-регистраторы температуры и параметров работы рефрижератора iQFreeze (исполнение СП...»

«Информационные процессы, Том 18, № 3, 2018, стр. 223–231 2018 БЕДРИНЦЕВ, ЧЕПЫЖОВ. c МАТЕМАТИЧЕСКИЕ МОДЕЛИ, ВЫЧИСЛИТЕЛЬНЫЕ МЕТОДЫ Построение ближайшего эллипсоида в задаче описания пространства дизайна с о...»

«ВЕСТНИК ТОМСКОГО ГОСУДАРСТВЕННОГО УНИВЕРСИТЕТА 2011 Управление, вычислительная техника и информатика № 1(14) УДК 681.32 О.В. Климова ЭВОЛЮЦИЯ СПОСОБОВ ОРГАНИЗАЦИИ ВЫЧИСЛЕНИЙ ДЛЯ ОПЕРАЦИЙ ЦИФРОВОЙ ОБРАБОТКИ СИГНАЛОВ: ОТ АЛГОРИТМА К МО...»

«2 Оглавление Введение Глава 1 Комбинированный алгоритм определения аэродинамических характеристик Метод расчета 1.1 Понятие вычислительного эксперимента 1.1.1 Уравнения Рейнольдса, замкнутые модел...»




 
2019 www.mash.dobrota.biz - «Бесплатная электронная библиотека - онлайн публикации»

Материалы этого сайта размещены для ознакомления, все права принадлежат их авторам.
Если Вы не согласны с тем, что Ваш материал размещён на этом сайте, пожалуйста, напишите нам, мы в течении 1-2 рабочих дней удалим его.