Изменение размера оптимальной схемы при переходе к другому базису — различия между версиями

Материал из Викиконспекты
Перейти к: навигация, поиск
Строка 1: Строка 1:
−
{{В разработке}}
+
{{Определение
 +
|definition =
 +
'''Схемная сложность''' функции <tex>~f</tex> относительно базиса <tex>~B</tex>(обозначается <tex>~size_B(f)</tex>) - это минимальное количество функциональных элементов из набора <tex>~B</tex>, необходимое для реализации функции <tex>~f</tex> в базисе <tex>~B</tex>.
 +
}}
  
−
==Определение==
+
{{Теорема
−
Схемная сложность функции <math>~f</math> относительно базиса <math>~B</math>(обозначается <math>~size_B(f)</math>) - это минимальное количество функциональных элементов из набора <math>~B</math>, необходимое для реализации функции <math>~f</math> в базисе <math>~B</math>.
+
|statement =
−
 
+
Для любых базисов <tex>~B_1</tex>, <tex>~B_2</tex> и функции <tex>~f</tex> верно неравенство <tex>~size_{B_2}(f) \leq C_{(B_1,\;B_2)}size_{B_1}(f)</tex>, где константа <tex>~C</tex> зависит только от базисов <tex>~B_1</tex> и <tex>~B_2</tex>.
−
==Теорема==
+
|proof =
−
Для любых базисов <math>~B_1</math>, <math>~B_2</math> и функции <math>~f</math> верно равенство <math>~size_{B_2}(f) \leq C_{(B_1,\;B_2)}size_{B_1}(f)</math>, где константа <math>~C</math> зависит только от базисов <math>~B_1</math> и <math>~B_2</math>.
+
Пусть базис <tex>~B_2</tex> состоит из функций <tex>~g_1, g_2, ..., g_n</tex>. Схемная сложность функции <tex>~g_i</tex> относительно базиса <tex>~B_1</tex> равна <tex>~size_{B_1}(g_i)</tex>(по определению схемной сложности). Иначе говоря, каждый функциональный элемент базиса <tex>~B_2</tex> можно собрать с помощью элементов из базиса <tex>~B_1</tex>, затратив на это не более чем <tex>~size_{B_1}(g_i)</tex> элементов. Поэтому в сумме мы затратим не более чем в <tex>~C = \max_{i=1}^n size_{B_1}(g_i)</tex> раз больше функциональных элементов, и <tex>~C</tex> зависит только от выбранных базисов.
−
 
+
}}
−
==Доказательство==
 
−
Пусть базис <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>~size_{B_1}(g_i)</math> элементов. Тогда понятно, что в сумме мы затратим не более чем в <math>~C = \max_{i=1}^n size_{B_1}(g_i)</math> раз больше функциональных элементов, и <math>~C</math> зависит только от выбранных базисов.
 

Версия 02:22, 18 октября 2010

Определение:
Схемная сложность функции [math]~f[/math] относительно базиса [math]~B[/math](обозначается [math]~size_B(f)[/math]) - это минимальное количество функциональных элементов из набора [math]~B[/math], необходимое для реализации функции [math]~f[/math] в базисе [math]~B[/math].


Теорема:
Для любых базисов [math]~B_1[/math], [math]~B_2[/math] и функции [math]~f[/math] верно неравенство [math]~size_{B_2}(f) \leq C_{(B_1,\;B_2)}size_{B_1}(f)[/math], где константа [math]~C[/math] зависит только от базисов [math]~B_1[/math] и [math]~B_2[/math].
Доказательство:
[math]\triangleright[/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]~size_{B_1}(g_i)[/math] элементов. Поэтому в сумме мы затратим не более чем в [math]~C = \max_{i=1}^n size_{B_1}(g_i)[/math] раз больше функциональных элементов, и [math]~C[/math] зависит только от выбранных базисов.
[math]\triangleleft[/math]
Источник — «http://neerc.ifmo.ru/wiki/index.php?title=Изменение_размера_оптимальной_схемы_при_переходе_к_другому_базису&oldid=4137»