Рассматриваются программы, написанные на while-языке, с переменными двух типов безопасности: секретными и открытыми. Статический анализ безопасности информационных потоков программ идентифицирует небезопасные информационные потоки, через которые могут произойти утечки информации. При таком анализе по правилам, предложенным в [6], определяются типы конфиденциальности выражений, операторов и композиции операторов.

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

С помощью средств генерации лексических и синтаксических анализаторов flex и bison [5] был разработан транслятор программ, написанных на while-языке, в код машины MMIX [2].

Мультиклиентский кластер баз данных – это концепция хранилища данных для облачных приложений с мультиклиентской архитектурой. Кластер представляет собой набор серверов реляционных баз данных с единой точкой входа, объединенных в одно целое и работающих под управлением контроллера кластера. Данная система нацелена на использование приложениями, разрабатываемыми в соответствии с парадигмой Software as a Service (SaaS), и позволяет разместить на предоставленных серверах данные большого количества клиентов таким образом, чтобы обеспечить их изоляцию, резервирование и наиболее эффективное использование предоставленных вычислительных мощностей. Одной из наиболее важных задач при разработке системы подобного рода является эффективное распределение данных по серверам, которое определяет степень загруженности отдельных узлов, а также устойчивость системы к сбоям. В работе рассматривается подход к управлению данными, основанный на применении функции оценки эффективности балансировки нагрузки. Данная функция применяется как при первичном размещении клиентов, так и для оптимизации уже имеющегося распределения клиентов. Оптимизация размещения ведется по стандартным схемам стохастических метаэвристик: имитации отжига (simulated annealing) и поиска с запретами (tabu search).

На последовательности M_n,k вложенных релаксаций булева квадратичного многогранника, включающей корневой полуметрический M_n и метрический M_n,3 многогранники, рассматривается задача распознавания целочисленности. Ограничения метрического многогранника отсекают все грани корневого полуметрического многогранника, содержащие только нецелочисленные вершины, что позволяет решить задачу распознавания целочисленности на Mn за полиномиальное время. Для решения задачи распознавания целочисленности на метрическом многограннике исследуется возможность отсечения всех нецелочисленных граней M_n,₃ некоторой релаксацией M_n,k. Координаты точек метрического многогранника представляются в однородном виде в форме трехмерной блочной матрицы. Показывается, что при исследовании вопроса отсечения нецелочисленных граней метрического многогранника достаточно учитывать только ограничения вида неравенств треугольника.  

В данной работе мы изучаем многообразие Фано прямых на полном пересечении грассманиана G(n, 2n) с гиперповерхностями степени d₁, ..., d_s. Путем длины l на таком многообразии мы называем связную кривую, состоящую из l прямых. Главным результатом работы является факт, что при 2 ∑_i (di+1) ≤ [n/2] пространство путей длины n, соединяющих любые две точки полного пересечения, связно и непусто. Для доказательства этого результата мы показываем, что на грассманиане G(n, 2n) пространство путей длины n, соединяющих две общие точки, изоморфно прямому произведению F_n × F_n двух полных пространств n-мерных флагов. Затем строим на F_n ×F_n глобально порожденное векторное расслоение E с выделенным сечением s, таким что нули s задают пространство путей длины n, соединяющих x и y и лежащих в пересечении гиперповерхностей степеней d₁,...,d_k. Используя явное представление расслоения E в виде прямой суммы линейных, мы показываем, что нули общего, а следовательно, и любого сечения E образуют непустое, связное подмногообразие в F_n × F_n.

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

 

Совершенным призмоидом называется выпуклый многогранник P такой, что для каждой его F существует опорная гиперплоскость α, параллельная F, такая что любая вершина многогранника P лежит либо в F, либо в α. Совершенные призмоиды связаны с гипотезой Калаи о том, что у любого выпуклого центрально-симметричного многогранника не менее 3^d граней, а ровно 3^d граней содержат только многогранники Ханнера. Любой многогранник Ханнера является совершенным призмоидом (обратное не верно). Многогранник, который является выпуклой оболочкой некоторого подмоножества вершин единичного куба, называется 0/1-многогранником. Мы докажем, что любой совершенный призмоид аффинно эквивалентен некоторому 0/1-многограннику той же размерности. (Это означает, что любой совершенный призмоид является решетчатым многогранником). Пусть в пространстве R^d задана решетка Λ и многогранник D, вписанный в шар B. Многогранник D называется решетчатым многогранником Делоне, если внутри шара нет точек решетки и D является выпуклой оболочкой множества Λ ∩ ∂B, где ∂B — граница шара B. Мы докажем, что любой совершенный призмоид аффинно эквивалентен некоторому решетчатому многограннику Делоне.

Задача комбинаторной оптимизации называется устойчивой, если ее решение сохраняется при возмущении входных параметров, не превышающих некоторого порогового значения – радиуса устойчивости. В работах [1–3], в предположении об устойчивости входа, построены точные полиномиальные алгоритмы для некоторых NP-трудных задач о разрезах. В настоящей работе показано, как строить ускоренные алгоритмы для достаточно устойчивых полиномиальных задач. Подход иллюстрируется на примере известной задачи о минимальном разрезе (MINCUT). Построен O(n²) точный алгоритм решения n-устойчивой задачи MINCUT. Кроме того, построен полиномиальный алгоритм вычисления радиуса устойчивости задачи MINCUT и получен простой критерий n-устойчивости.

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

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

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

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

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

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

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

 

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

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

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

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

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

Пусть K — произвольный корневой класс групп (это означает, что K содержит хотя бы одну неединичную группу, замкнут относительно взятия подгрупп и прямых произведений конечного числа сомножителей и удовлетворяет условию Грюнберга: если 1 ≤ Z ≤ Y ≤ X — субнормальный ряд группы X такой, что фактор-группы X/Y и Y /Z принадлежат классу K, то в груп- пе X существует нормальная подгруппа T такая, что T ⊆ Z и фактор-группа X/T принадлежит классу K). В данной статье исследуются условия ап- проксимируемости классом K (K-аппроксимируемости) частного случая общей конструкции HNN-расширения, когда связанные подгруппы совпадают. Пусть G = (B, t; t¯¹Ht = H, φ). В случае, когда B ∈ K и подгруппа H нормальна в группе B, автором получено достаточное условие K-аппроксимируемости группы G, которое становится и необходимым, если класс K замкнут относительно факторизации (т. е. взятия гомоморфных образов). Также установлены критерии K-аппроксимируемости группы G при условии, что класс K замкнут относительно факторизации, группа B K-аппроксимируема, а подгруппа H нормальна в группе B и удовлетворяет хотя бы одному из следующих ограничений: группа Aut_G(H) всех автоморфизмов подгруппы H, представляющих собой ограничения на эту подгруппу всевозможных внутренних автоморфизмов группы G, является абелевой; группа Aut_G(H) конечна; автоморфизм φ совпадает с ограничением на подгруппу H некоторого внутреннего автоморфизма группы B; подгруппа H конечна; подгруппа H является бесконечной циклической; подгруппа H имеет конечный ранг Гирша–Зайцева (т. е. обладает конечным субнормальным рядом, каждый фактор которого является либо периодической, либо бесконечной циклической группой). Кроме того, найдено достаточное условие K-аппроксимируемости группы G в случае, когда группа B K-аппроксимируема, а подгруппа H является ее ретрактом (в этом утверждении класс K не обязан быть замкнутым относительно факторизации).

Извлечение процессов (process mining) – новая и активно развивающаяся область исследований, тесно связанная с управлением процессами, формальными моделями процессов и извлечением данных (data mining). Одна из основных задач извлечения процессов – синтез (извлечение) модели процесса на основании анализа журнала событий. Разработан широкий спектр алгоритмов для извлечения, анализа и усовершенствования моделей процессов. Журналы событий реальных систем часто содержат шум различных видов. В данной работе описываются основные причины возникновения шума в журналах событий и изучается влияние шума на эффективность применения основных алгоритмов извлечения процессов. Приводятся экспериментальные результаты применения основных алгоритмов извлечения моделей процессов к искусственным журналам событий с шумами различного типа. Для этого специальным образом сгенерированные журналы событий с шумом обрабатывались с использованием четырех основных методов извлечения процессов. Хотя современные алгоритмы могут справляться с некоторыми типами шума, в большинстве случаев их применение не приводит к получению удовлетворительного результата. Таким образом, существует необходимость в разработке более совершенных подходов для журналов событий с шумом.