Изменение размера оптимальной схемы при переходе к другому базису — различия между версиями
Sementry (обсуждение | вклад) |
Sementry (обсуждение | вклад) |
||
| Строка 3: | Строка 3: | ||
==Определение== | ==Определение== | ||
Размер схемы - количество функциональных элементов, необходимое для построения этой схемы. | Размер схемы - количество функциональных элементов, необходимое для построения этой схемы. | ||
| − | Схемная сложность функции <math>f</math> относительно базиса <math>B</math>(обозначается <math>size_B(f)</math>) - минимальный размер схемы, вычисляющей функцию <math>f</math>, собранной из функциональных элементов, принадлежащих базису <math>B</math>. | + | Схемная сложность функции <math>~f</math> относительно базиса <math>~B</math>(обозначается <math>~size_B(f)</math>) - минимальный размер схемы, вычисляющей функцию <math>~f</math>, собранной из функциональных элементов, принадлежащих базису <math>~B</math>. |
==Теорема== | ==Теорема== | ||
| − | Для любых базисов <math>B_1</math>, <math>B_2</math> и функции <math>f</math> верно равенство <math>size_{B_1}(f) \leq C_{(B_1,\;B_2)}size_{B_2}(f)</math> | + | Для любых базисов <math>~B_1</math>, <math>~B_2</math> и функции <math>~f</math> верно равенство <math>~size_{B_1}(f) \leq C_{(B_1,\;B_2)}size_{B_2}(f)</math> |
==Доказательство== | ==Доказательство== | ||
| − | Пусть базис <math>B_2</math> состоит из функций <math>g_1, g_2, ..., g_n</math>. Схемная сложность функции <math>g_i</math> относительно базиса <math>B_1</math> равна <math>size_{B_1}(g_i)</math>. Иначе говоря, каждый функциональный элемент базиса <math>B_2</math> мы собираем с помощью элементов из базиса <math>B_1</math>. Тогда понятно, что в сумме мы затратим не более чем в <math>C = | + | Пусть базис <math>~B_2</math> состоит из функций <math>~g_1, g_2, ..., g_n</math>. Схемная сложность функции <math>~g_i</math> относительно базиса <math>~B_1</math> равна <math>~size_{B_1}(g_i)</math>. Иначе говоря, каждый функциональный элемент базиса <math>~B_2</math> мы собираем с помощью элементов из базиса <math>~B_1</math>. Тогда понятно, что в сумме мы затратим не более чем в <math>~C = \max_{i=1}^n size_{B_1}(g_i)</math> раз больше функциональных элементов, и <math>~C</math> зависит от выбранных базисов, но не зависит от формулы. |
Версия 06:47, 4 октября 2010
Эта статья находится в разработке!
Определение
Размер схемы - количество функциональных элементов, необходимое для построения этой схемы. Схемная сложность функции относительно базиса (обозначается ) - минимальный размер схемы, вычисляющей функцию , собранной из функциональных элементов, принадлежащих базису .
Теорема
Для любых базисов , и функции верно равенство
Доказательство
Пусть базис состоит из функций . Схемная сложность функции относительно базиса равна . Иначе говоря, каждый функциональный элемент базиса мы собираем с помощью элементов из базиса . Тогда понятно, что в сумме мы затратим не более чем в раз больше функциональных элементов, и зависит от выбранных базисов, но не зависит от формулы.
