Читать онлайн «Кибернетический сборник. Новая серия. Выпуск 26»

КИБЕРНЕТИЧЕСКИЙ СБОРНИК ВЫП. 26 Кибернетический сборник НОВАЯ СЕРИЯ ВЫПУСК 26 Сборник статей Перевод с английского под редакцией О. Б. ЛУПАНОВА И О. М. КАСИМ-ЗАДЕ МОСКВА «МИР» 1989 ББК 32. 81 К38 УДК 519. 95 Кибернетический сборник. Новая серия. Вып. 26. Сб. К38 статей: Пер. с англ. — М. : Мир, 1989. — 208 с, ил. ISBN 5-03-000998-1 Продолжение серии, начатой издательством «Мир» в 1965 г. В выпуске содержатся обзорные статьи и оригинальные работы известных зарубежных ученых по наиболее актуальным проблемам теоретической кибернетики и ее приложениям. Большой интерес представляют статьи Г. Вьенно и М. Делеста (Франция) по перечислительным задачам с приложениями в биологии и физике, а также статьи по сложности вычислений Л. Стокмейера (США) и Л. Тейрлинка (Нидерланды), по функциональному программированию М. Бисона (США), обзор по математическим вопросам проектирования БИС. Тейрлинк2) Изучаются некоторые классы объектов, являющихся обобщениями /-схем и ортогональных таблиц. С их использованием для всех / строятся нетривиальные /-схемы без кратных блоков. § 1. СХЕМЫ И ТАБЛИЦЫ В этой статье все множества, не являющиеся очевидным образом бесконечными, предполагаются конечными. Пусть X и У —множества, тогда через XY обозначается множество функций из Y в X. Через 9>(Х) обозначим множество всех подмножеств X, а через &t(X), /eN- множество всех /-элементных подмножеств X. Пусть Фг, х^{0, 1}х есть характеристическая функция подмножества Y czX, a ix — тождественное отображение J на себя. Функцию \i: Х->М,"такую что | \i \=?х& х Iх (*)=*> назовем t-X-мультимножеством, при этом \х (х) называется кратностью х. Будем говорить, что х — элемент |х, если jut (я) Ф О, и что х — кратный элемент, если р, (х) ^ 2. Если \х не содержит кратных элементов, т. е. \x(x)cz{0, 1}, то [х = Фц-1A), х И М» можно отождествить с \\i~l(l)cX. Если Х{аХ2, то отождествим HXl с подмножеством Nx\ состоящим из тех \х, ограничение которых на Х2\Х{ равно 0. Назовем t-схемой S(k\t,k,v), где Л; /, k, tieN, t^. ky такое ^E)-мультимножество \х, что |S| = a и для любого T^