Распознавание параметров узла защиты информации, реализованного пороговой k-значной функцией
Ключевые слова:
пороговая k-значная функция, пороговая логика, метод эллипсоидов, характеризация пороговой функцииАннотация
В статье рассматриваются некоторые подходы к распознаванию параметров пороговых k-значных функций, которые могут быть использованы для построения узлов обработки и защиты информации. Основное внимание сосредоточено на проблеме доказательства принадлежности некоторой k-значной функции к классу пороговых. Для решения этого вопроса предлагается использовать вводимые коэффициенты роста и возрастания, с помощью которых процедурно аппроксимируются коэффициенты линейной формы k-значной пороговой функции. На ряду с предложенным аналитическим подходом в статье рассматривается алгоритмический метод, основанный на сведении задачи нахождения порогового представления k-значной функции к системе линейных неравенств, для решения которой применяется модифицированный метод эллипсоидов Хачияна. На основании экспериментов проводится сравнительный анализ предложенных методов.Литература
1. Бутаков Е.А. Методы синтеза релейных устройств из пороговых элементов // М: Энергия. 1970. 328 с.
2. Дертоузос М. Пороговая логика // М.: Мир. 1967. 344 с.
3. Зуев А.Ю. Пороговые функции и пороговые представления булевых функций // Математические вопросы кибернетики. 1994. № 5. С. 5–61.
4. Никонов В.Г. Пороговые представления булевых функций // Обозрение прикл. и промышл. матем. 1994. Вып. 1. № 3. С. 458–545.
5. Никонов В.Г., Никонов Н.В. Особенности пороговых представлений k значных функций // Труды по дискр. матем. 2008. Вып. 11. №. 1. С. 60–85.
6. Вальцев В.Б., Григорьев В.Р., Никонов В.Г. Некоторые структурные принципы организации высших функций мозга // Нейрокомпьютер как основа мыслящих ЭВМ. 1993. С. 38–46.
7. Хачиян Л.Г. Полиномиальные алгоритмы в линейном программировании // ЖВМиМФ. 1980. Вып. 20. № 1. С. 51–68.
8. Золотых Н.Ю. Расшифровка пороговой функции, заданной расширенным оракулом // Вестник Нижегородского университета им. Н.И. Лобачевского. 2012. № 3(1). С. 175–178.
9. Хачиян Л.Г. Полиномиальный алгоритм в линейном программировании // Докл. АН СССР. 1978. Вып. 244. № 5. С. 1093–1096.
10. Кудрявцев В.Б. Теория тестового распознавания // Дискретная математика. 2006. Вып. 18. № 3. С. 3–34.
11. Winder R.O. The status of threshold logic // RCA Review. 1969. vol. 30. no. 1. pp. 62–84.
12. Золотых Н.Ю. Расшифровка пороговых и близких к ним функций многозначной логики: Автореферат диссертации на соискание ученой степени канд. физ.-мат. наук. Нижний Новгород: Нижегородский гос. университет им. Н. И. Лобачевского. 1998. 12 с.
13. Загоруйко Н.Г. Прикладные методы анализа данных и знаний // Новосибирск: ИМ СО РАНю 1999. 270 с.
14. Золотых Н.Ю. О пороговых и близких к ним функциях, определенных в целочисленных точках политопа // Дискретный анализ и исследование операций: серия 1. 1998. Вып. 5. № 2. С. 40–54.
15. Кудрявцев В.Б. Теория тестового распознавания // Дискретная математика. 2006. Вып. 18. № 3. С. 3–34.
16. Журавлев Ю.И. Об алгебраическом подходе к решению задач распознавания или классификации // Проблемы кибернетики. 1978. №. 33. С. 5–68.
17. Goldberg P.W. Learning fixed-dimension linear thresholds from fragmented data // Information and Computation. 2001. vol. 171. no. 1. pp. 98–122.
18. Irmatov A.A. Arrangements of hyperplanes and the number of threshold functions // Acta Applicandae Mathematicae. 2001. vol. 68. no. 1–3. pp. 211–226.
2. Дертоузос М. Пороговая логика // М.: Мир. 1967. 344 с.
3. Зуев А.Ю. Пороговые функции и пороговые представления булевых функций // Математические вопросы кибернетики. 1994. № 5. С. 5–61.
4. Никонов В.Г. Пороговые представления булевых функций // Обозрение прикл. и промышл. матем. 1994. Вып. 1. № 3. С. 458–545.
5. Никонов В.Г., Никонов Н.В. Особенности пороговых представлений k значных функций // Труды по дискр. матем. 2008. Вып. 11. №. 1. С. 60–85.
6. Вальцев В.Б., Григорьев В.Р., Никонов В.Г. Некоторые структурные принципы организации высших функций мозга // Нейрокомпьютер как основа мыслящих ЭВМ. 1993. С. 38–46.
7. Хачиян Л.Г. Полиномиальные алгоритмы в линейном программировании // ЖВМиМФ. 1980. Вып. 20. № 1. С. 51–68.
8. Золотых Н.Ю. Расшифровка пороговой функции, заданной расширенным оракулом // Вестник Нижегородского университета им. Н.И. Лобачевского. 2012. № 3(1). С. 175–178.
9. Хачиян Л.Г. Полиномиальный алгоритм в линейном программировании // Докл. АН СССР. 1978. Вып. 244. № 5. С. 1093–1096.
10. Кудрявцев В.Б. Теория тестового распознавания // Дискретная математика. 2006. Вып. 18. № 3. С. 3–34.
11. Winder R.O. The status of threshold logic // RCA Review. 1969. vol. 30. no. 1. pp. 62–84.
12. Золотых Н.Ю. Расшифровка пороговых и близких к ним функций многозначной логики: Автореферат диссертации на соискание ученой степени канд. физ.-мат. наук. Нижний Новгород: Нижегородский гос. университет им. Н. И. Лобачевского. 1998. 12 с.
13. Загоруйко Н.Г. Прикладные методы анализа данных и знаний // Новосибирск: ИМ СО РАНю 1999. 270 с.
14. Золотых Н.Ю. О пороговых и близких к ним функциях, определенных в целочисленных точках политопа // Дискретный анализ и исследование операций: серия 1. 1998. Вып. 5. № 2. С. 40–54.
15. Кудрявцев В.Б. Теория тестового распознавания // Дискретная математика. 2006. Вып. 18. № 3. С. 3–34.
16. Журавлев Ю.И. Об алгебраическом подходе к решению задач распознавания или классификации // Проблемы кибернетики. 1978. №. 33. С. 5–68.
17. Goldberg P.W. Learning fixed-dimension linear thresholds from fragmented data // Information and Computation. 2001. vol. 171. no. 1. pp. 98–122.
18. Irmatov A.A. Arrangements of hyperplanes and the number of threshold functions // Acta Applicandae Mathematicae. 2001. vol. 68. no. 1–3. pp. 211–226.
Recognizing Parameters of the Information Security Unit Implemented by the Threshold K-Valued Function
Abstract
This article discusses some approaches to the recognition of the parameters of the threshold k-valued functions, which can be used for building information processing and security units. The main focus is put on the issue of proving k-valued function belonging to the threshold class. For solving this problem it is proposed to use the input coefficients of expansion and increase. With the help of the latter, the coefficients of linear forms of the k-valued threshold function are procedurally approximated. Along with the proposed analytical approach, the article discusses an algorithmic method based on reducing the problem of finding a threshold representation of k-valued functions to the system of linear inequalities, for the solution of which the ellipsoid method, modified by Khachiyan, is applied. The comparative analysis of the proposed methods is carried out based on experiments.
Опубликован
2016-06-06
Как цитировать
Бурделев, А. В., Никонов, В. Г., & Лапиков, И. И. (2016). Распознавание параметров узла защиты информации, реализованного пороговой k-значной функцией. Труды СПИИРАН, 3(46), 108-127. https://doi.org/10.15622/sp.46.9
Раздел
Информационная безопасность
Авторы, которые публикуются в данном журнале, соглашаются со следующими условиями:
Авторы сохраняют за собой авторские права на работу и передают журналу право первой публикации вместе с работой, одновременно лицензируя ее на условиях Creative Commons Attribution License, которая позволяет другим распространять данную работу с обязательным указанием авторства данной работы и ссылкой на оригинальную публикацию в этом журнале.
Авторы сохраняют право заключать отдельные, дополнительные контрактные соглашения на неэксклюзивное распространение версии работы, опубликованной этим журналом (например, разместить ее в университетском хранилище или опубликовать ее в книге), со ссылкой на оригинальную публикацию в этом журнале.
Авторам разрешается размещать их работу в сети Интернет (например, в университетском хранилище или на их персональном веб-сайте) до и во время процесса рассмотрения ее данным журналом, так как это может привести к продуктивному обсуждению, а также к большему количеству ссылок на данную опубликованную работу (Смотри The Effect of Open Access).
