Читать онлайн «Математические вопросы кибернетики. Выпуск 12»

МАТЕМАТИЧЕСКИЕ ВОПРОСЫ КИБЕРНЕТИКИ Под редакцией О. Б. ЛУПАНОВА ВЫПУСК 12 Ш МОСКВА ФИЗМАТЛИТ 2003 УПК SI9 6 fO82^ (( Издание осуществлено при поддержке ББК 22 1*8 F^ctpM! Российского фонда фундаментальных JJ исследований по проекту 03-01-14148 Сборники «Математические вопросы кибернетики» выпускаются под общим руководством Отделения математики РАН с 1988 г. В СОСТАВЛЕНИИ И РЕДАКТИРОВАНИИ СБОРНИКА ПРИНИМАЛИ УЧАСТИЕ: Н. А. КАРПОВА, О. С. КУЛАГИНА, Ю. И. ЯНОВ Математические вопросы кибернетики. Вып. 12: Сборник статей / Под ред. О. Б. Лупанова. - М. : Физматлит, 2003. - 304 с. - ISBN 5-9221-0498-5. Сборник продолжает (с 1988 г. ) математическую направленность всемирно известной се- серии «Проблемы кибернетики». Представленные в выпуске работы охватывают широкий спектр проблем дискретной математики, математической логики, теории программирования, сложно- сложности и надежности управляющих систем, криптографии. Выпуск 11 — 2002 г. Для специалистов, аспирантов, студентов, интересующихся современным состоянием ма- математической кибернетики и ее приложений. Научное издание МАТЕМАТИЧЕСКИЕ ВОПРОСЫ КИБЕРНЕТИКИ Выпуск 12: Сборник статей Под редакцией О. Б. Лупанова Редакторы М. И. Гринчук, К. А. Зыков, А. А. Ошемков, Е. Ю. Ходан Компьютерная верстка М. И. Гринчука, К. А. Зыкова, А. А. Ошемкова Оригинал-макет подготовлен с использованием издательской системы ЛР №071930 от 06. 07. 99. Подписано к печати 25. 12. 2003. Формат 70x108/16. Бумага офсетная. Гарнитура литературная. Печать офсетная. Усл. печ. л. 26,7. Уч. -изд. л. 29,22. Тираж 400 экз. Заказ № Издательская фирма «Физико-математическая литература» 117864 Москва, ул. Профсоюзная, 90 Отпечатано с диапозитивов в ОАО «Чебоксарская типография № 1» 428019, г. Чебоксары, пр. И. Яковлева, 15 © О. Б. Лупанов, Н. А. Карпова, О. С. Кулагина, ISBN 5-9221-0498-5 Ю. И. Янов, составители, 2003 СОДЕРЖАНИЕ A. А. Сапоженко. Доказательство гипотезы Камерона — Эрдеша о числе множеств, свободных от сумм 5 С. С. Марченков. Дискриминаторные классы трехзначной логики 15 Е. А. Орехова. Об одном критерии неявной полноты в трехзначной логике 27 С. В. Архангельский, Н. П. Редькин. О кодировании цифровых сигналов 75 М. С. Ярыкина. Применение оценок для сумм биномиальных коэффициентов при ре- решении некоторых задач теории кодирования и криптографии 87 Р. М. Колпаков. О дискретных преобразованиях конечных распределений с рациональ- рациональными вероятностями 109 B. О. Мантуров. Комбинаторные вопросы теории виртуальных узлов 147 О. Б. Лупанов. О сложности моделирования степеней булевых (п, п)-функций ... . 179 Н. П. Редькин. Единичные проверяющие тесты для схем при инверсных неисправностях элементов 217 A. В. Чашкин. Об одном методе вычисления частичных булевых функций 231 B. Н. Чубариков. О сложности некоторых классов чисел 247 Ф. П. Васильев. Методы решения неустойчивых задач минимизации 253 Р. И. Подловченко, Б. А. Долгих. Двухступенчатое моделирование программ с про- процедурами 283 КРАТКИЕ СООБЩЕНИЯ Ю. А. Виноградов. К синтезу трехзначных МОП-структур 301 ХРОНИКА XIV Международная школа-семинар «Синтез и сложность управляющих систем» . . . 303 Серия «Математические вопросы кибернетики» предназначена для пуб- публикации оригинальных и обзорных статей, относящихся или примыкающих к следующим направлениям: — теория функциональных систем, — теория графов, — теория кодирования, — комбинаторный анализ, — дискретная оптимизация, — синтез и сложность управляющих систем, — математическая теория эквивалентных преобразований и логиче- логического вывода в формальных системах, — построение систем автоматического доказательства теорем и автоматизация математических методов решения задач, — методы построения надежных схем из ненадежных элементов, — теория игр, — математическое программирование, — исследование операций и оптимальное управление, — теория автоматов, — математические вопросы теории вычислений, — построение и изучение моделей естественных и искусствен- искусственных языков, — математические вопросы распознавания, — математическое моделирование в биологии и медицине, — вероятностные методы в математической кибернетике.