12.2015 - том 19 выпуск 4 (PDF)
Статья посвящена логике работы эндокринной системы человека на примере функционирования αи β-клеток поджелудочной железы. Представлены несколько уровней абстракции для данной системы. Рассмотрены взаимодействия αи β-клеток поджелудочной железы между собой, а также с отдельными органами и периферическими тканями организма. В пространстве состояний этой системы выделены «состояния тревоги».
Ключевые слова: эндокринная система, поджелудочная железа, α-клетка, β-клетка, автоматное моделирование в биологии.
В статье дается краткое введение в ансамбли классификаторов в машинном обучении и описывается алгоритм, повышающий качество классификации за счет рекомендации классификаторов объектам. Гипотеза, заложенная в основу алгоритма, состоит в том, что классификатор скорее правильно классифицирует объект, если он правильно предсказал метки соседей этого объекта из обучающей выборки. Автор иллюстрирует принцип алгоритма на простом примере и описывает тестирование на реальных данных..
Построена дискретная модель газообмена СО в легких человека, позволяющая рассчитывать концентрацию СО в выдыхаемом воздухе в зависимости от физиологических и реальных спирометрических параметров. Получены формулы для расчета измеряемой концентрации СО при спонтанном и форсированном режимах дыхания. Сформулирована постановка обратной задачи, в результате решения которой по значениям измеряемой концентрации СО и детальным спирометрическим данным, могут быть рассчитаны диффузионная способность мембраны и альвеолярный объем легких. На основе полученных результатов может быть разработано программное обеспечение для обработки данных приборов функциональной диагностики заболеваний, характеризующихся нарушением проницаемости альвеолярнокапиллярной мембраны, таких как хроническая обструктивная болезнь легких, легочная артериальная гипертензия и др.
Ключевые слова: газообмен, монооксид углерода, диффузионная способность легких, альвеолярный объем, математическое моделирование.
Излагаются основные понятия теории вероятностных автоматов, приводятся новые доказательства классических результатов теории вероятностных автоматов, связанных с эквивалентностью и редукцией вероятностных автоматов, а также излагается и доказывается критерий реализуемости вероятностных реакций конечными вероятностными автоматами общего вида, являющийся усилением соответствующего критерия Р.Г.Бухараева и Х.Хомута ([22], [23]).
Ключевые слова: вероятностные автоматы, вероятностные реакции, случайные функции.
Рассматривается динамическая задача поиска идентичных объектов (ДЗПИО). В работах [1, 2, 3] автор показал, как эту задачу можно решать с помощью многоавтоматного динамического информационного графа (МДИГ) для любого потока запросов. В данной работе показано, что не существует конечного МДИГ с радиусом видимости один, и степенью ветвления два, обрабатывающий произвольный поток запросов.
Ключевые слова: динамические базы данных, поиск по ключу, информационный граф, автомат, потоки запросов.
В работе рассматривается система Фреге в сигнатуре {∧, ∨, ¬}. Для данной системы доказывается нетривиальная нижняя оценка длины минимального вывода.
Ключевые слова: Системы Фреге, длина вывода, нижние оценки.
В работе рассматривается задача расшифровки арифметических сумм монотонных конъюнкций, определенных на n-мерном булевом кубе, в модели точной расшифровки при помощи запросов на значение функции. Предложен алгоритм расшифровки, на основе которого получена верхняя оценка сложности расшифровки. Так же предложен алгоритм ответов на запросы, с помощью которого были получены нижние оценки сложности расшифровки исследуемого класса функций для малого числа монотонных конъюнкций.
Ключевые слова: расшифровка дискретных функций, суммы мототонных конъюнкций.
Предлагается алгоритм восстановления соответствия между двумя N-точечными изображениями в конечномерном действительном евклидовом пространстве, связанными невырожденным аффинным преобразованием. Исследуются инварианты для поиска соответствия за линейное время.
Ключевые слова: отслеживание динамики изображений, аффинное преобразование, многомерные изображения, соответствие особых точек.
В работе рассмотрена задача о возможности построения дерева разводки сигнала с заданными величинами задержек сигнала до листьев дерева. Исследован класс деревьев с функциями задержки сигнала, на которые наложены некоторые ограничения. Предложен алгоритм, решающий данную задачу. Для фиксированного набора функций задержки сигнала время работы алгоритма полиномиально относительно количества листьев дерева.
Ключевые слова: Синтез больших интегральных схем, разводка сигнала, дерево буферов.
В работе рассматривается два вида схем из функциональных элементов. Задача получения нижней оценки сложности реализации булевых функций для одного типа схем сведена к задаче получения верхней оценки для другого типа схем. Получена точная по порядку нижняя оценка сложности укладки графа-двоичного дерева в клеточную структуру.
Ключевые слова: булевы функции, сложность реализации, схемы из функциональных элементов.
09.2015 - том 19 выпуск 3 (PDF)
В статье приводится результат о нахождении минимального количества \[f(n)\] арифметических прогрессий, необходимых для того, чтобы получить в объединении все натуральные числа, не делящиеся на n. Здесь n произвольное натуральное число. При этом исследованы два случая. В первом случае прогрессии могут пересекаться, во втором не могут. В обоих случаях авторам статьи удалось найти точное значение для функции \[f(n)\] и привести конструктивное разбиение этого подмножества натурального ряда на \[f(n)\] арифметических прогрессий.
Ключевые слова: Натуральный ряд, арифметическая прогрессия, декомпозиция.
Авторы вводят расширенную суперпозицию автоматов. Расширенная суперпозиция – это суперпозиции автоматов с фиксированной добавкой булевых функций и задержки. Авторы доказали, алгоритмическая разрешимость выразимости задачи выразимости для групповых автоматных функций Медведева, а также линейных автоматных функций для группы Медведева автоматов, константных автоматов, линейных автоматов.
Ключевые слова: Автомат, суперпозиция, алгоритм.
В работе рассмотрена модель динамической системы, состоящей из графа, к каждой вершине которого приписаны характеристики "благоприятности"и "количества элементов в данной вершине". Каждый элемент стремится попасть в наиболее благоприятную вершину, при этом наличие элементов в вершине есть неблагоприятный фактор. Показано, что такая система всегда имеет предельное состояние, указан класс систем, для которых это предельное состояние зависит только от количества элементов во всём графе, но не от их распределения по вершинам
Ключевые слова: динамические системы, стабилизация, автоматное моделирование миграционных процессов.
В данной статье рассматривается задача подбора вентилятора по заданным параметрам. В качестве основных параметров будут использоваться расход воздуха и давление. Для вентиляторов, характеристика которых не позволяет получить требуемые расход воздуха и давление, будет рассмотрена задача изменения характеристики путем регулирования рабочей частоты.
Ключевые слова: PHP, промышленная вентиляция, частотное регулирование.
В данной статье рассматривается задача расчета характеристик водяного охладителя. По заданным входным параметрам для воздуха (температура входящего воздуха, относительная влажность входящего воздуха и т. д.), теплоносителя (прямая и обратная температура теплоносителя, процентное содержание примеси и т. д.) и самого охладителя (площадь поперечного сечения, площадь теплообмена, количество контуров, расстояние между пластинами и т. д.) требуется вычислить такие величины, как температура воздуха на выходе, относительная влажность воздуха на выходе, полная тепловая мощность батареи, количество конденсата, гидравлическое сопротивление батареи и другие важные физические характеристики.
Ключевые слова: PHP, промышленная вентиляция, теплообменники.
В работе строится математическая модель рекомендательных систем. Приводятся оценки числа типов пользователей в матрице пользователей. Доказывается NPтрудность задач поиска представителя и перечисления матриц пользователей в общем случае и приводится полиномиальный алгоритм поиска представителя матриц пользователей в случае, когда число типов пользователей равно двум.
Ключевые слова: рекомендательные системы, восстановление матриц, пополнение матриц, поиск представителя матриц пользователей, перечисление матриц пользователей, оценка числа типов пользователей, NP-трудность
Приводится пример замкнутого класса автоматов с операцией сурерпозиции, нерасширяющегося до предполного класса.
Ключевые слова: Автомат, суперпозиция, предполный класс.
В данной работе построено неразрешимое суперинтуиционистское пропозициональное исчисление, аксиомы которого содержат только три переменные.
Ключевые слова:Суперинтуиционистское пропозициональное исчисление, неразрешимое исчисление, машина Минского.
В работе рассматривается задача точной расшифровки линейной булевой функции арности n, существенно зависящей от k переменных. Получены точные значения сложности расшифровки для малых k, и верхние оценки для общего случая.
Ключевые слова: точная расшифровка функций, линейные булевые функции.
В статье доказаны критерий прогнозируемости общерегулярных сверхсобытий и критерий прогнозируемости сверхитераций регулярных событий. Приведены алгоритмы построения прогнозирующих автоматов.
Ключевые слова: прогнозирование событий, автоматы, общерегулярные события.
В статье рассматривается класс T тонких языков регулярных языков с не более чем линейной функцией роста. Для этих языков вводится понятие двух размерностей dim и Dim. Приводится результат о том, какие значения принимаются этими величинами на T. Кроме того, находится множество всех реализуемых пар (dimP, DimP), где на P ∈ T.
Ключевые слова: cпектр, тонкие языки, размерность, функция роста.
Ранее автором было доказано, что автоматы с магазинной памятью сохраняют периодические последовательности, и была приведена экспоненциальная от характеристик автомата оценка сверху на максимальную длину периода. Далее для случая, когда алфавит магазина состоит из одного символа, автору удалось понизить общую оценку до квадратичной. В данной работе показано, что в случае, когда в магазине автомата имеется хотя бы два символа, то существенно понизить верхнюю оценку нельзя, так как удалось построить примеры автоматов, которые генерируют последовальности с экспоненциальной длиной периода.
Ключевые слова: автомат с магазинной памятью, детерминированная функция, периодические последовательности.
Получены счетные критериальные систмы замкнутых подклассов в классах линейно-автоматных функций над конечными полями.
Ключевые слова: конечный автомат, линейно-автоматная функция, операции композиции, операции суперпозиции, обратная связь, проблема полноты, замкнутый подкласс, критериальная система, сумматор, задержка.
06.2015 - том 19 выпуск 2 (PDF)
В отличие от СО2 при последовательных задержках дыхания, с возрастающим временем, концентрация монооксида углерода (СО) стремится к некоторому равновесному значению (равновесной концентрации), зависящему от содержания карбоксигемоглобина в крови. Показано, что диффузионная способность легких, рассчитанная по скорости нарастания концентрации СО в альвеолярном объеме, примерно вдвое превышает их общую диффузионную способность, определенную известным «single breath» методом, то есть соответствует диффузионной способности альвеолярно-капиллярной мембраны. На основе математического моделирования процесса газообмена СО в легких человека, получена формула для расчета интегральной измеряемой концентрации СО в выдыхаемом воздухе, с учетом влияния на результаты измерений мертвого (анатомического и приборного) объема. Влияние мертвого объема учитывалось в предположении, что в нем не происходит газообмен, но в выдыхаемый объем из него сначала поступает СО, содержащийся во вдыхаемом воздухе, а за тем выдыхаемая часть альвеолярного СО. При этом учитывалось, что в начале вдоха мертвый объем заполнен конечной порцией альвеолярного воздуха, поступившего в него в результате предыдущего выдоха. Рассмотрены две модели: линейная модель (ЛМ), когда газообмен СО в изменяющемся альвеолярном объеме происходит при постоянном коэффициенте переноса, и модель эластичной оболочки (МЭО), когда коэффициент переноса при дыхании изменяется пропорционально площади поверхности мембраны и обратно пропорционально ее толщине. В результате анализа полученных результатов показано, что расчеты в приближении МЭО более адекватно описывают экспериментальные данные и могут быть использованы для решения обратной задачи, то есть 6 Е. В. Бабарсков расчета диффузионной способности альвеолярно-капиллярной мембраны, альвеолярного объема легких и равновесной концентрации СО, по трем значениям измеряемой концентрации СО при различных режимах дыхания. Таким образом, предлагаемый метод, в отличие от «single breath», позволяет определять указанные важные физиологические параметры без использования тестовых газовых смесей.
Ключевые слова: газообмен, монооксид углерода, диффузионная способность легких, альвеолярный объем, математическое моделирование.
В работе приводится постановка задачи, в рамках решения которой был разработан Язык описания медицинских протоколов (ЯОМП), описывается этот язык, по сути являющийся специализированным языком программирования высокого уровня, а также перечисляются области, в которых ЯОМП оказывается востребованным.
Ключевые слова: специализированный язык программирования высокого уровня, медицинские системы поддержки принятия решений.
В работе будут доказаны достаточные условия континуальности решетки пропозициональных исчислений с операцией подстановки и произвольными схемными операциями вывода. Кроме того будут описаны мощности множеств всех замкнутых классов, предполных и дуально-предполных классов тавтологий в решетке пропозициональных исчислений. Также будут описаны типы критериальных систем для пропозициональных исчислений.
Ключевые слова: решетка пропозициональных исчислений, предполные классы, дуально-предполные классы, критериальные системы.
В данной работе представлены результаты экспериментального анализа свойств абелевых групп в связи с их криптографическими приложениями. В силу сложности вычислительной задачи рассмотрены группы малого порядка.
Ключевые слова: порядок 2-транзитивности, абелева группа, конечная группа, симметричный шифр.
В данной работе рассматриваются модели формы объектов на изображении: бинарная и многоклассовая модели Больцмана. Предлагается новый алгоритм обучения многоклассовой модели формы Больцмана, для применения которого достаточно неполной разметки данных, а именно: бинарной разметки и задания семян, указывающих приближенное расположение частей объектов.
Ключевые слова: модель формы Больцмана, многоклассовая модель формы Больцмана, графические модели, ЕМ-алгоритм.
В данной статье описывается процесс создания вебприложения, реализующего функционал географической карты. Материал делится на две части. В первой части решаются проблемы отрисовки карты на экране, масштабирования карты, перемещения по карте, отображения объектов на карте. Во второй рассматривается задача кластеризации заранее определенного множества объектов, расположенных на карте, методом k-средних и методом расстояний.
Ключевые слова: онлайн-карта, одностраничные приложения, тайлы, php, jQuery, ajax, SQL, метод k-средних, метод расстояний, кластеризация.
В работе рассматриваются одно-переменные итеративные пропозициональные исчисления, представляющие собой конечные множества пропозициональных формул от одной переменной вместе с операцией modus ponens и операцией суперпозиции, заданной множеством операций Мальцева. Для таких исчислений будет проведено сведение проблемы выводимости формул к проблеме вывода слов в линейных канонических системах. В частности, будет показано, что все одно-переменные итеративные пропозициональные исчисления разрешимы.
Ключевые слова: итеративные пропозициональные исчисления, проблема выводимости, линейные канонические системы.
В статье исследуется зависимость между принадлежностью внутренних функций автомата к предполным классам булевых функций с реализацией автоматом словарной функции из того же класса.
Ключевые слова: теория автоматов, предполные классы, словарная функция.
В статье рассматривается две проблемы: проблема вложения допустимых классов алфавитного кодирования и проблема вложения допустимых классов регулярных языков. В первом случае для произвольной пары регулярных языков в общем алфавите необходимо понять, верно ли, что любое алфавитное кодирование, биективное на первом языке, будет биективно и на втором. Во втором случае для произвольной пары алфавитных кодирований в общих входном и выходном алфавитах необходимо понять, верно ли, что произвольный регулярный язык, на котором первое кодирование биективно, будет обладать тем же свойством и при втором кодировании. Показано, что первая проблема алгоритмически разрешима для случая, когда мощность входного алфавита равна двум. Во втором случае показано, что проблема всегда алгоритмически разрешима.
Ключевые слова: алфавитное кодирование, регулярные языки, проблема вложения, допустимые классы.
В работе формулируется и доказывается критерий реализуемости функций на строках вероятностными автоматами Мура с числовым выходом.
Ключевые слова: вероятностные автоматы, автоматы Мура, реакции, случайные функции.
В статье рассматриваются языки в алфавите \[\{a_1, . . . , a_n\}\], в словах которых зафиксирована доля всех последовательных пар \[a_ia_j\] . Эта доля описывается порождающей матрицей языка Θ. Автор назвал такие языки биграммными. Подобным свойством обладают естественные языки. Оказывается, что свойства таких языков быть пустыми, конечными, регулярными, контекстно-свободными или контекстно-зависимыми проверяемы по матрице Θ. В данной работе подробно рассматривается вопрос бесконечных контекстно-свободных языков.
Ключевые слова: биграмма, матрица кратностей биграмм, биграммный язык, контекстно-свободный язык, ориентированный граф, эйлеров граф.
В работе строится обобщение автоматной модели невлияния на случай квантовых автоматов. Доказывается «теорема раскрутки», описывающая достаточные условия безопасности.
Ключевые слова: конечные автоматы, безопасность системы, модель невлияния.
03.2015 - том 19 выпуск 1 (PDF)
В работе описывается технология оценки и мониторинга сложных процессов, разрабатываемая на кафедре МАТИС с начала 90-х годов. Приводится содержательная постановка проблемы информационного мониторинга, описываются технологические и математические аспекты разработки систем информационного мониторинга. Приводится обзор основных результатов.
Ключевые слова: системы оценки и мониторинга, нечеткие множества, оценка нечеткости, поиск в нечетких базах данных.
В статье обобщаются результаты работы [1] на случай kзначных логик. Вводится понятие прогнозирующего автомата, который для каждого поданного ему на вход сверхслова из заданного множества, начиная с некоторого шага в каждый момент t выдает значение входного слова в момент t + 1, то есть предугадывает входное сверхслово. Получен критерий прогнозируемости множеств сверхслов. Приведен наилучший по порядку метод построения прогнозирующего автомата для произвольного прогнозируемого множества сверхслов.
Ключевые слова: конечный автомат, прогнозирующий автомат, прогнозирование событий.
Рассматривается класс P L кусочно-линейных функций вместе с операциями суперпозиции [1]. В настоящей работе показано, что в P L существуют три предполных класса, содержащих класс L всех линейных функций: класс финитных функций, класс непрерывных функций и класс согласованных функций. Получен критерий позволяющий по конечному множеству M ∈ P L проверить полноту множества M ∪ L.
Ключевые слова: класс кусочно-линейных функций, класс финитных функций, класс непрерывных функций, класс согласованных функций, функция Хэвисайда, операции суперпозиции, существенный разврыв.
В работе представлен алгоритм построения множества по заданным параметрам, для которого фактическое число шагов достигает половину верхней оценки числа шагов для данного множества в теореме Новикова. Дополнительно доказывается, что для множества, состоящего из двух точек, фактическое число шагов не более чем \[({D^2}/{2*r^2})+2\].
Ключевые слова: нейронные сети, теорема Новикова.
В работе рассматриваются две задачи — классификация музыкальных файлов по жанрам и классификация изображений. В первом случае требуется реализовать веб-приложение, которое определяет жанры загружаемых в него музыкальных файлов (джаз, классика, диско, метал, блюз). Во втором случае требуется реализовать веб-приложение с возможностью загрузки картинок-эталонов. При последующей загрузке картинок система должна определять, на какой из эталонов наиболее похожа загруженная картинка, и определять ее в соответствующий класс.
Ключевые слова: классификация, музыкальные файлы, mfcc, hog, php.
Ставится задача построения поисковой системы вебстраниц. Основной задачей системы является выдача отсортированного списка результатов, удовлетворяющий заданному поисковому запросу пользователя. Система разделена на несколько частей: кроулер, индексер, ранжирование и поисковый интерфейс. Статья содержит детальное описание каждой из этих частей. Кроме того, по каждой части предоставлена реализация.
Ключевые слова: интернет, поисковая система, кроулер, индексер, ранжирование, HITS, PageRank, TF-IDF.
Рассматриваемая в работе задача состоит в следующем: пусть дано множество слов; требуется для произвольного подслова найти все вхождения этого подслова в слова из этого множества. В данной работе приведена нижняя оценка времени работы алгоритмов, позволяющих осуществлять такой поиск, а также получен порядок объёма памяти для алгоритмов, осуществляющих поиск за минимальное по порядку время.
Ключевые слова: поиск вхождения подслов, нижняя оценка, верхняя оценка.
В данной работе рассматривается решение динамической задачи поиска идентичного объекта для произвольного потока запросов. Сложность параллельной обработки запросов над общей структурой данных заключается в избежании конфликтов, которые возникают при изменении одного и того же участка памяти. При этом считаем, что считывать из одного участка памяти нескольким процессам допустимо. Решение получено с помощью динамического информационного графа [1], [2], который в свою очередь является обобщением информационного графа [3] на случаи вставки и удаления записи.
Ключевые слова: динамические базы данных, информационный граф, конечный автомат, потоки запросов, параллельная обработка данных.
Ранее автор доказал, что автоматные функции с магазинной памятью сохраняют множество периодических последовательностей и привел экспоненциальную оценку удлинения периода при этом. Для автоматов с унарным магазином эту оценку удалось понизить до квадратичной.
Ключевые слова: автомат с магазинной памятью с однобуквенным магазином, детерминированная функция, периодические последовательности.
Доказана алгоритмическая разрешимость задачи выразимости линейных автоматов через произвольную конечную систему автоматов относительно расширенной суперпозиции.
Ключевые слова: автомат, линейный автомат, выразимость, суперпозиция, алгоритмическая разрешимость.
В данной работе рассматривается решение динамической задачи поиска идентичных объектов для произвольного потока запросов с логарифмической сложностью. Сложность параллельной обработки запросов над общей структурой данных заключается в избежании конфликтов, которые возникают при изменении одного и того же участка памяти. При этом считаем, что считывать из одного участка памяти нескольким процессам допустимо. Решение получено с помощью многоавтоматного динамического информационного графа [1].
Ключевые слова: динамические базы данных, информационный граф, автомат, потоки запросов, параллельная обработка данных, сбалансированные деревья.
В работе рассматривается задача расшифровки полиномиальных функций ранжирования. В случае когда функция ранжирования зависит от известной переменной линейно предложен алгоритм расшифровки с точностью до мультипликативного множителя с известной погрешностью, а так же его оценка сложности. Представлен класс функций, для которых существует алгоритм, определяющий для какой из переменных соответствующий моном имеет наименьшую степень и наименьший по модулю старший коэффициент. Дана оценка сложности данного алгоритма.
Ключевые слова: расшифровка функций, функции ранжирования, продвижение веб-сайтов.