Preview

Моделирование и анализ информационных систем

Расширенный поиск
Том 22, № 2 (2015)

Оригинальные статьи 

149-157 692
Аннотация
Пусть π — множество простых чисел. Напомним, что группа G называется аппроксимируемой конечными π-группами, если для любого неединичного эле- мента a группы G существует гомоморфизм группы G на некоторую конечную π-группу, при котором образ элемента a отличен от 1. Группа G называется почти аппроксимируемой конечными π-группами, если она содержит подгруп- пу конечного индекса, аппроксимируемую конечными π-группами. Напомним, что элемент g группы G называется π-полным, если из него в группе G мож- но извлечь корень m-й степени для любого целого положительного π-числа m. Пусть N — нильпотентная группа, и все степенные подгруппы группы N финитно отделимы. Доказано, что группа N аппроксимируема конечными π- группами тогда и только тогда, когда в ней нет π-полных элементов отличных от 1. Пусть теперь множество π не совпадает с множеством Π всех простых чи- сел, и π 0 — дополнение множества π в множестве Π. И пусть T — π 0 -компонента группы N, т. е. множество всех элементов группы N, порядки которых конечны и являются π 0 -числами. Доказано, что следующие три условия равносильны между собой: (1) группа N почти аппроксимируема конечными π-группами; (2) подгруппа T конечна, и фактор-группа N/T аппроксимируема конечными π-группами; (3) подгруппа T конечна и совпадает с множеством всех π-полных элементов группы N.
158-175 870
Аннотация
В статье приводится обзор средств, используемых в объектной СУБД нового типа для повышения эффективности доступа к данным. Описываются особенности объектной СУБД DIM, основанные на использовании отношений классов объектов (как множеств объектов): наследования, включения, взаимодействия и истории – и отношений объектов: наследования, внутреннего наследования, включения, внутреннего включения, взаимодействия и истории. Вводится описание предметной области при помощи объектно-динамической модели данных (OD-модели) и обосновывается полнота СУБД DIM для произвольной OD-модели. Описывается объектный язык запросов ODQL, позволяющий совместить сложность точного описания с простотой использования за счет введения двух уровней запросов. В целях выяснения наиболее эффективного способа обращения к СУБД DIM проводится исследование различных запросных технологий для этой среды, а также разрабатываются и реализуются механизмы для работы пользователей с ней. Для этого разрабатывается комплекс программных средств, необходимых для работы с СУБД DIM. Приводится описание основных концепций разработки ПО «Навигатор DIM», необходимо- го для возможности манипулирования данными в имеющейся БД посредством графиче- ского интерфейса. Рассматривается разработка ПО «Генератор ODQL-запросов», который нужен для упрощения построения запросов к СУБД DIM без необходимости для пользо- вателя в обязательном порядке знать синтаксис нового языка запросов. Рассматриваются пути решения проблемы конвертации данных из существующих СУБД в СУБД DIM. Статья публикуется в авторской редакции.
176-196 641
Аннотация
Магазинные автоматы с независимыми счётчиками (МПНС) объединяют возможности МП-автоматов и сетей Петри. Они были предложены в работах [21, 15] как средство для распознавания языков, порождаемых категориальными грамматиками зависимостей (КГЗ). КГЗ представляют собой классические категориальные грамматики, расширенные ориентированными поляризованными валентностями. Они позволяют выразить как проективные, так и непроективные зависимости между словами предложения. МПНС — это обычный МП-автомат, к которому добавлено конечное число счётчиков. Независимость счётчиков означает, что их содержимое не влияет на выбор очередного действия автомата. В первой части статьи мы сравниваем несколько вариантов определения МПНС и доказываем эквивалентность двух вариантов МПНС: без синтаксических пустых циклов и без семантических пустых циклов. Отмечаем также некоторые связи между МПНС-языками и языками сетей Петри. Мы показываем, что МПНС эквивалентны стек+бэг МП- автоматам (СБМПА), предложенным независимо Сёгаардом (Søgaard), и что СБМПА без пустых циклов распознают в точности КГЗ-языки. Мультимодальные категориальные грамматики зависимостей (ммКГЗ) были введены в [4] как расширения КГЗ, позволяющие управлять пересечениями некоторых зависимостей. Класс ммКГЗ-языков достаточно богат и обладает многими свойствами замкнутости, в частности, он образует абстрактное семейство языков. Во второй части статьи мы расширяем МПНС и определяем МП-автоматы со стеками независимых счётчиков (МПСНС). Это расширение двоякое: (1) каждый счётчик представляет стек натуральных чисел и (2) добавляется функция, которая позволяет уменьшать число на вершине стека счётчика, только если вершины всех связанных с ним счётчиков равны нулю. Наш основной результат утверждает, что МПСНС допускают в точности класс ммКГЗ-языков.
197-208 685
Аннотация
В работе исследуется устойчивость решений начально-краевой задачи для линейной гибридной системы дифференциальных уравнений, моделирующей поворот твердого тела с двумя упругими стержнями, расположенными в одной плоскости. К оси вращения, проходящей через центр масс твердого тела перпендикулярно плоскости расположения стержней, приложен стабилизирующий момент, пропорциональный углу поворота, скорости от угла поворота и интегралу от угла поворота тела, обеспечивающий обратную связь. Для исследования поведения решений начально-краевой задачи предложена методика, позволяющая исключить из гибридной системы дифференциальных уравнений уравнения в частных производных, которые описывают динамику распределенных элементов механической системы. Это позволило построить одно интегродифференциальное уравнение для угла поворота. Его характеристическое уравнение отвечает за устойчивость решений всей системы. В пространстве коэффициентов обратных связей построены области, значения параметров из которых обеспечивают асимптотическую (но не экспоненциальную) устойчивость решений начально-краевой задачи.
209-218 617
Аннотация
Линейное проективное инд-многообразие X называется 1-связным, если любые две точки на нем можно соединить цепочкой проективных прямых l1, l2, ..., lk в X, таких, что li пересекается с li+1. Линейное проективное инд-многообразие X называется 2-связным, если всякая точка из X лежит на проективной прямой в X, и для любых двух прямых l и l 0 из X существует цепочка прямых l = l1, l2, ..., lk = l 0 , такая, что любая пара (li , li+1) содержится в проективной плоскости P 2 , принадлежащей X. В данной работе изучается линейное инд-многообразие X, являющееся полным пересечением в линейном инд-грассманиане G = lim−→G(km, nm). По опре- делению X – это пересечение G с конечным числом инд-гиперповерхностей Yi = lim−→Yi,m, m ≥ 1, фиксированных степеней di , i = 1, ..., l, в пространстве P∞, в которое инд-грассманиан G вложен по Плюккеру. Из работы [17] вытекает, что X 1-связно. Обобщая этот результат, в данной работе мы доказываем, что X 2-связно. Из этого свойства выводится, что всякое векторное расслоение E конечного ранга на X является равномерным, то есть ограничение расслоения E на все проективные прямые в X имеет одинаковый тип расщепления. Мотивация данной работы состоит в распространении теорем типа Барта– Ван де Вена–Тюрина–Сато на случай полных пересечений конечной коразмерности в инд-грассманианах.
219-237 609
Аннотация
Группу G, имеющую в качестве своих подгрупп A и B, называют ABA- группой, если каждый элемент g ∈ G можно представить в виде g = aba1, где a, a1 ∈ A, b ∈ B. Частным случаем факторизаций такого вида является AB-факторизация группы G. Поиск факторизаций группы является фундаментальной математической задачей, решение которой позволит лучше понимать ее строение. Все группы лиева типа обладают факторизацией этого вида. Кроме того, тройные факто- ризации групп автоморфизмов естественным образом возникают при изучении таких структур, как графы, многообразия и геометрии. Целью данной работы является изучение ABA-факторизаций для спорадических групп ранга 3. Для некоторых спорадических групп известны факто- ризации вида G = AB. В то же время для таких спорадических групп ранга 3, как группа МакЛафлина M cL и группа Фишера F i22, факторизации вида G = ABA до настоящего момента были неизвестны. Основным результатом статьи является доказательство существования ABA – факторизаций у спорадических групп M cL и F i22, где A – стабили- затор точки у соответствующей группы подстановок ранга 3. Для группы F i22 имеется два представления ее в качестве группы подстановок ранга 3, причем существование ABA-факторизаций доказано в обоих случаях.
238-247 797
Аннотация
Рассматривается современная архитектура процессоров общего назначения, ее основные компоненты, описывается эволюция, а также подчеркиваются проблемы, препятствующие дальнейшему развитию такой архитектуры. Далее рассмотрены предложенные ранее пути развития процессоров, подчеркиваются их недостатки и предлагается новая архитектура, основанная на беспроводном доступе к кеш-памяти в многоядерных процессорах. В основе предлагаемого решения лежит организация надежного обмена данными между кешем третьего уровня и ядрами процессора через беспроводной канал в терагерцовом диапазоне. Таким образом, масштабируемость системы повышается до десятков и, потенциально, сотен ядер. В то же время, детальный анализ применимости предложенного решения требует точного предсказания количества информации, передаваемой между ядрами и кеш-памятью в процессорах текущего и следующего поколения. В данной работе рассматриваются основные подходы к построению оценки количества передаваемых данных, выделены их достоинства и недостатки. Авторы останавливают свой выбор на непосредственных измерениях количества данных с помощью существующих программных инструментов. Для измерений используется программный инструмент Intel Performance Counter Monitor, позволяющей оценить количе- ство данных, передаваемых между кеш-памятью второго и третьего уровней каждого ядра. В работе рассматриваются три варианта нагрузки на ядро – два искусственных теста и фоновая нагрузка от операционной системы. Для каждого типа нагрузки в работе приведены численные значения количества данных, проходящих по шине между кешем второго и третьего уровней, и показана их зависимость от тактовой частоты работы процессора и количества ядер.
248-258 1108
Аннотация
В данной статье предлагается новый метод кэширования запросов к реляционной базе данных для систем с центральным сервером и распределенными клиентами. Данные загружаются в клиентский кэш, основываясь на запросах, выполненных на сервере БД. Каждому запросу ставится в соответствие таблица – результат выполнения запроса. Эти запросы имеют специальный вид, называемый "универсальный реляционный запрос", основанный на трех базисных операциях реляционной алгеб- ры: селекции, проекции, естественном соединении (natural join). Следует отметить, что такая форма запроса наиболее близка к естественному языку и большинство запросов может быть записано в этом виде. Кроме того, эта форма записи позволяет анализировать корректность запроса, проверяя свойство соединения без потери информации (СБПИ). Последовательные запросы могут исполняться на клиенте, используя кэш, если удастся определить, что результаты искомого запроса полностью содержатся в кэше. Для осуществления такой проверки анализируются области истинности логических ограничений искомого запроса и запросов, результаты которых уже содержатся в кэше. Требуемые операции могут быть проведены аналитически, без необходимости дополнительных запросов к базе банных. Предложенный метод может быть использован для определения недостающих в кэше данных и последующего запроса только на эти данные. Для этого также используются аналитические вычисления, что является принципиальным отличием данной статьи от существующих технологий. Для этой цели в статье представлено четыре теоремы. В первой и третьей теореме получены условия, позволяющие определить наличие необходимых данных, а во второй и четвертой получены условия вычисления данных только с использованием кэша. Проблема актуализации данных не затрагивается в этой статье. Однако она может быть решена путем учета запросов на сервере и обновлении данных при помощи триггеров. Статья публикуется в авторской редакции.
259-277 600
Аннотация
Данная работа посвящена обоснованию возможности использования объектной СУБД DIM и ее механизма взаимодействий в качестве алгоритмически полной реализации объектно-динамической модели. В статье описывается расширение статической OD-модели путем включения в неё множеств алгоритмических процедур, описывающих изменения значений свойств объектов, а также создание, удаление и изменение самих объектов. Для обеспечения DIM возможностями модификации данных, эквивалентной модификациям в OD-модели, вводятся отношения взаимодействий и истории. Для того, чтобы минимизировать зависимость от конструкций описаний алгоритмических процедур OD-модели, которые могут быть записаны на различных языках, выполняется сведение аппарата процедур к универсальной форме – машине Тьюринга. Представляется способ построения машины Тьюринга эквивалентной OD.MT в рамках DIM, использующей набор PL/ODQL проце- дур в качестве аналога управляющего устройства и функциональной таблицы. Описывается принцип формирования ленты памяти такой DIM.MT путём кодирования информации об объектах DIM и их последующего декодирования с ленты обратно в объекты DIM. При этом процесс работы такой машины моделируется с помощью бесконечного цикла вы- полнения PL/ODQL процедур чтения / записи объектов с входной ленты. В заключение приводится доказательство теоремы о полноте представления динамики данных математической модели DIM новой объектной СУБД, основанное на доказанной ранее теореме о статической полноте представления данных в DIM. Статья публикуется в авторской редакции.
278-294 637
Аннотация
Для задачи маршрутизации перемещений инструмента при термической резке деталей из листового материала на машинах с числовым программным управлением (ЧПУ) исследуются вопросы, связанные с построением точных (оптимальных) и эвристических алгоритмов, используемых на этапе математического моделирования элементов маршрутизации последовательного обхода мегаполисов. Пунктами (городами) упомянутых мегаполисов являются точки врезки (пробивки) материала и точки выключения инструмента. В каждом из мегаполисов предусматриваются внутренние работы, состоящие в продвижении к эквидистанте "вырезаемого" контура детали от точки врезки и в продвижении (по завершении резки) от эквидистанты к точке выключения инструмента (имеется в виду рабочий ход). Исследуется задача быстродействия процесса резки, являющаяся специальным случаем обобщенной задачи курьера (задача последовательного обхода мегаполисов с условиями предшествования). Предлагается оптимальная процедура на основе динамического программирования, а также эффективный эвристический алгоритм, реализованный на многоядерной ПЭВМ. Процедура на основе динамического программиро- вания использует специальное расширение основной задачи, при котором допустимость по предшествованию заменяется допустимостью по вычеркиванию (заданий из списка). Условия предшествования используются для снижения сложности вычислений: не осуществляется построение всего массива значений функции Беллмана (последняя заменяется в процедуре системой слоев).
295-303 550
Аннотация

В работе рассматривается задача о числе решетчатых разбиений плоскости на центрально–симметричные полимино заданной площади. Полимино представляет собой связную фигуру на плоскости, составленную из конечного числа единичных квадратов, примыкающих друг к другу по сторонам. В настоящее время активно исследуются различные перечислительные комбинаторные задачи, связанные с полимино. Представляет интерес подсчет числа полимино определенных классов, а также подсчет числа разбиений конечных фигур или плоскости на полимино определенного типа. В частности, разбиение называется решетчатым, если любую фигуру разбиения можно перевести в любую другую фигуру параллельным переносом, переводящим все разбиение в себя. Ранее нами было доказано, что если T(n) – число решетчатых разбиений плоскости на полимино площади n, то справедливы неравенства 2 n−3 + 2[ n−3 2 ] ≤ T(n) ≤ C(n + 1)3 (2, 7)n+1 . В настоящей работе мы получаем аналогичную оценку для числа решетчатых разбиений, дополнительно обладающих центральной симметрией. Пусть Tс(n) – число решетчатых разбиений плоскости на центрально–симметричные полимино площади n, решетка периодов которых является подрешеткой решетки Z 2 . В работе доказано, что C1( √ 2)n ≤ Tс(n) ≤ C2n 2 ( √ 2.68)n . При доказательстве нижней оценки исполь- зована явная конструкция, позволяющая построить требуемое число решетчатых разбиений плоскости. Доказательство верхней оценки основано на критерии существования решетчатого разбиения плоскости на полимино, а также на теории самонепересекающихся блужданий на квадратной решетке.

304-321 1577
Аннотация
Рассматривается задача распространения волны плотности в логистическом уравнении с запаздыванием и диффузией (уравнение Фишера–Колмогорова–Петровского–Пискунова с запаздыванием). Для исследования качественного поведения решений этого уравнения вблизи единичного состояния равновесия было построено уравнение Гинзбурга–Ландау. Численный анализ процесса распространения волны показал, что при достаточно малых значениях запаздывания данное уравнение имеет решения, близкие к решениям стандартного уравнения КПП. Увеличение параметра запаздывания приводит сначала к появлению затухающей колебательной составляющей в пространственном распределении решения. Дальнейший рост данного параметра приводит к разрушению бегущей волны. Это выражается в том, что в окрестности участка начального возмущения сохраняются незатухающие по времени и медленно распространяющиеся по пространству колебания, близкие к решениям соответствующей краевой задачи с периодическими граничными условиями. Наконец, если значение запаздывания достаточно велико, то во всей области распространения волны наблюдаются интенсивные пространственно-временные колебания.


Creative Commons License
Контент доступен под лицензией Creative Commons Attribution 4.0 License.


ISSN 1818-1015 (Print)
ISSN 2313-5417 (Online)