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

МАТЕМАТИЧЕСКИЕ ВОПРОСЫ КИБЕРНЕТИКИ Под редакцией О. Б. Российского фонда фундаментальных JJ исследований по проекту 04-01-14085 Сборники «Математические вопросы кибернетики» выпускаются под общим руководством Отделения математики РАН с 1988 г. В СОСТАВЛЕНИИ И РЕДАКТИРОВАНИИ СБОРНИКА ПРИНИМАЛИ УЧАСТИЕ: Н. А. КАРПОВА, О. С. КУЛАГИНА, Ю. И. ЯНОВ Математические вопросы кибернетики. Вып. 13: Сборник статей / Под ред. О. Б. Лупанова. - М. : Физматлит, 2004. - 304 с. - ISBN 5-9221-0043-2. Сборник продолжает (с 1988 г. ) математическую направленность всемирно известной се- серии «Проблемы кибернетики». Представленные в выпуске работы охватывают широкий спектр проблем дискретной математики, математической логики, сложности и надежности управля- управляющих систем, криптографии, теории распознавания. Выпуск 12 — 2003 г. Для специалистов, аспирантов, студентов, интересующихся современным состоянием ма- математической кибернетики и ее приложений. Научное издание МАТЕМАТИЧЕСКИЕ ВОПРОСЫ КИБЕРНЕТИКИ Выпуск 13: Сборник статей Под редакцией О. Б. Лупанова Редакторы М. И. Гринчук, К. А. Зыков, А. А. Ошемков, Е. Ю. Ходан Компьютерная верстка М. И. Гринчука, К. А. Зыкова, А. А. Ошемкова Оригинал-макет подготовлен с использованием издательской системы ЛР №071930 от 06. 07. 99. Подписано к печати 1. 12. 2004. Формат 70x108/16. Бумага офсетная. Гарнитура литературная. Печать офсетная. Усл. печ. л. 26,7. Уч. -изд. л. 29,22. Тираж 400 экз. Заказ № Издательская фирма «Физико-математическая литература» МАИК «Наука/Интерпериодика» 117997, Москва, ул. Южнопортовая, 24 © О. Б. Лупанов, Н. А. Карпова, О. С. Кулагина, ISBN 5-9221-0043-2 Ю. И. Янов, составители, 2004 СОДЕРЖАНИЕ К. В. Воронцов. Комбинаторный подход к оценке качества обучаемых алгоритмов. ... 5 В. М. Фомичев. О периодах усложненных последовательностей 37 Ю. В. Нестеренко. О проверке чисел на простоту 41 О. С. Тарасова. Классы функций трехзначной логики, замкнутые относительно операций суперпозиции и перестановок 59 А. А. Часовских. Замкнутые классы линейно-автоматных функций 113 Ф. М. Аблаев. О сложности классических квантовых моделей вычислений 137 Т. В. Андреева. Развитие метода граничных функционалов и его приложение к комбина- комбинаторным задачам 147 Р. Ф. Сафин. О соотношении между глубиной и сложностью формул для предполных классов /г-значной логики 223 А. В. Кондратов. Асимптотческие оценки высокой степени точности для сложности реа- реализации функций, связанных с автоматными языками, в некоторых классах схем . 279 КРАТКИЕ СООБЩЕНИЯ А. А. Сапоженко, Н. В. Сумкина. О тупиковых доопределениях частичных монотонных функций 289 ХРОНИКА Семинар по кибернетике в МГУ 295 Серия «Математические вопросы кибернетики» предназначена для пуб- публикации оригинальных и обзорных статей, относящихся или примыкающих к следующим направлениям: — теория функциональных систем, — теория графов, — теория кодирования, — комбинаторный анализ, — дискретная оптимизация, — синтез и сложность управляющих систем, — математическая теория эквивалентных преобразований и логиче- логического вывода в формальных системах, — построение систем автоматического доказательства теорем и автоматизация математических методов решения задач, — методы построения надежных схем из ненадежных элементов, — теория игр, — математическое программирование, — исследование операций и оптимальное управление, — теория автоматов, — математические вопросы теории вычислений, — построение и изучение моделей естественных и искусствен- искусственных языков, — математические вопросы распознавания, — математическое моделирование в биологии и медицине, — вероятностные методы в математической кибернетике.