Восстановление параметров дискретных устройств, основанное на переоценке вероятностей с использованием действительных пороговых соотношений тема диссертации и автореферата по ВАК РФ 05.13.11, кандидат технических наук Нетыкшо, Виктор Борисович

• Нетыкшо, Виктор Борисович
• кандидат технических наук
• 2003

Оглавление диссертации кандидат технических наук Нетыкшо, Виктор Борисович

Введение

Глава 1. О возможности определения неизвестных параметров дискретного узла с помощью переоценю! вероятностей для пороговых функций

1.1. Переоценка вероятностей для мажоритарных функций

1.2. Сравнительный анализ некоторых дискретных методов для мажоритарных функций

1.3. Переоценка вероятностей для пороговых функций

1.4. О возможности восстановления правила выделения существенных переменных для пороговых функций

1.5. О восстановлении пороговой функции

1.6. Переоценка вероятностей совокупностей переменных и о некоторых статистических аналогах пороговых функций

1.7. Переоценка вероятностей значений переменных для произвольных пороговых функций с использованием геометрического подхода

Глава 2. Исследование возможностей переоценки вероятностей для других классов функций

2.1. Переоценка вероятностей для некоторого класса непороговых функций

2.2. Переоценка вероятностей для функций с нелинейными членами в псевдобулевом задании

2.3. О суперпозиции пороговых функций

2.4. Достаточные условия уменьшения числа неравенств в некоторых системах без потери решений

2.5. Переоценка вероятностей по системе ограниченного количества псевдобулевых неравенств с использованием геометрического подхода

2.6. Переоценка вероятностей для пороговых функций к -значной логики

2.7. О некоторых классах к -значных функций

2.8. Еще об одном классе £-значных функций 133 Заключение 137 Литература 140 Приложение

Введение диссертации (часть автореферата) на тему «Восстановление параметров дискретных устройств, основанное на переоценке вероятностей с использованием действительных пороговых соотношений»

Исследование систем описывающих функционирование узлов дискретной аппаратуры булевых уравнений (СБУ) х) = а,.,/ = 1Г7, (1) связанное с нахождением представлений нелинейных булевых уравнений из системы (1) в базисе арифметических операций в поле действительных чисел, является актуальным направлением в дискретной математике. Его развитие обусловливается как задачами анализа СБУ, так и задачами синтеза булевых функций и различных устройств обработки дискретной информации. Аналитические задачи являются расширением арсенала математических методов исследования СБУ (1). В области синтеза замена нелинейных булевых уравнений на равносильные действительные соотношения приводит к расширению возможностей задания булевых функций алгоритмическим путем в базисе традиционных арифметических команд вычислительной техники. Вместе с тем появляется возможность задания булевых функций на новой элементной базе с реализацией операций суммирования и сравнения с высоким быстродействием, а также непосредственно в физической или химической среде. Наиболее известными образцами таких вычислительных модулей являются нейроплаты и ней-росети с широкими функциональными возможностями.

Линейные неравенства, лежащие в основе этих идей, могут возникать естественно, как следствие работы того или иного узла, но могут быть введены и искусственно, путем специального преобразования исходной задачи.

К анализу СБУ, которым занимались многие авторы [1-9, 20, 31, 34, 35, 38, 41, 43], относятся псевдобулевые методы, сводящие решение СБУ к решению систем псевдобулевых уравнений или неравенств (метод разделяющей поверхности, метод замены булева равенства на линейное псевдобулево равенсто с неоднозначно определенной правой частью, метод, использующий экстраполяцию булевых уравнений выпуклыми функционалами и другие). В большинстве случаев предлагаются способы построения таких систем уравнений или неравенств, что задача решения СБУ сводится к отысканию булевого вектора, минимизирующего некоторую функцию и удовлетворяющего построенным ограничениям. Ограничения и функцию удобно выбирать линейными, что позволяет использовать для решения получаемой задачи хорошо разработанный аппарат линейного программирования. Значительная часть исследований, проводимых в этой области ранее, была связана с методом разделяющих плоскостей (МРП) [9, 35], основанном на сведении нелинейных булевых уравнений к равносильным системам линейных псевдобулевых неравенств, и решении последних методами линейного программирования.

Вопросы решения систем линейных неравенств относительно дискретных неизвестных представляют большой практический интерес. В настоящее время не существует универсальных аналитических методов, позволяющих за приемлемое время решить произвольную действительную систему относительно дискретных неизвестных либо ответить на вопрос, совместна она или нет. Мало внимания уделялось проблеме переноса вероятностной меры из действительной области в булеву. Вместе с тем сама специфика линейного псевдобулевого неравенства позволяет получать дополнительную информацию о значениях входных переменных с помощью теоретико-вероятностных методов.

Теоретико-вероятностный подход к анализу СБУ определяет научную задачу разработки методики получения дополнительной информации относительно значений входных переменных булевой функции по ее выходным значениям при использовании псевдобулевого способа задания.

Целями работы являются расширение возможностей решения систем линейных псевдобулевых неравенств, восстановления различных параметров дискретных устройств, повышение скорости настройки нейросетевых моделей.

Процесс решения псевдобулевых систем неравенств можно рассматривать в более общем смысле. Задание действительных ограничений для булевых переменных определяет некую меру «выполнимости» этих неравенств, или -меру соответствия тех или иных значений искомых переменных тем неравенствам, в которых они участвуют. Решение системы означает, что на множестве всех возможных значений переменных задана или вырожденная, если решение единственное либо не существует, или невырожденная вероятностная мера, если решений не меньше двух, в соответствии с которой переменные принимают свои значения. По существу происходит перенос вероятностной меры из действительной области в булевую.

В работах [1, 3; 5, 20] введены понятия полу случайных, случайных и заведомо совместных случайных систем уравнений. Отличительной особенностью систем линейных неравенств, возникающих при анализе дискретных задач, является, как правило, обязательное наличие одного или нескольких решений. Следовательно, такие системы согласно введенной терминологии можно классифицировать как заведомо совместные случайные системы неравенств. В диссертации показано, что эта вероятностная мера зависит от количества и качества неравенств системы, использующихся для ее построения.

В диссертации рассмотрены свойства широкого класса систем линейных псевдобулевых и псевдо- к -значных неравенств с применением методов математического анализа, теории вероятностей, математической статистики, комбинаторного анализа и аналитической геометрии.

Дадим несколько определений. Определение 1. Функцию •/(*,,.,*„) такую, что где В = ВхВх.хв, В = 2) - поле из двух элементов, назовем булевой функцией от « переменных.

Определение 2. Псевдобулеву функцию ф(х1,.,хп) определим отображением ф:Вп Я, где В = ВхВх.хВ, В = - поле из двух элементов, Я - поле действительных чисел.

Определение 3. Псевдобулевым ограничением назовем соотношение

0(х„.,хл)бг, геЯ, где О, - одно из следующих ограничений, определенных в поле Я:

Определение 4. Пару чисел (£,, к2), где к2 - такие минимальные числа, что для булевой функции / выполняется назовем пороговой структурой функции /.

Определение 5. Булеву функцию /(*,,.,.,х„) назовем пороговой, если ее пороговая структура есть (1, 1).

Чаще будем пользоваться следующим эквивалентным определением пороговой функции: / - пороговая, если

Коэффициенты а,, / = 1, п, назовем весовыми коэффициентами, а число с - порогом.

Определение 6. Пороговую функция назовем мажоритарной, если все весовые коэффициенты равны единице.

Для получения основных результатов и оценок рассмотрен некоторый простейший узел дискретной аппаратуры со сдвиговым характером поступления входной информации и с пороговой функцией на выходе. В работе [38] определено понятие системы рекуррентного типа, описывающей функционирование такого узла. Существует несколько аргументов по поводу целесообразности исследования вероятностных свойств такого автомата. Во-первых, сложность нахождения неизвестных параметров дискретных узлов зависит от пороговых структур функций, реализующихся этими узлами, а изучение свойств пороговой функции является важным этапом на этом пути. Во-вторых, и об этом будет сказано ниже, функции с ограниченной пороговой структурой могут рассматриваться в качестве статистических аналогов реально использующихся функций, либо - как моделирующие некоторые более сложные процессы. В = 1 третьих, исследование малоизученных свойств пороговых функций и их последующее использование в различных нейронных моделях позволит, вероятно, улучшить количественные и качественные характеристики последних при решении большого класса различных задач.

В зависимости от различных типов пороговой функции результаты были достигнуты с применением разных методов. Для мажоритарных функций оценки получены при прямом подсчете вероятностей, для других пороговых функций удалось использовать некоторые методы теории вероятностей и аналитической геометрии. Необходимо отметить, что построение меры на множестве допустимых значений переменных предпринималось как в асимптотике, то есть при стремлении количества неизвестных в бесконечность, и с наложением ограничений на весовые коэффициенты, так и для любого конечного числа переменных без каких-либо ограничений.

В ряде работ [19, 22], посвященных исследованию свойств узлов дискретной аппаратуры, было замечено, что между знаками выходной последовательности могут возникать корреляционные связи, зависящие от различных параметров. Эти связи описываются с помощью распределений мультиграмм в выходной последовательности, которые используются при разработке методов определения неизвестных параметров рассматриваемых узлов. Поэтому вполне естественно, что для успешного решения ряда задач дискретной математики необходимо использование на выходе таких обобщенных мультиграмм (или, что то же самое, - таких подсистем линейных псевдобулевых неравенств), для которых апостериорные вероятности максимально приближены к единице. Определение 7. Обобщенной V -граммой (а,. *. * а, ), 1 </,<.</„<*, назовем упорядоченную мультиграмму с фиксированными значениями на местах /,,.,/„ соответственно.

На уровне идеи представляется очевидным то, что рассматривать нужно обобщенные п-граммы (и - количество входных переменных функции), или п неравенств, в образовании которых участвует искомая переменная, поскольку в данной подсистеме содержится наиболее полная информация об этой переменной. В работе [3] было показано преимущество использования т-грамм, т>п, (метод окрестностей). В диссертации аналитически доказана эффективность применения и-грамм специального вида. Указанные мультиграммы формируют подсистемы с повышенной вероятностью появления некоторых решений. Были найдены условия, налагаемые на выходную обобщенную мультиграмму, при которых апостериорная вероятность стремится к единице. По таким мульти-граммам можно локально восстанавливать значения некоторых переменных с высокой вероятностью. Общая идея локального подхода к решению задач дискретной математики высказывалась в работе [17].

Использование одной оптимальной и-граммы при построении вероятностной меры, близкой к вырожденной, с алгебраической точки зрения совпадает по смыслу с выделением из исходной системы подсистемы максимального ранга. Иными словами, существует широкий класс систем п линейных псевдобулевых неравенств от л(«-1)+1 переменных, по каждой из которых можно определить значение некоторой неизвестной с вероятностью, стремящейся к единице с ростом п. Нахождение начального вектора (НВ) входной линейной рекуррентной последовательности (ЛРП) в этом случае при прочих известных параметрах рассматриваемой схемы сводится к построению и решению булевой системы линейных уравнений (СЛУ) с ограниченным числом искажений в правой части.

Выше обсуждались вопросы, связанные с переоценкой вероятностей значений некоторых переменных для пороговой функции. Здесь для более уверенного определения неизвестной х1 использовалась подсистема

Wil))Qч где I - псевдобулевая линейная форма, Зс(Аг)П*(/) = .д^} = {*,},

- один из знаков <, у = 1, у.

Далее рассматривается принципиально иная ситуация — функции с пороговой структурой (к,, к2), кх, кг>2. Сначала изучаются арифметические соотношения между весовыми коэффициентами, которые позволяют свести переоценку вероятностей для новых функций к уже решенной задаче для пороговых функций. Затем с помощью геометрической интерпретации оценены апостериорные вероятности для произвольной булевой функции с ограниченной пороговой структурой. Это эквивалентно вычислению оценок весов функции и всех ее подфункций.

Рассматривается булева функция с пороговой структурой (2,2). Переменные переупорядочиваются в соответствии с убыванием модулей к -6,1, / = 1, и, где /(х,,.,хи) = 1<=> п

1-1 я

- С2

1=1

Изучение апостериорных вероятностей значений переменных по одному значению функции с пороговой структурой (2,2) показало, что максимальная информация из неравенств извлекается для переменной хх (в отличие от переменной с максимальным по модулю весовым коэффициентом - для пороговой функции).

Асимптотический подход к оценке апостериорных вероятностей для пороговых функций имеет сильные и слабые стороны. К первым можно отнести скорость, простоту и точность в вычислениях, к недостаткам - ограниченную применимость. Решение задачи на основе геометрической интерпретации позволяет получать оценки апостериорных вероятностей для любых функций с ограниченной пороговой структурой, но за счет повышения сложности вычислений.

Если при решении задач дискретной математики удается построить систему булевых нелинейных, а иногда и линейных, уравнений с искаженными правыми частями, то получение дополнительной информации о некоторых состояниях входной последовательности позволяет уменьшить вероятность искажения, а для некоторых уравнений - свести ее к нулю. Решение СЛУ с искаженными правыми частями в общем случае является экспоненциальной по сложности задачей. С помощью достигнутых в данной работе оценок апостериорных вероятностей в некоторых случаях согласно [2, 3, 8] можно решать СЛУ с искаженными правыми частями за полиномиальное время.

В диссертации рассмотрены вопросы, связанные с восстановлением других параметров дискретных устройств, где используются полученные результаты.

Разработана методика восстановления неизвестной пороговой функции. К этой задаче сводится, например, настройка порогового элемента [13, 15]. Такая задача в принципе разрешима с помощью алгоритма решения систем линейных неравенств Хачияна за полиномиальное время, однако реализация этого метода на практике является очень трудоемким процессом. В диссертации предложен и математически обоснован простой алгоритм, с помощью которого на сравнительно небольшой длине выходной последовательности за полиномиальное время строится пороговая функция, стремящаяся по вероятности к исходной.

Рассмотрена задача восстановления правила выделения существенных переменных. Она разбита на две части, когда у исследователя имеется в наличии входная и выходная последовательности либо только выходная последовательность, и сведена к задаче разделения двух простых биномиальных гипотез.

Интересное приложение имеет задача восстановления неизвестных весовых коэффициентов каскада пороговых функций. Имеется в виду настройка нейросетей — суперпозиции пороговых функций. Фактически перед исследователем стоят две задачи. Во-первых, построение объекта, нейросети, который бы заданную входную последовательность значений преобразовывал в выходную. Во-вторых, адаптация этого объекта реальной жизни, то есть при поступлении на входы новых данных нейросеть должна сгенерировать на выходе результат, с некоторой точностью соответствующий практике. Первая часть задачи решается в настоящее время путем многократного повторения одних и тех же действий: по входу нейросетью со случайно заданными весовыми коэффициентами строится выход, который затем сравнивается с обучающим, после чего по некоторому алгоритму пересчитываются коэффициенты в соответствии с ошибкой. Этот процесс отнимает у исследователя очень много времени, и не гарантирует решение второй задачи. Дальнейшее развитие результатов, полученных в диссертации, могло бы существенно упростить решение задач по настройке нейро-сетей.

Определим следующее вероятностное пространство в»*-1, I, />), где вы+п~1 - декартово произведение Ы + п-1 множеств В = {0,1}, 2 - сигма-алгебра на множестве В(то есть 2 - это множество всех подмножеств Вы+"~1 с заданными на нем операциями пересечения, объединения и разности), и вероятностная мера Р: 2 [О, 1] такая, что дг, ,.,Хдг+я, £

Тогда очевидно определяется вероятность произвольного события, состоящего из более коротких последовательностей.

Входные переменные, подающиеся на вход устройства в каждом такте работы, считаем независимыми равномерно распределенными (если не оговорено обратное) на множестве В случайными величинами. Семейство вероятностных мер на выходе устройства задается стандартным образом, а именно: определим вероятностное пространство в*. 2, Р), где Вы - декартово произведение N множеств В - {О, 1}, Е - сигма-алгебра на множестве Вы, а Р - вероятностная мера со свойством

Р{в = \ух,.,у„) | г, е {0, 1}, / = 2}= о ^ где £> = {(*„.,х„+л,)| /(х1,.,хп) = г1, /(х2,-,хп+1) = Г2./(%>■■•,**+„) = Гц}

Для дальнейшего изложения введем новые понятия. Определение 8. Апостериорную вероятность

К* * '2 *. * О) = ~Уг] = = '2'• • • = с) = />{{*0) = *}& К =/1 'У=/».Ум*.«, , =/Л)

Р^у = *1»У='г» ••• »У ./+»,■•• .+»„, ='V } где участвует в образовании знака выходной последовательности у] = ¡х, - расстояния между существенными переменными в системе рекуррентного типа, назовем вероятностью переоценки входного значения по выходной обобщенной у -грамме (/, * /2 *.*/„).

Будем также говорить о переоценке вероятности как о процессе вычисления вероятности переоценки значения некоторой переменной по выходной у -грамме, лг(у) - переоцениваемая переменная по у -грамме. Переоценку вероятности полагаем успешной, если р{х0) = £Ач2*.ч))>р(х0) = ^ или ^ = £А*Н*-*К)\<= эффективной, если существует \ такое, что /2 *.*/„))- ^ > р(*и) = или * к ** о) ~А°< р(х°} = ^ для достаточно больших п; у -наилучшей по некоторой у -грамме (/, * г2 *.*/„), если р(х0> =Л*, ч *. ч >) - р[*и)н'-' л>) для любых у -грамм (д * у2 * • • • * л); наилучшей по у -грамме (/, */2 *.*/„), если

Р[Х°} '/(К* к*:.' о) 1' ^ Л)) для произвольной 5 -граммы (л * Л * • • • * Л) > $ = 1, и; переоценку вероятности для переменной считаем успешнее переоценки вероятности для переменной если выполняются неравенства "X ч •-ч))> К""'ч •-ч)Н

Переменная может и не участвовать в образовании знаков

При решении задач для пороговых функций к -значной логики были использованы точно такие же методы, полученные результаты тем не менее заметно отличаются.

Определение 9. Функцию /(*,,.,хя) такую, что где В = ВхВх.хВ, 5 = {0,.,А:-1}, назовем Л-значной функцией от п переменных.

Определение 10. Псевдо-к-значную функцию ф{хх,.,хп) определим отображением ф:В" Я, где В = ВхВх.хВ, £ = {0,.,£-1}, Л - поле действительных чисел. Определение 11. Псевдо- к -значным ограничением назовем соотношение ф(х1,.,хп)дг, г еЛ, где 2 - одно из следующих ограничений, определенных в поле Я: ф, >, с, >, <.

Например, для наилучшей переоценки вероятности фиксированного значения переменной в системе рекуррентного типа нельзя указать выходную мультиграмму, по которой эта переоценка проводится, основываясь только на значности весовых действительных коэффициентов (в отличие от булевого случая). Для построения такой мультиграммы следует вычислить апостериорные вероятности по всем возможным у -граммам и найти максимальную, что реализуемо для небольших значений у. Хотя, учитывая предварительный характер такой задачи, выполнение этих действий представляется целесообразным. Используя полученные в работе результаты, можно локализовать значения элементов входной последовательности и тем самым сократить перебор.

Требуют дальнейшего изучения задачи: - разбиение по какому-либо признаку £-множества {0,.,£-1} на несколько непересекающихся подмножеств Д. , / = 1, переоценка вероятностей и выбор наилучшей переоценки; если в этом случае одна из вероятностей значительно преобладает над другими, то это дает дополнительную информацию о переменной;

- если из системы неравенств, описывающей функционирование дискретного узла, удается выделить несколько подсистем представить ¿-множество

0,.Д-1} в виде г

0,.,£-1} = р)4, Д. гм, * о, для всех 1 </<у<г, /=1 подсчитать вероятности переоценки и упорядочить их лМ то, пересекая подмножества А1(| и А,г, получим с большой вероятностью новое, меньшее по мощности, подмножество, в котором с повышенной вероятностью находится искомое решение.

Данные обстоятельства нужно учитывать при дальнейшем использовании этого и других алгоритмов, а также методов перебора. Применение такой методики оправдано еще и тем, что вычисление апостериорных вероятностей где е 5 - подсистема исходной системы неравенств, может оказаться проще, чем вычисление вероятностей переоценок значения для отдельной переменной, и, в то же время, полученные оценки апостериорных вероятностей могут существенно отличаться от априорных. Из вида псевдо- к -значных неравенств можно заранее сделать выводы о том, как эффективнее разбить к -множество.

Таким образом, применение пороговых функций в качестве статистических аналогов либо как результат суммарных наблюдений за некоторыми свойствами различных узлов дискретной аппаратуры позволяет существенно упростать решение задач по определению неизвестных параметров схемы. Последнее замечание является весьма актуальным для применения в дискретной математике.

Структура диссертации.

Диссертация состоит из введения, двух глав, заключения, списка литературы (44 наименования) и приложения. Работа изложена на 148 стр., из них 113 стр. основного текста. Нумерация утверждений, определений, примеров и формул во введении и главах - независимая. Ссылки на утверждения, определения, примеры и формулы внутри главы - по номеру, например, «определение 7», «формула (11)»; ссылки на введение и другую главу - с добавлением префикса, например, «система (0.2)» - ссылка на систему (2) из введения, «теорема 1.12» -ссылка на теорему 12 из главы 1.

Заключение диссертации по теме «Математическое и программное обеспечение вычислительных машин, комплексов и компьютерных сетей», Нетыкшо, Виктор Борисович

Основные результаты диссертационной работы заключаются в следующем.

1. Разработана методика подсчета апостериорных вероятностей значений входных переменных по одному выходному значению пороговой функции.

2. Построен алгоритм поиска в исходной системе рекуррентного типа подсистем линейных псевдобулевых неравенств специального вида, переоценка вероятностей значений входных переменных по которым максимальна.

3. Предложен способ восстановления неизвестной пороговой функции по коротким входным и выходным последовательностям.

4. Описана процедура построения каскада пороговых функций (нейросети) по независимым в совокупности входным и выходной учебным последовательностям.

5. Разработан метод подсчета весов всех подфункций произвольной булевой функции с ограниченной пороговой структурой.

На защиту выносятся следующие результаты.

1. Вероятностно-статистический метод анализа систем линейных псевдобулевых неравенств.

2. Алгоритм решения систем линейных псевдобулевых неравенств, основанный на вероятностно-статистическом методе.

3. Построенный алгоритм распространен на системы с произвольными булевыми уравнениями.

К нерешенным проблемам по данной тематике можно отнести следующие: получение дополнительной информации относительно входов по выходу для пороговой функции при условии, что некоторые входные переменные зависимы; распространение геометрического подхода на функции к -значной логики (к> 2); разработка метода решения систем псевдо-к-значных неравенств с использованием вероятностно-статистического подхода.

Решение данных проблем помогло бы перейти к рассмотрению вопросов теоретического обоснования правильности настройки и работы различных ней-росетевых и генетических алгоритмов.

В заключение автор хотел бы выразить глубокую благодарность научному руководителю д.т.н. Никонову Владимиру Глебовичу за помощь, оказанную при проведении исследований и написании работы; признательность за критику и помощь д.ф.м.н. Балакину Геннадию Васильевичу, к.т.н. Коновальчику Павлу Михайловичу, д.ф.м.н. Алиеву Физули Камиловичу, к.ф.м.н. Колпакову Сергею Анатольевичу, к.ф.м.н. Мельникову Сергею Юрьевичу, к.ф.м.н. Смирнову Владимиру Георгиевичу, к.т.н. Поспелову Гелию Ивановичу.

ЗАКЛЮЧЕНИЕ

В диссертации разработана методика получения дополнительной информации относительно значений входных переменных булевой функции по ее выходным значениям при использовании псевдобулевого способа задания, имеющая невысокую вычислительную сложность. Построенные алгоритмы применимы для расширения возможностей решения систем псевдобулевых неравенств, восстановления различных параметров дискретных устройств, настройки нейросетей с независимыми входами.

В главе 1 получены основные результаты для мажоритарных и пороговых функций по переоценке вероятностей значений входных переменных при наблюдении выходных мультиграмм. Для систем рекуррентного типа указана структура мультиграмм, переоценка вероятностей по которым наилучшая. Показано, что на небольшой длине поиск решения системы линейных неравенств рекуррентного типа сводится к построению и решению СЛУ с искаженными правыми частями. Разработан и проанализирован алгоритм выделения существенных переменных пороговой функции по входной и выходной (или только по выходной) последовательностям ограниченной длины. Построен теоретико-вероятностный метод восстановления пороговой функции, стремящейся по вероятности к неизвестной исходной пороговой функции. С помощью геометрической интерпретации условия задачи получена возможность переоценки вероятностей для произвольной пороговой функции без каких-либо ограничений на весовые коэффициенты.

В главе 2 рассмотрены некоторые классы к-значных функций (к >2), к которым применима разработанная методика. Показана возможность быстрой переоценки апостериорных вероятностей для совокупности ограниченного числа пороговых функций с одинаковой линейной псевдобулевой формой и разными порогами; для функций с ограниченным количеством нелинейных членов в псевдобулевой форме; для суперпозиции пороговых функций. Получены условия, накладываемые на весовые коэффициенты, при которых функции с пороговой структурой (£,/),, к,1< 3, являются пороговыми. Геометрический подход к переоценке вероятностей значений переменных распространен на произвольную булеву функцию с ограниченной пороговой структурой, что фактически означает возможность переоценки вероятностей для любой булевой функции. Рассмотрены вопросы получения дополнительной информации о значениях входов по выходам для пороговых функций к-значной логики (к >2).

В результате проведенных в диссертации исследований установлено, что для расширения возможностей решения систем линейных псевдобулевых неравенств, восстановления различных параметров дискретных устройств, повышения скорости настройки нейросетевых моделей необходима разработка математического аппарата анализа булевых функций с использованием их псевдобу-левого способа задания. Эта задача была решена на основе переоценки вероятностей для пороговых функций, а также - с помощью геометрического подхода — для произвольных булевых функций с ограниченной пороговой структурой.

Список литературы диссертационного исследования кандидат технических наук Нетыкшо, Виктор Борисович, 2003 год

1. Балакин Г.В. О возможности решения систем линейных целочисленных уравнений методом выделения и оценки отдельных неизвестных. Дискретная математика, 1994, т. 6, в. 1, с. 116-126.

2. Балакин Г.В. О вероятностном подходе к решению систем уравнений с целочисленными неизвестными. Дискретная математика, 1995, т. 7, в. 1, с. 8898.

3. Балакин Г.В. Об одном подходе к решению систем линейных целочисленных уравнений. В кн.: Тез. IX Всесоюзной конф. «Проблемы теоретической кибернетики», № 1. Волгоград, 1990, с. 12.

4. Балакин Г.В. Системы случайных линейных псевдобулевых уравнений. В кн.: Тез. докл. VIII Всесоюзной конф. «Проблемы теоретической кибернетики», № 1.-Горький, 1988, с. 35-36.

5. Балакин Г.В. Системы уравнений с мешающими параметрами. — Всероссийская школа-коллоквиум по стохастическим методам геометрии и анализа. Тез. докл. М.:ТВП, 1994, с.11-12.

6. Балакин Г.В. Эффективно решаемые классы систем булевых уравнений. -Обозрение прикл. и промышл. матем., сер. «Дискр. матем.», 1995, т. 2, в. 3, с. 494-501.

7. Балакин Г.В., Никольский Ю.Б. Последовательное применение метода максимума правдоподобия к решению систем уравнений с мешающими параметрами. Обозрение прикл. и промышл. матем., сер. «Дискр. матем.», 1995, т. 2, в. 3, с. 468-476.

8. Балакин Г.В., Никонов В.Г. Методы сведения булевых уравнений к системам пороговых соотношений. Обозрение прикл. и промышл. матем., сер. «Дискр. матем.», 1994, т. 1, в. 3, с. 389-401.

9. Барздинь Я.М., Трахтенброт Б.А. Конечные автоматы (поведение и синтез). -М., 1970.

10. Большее Л.Н., Смирнов Н.В. Таблицы математической статистики. М.: Наука,1983.

11. Боровков A.A. Математическая статистика. Оценка параметров, проверка гипотез. Новосибирск: Наука, 1984.

12. Гаврилкевич М. Введение в нейроматематику. Обозрение прикл. и промышл. матем., сер. «Дискр. матем.», 1994, т. 1, в. 3, с. 377-388.

13. Глухов М.М., Ремизов А.Б., Шапошников В.А. Обзор по теории к-значных функций. Справочное пособие. -М.: в/ч 33965, 1988.

14. Григорьев В.Р. Нейронные сети и клеточные автоматы. Обозрение прикл. и промышл. матем., сер. «Дискр. матем.», 1994, т. 1, в. 3, с. 357-376.

15. Дертоузос М. Пороговая логика. М.: Мир, 1967.

16. Журавлев Ю.И., Финкелынтейн Ю.Ю. Локальные алгоритмы для задач линейного целочисленного программирования. — Пробл. кибер., 1965, 14, с. 289-295.

17. Зуев Ю.А. Пороговые функции и пороговые представления булевых функций. -Математические вопросы кибернетики, 1994, 5, с. 5-61.

18. Колесников О.В. Использование запретов двоичных функций при решении систем уравнений. Обозрение прикл. и промышл. матем., сер. «Дискр. матем.», 1995, т. 2, в. 3, с. 483-493.

19. Копытцев В.А. О некоторых случайных заведомо совместных системах уравнений. Обозрение прикл. и промышл. матем., сер. «Дискр. матем.», 1994, т. 1, в. 3, с. 56-84.

20. Корн Г., Корн Т. Справочник по математике для научных работников и инженеров. М.: Наука, главная редакция физико-математической литературы,1984.

21. Михайлов В.Г., Чистяков В.П. О задачах теории конечных автоматов, связанных с числом прообразов выходной последовательности. Обозрение прикл. и промышл. матем., сер. «Дискр. матем.», 1994, т. 1, в. 1, с. 7-32.

22. Нетыкшо В.Б. О некоторых вероятностных свойствах пороговых функций. -Нейрокомпьютеры: разработка, применение, 2002, № 11, с. 48-56.

23. Нетыкшо В.Б. Об одном вероятностно-статистическом подходе к анализу систем линейных псевдобулевых неравенств. Информационные технологии в проектировании и производстве, 2003, № 1, с. 79-85.

24. Нетыкшо В.Б. Об исследовании и применении вероятностных и геометрических свойств пороговых функций. Вестник Московского государственного университета леса, 2003, № 1(26), с. 102-112.

25. Нетыкшо В.Б. О некоторых вероятностных свойствах мажоритарных функций. Техника машиностроения, 2004, № 1, в печати.

26. Нетыкшо В.Б. О вероятностно-статистическом подходе к анализу систем линейных неравенств специального вида. В кн.: Тез. докл. IV Всероссийского симпозиума по прикладной и промышленной математике. Весенне-летняя сессия. 2003, т. 10, в. 2, с. 504-505.

27. Нетыкшо В.Б. О вероятностно-статистическом подходе к анализу систем линейных неравенств более общего вида. В кн.: Тез. докл. IV Всероссийского симпозиума по прикладной и промышленной математике. Весенне-летняя сессия. 2003, т. 10, в. 2, с. 503.

28. Никонов В.Г. Пороговые представления булевых функций. Обозрение прикл. и промышл. матем., сер. «Дискр. матем.», 1994, т. 1, в. 3, с. 402-457.

29. Никонов В.Г. Классификация минимальных базисных представлений всех булевых функций от четырех переменных. Обозрение прикл. и промышл. матем., сер. «Дискр. матем.», 1994, т. 1, в. 3, с. 458-545.

30. Никонов В.Г., Рыбников К.К. Применение полиэдральных методов в прикладных математических задачах, сводящихся к анализу и решению систем линейных неравенств. Вестник Московского государственного университета леса, 2003, №2, с. 81-85.

31. Прохоров Ю.В., Розанов Ю.А. Теория вероятностей. М.: Наука, 1987.

32. Рыбашов М.В., Дудников Е.Е. Градиентные методы решения линейных равенств, неравенств и задач линейного программирования на ABM. — М.: Советское радио, 1970.

33. Рыбников К.К. Схемы функционирования формальных нейронов в нейрокомпьютерных сетях как модели анализа множества решений системы булевых уравнений. Вестник Московского государственного университета леса, 2003, № 2, с. 85-77.

34. Рыбников К.К., Никонов В.Г. Прикладные задачи, сводящиеся к анализу и решению систем линейных неравенств. Метод разделяющих плоскостей. -Вестник Московского государственного университета леса, 2002, № 2(22), с. 191-195.

35. Сачков В.Н. Комбинаторные методы дискретной математики. — М.: Наука, 1977.

36. Сачков В.Н. Введение в комбинаторные методы дискретной математики. М.: Наука, 1982.

37. Смирнов В.Г. Системы булевых уравнений рекуррентного типа. Обозрение прикл. и промышл. матем., сер. «Дискр. матем.», 1995, т. 2, в. 3, с. 477-482.

38. Феллер В. Введение в теорию вероятностей и ее приложения.- М.: Мир, 1984.

39. Фихтенгольц Г.М. Основы математического анализа. Т. I, И. Учебник. 7-е изд.- М.: Физматлит, 2002.

40. Хачиян Л.Г. Полиномиальные алгоритмы в линейном программировании. — Журнал вычислительной математики и математической физики, 1980, № 1(20), с. 51-68.

41. Хачиян Л.Г. Полиномиальный алгоритм в линейном программировании. — Докл. АН СССР, 1979, т. 244, № 5 , с. 1093-1096.

42. Черникова Н.В. Алгоритм для нахождения общей формулы неотрицательных решений системы линейных неравенств. Выч. Матем. Физ., 1965, т. 5, № 2, с. 334-337.

43. Шурупов А.Н. О функциональной разделимости булевых пороговых функций.- Дискретная математика, 1994, т. 9, в. 2, с. 59-73.