|
ИСТИНА |
Войти в систему Регистрация |
ИПМех РАН |
||
Временная сложность реализации булевых функцийдоклад на конференции
- Автор: Шуткин Ю.С.
- Международная Конференция : Международная конференция "Современные проблемы математики, механики и их приложений", посвященная 70-летию ректора МГУ акад. В. А. Садовничего
- Даты проведения конференции: 1-5 мая 2009
- Тип доклада: не указан
- Докладчик: Шуткин Ю.С.
- Место проведения: Москва, механико-математический ф-т МГУ, Russia
-
Аннотация доклада:
Рассматривается задача реализации булевых функций с помощью информационных графов. Получены основные оценки сложности реализации, такие как оценка функции Шеннона сложности реализации булевых функции в классе информационных графов и информационных деревьев. Также для почти всех булевых функций получен порядок сложности реализации их информационными графами с простым базовым множеством, а для деревьев установлена асимптотика сложности. Для обобщенных базовых множеств также получены оценки сложности для почти всех булевых функций в разных классах функций.
- Добавил в систему: Шуткин Юрий Сергеевич