|
Проблемы передачи информации, 1978, том 14, выпуск 4, страницы 85–97
(Mi ppi1561)
|
|
|
|
Эта публикация цитируется в 1 научной статье (всего в 1 статье)
Теория автоматов
О числе проверок для определения значимых переменных булевских функций
И. И. Викторова, А. М. Леонтович
Аннотация:
Пусть имеется булевская функция $\tilde{f}(x_0,\dots, x_{n-1})$, которая в действительности зависит лишь от $m$ переменных: $\tilde{f}(x_0,\dots, x_{n-1})\equiv f(x_{i_1}\dots,x_{i_m})$. Функция $f$ известна, но неизвестны номера значимых переменных $i_1,\dots,i_m$. Мы хотим найти эти номера. При этом мы можем за одну проверку узнать значение $\tilde{f}(x_0,\dots, x_{n-1})$ для произвольного набора переменных $x_0,\dots, x_{n-1}$. В работе даны оценки для числа проверок, за которое заведомо можно найти номера $i_1,\dots,i_m$, а также приведены некоторые конкретные алгоритмы поиска этих номеров.
Поступила в редакцию: 09.07.1976
Образец цитирования:
И. И. Викторова, А. М. Леонтович, “О числе проверок для определения значимых переменных булевских функций”, Пробл. передачи информ., 14:4 (1978), 85–97; Problems Inform. Transmission, 14:4 (1978), 298–306
Образцы ссылок на эту страницу:
https://www.mathnet.ru/rus/ppi1561 https://www.mathnet.ru/rus/ppi/v14/i4/p85
|
Статистика просмотров: |
Страница аннотации: | 211 | PDF полного текста: | 83 |
|