О СЛОЖНОСТИ РЕАЛИЗАЦИИ БУЛЕВЫХ ФУНКЦИЙ ИЗ ИНВАРИАНТНЫХ КЛАССОВ КЛЕТОЧНЫМИ СХЕМАМИ ОГРАНИЧЕННОЙ ВЫСОТЫ С КРАТНЫМИ ВХОДАМИ |
4 | |
2012 |
научная статья | 519.714 | ||
225-231 | клеточные схемы, ограниченная высота, кратные входы, инвариантный класс, асимптотика, функция Шеннона |
Рассматривается модель клеточных схем ограниченной высоты с кратными входами и устанавливается асимптотическое поведение функции Шеннона для площади клеточных схем, реализующих
функции из ненулевых инвариантных классов. |
1 . Кравцов С.С. О реализации функций алгебры логики в одном из классов схем из функциональных и коммутационных элементов // Проблемы кибернетики. М.: Наука, 1967. Вып. 19. С. 285-292. 2 . Альбрехт А. О схемах из клеточных элементов // Проблемы кибернетики. М.: Наука, 1975. Вып. 33. С. 209-214. 3 . Грибок С.В. Об одном базисе для схем из клеточных элементов // Вестник Московского Университета, сер. 15. Вычислительная математика и кибернетика. 1999. № 4. С. 36-39. 4 . Улесова А.Ю. О сложности односторонних клеточных схем фиксированной высоты с кратными входами // Материалы XVI Международной конфе- ренции «Проблемы теоретической кибернетики». Н. Новгород: Издательство Нижегородского госуни- верситета, 2011. 5 . Лупанов О.Б. Асимптотические оценки сложности управляющих систем // М.: Издательство МГУ, 1984. 6 . Тиунчик А.А. О реализации функций алгебры логики клеточными схемами ограниченной ширины // Методы дискретного анализа в решении экстре- мальных задач. Новосибирск: Институт математики СО АН СССР, 1990. Вып. 50. С. 73-83. 7 . Яблонский С.В. О невозможности элиминации перебора всех функций из P2 при решении некоторых задач теории схем // ДАН СССР. 1959. Т. 124. № 1. С. 54-62. 8 . Лупанов О.Б. О реализации функций алгебры логики формулами из конечных классов (формулами ограниченной глубины) в базисе &, v, - // Проблемы кибернетики. М.: Физматгиз, 1961. Вып. 6. С. 5-14. |