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

о

со

5 51? НИЖЕГОРОДСКИЙ ГОСУДАРСТВЕННЫЙ

сс УНИВЕРСИТЕТ им. Н. И. ЛОБАЧЕВСКОГО т

2Е

ГС?

а,

На правах рукописи

ЗОЛОТЫХ Николай Юрьевич

РАСШИФРОВКА ПОРОГОВЫХ И БЛИЗКИХ К НИМ ФУНКЦИЙ МНОГОЗНАЧНОЙ ЛОГИКИ

05.13.17 - Теоретические основы информатики

Автореферат

диссертации на соискание ученой степени кандидата физико-математических наук

Нижний Новгород, 1998

Работа выполнена на кафедре математической логики и высшей алгебры факультета вычислительной математики и кибернетики Нижегородского государственного университета им. Н.И.Лобачевского.

Научный руководитель: доктор физико-математических наук, профессор В.Н. Шевченко.

Официальные оппоненты:

доктор физико-математических наук, ведущий научный сотрудник В. К. Леонтьев;

кандидат физико-математических наук, старший научный сотрудник М. Ю. Мошков.

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

Защита состоится " _1998 г. в ^ час.

на заседании специализированного совета ССК 063.43.01 научно-исследовательского института прикладной математики и кибернетики при Нижегородском государственном университете им.Н.И.Лобачевского по адресу: 603005, Нижний Новгород, ул. Ульянова, д. 10.

С диссертацией можно ознакомиться в библиотеке НИИ ПМК. Автореферат разослан " "_СЫ1р£<МХ юдя г

Ученый секретарь специализированного совета, доктор технических наук

/к.

/ 4г

Ю. Л. Кетков

Общая характеристика работы

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

Наиболее известной проблемой из этой серии является впервые рассмотренная В. К. Коробковым и Т. Л. Резником задача расшифровки монотонных булевых и многозначных функций. Известна сводимость к последней проблеме целого класса задач математической логики, математической экономики, целочисленного линейного программирования, теории распознавания образов.

В. Н. Шевченко рассмотрел задачу расшифровки пороговых функций ¿-значной логики. Пороговые функции возникают во многих областях дискретной математики и приложениях, например, в дискретной оптимизации, теории графов, при синтезе схем из функциональных элементов, нейронных сетей, в цифровой обработке сигналов. Их можно интерпретировать как характеристические функции подмножеств множества {0,1,..., к — 1}" , обладающих специальным свойством "линейной отделимости". В связи с последней возможностью естественно стремление расширить их область определения. Значительный интерес имеют постановки задач, в которых функции определены на множестве М целочисленных решений заданной системы линейных неравенств. Функция, отображающая М в множество {0,1}, называется пороговой, если найдется гиперплоскость, разделяющая множества ее нулей и единиц (точек, в которых функция равна нулю или единице соответственно). К расшифровке таких функций сводятся специальные задачи теории распознавания образов с линейной разделяющей поверхностью. Большое значение задача расшифровки пороговых функций имеет в машинном обучении — интенсивно развивающейся теории, исследующей процессы обучения в интеллектуальных системах. Другой смежной областью является связанная с большим кругом приложений теория тестов. Таким образом, достаточно важным является целый ряд проблем, связанных с пороговыми функциями и их расшифровкой. Как пра-

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

Естественной мерой сложности алгоритма расшифровки является минимальное число вопросов, достаточное для расшифровки любой функции из заданного класса. Другой характеристикой является трудоемкость — число арифметических операций, выполненных алгоритмом в худшем случае. В.Н.Шевченко предложил алгоритм расшифровки пороговой функции fc-значной логики, имеющий при любом фиксированном п полиномиальные от log к сложность и трудоемкость. Им было также показано, что полиномиального от п алгоритма, решающего данную задачу, не существует. Таким образом, для задачи расшифровки пороговой функции приведенные результаты заставляют ограничиться поиском алгоритмов, полиномиальных при фиксированном п. Для оценки их качества и для харак-теризации сложности всей задачи расшифровки пороговых функций необходимы результаты о близости предлагаемых алгоритмов к оптимальным. В частности, представляет интерес поиск нижних оценок сложности расшифровки. Дальнейшие результаты в этих направлениях означали бы также более глубокое исследование структурных свойств и, возможно, мощностных характеристик класса пороговых функций.

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

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

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

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

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

Апробация результатов. Результаты диссертации докладывались и обсуждались на Межгосударственных семинарах по дискретной математике и ее приложениям (Москва, 1995, 1998), на Международных конференциях "Математические алгоритмы" (Нижний Новгород, 1994, 1995), на школе-семинаре "Синтез и сложность управляющих систем" (Нижний Новгород, 1994), на Молодежной научной школе по дискретной математике и ее приложениям под руководством чл.-корр. РАН О. Б. Лупанова (Москва, 1997), на совместных семинарах кафедры математической логики и высшей алгебры ВМК ННГУ и отдела дискретной математики НИИ ПМК при ННГУ.

Публикации. По теме диссертации опубликовано 12 работ, список которых приводится в конце автореферата.

Структура и объем работы. Диссертация состоит из введения, четырех глав, приложения и списка литературы. Общий объем работы 136 машинописных страниц. Список литературы содержит 70 наименований. Основные результаты излагаются в главах 2, 3.

Краткое содержание работы

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

Глава 1 посвящена изучению основных свойств пороговых и близких к ним функций, определенных в целочисленных точках политопа. В §1.1 вводятся основные классы рассматриваемых функций и даются необходимые и достаточные условия принадлежности функций тому или иному из этих классов. Обозначим через v(tï, 1,7) множество политопов р С R™, каждый из которых можно задать системой / линейных неравенств с целочисленными коэффициентами, ограниченными по абсолютной величине числом 7; пусть М{п, l,y) = {Р П Ъп : Р G V(n,l, 7)}. Для некоторых п > .2, / > п, 7 > 2 рассмотрим множество M Е Л4(п,/,7); предположим, что M ф 0. Множество всех функций, отображающих M в {0,1}, обозначим через F(M). Пусть Ей = {0,..., к — 1}. Класс F{E%) объединяет функции булевой логики, a F(EJ?) при к > 3 является подклассом тех функций £-значной логики, множество значений которых есть {0,1}. Для / G F(M) через Мо(/) и Mi(/) обозначим множество нулей и единиц функции / соответственно, т.е. Mv(f) = {ж G M : f(x) = и} (у = 0,1). Пусть P„(f) ~ Conv M„(f), N„(f) — множество крайних точек (вершин) политопа Pv(f) (f = 0,1).

Для каждого v = 0,1 через Fv(M) будем обозначать множество таких / G F (M), для которых М„(/) можно описать в виде системы линейных неравенств Ах < ао■ Систему Ах < ао назовем характеристической. Обозначим через пг„(/) наименьшее число неравенств в системе Ах < а о, при котором возможно такое описание. Если для некоторого v G {0,1} / G FU(M) и m„(/) — 1, то функция f назы-

п

вается пороговой. Пусть для такой / неравенство ^ ajxj < ко-

¿=1

торое назовем пороговым, описывает множество Мо(/). Можно считать, что aj G Z (j = 0,1,... , n). Обозначим через FW(M) множество всех пороговых функций, заданных на M.

В § 1.2 для функций из классов Fn{M), Fq(M), F\{M) получены верхние оценки величины коэффициентов характеристической системы, а в § 1.3 — верхние оценки числа крайних точек (вершин) политопа Pi/{f)- Также в § 1.3 исследуется задача построения этих точек по заданной характеристической системе функции /.

Мощностные свойства классов FW(M), Fo(M), Fi (M) изучаются в § 1.4. Пусть V(n,y) — множество политопов Р С R", каждый из которых можно задать системой линейных неравенств с целочисленными коэффициентами, ограниченными по абсолютной величи-

не числом у,

фж(п,7) = шах \Рг(Ъп ЛР)|.

рет>(п, 7)

В диссертации установлена следующая асимптотическая по п двусторонняя оценка:

п2

~2~ 7 ~ log^I(n>7) < n3log(7^A»),

справедливая при любом 7 > 2. Соотношение классов ^(М) и Ро(М) П исследуется в § 1.5. Построенные примеры показы-

вают, что при к > 2, тг > 3 класс ЕЖ(Е^) является собственным подмножеством класса Ро(Е") П Р\(Е£). Для п = 2, к > 3 в диссертации установлено равенство () = Ро(Е1) П Р\(Е1).

В главе 2 предлагаются алгоритмы расшифровки пороговых и близких к ним функций. Пусть каждая функция / из некоторого класса Е' С ^(М) задана оракулом, позволяющим по произвольной точке х £ М определить /(аг). Под расшифровкой (неизвестной нам) функции / в классе Г' понимается последовательное обращение к оракулу в точках г^2),..., х^ из М, такое, что из соотношений /(*(!)) = д(хМ),ПхЫ) = д(хЮ),...,Г(хЮ) = д(х(% д е Р' следует /(х) = ^(х) для всех х £ М, т. е. / = д.

Пусть А — алгоритм, который для заданного системой неравенств множества М £ М(п,1,-у) расшифровывает любую заданную оракулом функцию из .Р' С Р(М). Предположим, что при расшифровке функции / € Е' алгоритм А последовательно обращается к оракулу в точках ж'1), ..., х^ и выполняет р(А, /) битовых арифметических операций. Обозначим Т(/, А) = {х^, х^2\ ..., х^}, Ти{/,А) = Т(/, Л) П М„(/) (у = 0,1). Сложностью алгоритма А называется величина г(А) = шах |Т(/, Л)|. Трудоемкостью алгоритма

Л назовем число арифметических операций, выполненных в худшем случае: р(А) = тахр(А, /). Величины т(А), р{А) являются функциями от параметров политопа Р. Алгоритм А назовем полиномиальным, если функция р{Л) ограничена некоторым полиномом от трех переменных п, /, ^7. Будем говорить, что алгоритм А полиномиален при фиксированной размерности п (квазиполиномиален), если найдется такой полином рп(£, ц), степень и коэффициенты которого зависят только от п, что р(А) < рп(1, log7). Очевидно, т(А) < р{А) и

поэтому верхняя оценка трудоемкости алгоритма является таковой и для его сложности.

В диссертации рассматриваются алгоритмы (условные тесты), в которых выбор точки для" нового обращения к оракулу, определяется ответами на предыдущие вопросы. Что же касается алгоритмов, не учитывающих ответы на предыдущие вопросы (безусловные тесты), то для рассматриваемых классов они оказываются весьма неэффективными. Множество U С М называется безусловным тестом для класса функций F', если для любых двух f,g из F', / ф д, найдется точка х £ U, такая, что f(x) ф д(х). В §2.2 показано, что классы FT(M), F0(M), Fi(M), F0{M)C\ F\(M) обладают единственным безусловным тестом U = М.

Обозначим через F(M, h) множество таких функций / £ Fo(M)C\ F\(M), для которых min {mo(/),?ni(/)} < h. В § 2.3 описывается алгоритм А\ расшифровки в классе Fq(M) C\Fi(M). В классе F(M,h) при любом фиксированном п алгоритм Л1 имеет полиномиальную от h, /, logy трудоемкость и сложность

r(Ai) < C„(/ + /l)L"/2J>/2j log("-1>L"/2J+"T,

где Сп — некоторая зависящая только от п величина. Алгоритм ,4i может быть приспособлен для распознания пороговости функции / £ Fo(M) П F\{M). Такая модификация алгоритма при любом фиксированном п является полиномиальной от I, mo(f), mi(f), log 7.

Очевидно, алгоритм Ai применим и для расшифровки в классе Flr(M). Для последнего случая однако существует более эффективный алгоритм Аг, описанный в §2.4. При любом фиксированном п предложенный алгоритм имеет полиномиальную от I и log 7 трудоемкость и сложность г(Лг) < 2n9"-16n+3/l-n/2J log"(7n). Для расшифровки пороговых функций ¿-значной логики Л2 требует не более Сп log" к обращений к оракулу, где Сп — некоторая зависящая только от п величина.

В § 2.5 для расшифровки пороговой функции Аг-значной логики, зависящей от двух переменных (класс F„(El)), удалось построить более эффективный алгоритм Аз- Алгоритм Аз имеет полиномиальную трудоемкость и совершает не более т(Аг) < 61og(fc — 1) + 4 обращений к оракулу.

В главе 3 устанавливаются нижние оценки сложности расшифровки пороговых функций. Под сложностью расшифровки в некотором классе F' С F(M) понимается величина t(F') = min т(А),

л

где минимум берется по всем алгоритмам Л расшифровки в классе F'. Другими словами, сложность расшифровки — это сложность наилучшего по числу обращений к оракулу алгоритма расшифровки в данном классе. Множество Т С М называется разрешающим для f в классе F', если для любой функции д G F', / ф д, найдется по крайней мере одна точка z £ Т, такая, что g(z) ф f(z). Разрешающее множество, никакое собственное подмножество которого не является разрешающим для /, называется тупиковым. Разрешающее множество минимальной мощности назовем минимальным. Его мощность обозначим через t(F',f). Длиной обучения назовем величину t(F') = maxt(F',f). Для любых М и F' справедливы неравенства t(F') > t(F'), t(F') > log \F'\, являющиеся ключевыми для получения в диссертации нижних оценок сложности расшифровки.

В § 3.2 получены некоторые вспомогательные результаты о строении конуса K(f) разделяющих функционалов функции / £ K(f) описывается следующей системой линейных неравенств относительно переменных од, <zi,..., a„_).i:

n

Y2ajXj<aо для всех (ib...,in) £ М0(/);

j=i < п

J2 ajXj > а0 + ага+1 для всех (гь...,1„) е Mi(/); i=i . a«+i > 0.

Показано, что конус Л'(/) полномерный (телесный) и в важном случае AffdimM = п — острый. Из теории линейных неравенств затем выводится лемма о двойственном описании конуса K(f). В частности, если AffdimM = п, то K(f) имеет единственное с точностью до положительных множителей минимальное порождающее множество (остов)

= ...,6« ¿ = 1,...,*}.

В § 3.3 исследуется структура разрешающего множества пороговой функции. Там показано, что множество Т = TqUTi, Т„ С M„(f)

(и = 0,1) является разрешающим для / Е РХ(М) тогда и только тогда, когда система неравенств

п

12а]хз<ао при всех (жь ..., хп) £ То;

3 = 1

П

£ щХ] > а0 + ап+1 при всех ..., х„) 6 Т\\ 3 = 1 . ап+1 > О

описывает конус А'(/). Отсюда выводится теорема о едиственности минимального разрешающего и тупикового множества функции / € ^(М). Обозначим его через Т(/) = Т0(/) иТ^/), Т„(/) С М„(/) (и = 0, 1).

Пусть ААИипЛ/ = п и / £ Г1Т(М). Не нарушая общности, будем считать, что в остове конуса /\'(/) > 0 при 1 = 1,..., р и = 0 при г = ¡1 + 1,... Пусть а = (<ц,. ..ап) Е

Mo(f,a) =■< {yi,...,yn) € М : = шахI ,

Mi(f,a) - < Ы,...,уп) е М : J2ajyj = ттп У] ajXj

{ fzi

Обозначим через iV„(/, а) множество крайних точек (вершин) выпуклой оболочки множества М„(/, а). Доказано, что если AffdimM =

7i, тогда для любой функции / G FT(M) _ __

T(f) = U (w, Щ и ВД 6(0)) = у (ВД, а) и ВД, а)),

» = 1 а

в последнем случае объединение берется по всем а = (ai,..., ап) 6 Z" таким, что неравенство

< max > atx; fr! 3 -x€M0U)fri 3 3

3=1 1=1

является пороговым для функции /.

На основе анализа структуры разрешающего множества, проведенного в § 3.3, в § 3.4 выводятся нижние оценки длины обучения в классе Fir(M). Доказано, что для любых п > 2 и / > п найдется такое 7о, что для всех 7 > 7о существует политоп Р 1,7) такой, что r(F,(M)) > t(Fn(M)) > b„/l"/2J log"-17, где M = Р П Z", a Dn — некоторая зависящая только от п положительная величина.

Для п>2,к>2 получено неравенство

Сп log"-2 к < t(Fn(E"k)) < С'п log"-1

где С„ и С'п — некоторые зависящие только от п положительные величины. Объединяя установленные в диссертации оценки, для любых к > 2, п > 2 получаем:

C„log"-2fc < t(F*(EZ)) < r(Fn(EZ)) < С'п logn к,

где Сп,С'п — некоторые зависящие только от положительные величины.

В § 3.5 изучается задача построения минимального разрешающего множества пороговой функции / £ М = Р П Z" £ Л4(п,1,7), по известным коэффициентам порогового неравенства и по известной системе, описывающей политоп Р. Для решения этой задача предлагается полиномиальная от log 7 и I процедура (п фиксировано). Это позволяет модифицировать алгоритм Л2 так, чтобы сложность нового алгоритма Л^ отличалась бы от сложности оптимального алгоритма расшифровки не более, чем в 0(n3 log(n7)) раз.. Для класса Ft(E%) сложность алгоритма л!'' отличается от сложности оптимального алгоритма не более, чем в 0(п2 log(nfc)) раз.

В §3.6 рассматривается случай пороговых функций двух переменных. Разрыв в показателе степени log А: из оценки сложности расшифровки таких функций удалось устранить. Показано, что при к —► оо выполняются следующие асимптотические неравенства:

4\ogk<r(F4El))<6logk.

Для величины f(iv(£|)) установлено точное значение: t(Ft(E\)) = 4 при к > 2.

Пороговые булевы функции рассматриваются в §3.7. Справедливо следующее равенство:

t(F4EZ)) = r(F4E?)) = \E%\ = 2n.

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

В главе 4 показана связь задачи расшифровки пороговой функции двух переменных с проблемой нахождения диофантовых приближений вещественных чисел. Рассмотрим следующую задачу. Для а£Н,О1>0,(2€М требуется среди всех рациональных дробей со

знаменателем, не превосходящим <5, найти наилучшее приближение | к а:

Предположим, что вещественное число а задано оракулом, позволяющим по произвольному г £ <3 определить, выполняется или нет неравенство а < г. В §4.2 показано, как использовать алгоритм Аз для решения задачи наилучшего приближения к заданному таким образом числу. Время работы построенной процедуры ограничено полиномом от \oglc, где к = шах {С}. [а<5]}. В §4.3 на основе полученных результатов строится полиномиальный алгоритм нахождения наилучших приближений алгебраических вещественных чисел, заданных минимальным многочленом.

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

Основные результаты

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

а —

Р Я

= тт

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

3) Для пороговых функций fc-значной логики описано строение разрешающего множества и найдена двусторонняя оценка длины обучения.

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

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

Основные результаты диссертации опубликованы в следующих работах:

1. Золотых Н. Ю. Алгоритм расшифровки пороговой функции на плоскости с трудоемкостью 0(log" к). - Н. Новгород: Нижегородский гос. ун-т, 1994 / Деп. ВИНИТИ 28.04.94. №1062-В94. - 11с.

2. Золотых Н. Ю. Алгоритм расшифровки пороговой функции к-значной логики на плоскости с числом обращений к оракулу 0(log к) // Труды Первой Международной конференции "Математические алгоритмы". - Н.Новгород: Изд-во Нижегородского ун-та, 1995. -С. 21-26.

3. Золотых Н. Ю. О сложности расшифровки пороговых функций // Второй Сибирский Конгресс по Прикладной и Индустриальной математике. Тезисы докладов. Часть II. - Новосибирск: ин-т м-ки СО РАН, 1996.-С. 115

4. Золотых Н. Ю. Программная реализация алгоритма Моцкина-Бургера построения остова многогранного конуса и ее применение // Труды 2-ой международной конференции "Математические алгоритмы" / Под ред. М.А.Антонца, В.Е.Алексеева, В.Н.Шевченко. - Н. Новгород: изд-во Нижегородского ун-та, 1997. - С. 72-74

5. Золотых Н.Ю. О сложности расшифровки пороговых функций // Информационный бюллетень Ассоциации математического программирования N 7. X Всероссийская конференция "Математи-

ческое программирование и приложения" (тезисы докладов). - Екатеринбург: Уро РАН, 1997. - С. 107-108.

6. Золотых Н. Ю., Шевченко В. Н. О сложности расшифровки пороговых функций // Дискретный анализ и исследование операций. Тезисы докладов на Школе-семинаре "Синтез и сложность управляющих систем". - 1995. - Т. 2, № 1. - С. 72-73.

7. Золотых Н. Ю., Шевченко В. Н. Расшифровка пороговых функций ¿-значной логики // Дискретный анализ и исследование операций. - 1995. - Т. 2, № 3. - С. 18-23.

8. Шевченко В. Н., Золотых Н. Ю. Квазиполиномиальный алгоритм расшифровки пороговой функции ¿-значной логики // Информационный бюллетень Ассоциации математического программирования. Вып.5. IX Всероссийская конференция "Математическое программирование и приложения" (тезисы докладов). - Екатеринбург: УрО РАН, 1995. - С. 199-200.

9. Шевченко В. Н., Золотых Н. Ю. О сложности расшифровки пороговых функций &-значной логики // Тезисы докладов на XI Международной конференции по проблемам теоретической кибернетики / Под ред. С.В.Яблонского. - Ульяновск: изд-во СВНЦ, 1996. -С.204-205.

10. Шевченко В. Н., Золотых Н. Ю. Расшифровка пороговых и близких к ним функций, заданных на целочисленных точках политопа. // Труды 2-ой международной конференции "Математические алгоритмы" / Под ред. М.А.Антонца, В.Е.Алексеева, В.Н.Шевченко. - Н.Новгород: изд-во Нижегородского ун-та, 1997. - С.179-

11. Шевченко В. Н., Золотых Н. Ю. О сложности расшифровки пороговых функций fc-значной логики // Доклады Российской Академии наук, (в печати)

12. Shevchenko V. N., Zolotykh N. Y. Decoding of threshold functions defined on integer points of a poly tope // Pattern recognition and image analysis. - 1997.- Vol. 7, No. 2. - P. 235-240.

180