University-notes/1 курс/2 семестр/Дискретка/Билеты/8.md

	Схемы из функциональных элементов. Сложность и глубина схем. Способы построения схем в стандартном базисе.

# Схемы из функциональных элементов
**СФЭ** (Схема из функциональных элементов) - ациклический орграф, содержащий вершины двух типов:
1. **Входные** (источники) - к вершине приписан уникальный символ переменной
2. **Функциональные** (гейты) - приписан символ логической функции. [[1 курс/2 семестр/Дискретка/Билеты/7#^3dbfa3|Полустепень захода]] совпадает с числом аргументов соответствующей функции1
Для гейтов используется ограниченный набор функций:
- **Стандартный** - $\wedge, \vee, \bar{}$
- **Базис Жегалкина** - $\oplus, \wedge, 1$
# Сложность и глубина схем
- **Сложность схемы** - число гейтов в схеме
- **Схемная сложность** функции ($L(f)$) - наименьшая сложность схемы, вычисляющий функцию
- **$L(n)$** - наибольшая системная сложность функции от n переменных

> [!Заметка]
> $L(f)$ и $L(n)$ зависят от базиса
> 

- **Глубина схемы** - наибольшая длина ориентированного пути, с началом во входной вершине

# Способы построения схем в стандартном базисе
1. Использование нормальных форм
2. [[1 курс/2 семестр/Дискретка/Билеты/3#Разложение функции по переменной|Разложение по переменной]]