О НОВОМ АЛГОРИТМЕ ХАРАКТЕРИЗАЦИИ k-ЗНАЧНЫХ ПОРОГОВЫХ ФУНКЦИЙ
(Стр. 7-14)

Подробнее об авторах
Бурделёв Александр Владимирович ст. преподаватель кафедры математического моделирования и анализа данных факультета прикладной математики и информатики
Белорусский государственный университет Никонов Владимир Глебович доктор технических наук, профессор, член Президиума Российской академии естественных наук.
Российская академия естественных наук
Москва, Российская Федерация
Чтобы читать текст статьи, пожалуйста, зарегистрируйтесь или войдите в систему
Аннотация:
В статье изучены известные подходы к характеризации булевых и k-значных пороговых функций. Предложен новый алгоритм характеризации k-значных пороговых функций, для которого используются, введенные в предыдущих работах авторов, коэффициенты роста и возрастания для первичной аппроксимации коэффициентов линейной формы. Приведены результаты экспериментального сравнения нового алгоритма с известным алгоритмом Обрадовича.
Образец цитирования:
Бурделёв А.В., Никонов В.Г., (2017), О НОВОМ АЛГОРИТМЕ ХАРАКТЕРИЗАЦИИ K-ЗНАЧНЫХ ПОРОГОВЫХ ФУНКЦИЙ. Computational nanotechnology, 1: 7-14.
Список литературы:
Коробков В. К. Оценка числа монотонных функций алгебры логики и сложности алгоритма отыскания разрешающего множества для произвольной монотонной функции алгебры логики // Доклады Академии Наук СССР. -1963. - Т. 150, № 4. - С. 744-747.
Коробков В. К., Резник Т. Л. О некоторых алгоритмах вычисления монотонных функций алгебры логики // Доклады Академии Наук СССР. -1962. - Т. 147, № 5. - С. 1022-1025.
Бутаков Е.А. Методы синтеза релейных устройств из пороговых элементов // - Москва: Энергия, 1970.
Дертоузос М. Пороговая логика // - Москва: Мир, 1967.
В.И. Беляков-Бодин и С.И. Розенблит Исследование некоторых вопросов синтеза пороговых функций // - М. Институт теоретической и экспериментальной физики Гос. Комитета по использованию атомной энергии СССР, 1972.
Розенблатт Ф. Принципы нейродинамики. Перцептроны и теория механизмов мозга//- Москва: Мир, 1963.
Минский М., Паперт С. Персептроны // - Москва: Мир, 1971.
Хачиян Л.Г. Полиномиальные алгоритмы в линейном программировании // «Журнал вычислительной математики и математической физики», 1980, Т 20.
Золотых Н.Ю. Расшифровка пороговых и близких к ним функций многозначной логики. Диссерт. канд. физ.-мат. наук. / Нижегородский государственный университет им. Н.И. Лобачевского, Нижний Новгород, 1998.
Золотых Н.Ю. Расшифровка пороговых и близких к ним функций. Диссерт. докт. физ.-мат. наук. ФГБУН Институт математики им.С.Л.Соболева СО РАН, Москва, 2013.
Nick Littlestone. Learning Quickly When Irrelevant Attributes Abound: A New Linear-Threshold Algorithm. Machine Learning. April 1988, Volume 2, Issue 4, pp 285-318.
Obradovic, Z. and Parberry, I. (1990) "Learning with Discrete Multi-Valued Neurons," Machine Learning: Proc. 7th Int'l. Conf., ed. B. W. Porter and R.J. Mooney, Austin, TX, Morgan-Kaufmann, pp. 392-399.
Obradovic, Z. (1990) "Learning with Discrete Multi-Valued Neurons," Machine Learning: Proc. 7th Int'l. Conf., ed. B. W. Porter and R.J. Mooney, Austin, TX, Morgan-Kaufmann, pp. 392-399.
Ngom A., Synthesis of Multiple-Valued Logic Functions by Neural Networks, Ph.D. Thesis Dissertation, Computer Science Department, University of Ottawa, Ontario, October 1998.
Anthony M. Learning Multivalued Multithreshold Functions. CDAM Research Report LSE-CDAM-2003-03, January 2003.
Grove A.J., Littlestone N., Schuurmans D. General Convergence Results for Linear Discriminant Updates. Machine Learning, 43, 173-210, 2001.
Chow C. On the characterization of threshold functions. In Proceedings of the Symposium on Switching Circuit Theory and Logical Design (FOCS), pages 34-38, 1961.
O’Donnell R., Servedio R.A. The Chow parameters problem. In STOC, pages 517-526. 2008.
Anindya De, Diakonikolas Ilias. Nearly optimal solutions for the Chow Parameters Problem and low-weight approximation of halfspaces. Journal of the ACM (JACM). Volume 61 Issue 2, April 2014.
Бурделёв А.В., Никонов В.Г. О построении аналитического задания k-значной пороговой функции. Computational nanotechnology. Выпуск № 2 / 2015.
Бурделев А.В., Никонов В.Г., Лапиков И.И. Распознавание параметров узла защиты информации, реализованного пороговой k-значной функцией // Труды СПИИРАН. 2016. Вып. 46. C. 108-127.
Karmarkar N. «A New Polynomial Time Algorithm for Linear Programming», Combinatorica, Vol. 4, nr. 4, p. 373-395, 1984.
Филатов А. Ю. Развитие алгоритмов внутренних точек и их приложение к системам неравенств. Диссерт. канд. физ.-мат. наук. / Иркутский государственный университет, Иркутск, 2001.
Ключевые слова:
пороговая функция, k-значная логика, характеризация пороговых функций, коэффициенты роста, коэффициенты возрастания.