English
06.2016 - том 20 выпуск 2 (PDF)
4 июля 2016 г. исполнилось 80 лет основателю и бессменному главному редактору журнала «Интеллектуальные системы», доктору физико-математических наук, профессору механикоматематического факультета МГУ имени М.В.Ломоносова Валерию Борисовичу Кудрявцеву.
Решение задачи распознавания движений, производимых над объектом, имеет обширное количество приложений в робототехнике, производстве мобильных устройств и мобильных приложений. Она является примером типовой задачи классификации и во многих случаях может быть решена сравнительно простым анализом показаний приборов: акселерометра, гироскопа, магнитометра и других. Однако в случаях, когда графики показаний приборов для различных жестов визуально неотличимы и поверхностный анализ не даёт содержательных результатов, приходится пользоваться методами машинного обучения. В статье рассматривается одна из таких задач и освещается тема общей методологии решения задач классификации.
Ключевые слова: машинное обучение, анализ данных, распознавание жестов, Скрытые Марковские Модели, акселерометр
В работе рассматривается задача создания компьютерной программы, осуществляющей синтаксический анализ юридических текстов на русском языке. На вход эта программа должна принимать текст одного предложения, а на выход должна выдавать построенное по этому предложению синтаксическое дерево, в вершинах которого находятся слова предложения, а рёбрам приписаны синтаксические отношения между словами предложения. В работе приведены правила, позволяющие проводить синтаксический анализ при наличии морфологической информации о словах предложения.
Ключевые слова: синтаксический анализ, синтаксическое дерево, морфологические характеристики, правила.
В статье предлагается архитектура реконфигурируемого на лету аппаратного БЧХ декодера.
Ключевые слова: аппаратная реализация, структурные автоматы, помехоустойчивые коды, коды БЧХ.
В статье приводится результат о нахождении минимального количества f(n) арифметических прогрессий, необходимых для того, чтобы получить в объединении все натуральные числа, не сравнимые по модулю n с 0 и −1. Здесь n произвольное натуральное число. При этом прогрессии могут пересекаться. Приводится точное значение для функции f(n), а также конструктивное разбиение этого подмножества натурального ряда на f(n) арифметических прогрессий.
Ключевые слова: натуральный ряд, арифметическая прогрессия, декомпозиция.
В данной статье рассматривается решение двух задач: одномерная упаковка в одинаковые контейнеры и двумерное замощение прямоугольной области с программной реализацией на языке PHP. Для первой задачи будет получено приближенное решение с помощью эвристического BFD-алгоритма и метода ветвей и границ. Для второй задачи, в силу специфики ограничений на входные данные и способы замощения, будет использован метод ветвей и границ, позволяющий получить точное решение за премлемое время работы.
Ключевые слова: PHP, одномерная упаковка в контейнеры, двумерное замощение.
В статье представлен новый алгоритм верификации отпечатков пальцев на основе поиска максимального пути в графе. Центральной идеей данного подхода является поиск максимального пути в специальным образом сконструированном ациклическом графе. Средняя скорость работы алгоритма верификации составляет 100 сравнений в секунду (Intel Core i5-2500 CPU @3.30 GHz 3.30GHz, 4 Гб ОЗУ, ОС Windows 7).
Ключевые слова: отпечатки пальцев, верификация, минуции, граф, максимальный путь в графе.
В работе рассматривается задача параметроэффективной расшифровки линейных функций k-значной логики в рамках модели точной расшифровки. Получены точные значения сложности расшифровки для малого количества существенных переменных. Получены верхние и нижние оценки для общего случая для двух типов запросов: на значение и на сравнение. При стремлении числа переменных к бесконечности получен порядок сложности расшифровки для обоих типов запросов.
Ключевые слова: точная расшифровка функций, линейные функции k-значной логики, запросы на значение, запросы на сравнение.
Статья состоит из двух частей. В первой части рассматривается проблема проверки однозначности алфавитного декодирования в классе регулярных языков. Приводится ряд из нескольких ограничений на эти языки, выполнение которых позволяет построить новый решающий алгоритм и значительно улучшить его сложность в сравнении со сложностью аналогичного алгоритма из [4]. Вторая часть статьи посвящена проблеме проверки однозначности алфавитного декодирования для класса регулярных языков с полиномиальной функцией роста. Полученные в первой части статьи результаты ложатся в основу алгоритма, решающего рассматриваемую проблему. Разработана техника, позволяющая реализовать для языков с полиномиальной функцией роста те допущения, которые приведены в первой части статьи.
Ключевые слова: регулярные языки, функция полиномиального роста, алфавитное декодирование.
В работе рассматривается задача одновременной минимизации площади, мощности и глубины плоских схем, реализующих частичные булевы операторы. В качестве меры мощности рассматривается максимальный потенциал, он равен максимальному количеству выходов элементов, выдающих единицу на заданном входном наборе схемы, где максимум берётся по всем входным наборам. Показано, что при незначительных ограничениях на область определения оператора существует схема, имеющая оптимальный порядок мощности, площади и глубины. В частности, для всюду определённых операторов с n входами и m выходами порядок мощности равен \(({m\sqrt{2^n}})/({\sqrt{min(m,n)}})\), порядок глубины равен \(max(n,log_2m)\).
Ключевые слова: схемы из функциональных элементов, плоские схемы, клеточные схемы, мощность, глубина, функция Шеннона, верхние оценки, булевы операторы.
В работе предложены новые аналитические формулы для констант фазового равновесия, учитывающие влияние состава флюида и точнее передающее фазовое поведение многокомпонентных растворов. Подход позволяет построить термодинамически согласованную модель удобную для численного моделирования многокомпонентную фильтрации: сокращаются требуемые вычислительные ресурсы, повышается надежность расчетов.
Ключевые слова: константы фазового равновесия, УРС, фазовый переход.
Настоящая работа является продолжением статьи [1] и использует понятия и обозначения, введённые в [1]. В работе излагаются основные понятия теории вероятностных автоматов Мура с числовым выходом и теории вероятностных языков. Приводятся новые доказательства классических результатов теории вероятностных автоматов, связанных с эквивалентностью и редукцией вероятностных автоматов Мура с числовым выходом, а также с регулярностью вероятностных языков.
Ключевые слова: вероятностные автоматы, вероятностные языки.
Множество слов, у которых частоты встречаемости пар соседних букв образуют одну и ту же матрицу это формальный (биграммный) язык. В статье описывается матрицы, соответствующие регулярным и контекстно-свободным биграммным языкам.
Ключевые слова: биграммный язык, матрица частот, соседние буквы, эйлеровы циклы.
В работе изучается как связаны класс автоматов, являющихся «просто» реализуемыми, с классом автоматом, обладающим свойством, что все операторы, задаваемые всевозможными кодированиями, являются различными. Показывается, что указанные классы автоматов имеют не пустое пересечение, и ни один из классов не лежит в другом.
Ключевые слова: автомат, кодирование, свойство максимальности.