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

Статья в сборнике "Математические вопросы кибернетики" №12, Москва, 2003
Авторы: Чашкин А.В.
Об одном методе вычисления частичных булевых функций
Аннотация:
В работе изучается среднее время вычисления значений частичных булевых функций заданного веса неветвящимися программами с условной остановкой. Предложен новый метод вычисления таких функций, заключающийся в аппроксимации вычисляемой функции последовательностью более простых частичных функций. Получены новые совпадающие по порядку верхние и нижние оценки соответствующей функции Шеннона. Из полученных оценок следует, что средняя сложность почти всех рассматриваемых функций с точность до постоянного множителя зависит от веса w вычисляемой функции, не зависит от размера ее области определения и равна θ(w/log2w).
Ключевые слова:
сложность, функция Шеннона, булева функция, частичная функция
Язык публикации: русский, страниц: 16 (с. 231-246)
Направление исследований:
Математические вопросы и теория численных методов
Полный текст на русском языке: Сведения об авторах:
  • Чашкин Александр Викторович,  ,  механико-математический ф-т МГУ им. М.В.Ломоносова