English language
Содержание журнала "Интеллектуальные системы"
Том 13, выпуск 1-4, 2009 г.
Часть 1. Общие проблемы теории интеллектуальных систем
- К.Э. Плохотников. Математическое моделирование и вычислительный эксперимент: методология и практика.
В статье приводится новый взгляд на методологию (математического) моделирования и вычислительного эксперимента. Предложено формальное определение метода (математического) моделирования, приводятся некоторые неформальные аспекты данной методологии. Наибольшее внимание сосредоточено на обсуждении феноменов многомоделия в одной и той же познавательной ситуации, а также интерактивный характер взаимодействия в связке “модели данной предметной области — субъект-модельер”. Приводится набор оригинальных примеров, иллюстрирующих использование данного взгляда на методологию.
Ключевые слова: математическое моделирование, эксперимент, модель предметной области
Часть 2. Специальные вопросы теории интеллектуальных систем
- Д.В. Алексеев. Кодирование изображений, инвариантное относительно проективных преобразований.
В работе представлен метод кодирования плоских изображений, инвариантный относительно проективных преобразований расширенной плоскости. Показано, что при некоторых дополнительных условиях равенство кодов равносильно проективной эквивалентности изображений.
Ключевые слова: проективное преобразование, кодирование изображений - Д.Н. Жук. Континуальность множества предполных классов в классе дефинитных автоматов.
В данной работе показано, что в классе дефинитных автоматов мощность множества всех предполных классов равна континууму.
Ключевые слова: автомат, дефинитный автомат, предполный класс - С.Д. Махортов. Основанный на решетках подход к исследованию и оптимизации множества правил условной системы переписывания термов.
В работе рассматривается подход к исследованию и оптимизации множества правил условной системы переписывания термов, основанный на решетках.
Ключевые слова: предикат, терм - И.Н. Молодцов. Математическое моделирование упругопластических процессов с траекториями средней кривизны.
Построены и изучены определяющие четырехчленные уравнения дифференциального типа, связывающие напряжения и деформации в процессах сложного нагружения пластически деформируемого материала. Предложен вариант идентификации определяющих функционалов, произведено сравнение с теорией средних кривизн.
Ключевые слова: математическое моделирование, дифференциальные уравнения - Т.А. Ракчеева. Квазилемнискаты в задаче приближения формы кривых.
Предложен и разработан метод фокусной аппроксимации гладких замкнутых кривых. Базисом фокусного метода является семейство многофокусных лемнискат, параметрами которых являются конечное число фокусов внутри кривой и радиус. Анализ более общего класса квазилемнискат выделяет семейство лемнискат как удовлетворяющее наиболее общим требованиям к функции расстояния и описанию геометрических форм и их инвариантов.
Ключевые слова: кривые, фокусы, лемниската, эллипс, форма, преобразования, инвариант, базис, метрика, аппроксимация, степени свободы, генерация форм, интерактивное управление. - Е.А. Снегова. Случай задачи об опасной близости, сводящийся к одномерному интервальному поиску.
В работе рассматривается частный случай задачи об опасной близости. Доказано сведение этого случая к задаче одномерного интервального поиска.
Ключевые слова: интервальный поиск, одномерный интервальный поиск - А.П. Соколов. Асимптотика логарифма сложности перестройки нейронов.
В качестве средства задания пороговых функций в работе рассматриваются линейные формы вида x1w1 + ... + xnwn – s с целочисленными коэффициентами и свободным членом. Исследуется сложность преобразования одной пороговой функции, заданной линейной формой, к другой, путем пошагового изменения коэффициентов линейной формы. В качестве меры сложности данного процесса принимается изменение коэффициента или свободного члена линейной формы на единицу. Данный процесс может интерпретироваться как процесс обучения нейрона с пороговой функцией активации. Для характеризации сложности обучения в худшем случае вводится шенноновская функция r(n). Она говорит о том, сколько минимально достаточно выполнить единичных модификаций исходной линейной формы от n переменных для задания желаемой пороговой функции. Найдена асимптотика логарифма r(n).
Ключевые слова: пороговые функции, сложность обучения нейронов, нейрон, нейросеть - Б. Стаматович. Автоматное распознавание трехсвязных лабиринтов с конечным циклическим диаметром.
Распознавание образов – актуальная тема в компьютерных науках. Распознавание букв является одним из ее частных случаев. Идея использования шахматных лабиринтов применима к растровому преставлению изображений. Определен класс лабиринтов C8, который в геометрическом смысле представляет цифру восемь. В работе [1] показано, что не существует распознающего автомата для этого класса лабиринтов. В работе [2] показано, что существует распознающий коллектив автоматов типа (1,1) для класса лабиринтов C8. Здесь поставлена задача для подкласса лабиринтов C8d с конечным диаметром дыры, и она положительно решена.
Ключевые слова: лабиринт, трехсвязный лабиринт, автомат, конечный автомат, автоматное распознавание - Д. Цымжитов. Об одном алгоритме ML-декодирования для низкоплотностных кодов.
В работе представлен алгоритм мягкого декодирования для низкоплотностных двоичных кодов с графом Таннера без циклов. Показано, что этот алгоритм находит оптимальное решение задачи декодирования по максимальному правдоподобию и имеет асимптотическую сложность O(n), где n – длина кодового слова.
Ключевые слова: код, низкоплотностный код, декодирование, двоичный код
Часть 3. Математические модели
- Г.В. Боков. Проблема полноты в исчислении высказываний.
В работе проблема полноты систем аксиом в исчислении высказываний рассматривается с позиции оператора замыкания, порожденного правилами вывода. Описываются некоторые свойства данного оператора, а также свойства замкнутых и предполных классов, задаваемых этим оператором. Доказывается алгоритмическая неразрешимость проблемы полноты конечных систем аксиом в исчислении высказываний.
Ключевые слова: полнота, высказывание, исчисление высказываний, аксиома, правило вывода - Н.Ю. Волков. О возможности поимки жертв в квадранте.
Изучается процесс преследования коллективом автоматов ("хищников") нескольких независимых друг от друга автоматов ("жертв"). Преследование происходит в лабиринте, представляющем собой квадрант. Показано, что существует конечный коллектив хищников, который "ловит" любую конечную независимую систему жертв с фиксированными скоростями и обзорами при любом начальном расположении жертв и стартующих из одной точки хищников.
Ключевые слова: хищник, жертва, лабиринт, автомат, коллектив автоматов, конечный автомат, квадрант - Ю.И. Вторушин. О поиске вывода в системе натуральной дедукции логики предикатов.
В статье описывается метод автоматического доказательства теорем, который используется в системах автоматизации дедукции Class и Int. Публикуемый алгоритм находит выводы в рамках многосортной системы натуральной дедукции, которая адэкватно моделирует реальные человеческие рассуждения. Алгоритм полон для минимальной, интуиционистской и классической систем натуральной дедукции логики предикатов.
Ключевые слова: предикат, логика предикатов, дедукция, натуральная дедукция - А.В. Галатенко, В.В. Галатенко. О расстоянии Хэмминга между почти всеми функциями алгебры логики.
В работе оценивается расстояние Хэмминга между почти всеми функциями алгебры логики
Ключевые слова: расстояние Хэмминга, алгебра логики, булева функция - Ю.Г. Гераськина. О переводимости состояний автоматной модели легких в чистой среде.
В работе предлагается автоматная модель процесса транспортировки вещества в легочных структурах в чистой среде. Рассматривается процесс самоочищения легких от привнесенных веществ из среды, а также от веществ, образующихся в легких в процессе их жизнедеятельности. Для предложенной автоматной модели решаются следующие задачи – нахождение средней глубины диаграммы Мура, нахождение критерия перехода одного состояния в другое и оценки времени такого перехода.
Ключевые слова: автомат, диаграмма Мура, легочные структуры, процесс транспортировки вещества, переводимость состояний автомата, бронхи - Д.Н. Жук. Разрешимые случаи задачи об A-полноте для дефинитных автоматов.
В работе рассматриваются системы вида M = F U nu, где F – некоторый класс Поста, а nu – конечная система дефинитных автоматов. Выделены некоторые классы Поста, для которых проблема A-полноты для систем вида F U nu алгоритмически разрешима.
Ключевые слова: полнота, A-полнота, разрешимость, алгоритмическая разрешимость, класс Поста, решетка Поста, автомат, дефинитный автомат - М.А. Кибкало. О сложности представления коллекции языков в конечных автоматах.
Определение сложности представления языков – одна из традиционных задач теории автоматов. В статье рассматривается случай совместной представимости семейства языков в одном автомате. Существуют различные определения сложности регулярного языка основанные на характеристиках самого языка или представляющего его автомата. В данной работе под сложностью языка (семейства непересекающихся конечных языков) понимается число состояний в представляющем его (их) приведенном автомате. В работе решена задача о нахождении точного значения максимальной сложности семейства конечных языков в зависимости от максимальной длины слова в нем.
Ключевые слова: автомат, конечный автомат, приведенный автомат, язык - Н.С. Кучеренко. О промежуточных функциях роста сложности поиска для случайных баз данных.
В работе рассматриваются функции роста сложности оптимальных алгоритмов решения задачи поиска идентичных объектов в среднем по классу задач. Ранее автором были изучены случаи, когда функция роста является ограниченной функцией или имеет порядок логарифма от мощности базы данных. В данной статье описано семейство S возможных асимптотик и семейство S* возможных порядков функций роста, которые являются неограниченно возрастающими, но по порядку меньшими, чем логарифм от мощности базы данных.
Ключевые слова: поиск, сложность, база данных, алгоритм поиска - А.А. Летуновский. О выразимости константных автоматов суперпозициями.
Показано, что для конечных систем автоматных функций, содержащих все истинностные функции и задержку, существует алгоритм выразимости константных автоматных функций. Множество выразимых константных автоматных функций явно описывается по первоначально заданной конечной системе автоматов. Также показано существование алгоритма выразимости автономных автоматов.
Ключевые слова: автомат, конечный автомат, константный автомат, суперпозиция, автоматная функция, выразимость, алгоритмическая разрешимость - И.В. Лялин. Решение автоматных уравнений с двумя неизвестными.
Пусть имеется автоматная схема S, полученная из автоматов с помощью операции суперпозиции. Пусть в S несколько автоматов x1, x2, ..., xn разрешается заменять на любые подходящие по входам и выходам автоматы x1', x2', ..., xn'. Рассматривается следующая задача: существует ли такая замена, чтобы полученная схема S' реализовывала автомат, эквивалентный наперед заданному автомату h. В статье доказывается алгоритмическая неразрешимость этой задачи, если n >= 2.
Ключевые слова: автомат, конечный автомат, автоматное уравнение - М.В. Носов. Комбинаторная формула числа пороговых функций.
В работе представлен вывод комбинаторной формулы, задающей число пороговых функций. При выводе формулы использованы многочлены Лагранжа. Используется верхняя оценка на длину ребра куба, целочисленные точки которого задают все пороговые функции.
Ключевые слова: пороговые функции, многочлен Лагранжа - В.В. Осокин. О параллельной расшифровке разбиений булевого куба.
В работе рассматривается класс Фk,n дискретных функций, определенных на булевом кубе {0,1}n и существенно зависящих от не более чем k <= n переменных. Каждая функция f из Фk,n задает разбиение куба {0,1}n на непересекающиеся грани и сопоставляет уникальное число каждой грани результирующего разбиения. Мы доказываем нижнюю оценку сложности расшифровки функций из Фk,n и предлагаем алгоритм расшифровки функций из Фn = Фn,n, оптимальный в том смысле, что число запросов на значение функции, требуемое алгоритму для расшифровки произвольной функции из Фk,n, по порядку совпадает с нижней оценкой. Построенный алгоритм может быть эффективно распараллелен и при максимальном распараллеливании его сложность по порядку равна k.
Ключевые слова: булев куб, расшифровка булева куба, дискретная функция - Е.А. Поцелуевская. Теоретическая и практическая сложность задачи о выполнимости булевых формул.
В работе описываются различные варианты постановки задачи о выполнимости, а также приводится обзор наиболее известных алгоритмов её решения, их классификация и некоторые теоретические оценки сложности. В заключительной части статьи рассматриваются наиболее примечательные результаты, полученные в данном направлении за последние 10 лет, а также некоторые практические оценки сложности.
Ключевые слова: выполнимость, SAT, обзор, алгоритм, сложность - А.П. Соколов. Об одном семействе нейронов с ограниченной сложностью взаимной перестройки.
Исследуется сложность преобразования одной пороговой функции, заданной линейной формой, к другой, путем пошагового изменения коэффициентов линейной формы. В качестве меры сложности данного процесса принимается изменение коэффициента или свободного члена линейной формы на единицу. Данный процесс может интерпретироваться как процесс обучения нейрона с пороговой функцией активации. Приводится конструктивное построение такого класса пороговых фукнций, что сложность взаимной перестройки функций из данного класса ограничено заранее заданной величиной, лежащей в диапазоне от 3..n до 3..2n, где n – число переменных. При этом, мощность данного класса экспоненциально зависит от n.
Ключевые слова: пороговые функции, сложность обучения нейронов - Ю.С. Шуткин. Реализация монотонных булевых функций монотонными информационными графами.
Рассматривается задача реализации булевых функций с помощью монотонных информационных графов, т. е. графов, базовое множество которых состоит из переменных без отрицаний. Получены оценки сложности для различных подклассов этой задачи.
Ключевые слова: булева функция, монотонная булева функция, информационный граф