Preview

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

Расширенный поиск
Том 23, № 2 (2016)
Скачать выпуск PDF

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

93-118 711
Аннотация

В данной работе проведен анализ подходов к построению хранилищ данных на основе реляционных и NoSQL решений, указаны ограничения реляционного подхода для интеллектуального анализа данных. Выявлено противоречие между представлением данных в реальной предметной области и моделями представления данных в реляционном и NoSQL подходах. Выявленное противоречие связано с темпоральностью не только значений отдельных атрибутов данных, но и изменчивостью состава этих атрибутов, а также структуры связей между ними. Предложена новая логическая модель хранилища данных с динамической структурой. В основу модели положено понятие объекта как своеобразного контейнера для хранения свойств. Каждое свойство объекта включает в себя имя свойства, а также два типа значений свойства – бессылочное и ссылочное, актуальных на заданный момент времени. Ссылочное значение свойства указывает на объект, имя которого интерпретируется как значение этого свойства на заданный момент времени. Дано формальное описание модели с выделением необходимого функционала по манипулированию объектами и их свойствами (селекторы, предикаты, конструкторы), введены необходимые управляющие конструкции. Дано обоснование предложенной модели, названной OP-model, на основе проведения соответствия с логической ER моделью данных. Доказано, что любая ER модель данных может быть реализована в OP-model. В то же время указаны преимущества OP-model, связанные с возможностью изменения связей между сущностями за счет изменения ссылочных значений на определенный момент времени, отмечены потенциальные возможности по масштабируемости хранилища данных за счет уникальной идентификации каждого объекта.

119-136 614
Аннотация

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

137-152 689
Аннотация

Код C на группе G, индуцированный кодом N на подгруппе H, обладает тем свойством, что для декодирования кода C может применяться декодер кода N. Поэтому, если для N имеется эффективный алгоритм декодирования, то по N с помощью конструкции индуцирования можно построить класс кодов с известными алгоритмами декодирования. Эта особенность используется в настоящей работе для построения кодовой криптосистемы с открытым ключом типа Мак-Элиса на индуцированных групповых кодах. Для этой криптосистемы описаны операции шифрования и расшифрования, приводится анализ стойкости к атаке на ключ, а также выделены слабые ключи, в случае использования которых взлом криптосистемы типа Мак-Элиса на индуцированном коде C сводится к взлому этой криптосистемы на коде N. Показано, что практически стойкая криптосистема на индуцированном коде C может быть построена на коде N малой длины. На основе предложенной криптосистемы разработан протокол выработки общего ключа по открытому каналу. 

153-163 572
Аннотация

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

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

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

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

164-172 654
Аннотация

Пусть V – гладкое проективное многообразие над глобальным полем k = κ(C) рациональных функций на гладкой проективной кривой C над конечным полем Fq характеристики p. Предположим, что существует проективный плоский Fq-морфизм π : X → C, где X – гладкое проективное многообразие, общий схемный слой морфизма π изоморфен многообразию V (мы называем морфизм π : X → C арифметической моделью многообразия V ).

М. Артин высказал гипотезу о конечности группы Брауэра Br(X), классифицирующей пучки алгебр Адзумаи на X по модулю подобия. Хорошо известно, что группа Br(X) содержится в когомологической группе Брауэра

Br′(X)=H2(X,G ). et m

По определению, non−p – компонента когомологической группы Брауэра Br′(X) совпадает с прямой суммой l-примарных компонент группы Br′(X) по всем простым числам l, отличным от характеристики p.

Известно, что структура k-многообразия на V задает канонический морфизм групп Br(k) → Br′(V ).

В работе доказана конечность non −p – компоненты когомологической группы Брауэра Br′ (X ) многообразия X при условии, что факторгруппа

[Br′(V )/ Im[Br(k) → Br′(V )]](non −p)

конечная.
В частности, если V – поверхность типа K 3 (другими словами, V – гладкая проективная односвязная поверхность над полем k и канонический класс поверхности V тривиален: Ω2V = OV ), причем характеристика основного поля p > 2, то по теореме Скоробогатова — Зархина фактор-группа [Br′(V )/ Im[Br(k) → Br′(V )]](non −p) конечна, так что в этом случае группы Br′(X)(non −p) и Br(X)(non−p) конечные. 

173-184 835
Аннотация

Статья продолжает серию работ, посвященных подходу к построению и верификации «дискретных» программ логических контроллеров (ПЛК) по LTL-спецификации. Этот подход обеспечивает возможность анализа корректности программ логических контроллеров с помощью метода проверки модели (Model Checking). В рамках подхода в качестве языка спецификации программного поведения используется язык темпоральной логики LTL. Анализ корректности LTL-спецификации относительно программных свойств производится автоматически с помощью программного средства символьной проверки модели Cadence SMV. 

Ранее было показано, каким образом по корректной (проверенной на корректность относительно программных свойств) LTL-спецификации происходит построение ST-, LDи IL-программ. В этой статье описывается технология построения CFC-программ по LTL-спецификации. Язык непрерывных функциональных схем CFC (Continuous Function Chart) представляет собой разновидность языка FBD (Function Block Diagram) — графического языка диаграмм принципиальных схем электронных устройств на микросхемах. В отличие от FBD язык CFC обеспечивает возможность свободного размещения программных компонентов и их соединений на экране. Технология построения CFC-программ демонстрируется на примере. 

Представление ПЛК-программы на языке CFC в рамках подхода к программированию по LTL-спецификации в отличие от представлений на других стандартных языках дает возможность наглядного графического изображения потока данных от входных переменных к выходам ПЛК. Явным образом демонстрируется зависимость и влияние значений одних переменных на значения других переменных во время исполнения программы за один проход рабочего цикла ПЛК. Фактически CFC-программа представляет собой схему потоков данных ПЛК-программы. 

185-194 660
Аннотация

Для каждого λ, 0 < λ < 1 определим случайную величину (симметричную

свертку Бернулли)

где ξn – независимые случайные величины с
P{ξn =0}=P{ξn =1}= 1.

Yλ =(1−λ)ξnλn, n=0

2
Mn =EYλn =nlogλ22logλ(1−λ)+0.5logλ2−0.5eτ(−logλn)1+O(n−0.99),

1k2πikx τ(x)= kα −lnλ e

Основной результат настоящей работы

где функция

k̸=0 является периодической с периодом равным 1,

α(t) = − 1 (1 − λ)2πit(1 − 22πit)π−2πit2−2πitζ(2πit), 2i sh(π2t)

а ζ(z) – дзета-функция Римана.

195-210 859
Аннотация

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

211-227 581
Аннотация

Рассматривается задача маршрутизации перемещений, осложненная ограничениями различных типов (условия предшествования, ограничения на достижимость состояний при каждом перемещении и др.). Допускается многовариантность на этапе перемещений, что естественным образом приводит к задаче о посещении мегаполисов. Стоимости перемещений и работ, выполняемых при посещении мегаполисов, могут зависеть от списка заданий. Данный список может отвечать уже выполненным, либо, напротив, еще не выполненным заданиям. Допускается также, что "текущие" ограничения (на перемещения) могут зависеть от упомянутого списка заданий. Рассматриваемая постановка ориентирована на приложения к задачам атомной энергетики (проблема снижения облучаемости персонала АЭС при выполнении комплекса работ в условиях повышенной радиации) и машиностроения. В последнем случае, связанном с управлением инструментом при листовой резке деталей на машинах с ЧПУ, "текущие" ограничения на перемещения могут быть обусловлены тепловыми допусками по отношению к уже "пройденным" фрагментам листа. В статье приведена схема построения оптимального решения на основе широко понимаемого динамического программирования. Используемый при этом алгоритм реализован на ПЭВМ; результаты его применения иллюстрируются на модельных примерах. 



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


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