12.2014 - том 18 выпуск 4 (PDF)
В данной статье речь пойдёт о решении задачи распознавания нелегального контента в объявлениях на сайте Avito [1], опубликованной на популярном сервисе по решению задач машинного обучения Kaggle [2]. Нами был рассмотрен алгоритм, основанный на преобразовании текстовых полей методами обработки естественных языков [3] и нахождении правил из слов и словосочетаний, идентифицирующих объявление спамом. В работе были изучены основные варианты обработки текстовой информации, а также на основе экспериментов доказано, что сложная обработка, такая как построение биграмм и стемминг, не приводит к увеличению точности.
Ключевые слова: большие данные, анализ текста, обработка естественных языков, интеллектуальный анализ данных, ассоциативные правила.
Для решения ряда задач медицинской диагностики разработаны и исследованы возможностные методы моделирования медицинских объектов и процесса постановки диагноза, основанные на современной теории возможностей [1]. Статья посвящена применению вероятностных и возможностных алгоритмов и программ обучения и распознавания в условиях нечёткого описания медицинских объектов и изменчивости во времени их вероятностных характеристик. Программный комплекс диагностики заболеваний позволяет проводить процедуру обучения и постановки диагноза в диалоговом режиме с участием врача и применяется в данной работе для решения задачи диагностики острого аппендицита.
Ключевые слова: распознавание образов, программный комплекс, задача идентификации, вероятностная модель диагностики, возможностная модель диагностики, гранулирование, алгоритм классификации Кора, острый аппендицит.
В данной работе рассматривается возможность применения многоагентного подхода для расчета энергетического баланса города Калининград и его стран-соседей. Показаны этапы построения многоагентной модели в имитационной среде Anylogic, приведены результаты моделирования. Обсуждаются преимущества и ограничения данного подхода и возможности его применения для решения других задач.
Ключевые слова: энергетика, агент, модель, умная электросеть.
Впервые изложена фундаментальная методология интеллектуальных систем полного разума с интуицией для широкого практического назначения, способных динамически и эффективно самообучаться, самоорганизовываться и быстро принимать решения. Представлены технические решения практической реализации интеллектуальной системы с полным разумом и интуицией.
Ключевые слова: интеллектуальная система, полный разум, интуиция, обучение, распознавание информационных образов.
Предлагается система контроля состояния оператора сложной технической системы, ориентированная на анализ его речевого ответа. Для возможности работы в сильных шумах предусматриваются дополнительные каналы ввода информации, а также специальный сценарий диалога оператора с компьютером.
Ключевые слова: распознавание речи, сильный шум, самосравнение.
Рассмотрен вариант теории возможностей, позволяющий описать договоренность исследовательской группы об общей для них интерпретации некоторых значений возможности и необходимости. Это дает возможность уточнить критерий оптимальности решающего правила в задаче идентификации. Для случая моделирования стохастического объекта описан алгоритм восстановления возможности, принимающей значения в шкале с неподвижными точками, и самих этих точек.
Ключевые слова: возможность, необходимость, договоренность, оптимальное решающее правило.
В данной работе вводятся в рассмотрение итеративные пропозициональные исчисления, представляющие собой конечные множества пропозициональных формул вместе с операцией modus ponens и операцией суперпозиции, заданной множеством операций Мальцева. Для таких исчислений изучается вопрос разрешимости проблемы выразимости. В частности будет показано, что существуют неразрешимые итеративные исчисления. Будет предложен подход описания разрешимых итеративных исчислений, основанный на задании таких исчислений клонами k-значных логик. Кроме того, будет описана решетка клонов трёхзначной логики, порождающих итеративные исчисления, и доказана континуальность множества разрешимых итеративных исчислений.
Ключевые слова: итеративное пропозициональное исчисление, интерпретация, конечная модель, клоны трёхзначной логики.
Технология информационного мониторинга была разработана для анализа сложных, слабоформализованных проблем (процессов) на основе всей доступной информации, построения прогнозов их развития и выработки рекомендаций по управлению их развитием. В настоящей работе технология информационного мониторинга формализуется с использованием классического аппарата дискретной математики — схем функциональных элементов и функций k-значной логики. В этой формализации решаются две ключевые задачи технологии информационного мониторинга — проверка устойчивости модели и задача оптимального распределения ресурсов.
Ключевые слова: информационный мониторинг, оптимальное распределение ресурсов, устойчивость дискретных систем.
В статье рассматриваются задачи генерации спецификаций, характеристик и схем вентиляционных установок в формате dxf, а также генерации собранных установок в 3D-формате. Данный функционал должен быть реализован на веб-технологиях, поскольку будет встраиваться в веб-приложение по расчёту вентиляционного оборудования. В частности, должна быть реализована возможность вращения 3D-модели установки в браузере.
Ключевые слова: генерация чертежей, AutoCAD, openjscad, 3D, dxf, вентиляционные установки.
В статье рассматривается задача разработки конфигуратора промышленного вентиляционного оборудования в виде вебприложения. Мы реализуем веб-интерфейс, позволяющий собрать в браузере любую приточную, вытяжную и приточновытяжную установку простым перетаскиванием секций мышкой или пальцем. Данное решение готово для встраивания в веб-приложение по расчету вентиляционных установок.
Ключевые слова: JavaScript, HTML, CSS, конфигуратор, промышленная вентиляция.
Рассмотрен метод решения проблемы «экспоненциального взрыва» числа состояний конечного автомата, распознающего множество регулярных языков, задаваемых объединением регулярных выражений вида . \[* R_1. * R_2.*\], где \[R_1\] и \[R_2\] — произвольные регулярные выражения. Предложено расширение этого метода на случай объединения произвольного числа регулярных выражений данного вида. Приведены оценки на число состояний автомата при таком изменении в случае алфавита, состоящего из не менее чем трех символов. Показывается, что относительное уменьшение числа состояний может быть произвольным. Анализируется практическая эффективность предложенного метода применительно к регулярным выражениям системы Snort.
Ключевые слова: конечные автоматы, регулярные выражения, системы обнаружения вторжений.
В данной работе изучается функционирование лёгких курящего человека в чистой среде. Выявлена зависимость ухудшения эффективности ресничек от времени, в течение которого в лёгких находился никотин. Также получена временная оценка сложности процесса самоочищения лёгких от никотина.
Ключевые слова: лёгкие, процесс самоочищения, чистая среда, никотин.
В данной работе мы рассмотрим пропозициональные исчисления, формулы которых образованы логическими связками, содержащими классическую импликацию, а правилами вывода выступают операции modus ponens и подстановка. Известно, что в общем случае проблема распознавания выразимости одних исчислений через другие алгоритмически неразрешима. В данной работе будут рассмотрены частные случаи этой проблемы: распознавание аксиоматизации, распознавание расширения и распознавание полноты. В частности будет показано, что проблема распознавания расширения алгоритмически неразрешима для любого исчисления, а проблемы распознавания аксиоматизации и полноты алгоритмически неразрешимы для любого исчисления, из которого выводима формула \[x \rightarrow (y \rightarrow x)\].
Ключевые слова: классическое и интуиционистское исчисления высказываний, импликативное исчисление, разрешимость распознавание аксиоматизации, расширения и полноты, тэг система.
Понятие звездной высоты было впервые введено Эгганом в 1963 г. наряду с понятием циклической сложности конечного автомата. Циклическая сложность автомата связана со звездной высотой принимаемого им языка: звездная высота регулярного языка равна минимальной циклической сложности среди автоматов, принимающих данный язык. Однако проблема нахождения минимального (по отношению к циклической сложности) автомата до сих пор остается открытой. В данной работе рассматривается вопрос о соотношении циклической сложности минимального автомата регулярного языка и его звездной высоты.
Ключевые слова: конечные автоматы, регулярные языки, звездная высота, циклическая сложность, минимальный автомат.
Задача нахождения хроматического числа графов — одна из наиболее привлекательных и сложных задач теории графов. Известно, что для бипланарных графов (графов, реализуемых без пересечений рёбер на двух сторонах плоскости), хроматическое число не меньше 9 и не больше 12. В данной работе показывается, что хроматическое число бипланарных графов без треугольников не меньше 5 и не больше 8.
Ключевые слова: бипланарный граф, хроматическое число, граф без треугольников, граф толщины 2.
В работе продолжается исследование вопросов алгоритмического распознавания свойства обратимости для клеточных автоматов. Построен класс двухмерных бинарных клеточных автоматов с фиксированной локальной функцией переходов c 91 переменной, в котором задача распознавания свойства обратимости является алгоритмически не разрешимой.
Ключевые слова: клеточные автоматы, обратимые клеточные автоматы, машины Тьюринга, проблема остановки.
В статье излагается новое доказательство теоремы Гёделя о неполноте формальных логических систем, основанное на понятиях функционального программирования.
Ключевые слова: математическая логика, неполнота формальных систем, теорема Гёделя, функциональное программирование.
В этой статье предлагается новый подход для работы с вероятностными графическими моделями, основанный на недавно предложенном разложении тензорного поезда (Tensor Train, TT). TT-разложение позволяет хранить тензор в компактном виде и эффективно применять к нему операции линейной алгебры. В данной работе предложен метод для перевода тензоров энергии и ненормированной вероятности марковского случайного поля в TT-формат. Свойства этого формата используются для подсчета нормировочной константы и поиска конфигурации наибольшей вероятности. Предоставлены теоретические гарантии точности оценки нормировочной константы. Предложенные методы сравниваются с аналогами на различных наборах данных.
Ключевые слова: Марковское случайное поле, Тензорный Поезд, вывод, нормировочная константа.
В данной статье исследуется поведение однородных структур с точки зрения сохранения ими различных целочисленных характеристик своих конфигураций. Для характеристики, являющейся суммой значений данной функции на наборах ячеек конфигурации, был построен алгоритм, вычисляющий принадлежность однородной структуры к классу однородных структур, сохраняющих эту характеристику для любой своей конфигурации.
Ключевые слова: однородная структура, конфигурация, характеристика, консервативость, однородное отображение, Фконсервативность.
09.2014 том 18 выпуск 3 (PDF)
Путем анализа базовых определений интеллекта из разных источников ставится вопрос о допустимости применения к конструкциям и материалам термина интеллектуальности.
Ключевые слова: интеллект, познание, рассудок (разум), творчество, знание, абстрагирование, кибернетика, адаптация.
На основе анализа истории научных открытий, а также данных когнитивной психологии и теории искусственного интеллекта установлено, что основными факторами, исключающими алгоритмический характер творческой деятельности в науке, являются вероятностная природа индуктивного вывода, метод проб и ошибок (метод последовательного перебора), фактор случая в научном открытии и теорема Геделя о неполноте. Это позволяет решить 18-ю проблему С. Смейла: каковы пределы интеллекта, как искусственного, так и человека?
Ключевые слова: творческая деятельность, искусственный интеллект, индуктивный вывод, фактор случая в научном открытии, теорема Геделя о неполноте.
В работе рассматривается задача восстановления трехмерного изображения по кодам его плоских проекций. Описан алгоритм, работающий существенного быстрее ранее предложенного в [3]. Приведены результаты компьютерных экспериментов по сравнению скорости работы этих алгоритмов: старого и нового.
Ключевые слова: распознавание образов, аффинные преобразования, геометрическое распознавание, стереозрение.
Рассмотрены компьютерное моделирование вероятностных и возможностных моделей измерительно-вычислительных преобразователей (ИВП) на основе двух вариантов теории возможностей и зависимости качества ИВП как средства измерений от качества измерительного преобразователя. Проведено сравнение качества ИВП для вероятностной и возможностных моделей измерения, а также решена задача редукции измерения для модели измерения, описываемой вторым вариантом теории возможностей.
Ключевые слова: измерительно-вычислительные системы, редукция, качество датчика, второй вариант теории возможностей.
Рассматриваетя задача прогнозирования образования ледовых заторов на северных реках. В случае, когда места заторообразования известны, необходимо прогнозирование мощности явления. Для решения применен комбинаторно-логический подход теории распознавания образов.
Ключевые слова: распознавание образов, тесты.
В традиционной постановке задача семантической сегментации изображений использует обучающую выборку изображений, размеченных попиксельно. Получение такой разметки требует значительных человеческих усилий. Предлагается метод обучения семантической сегментации, позволяющий использовать менее подробную информацию, получение которой на практике требует меньше усилий, например, плотные рамки вокруг объектов на изображении или множество уникальных меток изображения.
Ключевые слова: машинное обучение, структурный метод опорных векторов, функция потерь, семантическая сегментация изображений.
В работе исследуются алгебры замкнутых термов, операции которых задаются формулами первого порядка с единственным предикатом равенства. Для таких алгебр показано, что в общем случае проблема выводимости термов алгоритмически неразрешима. При рассмотрении частных случаев проблемы выводимости строится соответствие Галуа между операциями и конечными автоматами над термами. На его основе доказаны достаточные условия алгоритмической разрешимости частных случаев проблемы выводимости термов и проблемы выразимости операций над термами.
Ключевые слова: алгебры термов, проблема выводимости, проблема выразимости, автоматы над термами, соответствие Галуа.
В работе исследуются алгоритмы поиска, используемые в фоновом режиме, и предлагается математическая модель этих алгоритмов, опирающаяся на понятие информационного графа. В работе также предлагается фоновый алгоритм решения двумерной задачи о доминировании с линейными затратами по памяти и константным в среднем временем поиска. Для сравнения отметим, что нефоновый алгоритм, среднее время поиска которого равно константе плюс среднее время перечисления ответа, требует квадратичных затрат по памяти.x
Ключевые слова: информационно-графовая модель, задача о доминировании, фоновый поиск.
В работе представлен вывод оценки числа способов разбиений вершин единичного куба полиномиально задаваемой поверхностью.
Ключевые слова: булевская функция, полиномиальная отделимость.
Задача анализа тональности играет важную роль в обработке естественного языка. Рассматривается задача классификации русскоязычного текста на два класса в зависимости от его эмоциональной окраски: положительный и отрицательный. В качестве классификатора используется наивный байесовский классификатор. Используются различные методы для отбора признаков, производится сравнение полученных результатов с результатами классификации англоязычного текста. Достигнута точность 78.4% на заданном тестовом наборе данных.
Ключевые слова: анализ тональности, наивный байесовский классификатор, выбор признаков.
В работе рассматривается задача построения дерева разводки сигнала с заданными величинами задержек сигнала до листьев дерева. Предложен алгоритм, который для заданного мультимножества натуральных чисел за линейное время строит дерево с величинами задержек до листьев дерева, совпадающими с элементами данного мультимножества, или говорит, что такое дерево построить нельзя.
Ключевые слова: синтез больших интегральных схем, разводка сигнала, дерево буферов.
Ранее была решена проблема полноты для класса линейноавтоматных функций над полем GF(2) с операциями композиции. В настоящей работе этот результат обобщен на класс линейно-автоматных функций над GF(p) для простого p. В рассматриваемом классе найдены все предполные подклассы.
Ключевые слова: конечный автомат, линейный автомат, линейно-автоматная функция, операции композиции, проблема полноты, критерий полноты, предполные классы, сумматор, задержка.
Рассматривается общая проблема построения различных типов схемных управляющих систем и некоторые функционалы их сложности. Особое внимание уделяется сложности моделирования схем на компьютере. Предложен общий метод моделирования схем, реализующих булевы функции.
Ключевые слова: схемы из функциональных элементов, контактные схемы, сложность управляющих систем, моделирование.
06.2014 - том 18 выпуск 2 (PDF)
В статье рассказывается о кафедре МаТИС, об основных направлениях ее деятельности, решаемых задачах и достижениях.
Ключевые слова: математическая теория интеллектуальных систем.
Рассмотрены методы моделирования неполного и недостоверного знания модели \[M(x)\] объекта, зависящей от неизвестного x ∈ X, выраженного в форме субъективных суждений исследователя. Математическая модель субъективных суждений определена как неопределенный элемент xe, канонический для пространства \[(X,\rho(X),Pl^\widetilde{x})\] с мерами правдоподобия и доверия, который характеризует субъективные суждения исследователя об истинности каждого значения x ∈ X значениями правдоподобия \[Pl^\widetilde{x}\] равенства \[\widetilde{x} = x\] и доверия \[Bel^\widetilde{x} = x\] неравенства \[\widetilde{x} \neq x\]. Приведены примеры исследования неопределенных моделей измерительно-вычислительного преобразователя, радиозондирования ионосферы и маятника Максвелла.
Ключевые слова: субъективные суждения, правдоподобие, доверие, интеграл, мера, случайный неопределенный элемент, интеллектуальный диалог, измерительно-вычислительные системы.
В данной работе ставится задача анализа безопасности информационной сети. Применяется теоретико-автоматный подход для моделирования поведения злоумышленника, вводится отношение частичного порядка на множестве состояний — векторов, значение координат которых отражает уровень прав доступа к соответствующим службам на анализируемых узлах. Рассматривается понятие трассы атаки и изучаются соответствующие количественные характеристики. Задача обнаружения уязвимостей сети переформулируется в терминах нахождения состояний, достижимых из некоторого начального состояния, и описания возможных путей до них. На основе построенной математической модели предложены алгоритмы, решающие поставленные задачи, и их возможные модификации. Также рассмотрены подходы к уменьшению построенного автомата.
Ключевые слова: компьютерная безопасность, оценка защищенности, конечные автоматы, трассы атак.
В работе показывается, как плоская среда «порождает» образы, и как в этом случае представляется распознавание образов. Доказываются некоторые утверждения о свойствах кодов изображений.
Ключевые слова: распознавание образов, зрительные образы, математическое моделирование в биологии, зрение роботов.
Доказана система соотношений для формализмов знаний, составляющх фрагмент семейства признанных подходов к форматам описания знаний в интеллектуальных системах.
Ключевые слова: формализм представления знаний, семантическая структура, алгебраическая структура, семантическое вложение.
В работе рассматривается задача автоматического распознавания текстов законов, касающихся заполнения форм отчётности. Эта задача состоит в следующем: создать компьютерную программу, которая принимала бы на вход тексты законов, а на выходе выдавала бы другую программу, осуществляющую заполнение формы в соответствии с этими законами. Предложен метод решения этой задачи, основанный на технологии компьютерного моделирования логических процессов.
Ключевые слова: семантический анализ текстов, нормативно-правовые акты, компьютерное моделирование логических процессов.
В ряде работ изучается взаимосвязь таких важных, с точки зрения теоретической криптографии, свойств булевых функций как нелинейности различных порядков (расстояние функции до полиномов степени не выше фиксированной) и алгебраическая иммунность. Одним из основных направлений исследований является вопрос получения нижних оценок на нелинейность фиксированного порядка через значение алгебраической иммунности функции. В частности, были получены точные оценки на нелинейности первого и второго порядков. В данной работе мы докажем новую оценку на нелинейность произвольного порядка через значение алгебраической иммунности, более сильную чем предыдущие аналогичные результаты разных авторов.
Ключевые слова: булева функция, алгебраическая иммунность, степень булевой функции, нелинейность, нелинейность высокого порядка, код Риде-Маллера.
В настоящей работе рассматривается задача аппроксимации временных рядов ломаными кратчайшей длины с заданной точностью. Временной ряд интерпретируется последовательностью точек плоскости, а задача аппроксимации этой последовательности ломаной приводит к поиску кратчайшего пути между двумя отрезками. Получен алгоритм, решающий поставленную задачу с использованием построения графа видимости и алгоритма Дейкстры.
Ключевые слова: аппроксимация точек на плоскости, граф видимости, плоскость с многоугольными препятствиями, кратчайший путь, алгоритм Дейкстры.
Рассматривается реализация CRM-системы для платформы Android. Система позволяет управлять клиентами, контактными лицами и контактами. В статье описан интерфейс данной системы и его реализация, а также реализация синхронизации данных с серверной частью.
Ключевые слова: Android, CRM, синхронизация.
Рассматривается задача синхронизации данных и кода между серверами, физически расположенными в различных местах. Реализована система репликации базы данных, настроена система контроля версий, а также система репликации содержимого каталогов.
Ключевые слова: система контроля версий, репликация баз данных, git, unison.
Работа посвящена изложению результатов компьютерного моделирования логических процессов в логической системе «Искра». Исследовались вопросы, связанные с обучением компьютерных решателей задач и автоматическим синтезом приемов.
Ключевые слова: интеллектуальная система, самообучение, логическая система, компьютерный решатель задач, автоматический синтез приемов.
По заданному натуральному числу N в базисе из линейных функций, логарифма, экспоненты, функции сигнум и функции извлечения кадратного корня строится схема проверки аффинной эквивалентности двух плоских N-точечных изображений. Нелинейная глубина схем не зависит от N. Таким образом, время обработки изображений полученными схемами не зависит от размера задачи.
Ключевые слова: особые точки изображений, динамика особых точек, видеоряд, аффинное преобразование плоскости, проверка аффинной эквивалентности изображений, нелинейная глубина схема.
В статье рассматривается мощность плоских схем, моделирующих СБИС. Плоская схема является укладкой схемы из функциональных элементов на двумерную целочисленную сетку. Все оценки мощности для плоских схем верны и для более сложных моделей СБИС. Рассматриваемая мера мощности моделирует электрическую мощность, выделяемую как на логических элементах, так и на проводах схемы. При этом предполагается, что электрическая мощность, потребляемая проводом единичной длины соизмерима с мощностью, потребляемой одним логическими элементом. Получена нижняя оценка \[(m\sqrt{|D|})/(\sqrt{min(m,log|D|)}\] средней мощности почти всех частичных булевых операторов с областью определения D и m выходами. Также получены нижние оценки мощности при некоторых ограничениях на расположение выходов схемы.
Ключевые слова: схемы из функциональных элементов, модель СБИС, плоские схемы, мощность схем, функция Шеннона, нижние оценки, частичные булевы операторы.
В данной работе обобщается конструкция параметрического семейства латинских квадратов над прямым произведением абелевых групп, предложенная ранее в работе [2], на многомерный случай с целью увеличения количества параметров. Дается критерий реализуемости данной конструкции. Также рассмотрен вопрос о связи правильности и циклов в графе существенной зависимости для функций над кольцами вычетов.
Ключевые слова: правильное семейство функций, латинские квадраты, параметрическое семейство латинских квадратов, критерий для многомерного латинского квадрата, граф существенной зависимости семейства функций, связь правильности и циклов в графе существенной зависимости.
В диссертации автора «Об оптимизации структурной реализации нейронных сетей» нейронные схемы рассматривались над полем действительных чисел. Большинство результатов, относящихся к схемам Мак-Каллока – Питтса, дословно переносится на нейронные схемы над полем рациональных чисел, однако для доказательства одной из теорем существенно использовалось понятие трансцендентного числа. Тем не менее результат теоремы для нейронных схем над полем рациональных чисел сохраняется. Новое доказательство приводится в данной работе.
Ключевые слова: нейронные схемы, функция Шеннона.
В данной работе изучаются квазициклические низкоплотностные коды. Приводится верхняя оценка на минимальное расстояние, которая зависит от минимального и максимального количества единиц в столбцах проверочной матрицы данного кода.
Ключевые слова: минимальное расстояние, квазициклический низкоплотностный код.
03.2014 - том 18 выпуск 1 (PDF)
Излагается методология построения феноменологического словаря теории интеллектуальных систем, основанная на постнеклассических информационно-эволюционном подходе к системному анализу и моделированию объективной реальности, атрибутивно-ингредиентной концепции информации и концепции управляемой эволюции естественного языка. В качестве терминологического базиса предлагаемой методологии определены понятия «информация», «эволюция» и «моделирование».
Ключевые слова: информация, моделирование, мышление, знания, систем интеллектуальных теория, феноменология, филогенезис, эволюция.
В статье рассмотрены основные способы реализации поиска по регулярным выражениям, используемым в сетевых системах обнаружения вторжений для исследования содержимого сетевых пакетов. Представлены как простейшие недетерминированные и детерминированные конечные автоматы, так и различные их модификации, показывающие более высокую производительность и (или) использующие меньшие объемы оперативной памяти.
Ключевые слова: конечные автоматы, регулярные выражения, сетевые системы обнаружения вторжений, исследование содержимого сетевых пакетов.
В работе исследуются свойства операции умножения с параметром, существенно использующейся в криптографических стандартах республики Узбекистан. Изучается структура группы обратимых элементов; устанавливается сложность операции дискретного логарифмирования.x
Ключевые слова: мультипликативная группа, криптография, электронная подпись, дискретный логарифм.
Рассматривается задача разработки современной системы онлайн-сопровождения научно-образовательных процессов ДвинемНауку (http://dvinemnauku.ru). Система позволяет сопровождать научно-образовательные процессы онлайнотображениями этих процессов. Система разделена на две части: на серверную и на клиентскую. Серверная часть используется для хранения, обработки и выдачи данных. Клиентская часть используется для представления и сбора данных. В рамках работы реализована подсистема управления процессами, событиями и комментариями, спроектирована архитектура системы и структура базы данных, а также реализованы вспомогательные модули.
Ключевые слова: научно-образовательный процесс, проектирование баз данных, научное событие, ДвинемНауку, вебприложение.
Рассматривается задача разработки сайта для ознакомления с материалами семинаров, проводимых ректором МГУ В. А. Садовничим. Создан сайт http://sa.msu.ru, позволяющий выкладывать для общественности результаты семинаров: статьи, доклады и фотографии. Архитектура сайта подразумевает использование уже готовой системы онлайн-сопровождения научно-образовательных процессов ДвинемНауку http://dvinemnauku.ru для хранения и ведения связанных с семинарами событий.
Ключевые слова: сайт, ДвинемНауку, база данных, программный интерфейс, материалы семинара.
В данной работе рассматривается математическая модель динамических баз данных, которая обрабатывает три типа запросов: поиск, вставка и удаление. Она построена на взаимодействие информационного графа [1] и конечного детерминированного автомата [2]. Модель позволяет решать динамические задачи поиска и оценивать сложность их решения. В качестве примера, иллюстрирующего работу модели, рассмотрена и решена известная динамическая задача поиска идентичных объектов.
Ключевые слова: динамические базы данных, математическое моделирование, информационный граф.
В работе показано, что правильность семейства функций эквивалентна правильности семейств, возникающих на сильных компонентах и блоках компонент графа существенной зависимости семейства функций. Решается задача упрощения семейства, граф существенной зависимости которого содержит «тривиальный» путь. При этом упрощении семейства свойство правильности не меняется. Полученные результаты справедливы для семейств функций k-значной логики, где \[k \geq 2\].
Ключевые слова: правильные семейства функций, латинские квадраты.
В работе рассматривается задача конструирования движущихся изображений клеточным автоматом на экране, представляющем из себя конечную либо бесконечную полосы. Найдены алгоритмы построения движущихся изображений для некоторых классов изображений. Показано, что для любого бесконечного экрана существует закон движения, не реализуемый на этом экране.
Ключевые слова: клеточный автомат, бесконечный экран, универсальный экран, конструирование движущихся изображений, автономное движение, скорость движения.
В рамках дискретно-геометрического подхода к распознаванию образов представлен алгоритм, вычисляющий по коду все классы а’-эквивалентных изображений с данным кодом. Алгоритм применим к изображениям произвольной размерности \[n \geq 2\], причем его временная сложность линейно зависит от числа точек в изображении.
Ключевые слова: распознавание образов, код изображения, алгоритм восстановления изображения, временная сложность.
Естественные языки обладают свойством постоянной частоты встречаемости букв и пар букв. В статье изучены регулярные языки с этим свойством.
Ключевые слова: естественный язык, регулярный язык, цепь Маркова, марковский язык.
В работе изучаются спектры класса тонких языков. Дается классификация языков по их спектральным свойствам. Для спектра тонкого языка определяется два понятия размерности. Оказывается, что для произвольного натурального числа n можно привести пример спектра, у которого и первая, и вторая размерности равны n. Рассматривается вопрос о том, какие значения пар этих размерностей в совокупности бывают у спектров тонких языков. Для каждой пары m, n натуральных чисел таких, что \[m = n = 1\] или \[2 \leq m \leq m\] удается построить тонкий язык со спектром, у которого первая размерность равна m, а вторая равна n. Используемая при этом техника нетривиальна и позволяет поставить и решить сразу несколько теоретико-числовых задач, которые сами по себе представляют определенный интерес.
Ключевые слова: тонкие языки, регулярные выражения, алфавитное кодирование.
В работе доказывается свойство сохранения периодических последовательностей автоматами с магазинной памятью и исследуются оценки на длину периода выходящей последовательности в зависимости от периода входящей и характеристик автомата.
Ключевые слова: автомат с магазинной памятью, детерминированная функция, периодические последовательности.
Найдены все А-предполные подклассы в классах линейноавтоматных функций над конечными полями. Доказана алгоритмическая разрешимость проверки А-полноты конечных подмножеств в рассматриваемых классах.
Ключевые слова: конечный автомат, линейный автомат, линейно-автоматная функция, оператор А-замыкания, проблема А-полноты, критерий полноты, А-предполный класс, сумматор, задержка.
В статье уточнена верхняя оценка слоистости произвольных полных систем булевых функций. Также приведен ответ на вопрос, верно ли, что слоистость любой полной системы в классе функций k-значной логики конечна. Введено понятие слоистости замкнутых классов фунций k-значной логики и приведены оценки слоистости всех замкнутых классов булевых функций.
Ключевые слова: булева функция, функция k-значной логики, полная система, сложность, слоистость, замкнутый класс.