Томский государственный университет
УЧРЕДИТЕЛЬ
РЕДАКЦИОННАЯ КОЛЛЕГИЯ ЖУРНАЛА
«ПРИКЛАДНАЯ ДИСКРЕТНАЯ МАТЕМАТИКА»
Агибалов Г. П., д-р техн. наук, проф. (главный редактор); Девянин П. Н., д-р техн. наук,
чл.-корр. Академии криптографии РФ (зам. гл. редактора); Черемушкин А. В., д-р
физ.-мат. наук, чл.-корр. Академии криптографии РФ (зам. гл. редактора); Панкратова
И. А., канд. физ.-мат. наук, доц. (отв. секретарь); Алексеев В. Б., д-р физ.-мат.
наук, проф.; Бандман О. Л., д-р техн. наук, проф.; Быкова В. В., д-р физ.-мат. наук,
проф.; Глухов М. М., д-р физ.-мат. наук, академик Академии криптографии РФ;
Евдокимов А. А., канд. физ.-мат. наук, проф.; Колесникова С. И., д-р техн. наук;
Крылов П. А., д-р физ.-мат. наук, проф.; Логачев О. А., канд. физ.-мат. наук, доц.;
Мясников А.Г., д-р физ.-мат. наук, проф.; Романьков В.А., д-р физ.-мат. наук, проф.;
Салий В. Н., канд. физ.-мат. наук, проф.; Сафонов К. В., д-р физ.-мат. наук, доц.;
Фомичев В. М., д-р физ.-мат. наук, проф.; Харин Ю.С., д-р физ.-мат. наук, чл.-корр.
НАН Беларуси; Чеботарев А. Н., д-р техн. наук, проф.; Шоломов Л. А., д-р физ.-мат.
наук, проф.
Адрес редакции и издателя: 634050, г. Томск, пр. Ленина, 36
E-mail: vestnik_pdm@mail.tsu.ru
аспирантов, в области дискретной математики и её приложений в криптографии,
компьютерной безопасности, кибернетике, информатике, программировании,
теории надёжности, интеллектуальных системах.
В журнале публикуются результаты фундаментальных и прикладных научных
исследований отечественных и зарубежных ученых, включая студентов и
Периодичность выхода журнала: 4 номера в год.
Редактор Н. И. Шидловская
Верстка И. А. Панкратовой
Подписано к печати 20.09.2017. Формат 60 Ч 841
Заказ № 2743. Цена свободная. Дата выхода в свет 04.10.2017.
Отпечатано на оборудовании
8 . Усл. п. л. 14,55. Тираж 300 экз.
Издательского Дома Томского государственного университета
634050, г. Томск, пр. Ленина, 36
Тел.: 8(3822)53-15-28, 52-98-49
Стр.2
ПРИКЛАДНОЙ ДИСКРЕТНОЙ МАТЕМАТИКИ
СОДЕРЖАНИЕ
ТЕОРЕТИЧЕСКИЕ ОСНОВЫ
Анохин М.И. О двух определениях степени функции над ассоциативным коммутативным
кольцом ................................................................................. 5
Novoselov S. A. Hyperelliptic curves, Cartier — Manin matrices and Legendre polynomials 20
МАТЕМАТИЧЕСКИЕ МЕТОДЫ КРИПТОГРАФИИ
Коренева А.М. О примитивности перемешивающих орграфов биективных регистров
сдвига с двумя обратными связями .................................................... 32
Романьков В. А., Обзор А. А. Общая алгебраическая схема распределения
криптографических ключей и её криптоанализ ................................................ 52
МАТЕМАТИЧЕСКИЕ ОСНОВЫ НАДЁЖНОСТИ ВЫЧИСЛИТЕЛЬНЫХ
И УПРАВЛЯЮЩИХ СИСТЕМ
Алехина М. А., Барсукова О.Ю. Оценки ненадёжности схем в базисе Россера
—Туркетта (в P3) при неисправностях типа 0 на выходах элементов ................. 62
МАТЕМАТИЧЕСКИЕ ОСНОВЫ ИНФОРМАТИКИ
И ПРОГРАММИРОВАНИЯ
Егорушкин О.И., Колбасина И. В., Сафонов К. В. О применении многомерного
комплексного анализа в теории формальных языков и грамматик............. 76
Костюк Ю.Л. Эффективная трансляция для LL(1)-грамматики на примере
языка программирования ........................................................................... 90
Рыбалов А. Н. О генерической сложности проблемы разрешимости систем диофантовых
уравнений в форме Сколема......................................................... 100
Тарков М.С. Редукция связей автоассоциативной памяти Хопфилда ...................... 107
ВЫЧИСЛИТЕЛЬНЫЕ МЕТОДЫ В ДИСКРЕТНОЙ МАТЕМАТИКЕ
Быкова В. В., Солдатенко А. А. Оптимальная маршрутизация по ориентирам
в нестационарных сетях ............................................................................. 114
СВЕДЕНИЯ ОБ АВТОРАХ ............................................................................ 124
Стр.3
CONTENTS
THEORETICAL BACKGROUNDS OF APPLIED DISCRETE MATHEMATICS
Anokhin M. I. On the two definitions of degree of a function over an associative,
commutative ring ...................................................................................... 5
Novoselov S. A. Hyperelliptic curves, Cartier — Manin matrices and Legendre
polynomials ............................................................................................ 20
MATHEMATICAL METHODS OF CRYPTOGRAPHY
Koreneva A.M. On primitivity of mixing digraphs associated with 2-feedbacks
shift registers ........................................................................................... 32
Roman’kov V. A., Obzor A. A. General algebraic cryptographic key exchange
scheme and its cryptanalysis ........................................................................ 52
MATHEMATICAL BACKGROUNDS OF COMPUTER
AND CONTROL SYSTEM RELIABILITY
Alekhina M. A., Barsukova O.Yu. Estimations of unreliability of circuits
in Rosser — Turkett basis (in P3) with faults of type 0 at the outputs of gates ........... 62
MATHEMATICAL BACKGROUNDS OF INFORMATICS
AND PROGRAMMING
Egorushkin O. I., Kolbasina I. V., Safonov K. V. On application of multidimensional
complex analysis in formal language and grammar theory ........................ 76
Kostyuk Yu. L. Effective translation for LL(1)-grammar in the example of a programming
language ................................................................................... 90
Rybalov A. N. On generic complexity of decidability problem for diophantine systems
in the Skolem’s form ........................................................................... 100
Tarkov M. S. Reduction of synapses in the Hopfield autoassociative memory ................ 107
COMPUTATIONAL METHODS IN DISCRETE MATHEMATICS
Bykova V. V., Soldatenko A. A. Optimal routing by landmarks in the timedependent
networks ................................................................................... 114
BRIEF INFORMATION ABOUT THE AUTHORS ................................................. 124
Стр.4