Изменение размера оптимальной схемы при переходе к другому базису — различия между версиями
Sementry (обсуждение | вклад) (Новая страница: «{{В разработке}} ==Определение== Размер схемы - количество функциональных элементов, необхо…») |
Sementry (обсуждение | вклад) |
||
| Строка 3: | Строка 3: | ||
==Определение== | ==Определение== | ||
Размер схемы - количество функциональных элементов, необходимое для построения этой схемы. | Размер схемы - количество функциональных элементов, необходимое для построения этой схемы. | ||
| − | Схемная сложность функции f относительно базиса B(обозначается SIZEb(f)) - минимальный размер схемы, вычисляющей функцию f, собранной из функциональных элементов, принадлежащих базису B. | + | Схемная сложность функции <math>f</math> относительно базиса <math>B</math>(обозначается <math>SIZEb(f)</math>) - минимальный размер схемы, вычисляющей функцию <math>f</math>, собранной из функциональных элементов, принадлежащих базису <math>B</math>. |
==Теорема== | ==Теорема== | ||
| − | Для любых базисов B1, B2 и функции f SIZEb1(f) = O(SIZEb2(f)) | + | Для любых базисов <math>B1</math>, <math>B2</math> и функции <math>f</math> <math>SIZEb1(f)</math> = <math>O(SIZEb2(f))</math> |
==Доказательство== | ==Доказательство== | ||
Версия 05:48, 4 октября 2010
Эта статья находится в разработке!
Определение
Размер схемы - количество функциональных элементов, необходимое для построения этой схемы. Схемная сложность функции относительно базиса (обозначается ) - минимальный размер схемы, вычисляющей функцию , собранной из функциональных элементов, принадлежащих базису .
Теорема
Для любых базисов , и функции =
