Таким образом, оценки для сложности функций в разных базисах отличаются лишь постоянными множителями. В связи ... - Большая Энциклопедия Нефти и Газа



Выдержка из книги Лупанов О.Б. Кибернетический сборник Выпуск21


Таким образом, оценки для сложности функций в разных базисах отличаются лишь постоянными множителями. В связи с этим первоочередной задачей является определение главного множителя оценки - того, который не зависит от базиса. Под этим подразумевается, что вместо одной конкретной булевой функции рассматривается последовательность аналогичных ей функций, содержащая при каждом п чаще всего по одной функции от п переменных, а оценка ищется в виде произведения коэффициента, зависящего от базиса, на функцию от я, которая и представляет собой главный множитель.

(cкачать страницу)

Смотреть книгу на libgen

Таким образом,  оценки для сложности функций в разных базисах отличаются лишь постоянными множителями.  В связи с этим первоочередной задачей является определение главного множителя оценки  -  того,  который не зависит от базиса.  Под этим подразумевается,  что вместо одной конкретной булевой функции рассматривается последовательность аналогичных ей функций,  содержащая при каждом п чаще всего по одной функции от п переменных,  а оценка ищется в виде произведения коэффициента,  зависящего от базиса,  на функцию от я,  которая и представляет собой главный множитель.