English language
Содержание журнала "Интеллектуальные системы"
Том 14, выпуск 1-4, 2010 г.
Часть 1. Общие проблемы теории интеллектуальных систем
- Баранович А.Е.. О систематизации аксиоматического аппарата предметной области «Искусственный интеллект».
C позиций информационно-эволюционного подхода рассматриваются вопросы систематизации аксиоматического аппарата предметной области науки, именуемой в настоящее время, <<искусственным интеллектом>> (ИИ). В контекстах научного и обыденного сознания речь идет о том, что есть <<естественно>>, а что <<неестественно>> и <<искусственно>> в ИИ. Результаты проведенного анализа позволяют внести существенные изменения в феноменологию его развития.
Ключевые слова: "Большая история"; информатизация; информационно-эволюционный подход; интеллект естественный, искусственный; интеллект вычислительный, компьютерный, технический; моделирование; системы антропогенные, антропоморфные, интеллектуальные, материальные
Часть 2. Специальные вопросы теории интеллектуальных систем
- Козлов В.Н.. Доказательность и эвристика при распознавании визуальных образов.
В статье в краткой форме излагаются основные идеи, положенные в основу дискретно-геометрического подхода к распознаванию зрительных образов, и на содержательном уровне описываются полученные результаты. Приводятся некоторые соображения о роли эвристики в распознавании визуальных образов.
Ключевые слова: распознавание образов, зрительные образы, 3D-реконструкция изображений - Маслобоев А.В., Ломов П.А.. Использование общесистемного тезауруса как основы интеллектуального пользовательского интерфейса системы распределенного семантического поиска.
В статье рассмотрена проблема использования общесистемного расширяемого тезауруса как основы интеллектуального интерфейса информационной системы распределенного семантического поиска. Предложено расширенное элементами онтологии DOLCE и метасвойствами определение разделяемого тезауруса. Разработана технология формирования запроса на основе правил определения возможных вариантов его усложнения, что позволяет использовать тезаурус в качестве основы для разработки интеллектуального пользовательского интерфейса.
Ключевые слова: информационная система, онтология, тезаурус, семантическая интеграция информации, формирование запроса, интеллектуальный пользовательский интерфейс - Адылова Л.Р.. О распознавании лиц.
Изучаются методы геометрического распознавания расовой принадлежности лица человека по фотографии. Находятся геометрические инварианты лица, позволяющие отнести его к одному из трех расовых кластеров: монголоидному, европеоидному, негроидному. Таких инвариантов в виде точек лица при определенным образом заданной системе координат оказалось 11. По этим точкам строился код, к которому затем применялись различные методы для распознавания лиц.
Ключевые слова: распознавание, инварианты, геометрические методы, раса, обучение - Боков Г.В.. Принцип максимума Понтрягина в задаче с временным запаздыванием.
В работе формулируется задача оптимального управления с постоянным запаздыванием по времени в фазовой переменной и в переменной управления, для которой доказывается теорема, дающая необходимые условия оптимальности решения. В конце работы приводиться обобщение данной задачи на случай бесконечного промежутка времени.
Ключевые слова: Теория оптимального управления, дифференциальные уравнения с временным запаздыванием, необходимые условия оптимальности, принцип максимума, конечный и бесконечный временной горизонт - Газарян В.А. Матвеева Т.В. Чехонина Ю.Г. Шаховская А.К.. О теоретико-возможностных методах анализа эффективности лечения.
В [1] показано, что для решения многих задач медицинской диагностики естественно применение не вероятностной, а возможностной модели анализа и интерпретации данных [2]. Построена возможностная модель симптомов заболевания, возможностная модель постановки медицинского диагноза. Целью данной работы является разработка возможностных методов анализа эффективности лечения пациентов, страдающих хроническим панкреатитом, в частности, – метода оценивания эффекта, производимого тем или иным препаратом на состояние и на биохимические показатели крови таких пациентов.
Ключевые слова: теория возможностей, проверка статистических гипотез, t-критерий, эффективность лечения, хронический панкреатит - Галатенко А.В.. О восстановлении разбиения безопасности.
В работе рассматривается автоматная система, часть состояний которой объявляется безопасной. Исследуется сложность восстановления разбиения множества состояний для безопасных и эпсилон-безопасных языков, введенных в работе ``Автоматные модели защищенных компьютерных систем''.
Ключевые слова: Конечный автомат, автоматная модель, кратный условный эксперимент - Гасанов Э.Э., Колесниченко А.В.. Предикатная эквивалентность формул алгебры логики.
В работе исследуется предикатная эквивалентность формул, вводимая с помощью множества предикатов P и множества перестановок M. Множества P и M согласованы, если соответствующая им предикатная эквивалентность совпадает с обычной эквивалентностью формул. Доказывается критерий согласованности множеств. Предложен алгоритм построения согласованных множеств предикатов. Приводятся серии примеров взаимно согласованных множеств P и M с разными соотношениями сложностных характеристик.
Ключевые слова: алгебра логики, логика предикатов, аналитическое описание геометрических фигур - Докучаева Т.В.. Процесс самоочищения легких с очаговыми поражениями в чистой среде.
В данной работе построена модель функционирования легких с патологиями. Рассмотрена функция самоочищения легких от вещества, поступающего из окружающей среды или образующегося в них в процессе жизнедеятельности, в чистой среде. Механизм транспортировки вещества в здоровых легких обобщен на случай патологий пропускной способности и эффективности ресничкового механизма. Получено описание временной сложности процесса самоочищения легких при очаговом поражении пропускной способности ресничек и(или) их эффективности в чистой среде.
Ключевые слова: биоинформатика, древовидные системы, легкие, ресничковый механизм, самоочищение, процесс транспортировки - Колесникова С.И.. Свойства корректной модификации метода парных сравнений.
Рассматриваются свойства функции относительного сходства как функции скаляризации критериев, применение которой разрешает нежелательные особенности известного метода парных сравнений Т. Саати (МАИ), связанные с применением линейной свертки и единичной нормализации при получении весовых коэффициентов альтернатив. Рассмотрен пример применения модификации МАИ.
Ключевые слова: метод анализа иерархий, весовые коэффициенты альтернатив, интеллектуальная система, тестовое распознавание образов, качество принятия решения - Лёвин В.Ю.. О повышении криптостойкости однонаправленных хеш-функций.
В статье приводится конструктивные предложения решения задачи обеспечения подлинности и достоверности цифровых документов с использованием однонаправленных хеш-функций. Численно оценена стойкость однонаправленных хеш-функций при различных видах их взлома. Предложен ряд алгоритмов позволяющих серьезно повысить криптостойкость хеш-функций без переделки их внутренных алгоритмов. Среди предложенных методов по повышению криптостойкости выбран лучший по скорости и качеству. Показано, что метод суффиксной суперпозиции, предложенный Б. Шнаером, не годится для использования в этих целях. Предложенные в статье методы могут быть использованы для улучшения большинства однонаправленных хеш-функций, таких как, MD4, MD5, RIPEMD, SHA, ГОСТ 34 11-94.
Ключевые слова: однонаправленные хеш-функции, метод Шнайера, целостность, информационная безопасность - Пархоменко Д.В.. Моделирование вероятностными источниками.
Скрытая Марковская Модель (СММ) – это марковская цепь, обладающая видимым пользователю «выходом». В каждом состоянии, в соответствие с зависящим от состояния законом распределения, СММ выдает выходной символ и переходит в другое состояние как марковская цепь. В случае конечного выходного алфавита СММ называют вероятностным источником. В статье описано применение аппарата скрытых марковских моделей и рассказано об актуальных инженерных задачах, где они используются.
Ключевые слова: скрытые марковские модели, распознавание образов, вероятностный источник - Петюшко А.А.. О марковских случайных полях и их связи с цепями Маркова.
В данной работе рассматриваются марковские и скрытые марковские случайные поля. Устанавливаются взаимосвязи между марковскими случайными полями и цепями Маркова, а также между скрытыми марковскими полями и скрытыми марковскими моделями посредством введенных порожденных случайных величин.
Ключевые слова: Марковское случайное поле, скрытое марковское случайное поле, марковская цепь, скрытая марковская модель - Пивоваров А.П.. Моделирование вычислительных задач информационного поиска.
Работа посвящена определению и сравнению двух моделей для описания алгоритмов решения вычислительных задач информационного поиска. Первая модель почти совпадает с понятием информационного графа, вторая получается использованием для вычислений автоматных функций. Исследование производится на примере модельной задачи –- вычислении размера ответа задачи одномерного интервального поиска. Обосновано преимущество использования автоматных функций для вычислительных задач информационного поиска.
Ключевые слова: вычислительная задача информационного поиска, информационный граф, вычислительный информационный граф, одномерный интервальный поиск, моделирование поиска, характеристики алгоритмов поиска - Рыков Д.О.. Об алгоритмах проверки правильности семейств функций.
В работе изучается вопрос проверки правильности семейств функций. Построен алгоритм проверки правильности, учитывающий информацию о графе семейства. Сложность приведенного алгоритма зависит от порядков сильных компонент графа. Построен алгоритм проверки правильности семейств монотонных функций. В основе алгоритма лежат два свойства правильных семейств монотонных функций: наличие константы и функциональная замкнутость класса монотонных функций в $P_2$. Сложность алгоритма значительно меньше сложности стандартных алгоритмов проверки правильности.
Ключевые слова: Правильное семейство функций, алгоритм проверки правильности семейств функций, граф существенной зависимости семейства функций, семейство монотонных функций, критерий правильности семейства функций
Часть 3. Математические модели
- Блохина Г.Н., Кудрявцев В.В.. О спектрах классов Поста булевских функций.
В работе изучаются длины базисов классов Поста булевских функций. Множество всех длин базисов такого класса называется его спектром. Основным результатом работы является нахождение всех спектров классов Поста.
Ключевые слова: булевская функция, спектр, базис, классы Поста - Болонкин М.В.. О распознавании вирусов в регулярных текстах.
Исследуются свойства регулярных выражений и их тождественных преобразований для распознавания полиморфных вирусов. Определена модель зараженности, сильной и слабой зараженности программы вирусом, исследованы некоторые классы выражений. Доказаны критерии зараженности программы вирусом как для множества программ, не содержащих оператор Клини, так и подмножества программ, содержащих его, но глубины вложенности не более 1.
Ключевые слова: распознавание, вирусы, регулярное выражение, подформулы - Кибкало М.А.. Об автоматной сложности некоторых классов булевых функций.
Под сложностью языка (его функцией Шеннона) будем понимать число состояний в представляющем его приведенном автомате. В данной работе устанавливается, что булевы языки, соответствующие замкнутым классам Поста, разбиваются на три пояса в соответствие с асимптотикой функции Шеннона, причем для некоторых классов устанавливается точное значение функции Шеннона.
Ключевые слова: сложность, конечные автоматы, конечный автомат, булевы функции, булева функция, решетка Поста, функция Шеннона - Кучеренко Н.С.. Задача поиска по ключу с определением позиции.
В работе изучаются два способа формализации задачи поиска по ключу – задача поиска идентичных объектов (ЗПИО) и расширенная ЗПИО. Показано, что сложность поиска для этих способов формализации одинакова. Описан алгоритм преобразования, который алгоритм поиска для ЗПИО преобразует в алгоритм поиска для расширенной ЗПИО без изменения сложности поиска.
Ключевые слова: базы данных, поиск по ключу, алгоритм поиска - Лашева М.И.. О переключательных алгоритмах преобразования некоторых классов графов.
В работе вводится понятие переключательного алгоритма для перехода от одного заданного графа к другому с сохранением степенной последовательности и класса графов. Свойства переключательных алгоритмов позволяют использовать их для оптимизации свойств компьютерных сетей с заданным множеством провайдеров и ограничениями на коммутационные возможности каждого из них. При этом необходимо знать лишь локальные свойства сети, а не глобальные ее характеристики.
Ключевые слова: степенная последовательность, конечный автомат, переключательный алгоритм, деревья, унициклы, связные графы - Летуновский А.А.. О выразимости суперпозициями автоматов c разрешимыми группами.
Рассматривается задача выразимости конечного автомата A суперпозициями системы Phi U nu, где Phi состоит из всех функций k-значной логики и "задержки", nu – произвольная конечная система автоматов. Ранее автор показал, что для автомата A с безусловными переходами существует алгоритм проверки выразимости A через Phi U nu. В настоящей работе решается задача алгоритмической разрешимости задачи выразимости автомата с разрешимой группой через систему Phi U nu.
Ключевые слова: выразимость, конечный автомат, задержка, константный автомат, алгоритмическая разрешимость, разрешимая группа - Ли В.А.. Порядок сложности укладки деревьев на плоскость.
В работе рассматривается задача укладки деревьев на 2-х мерную прямоугольную решетку. Предложено несколько алгоритмов укладки, оптимальных по порядку, как для суммарной длины ребер, так и для площади укладки.
Ключевые слова: укладка дерева, укладка в прямоугольную решетку, длина укладки, площадь укладки, минимальная укладка, алгоритм укладки - Муравьева А.А.. О кодировании дискретных фигур отрезками.
В работе изучается кодировка дискретных фигур упорядоченным по величине набором всех попарных расстояний между их точками (спектром). Приводится условный алгоритм построения всех фигур с заданным спектром в пространстве любой размерности. Изучаются свойства спектров и способы продолжения подспектра, являющегося невозрастающей конечной последовательностью чисел, до спектра путем добавления новых элементов.
Ключевые слова: распознавание образов, дискретная геометрия - Осокин В.В.. О параллельной параметро-эффективной расшифровке псевдо-булевских функций.
В работе рассмотрена задача параллельной параметро-эффективной расшифровки псевдо-булевских функций в рамках модели точной расшифровки. Для интервально-постоянных функций, примерами которых являются псевдо-булевские монотонные функции и разбивающие функции, предложен оптимальный по порядку алгоритм параметро-эффективной расшифровки. Предложен параметро-эффективный алгоритм расшифровки некоторых подклассов интервально-постоянных функций с оптимальной по порядку параллельной сложностью и оптимальной по порядку обычной сложностью.
Ключевые слова: сложность расшифровки функций, параметро-эффективная расшифровка, параллельная расшифровка, псевдо-булевские функции, интервально-постоянные функции, монотонные функции, модель точной расшифровки - Поцелуевская Е.А.. Криптосистема с открытым ключом на основе задачи об F-выполнимости булевых формул.
В современном мире значительная часть информации обрабатывается в электронном виде. В связи с необходимостью обеспечить защиту такой информации при передаче по открытым каналам связи, широкое распространение получили криптографические системы с открытым ключом, основанные на различных NP-полных задачах. В настоящей работе рассматривается реализация асимметричной криптографической системы на основе NP-полной задачи об F-выполнимости булевых формул.
Ключевые слова: криптосистема, шифрование, выполнимость, булевы функции - Поцелуевская Е.А.. Алгоритмы решения задачи об F-выполнимости приближением к классам Шефера.
В своей работе "The complexity of satisfiability problems" Шефер выделил 6 классов булевых функций, для которых обобщенная проблема выполнимости (т.н. F-выполнимость) решается за полиномиальное время. Нахождение других классов функций, для которых задача также решалась бы быстро, имеет значительную практическую ценность. В настоящей работе представлены два алгоритма решения задачи об F-выполнимости, которые основаны на приближении булевых функций к классам Шефера, и при определенных ограничениях на исходные функции, имеют полиномиальную сложность.
Ключевые слова: алгоритм, F-выполнимость, классы Шефера, сложность - Родин С.Б.. Линейно реализуемые переходные системы.
Данная работа посвящена изучению "линейно реализуемых" переходных систем, т.е. переходных систем, обладающих тем свойством, что существует кодирование, при котором порождаемый кодированием, булевкий оператор является линейным. В работе приведено необходимое условие линейной реализуемости переходной системы. Также приведены нижняя и верхняя оценка числа линейно реализуемых переходных систем.
Ключевые слова: теория автоматов, переходные системы, кодирование, сложность - Соколов А.П.. О сложности взаимной обучаемости почти всех нейронов.
Работа посвящена вопросам сложности обучения нейронов. В качестве математической модели нейронов рассматриваются пороговые функции алгебры логики. Рассматривается вопрос сложности взаимной обучаемости пар пороговых функций в большинстве случаев. В качестве средства задания пороговых функций выстапают целочисленные линейные формы. В качестве меры сложности процесса обучения принято единичное изменение весового коэффициента линейной формы. Показано, что для почти всех пар пороговых функций от n переменных сложность перестройки одной пороговой функции, заданной линейной формой, в другую с ростом n растет экспоненциально.
Ключевые слова: пороговые функции, сложность обучения нейросетей - Соколов А.П.. Об одном многообразии пороговых функций.
В работе исследуется сложность задания пороговых функций алгебры логики линейными формами с целочисленными коэффициентами и свободным членом. Приводится очень простой пример пороговой функции, при задании которой целочисленными линейными формами необходимы экспоненциальные весовые коэффициенты. При этом, для произвольного числа переменных данная линейная форма явно предъявляется.
Ключевые слова: пороговые функции, сложность обучения нейросетей - Соколов А.П.. О конструктивной характеризации пороговых функций, инвариантных относительно групп перестановок.
В работе рассматриваются классы пороговых функций, инвариантных относительно групп перестановок. Получено полное описание данных классов в терминах групп перестановок, сохраняющих разбиения. Показано, что <<почти все>> пороговые функции являются несимметрическими, то есть инвариантными относительно лишь тождественной перестановки. Рассматриваются вопросы сложности задания пороговых функций целочисленными линейными формами. Введено понятие размаха пороговой функции. Получены верхняя и нижняя оценки на величину размаха для пороговых функций, инвариантных относительно групп перестановок. Исследуется сложность взаимной перестройки пороговых функций, инвариантных относительно групп перестановок, путем пошагового изменения коэффициентов линейных форм. Получены верхняя и нижняя оценки сложности перестройки в худшем случае.
Ключевые слова: пороговые функции, сложность обучения нейросетей - Цымжитов Д.. О мягком декодировании линейных кодов методом минимальных слов.
В работе рассмотрена модификация известного алгоритма ML-декодирования методом минимальных слов, имеющая явное ограничение на максимальное количество итераций в виде некоторого числа t. В случае, если отведенного числа итераций недостаточно для получения оптимального решения, алгоритм объявляет об отказе. Предложена нижняя граница для константы t, соблюдение которой гарантирует, что вероятность отказа декодера будет близка к нулю. Если n – длина кодового слова, то данная граница лежит в классе O(ln(n)) при n->inf. Полученная оценка является улучшением известной ранее линейной оценки.
Ключевые слова: мягкое декодирование, декодирование по максимуму правдоподобия, линейные коды, сложность декодирования, минимальные кодовые слова - Чернова Ю.Г.. О состояниях конденсации автоматной модели легких в чистой среде.
В статье предложена автоматная модель процесса самоочищения легких и продолжается изучение свойств её диаграммы Мура. Выделен особый класс состояний этой диаграммы, а именно те состояния, которые имеют наибольшее число предшественников в чистой среде. В работе представлено критериальное описание таких состояний, их количество, а также найдено число прямых предшественников каждого состояния конденсации.
Ключевые слова: автомат, диаграмма Мура, лёгкие, процесс самоочищения, состояние конденсации - Членова Т.С.. О слоистости булевых функций и функций k-значной логики.
В статье вводится понятие слоистости полных систем в Pk, k>=2. Получена оценка сверху слоистости произвольной полной системы в P2. В случае Pk, k >= 3, произведено сведение проблемы конечности слоистости полных систем к проблеме конечности слоистости систем Слупецкого. Также приведен довольно широкий класс систем Слупецкого, слоистость которых конечна.
Ключевые слова: булева функция, функция k-значной логики, полная система, сложность, слоистость - Шуткин Ю.С.. Об одновременной минимизации объемной и временной сложности контактных и вентильных схем.
Рассматривается задача одновременной минимизации объемной и временной сложности контактных и вентильных схем. Под объемной сложностью контактной или вентильной схемы понимается ее стандартная сложность, определяемая числом ребер в схеме. Под временной сложностью понимается среднее время работы алгоритма, моделирующего контактную или вентильную схему. Модель схемы строится в виде информационного графа, для которого алгоритм функционирования определяется уже формально. Получено асимптотически наилучшее решение задачи одновременной минимизации временной и объемной сложности контактных и вентильных схем.
Ключевые слова: Контактные схемы, информационные графы, временная сложность контактных схем - Соколов А.П.. Письмо в редакцию.
Глубокоуважаемая редакция, прошу принять к рассмотрению замечания по следующим моим работам, опубликованным в журнале "Интеллектуальные системы"...