Головная страница ИПМ Библиотеки, издания  •  Поиск публикаций  English 
Публикация

Материал конференции: "XIV международный научный семинар "Дискретная математика и ее приложения" имени академика О.Б. Лупанова (20-25 июня 2022 г., Москва)"
Авторы: Жуков В.В.
Методы синтеза и оценки сложности программ с некоторыми структурными ограничениями
Аннотация:
Работа посвящена исследованию различных классов схем программного типа, реализующих булевы функции, и установлению асимптотических оценок функций Шеннона для сложности реализации булевых функций в данных классах схем. Вводятся и исследуются модели рефлексивно-рекурсивных схем из функциональных элементов и программ, в которых допустим рекурсивный вызов процедур. Исследуется влияние глубины рекурсии на сложность реализации функций алгебры логики. Для рассматриваемых моделей предложены методы синтеза схем и программ, реализующих произвольные булевы функции, а также методы получения нижних оценок функции Шеннона для сложности реализации булевых функций, с помощью которых при определенных ограничениях было установлено асимптотическое поведение соответствующих функций Шеннона.
Ключевые слова:
булевы функции, схемы из функциональных элементов
Язык публикации: русский,  страниц: 4 (с. 65-68)
Полный текст на русском языке:
Экспорт ссылки на публикацию в формате:   RIS    BibTeX
Сведения об авторах:
  • Жуков Владимир Владимирович,  МГУ имени М.В. Ломоносова