Основы кибернетики, Теормин

Материал из eSyr's wiki.

(Различия между версиями)

Перейти к: навигация, поиск

Версия 12:02, 21 июня 2008

Содержание

1 Представление функций с помощью дизъюнктивных нормальных форм. Тесты для таблиц
2 Основные классы дискретных управляющих систем. Структурные представления и эквивалентные преобразования схем, оценка их числа
3 Синтез, сложность и надежность управляющих систем

Представление функций с помощью дизъюнктивных нормальных форм. Тесты для таблиц

Определение ЧУМ, его цепи, антицепи, длины и ширины

Отношение, обладающее свойствами рефлексивности, транзитивности, антисимметричности — отношение частичного порядка
Если τ — отношение частичного порядка на множестве А, то пара (А,τ) — частично упорядоченное множество (ЧУМ)
Для ЧУМ (А, τ) множество, состоящее из попарно сравнимых/несравнимых элементов а ∈ А называется цепью/антицепью
Максимальная мощность цепей/антицепей ЧУМ называется его длиной/шириной
Цепь С ⊆ А ЧУМ (А, τ) — неуплотняемая, если С представляет собой максимальное по включению множество соответствующего типа
ЧУМ (А, τ) длины t (|A| = t) называется ранжированным ЧУМ, если все его неуплотняемые цепи имеют мощность t

Определение ранжированного ЧУМ и утверждение о его ширине

ЧУМ (А,τ) длины t (|A| = t) называется ранжированным ЧУМ, если все его неуплотняемые цепи имеют мощность t.

Утверждение. Если в ранжированном частично упорядоченном множестве (A,τ) через каждые два элемента одного и того же яруса проходит одинаковое число неуплотняемых цепей, то ширина частично упорядоченного множества (A,τ) равна максимальной мощности его ярусов.

Следствие. Ширина ЧУМ (Bⁿ, ≤) равна

Определение импликанты, простой импликанты и сокращенной ДНФ

ФАЛ ƒ имплицирует ФАЛ g (или, иначе, ФАЛ g поглощает ФАЛ ƒ) если N_ƒ ⊆ N_g, то есть импликация (ƒ → g) тождественно равна 1
ЭК, которая имплицирует ФАЛ ƒ, называется импликантой этой ФАЛ
Импликанта К ФАЛ ƒ называется простой импликантой этой ФАЛ, если она не поглощается никакой другой отличной от нее импликантой ФАЛ ƒ
Дизъюнкция всех простых импликант ФАЛ ƒ называется ее сокращенной ДНФ

Тождество поглощения и определение неприводимой ДНФ

Тождество поглощения: x₁ ∨ x₁x₂ = x₁
ДНФ U вида U = K₁ ∨ ... ∨ K_s называется неприводимой, если соответствующее ей покрытие является неприводимым, т.е. ни одна из граней N_K₁,...,N_{K_s} не содержится ни в одной из других граней покрытия N_ƒ = N_K₁ ∪ ... ∪ N_{K_s}

Формулировка утверждения, связанного с построением сокращенной ДНФ из какой-либо КНФ

Утверждение. Если неприводимая ДНФ U получается из КНФ B ФАЛ ƒ в результате раскрытия скобок и приведения подобных, то U — сокращенная ДНФ ФАЛ ƒ.

Тождество обобщенного склеивания и определение нерасширяемой ДНФ

Тождество обобщенного склеивания: x_iK‘ ∨ x_iK" = x_iK‘ ∨ x_iK" ∨ K‘K"

t^ОС: x₁ & x₂ ∨ x₁ & x₃ = x₁ & x₂ ∨ x₁ & x₃ ∨ x₂ & x₃

Формулировка утверждения, связанного с построением сокращенной ДНФ из какой-либо ДНФ

Утверждение. Из любой ДНФ А ФАЛ ƒ можно получить сокращенную ДНФ этой ФАЛ в результате построения последовательных строгих расширений и приведения подобных до получения неприводимой ДНФ, не имеющей строгих расширений.

Определение тупиковой, кратчайшей и минимальной ДНФ

ДНФ A, реализующая ФАЛ ƒ называется тупиковой, если ƒ ≠ A' для любой A', полученной из A удалением некоторых букв или целых ЭК.
Минимальная (кратчайшая) ДНФ — ДНФ, которая имеет наименьший ранг (длину) среди всех ДНФ реализующих ФАЛ ƒ.

Определение ядровой точки, ядровой грани и ДНФ Квайна

Набор α, α ∈ Bⁿ, называется ядровой точкой ФАЛ ƒ(x₁,...,x_n), если α ∈ N_ƒ и α входит только в одну максимальную грань ФАЛ ƒ.
Грань N_K, являющаяся максимальной гранью ФАЛ ƒ и содержащая ядровую точку α, называется ядровой гранью.
Совокупность всех различных ядровых граней ФАЛ ƒ называется ядром ФАЛ ƒ.
ДНФ, получающаяся из сокращенной ДНФ ФАЛ ƒ удалением тех ЭК К, для которых грань N_K покрывается ядром ФАЛ ƒ, но не входит в него, называется ДНФ Квайна этой ФАЛ.

Определение пучка, регулярной точки и регулярной грани

Множество всех проходящих через α ( α ∈ N_ƒ ) максимальных граней ФАЛ ƒ называется пучком ФАЛ ƒ через точку α (обозначается Π_α(ƒ)).
Точка α, α ∈ N_ƒ называется регулярной точкой ФАЛ ƒ, если существует такая точка β, что β ∈ N_ƒ и Π_β(f) ⊂ Π_α(ƒ).
Грань N_K ФАЛ ƒ называется регулярной гранью этой ФАЛ, если все точки N_K регулярны.

Определение ДНФ сумма тупиковых и критерий вхождения в нее простых импликант

ДНФ сумма тупиковых ФАЛ f - дизъюнкция всех тех различных простых импликант этой ФАЛ, которые входят хотябы в одну тупиковую ДНФ ФАЛ f.

Утверждение. Простая импликанта К ФАЛ f входит в ДНФ ∑T тогда и только тогда, когда грань N_K не является регулярной гранью этой ФАЛ.

Определение ДНФ пересечения тупиковых и критерий вхождения в неё простых импликант

ДНФ пересечение тупиковых ФАЛ ƒ - дизъюнкция всех тех различных простых импликант этой ФАЛ, которые входят в любую тупиковую ДНФ ФАЛ ƒ.

Утверждение. ДНФ пересечение тупиковых ФАЛ ƒ состоит из тех простых импликант ФАЛ ƒ, которые соответствуют ядровым граням этой ФАЛ.

Определение линейной ФАЛ и особенности её ДНФ

Линейная ФАЛ — это ФАЛ ƒ ∈ P₂(n) вида ƒ(x₁...x_n) = α₁x₁ ⊕ ... ⊕ α_nx_n ⊕ α₀, где α₀,...,α_n — булевы константы.

Утверждение. Совершенная ДНФ линейной существенной функции является единственной ДНФ этой ФАЛ от её существенных БП.

Необходимые и достаточные условия единственности представления ФАЛ в виде ДНФ

Утверждение. Совершенная ДНФ ФАЛ ƒ из P₂(n) является ее единственной ДНФ тогда и только тогда, когда во множестве N_ƒ нет соседних наборов.

Определение монотонной ФАЛ и её нижней единицы. Особенности простых импликант монотонной ФАЛ

ФАЛ ƒ (x₁,...,x_n) называется монотонной, если ƒ(α) ≤ ƒ(β) для любых наборов α,β ∈ Bⁿ таких, что α ≤ β.
Набор α ∈ Bⁿ называется нижней единицей монотонной ФАЛ ƒ, ƒ ∈ P₂(n), если α ∈ N_ƒ и ƒ(β) = 0 для любого отличного от α набора β такого, что β ≤ α.
Если ФАЛ ƒ(x₁,...,x_n) монотонно зависит от БП x_i, то ни одна из ее простых импликант не может содержать букву ¬x_i

Определение монотонной ФАЛ, формулировка утверждения об особенностях ДНФ для монотонных ФАЛ

ФАЛ ƒ(x₁...x_n) называется монотонной, если ƒ(α) ≤ ƒ(β) для любых наборов α и β куба B ⁿ таких, что α ≤ β

Утверждение. Сокращенная ДНФ U монотонной ФАЛ ƒ, ƒ ∈ P₂(n), является единственной тупиковой ДНФ этой ФАЛ и имеет вид: U(x₁...x_n) = ∨_{β∈N_ƒ⁺} K_β⁺(x₁...x_n)

Определение цепной и циклической ФАЛ. Особенности ДНФ циклической ФАЛ, используемые в теореме Журавлева о ДНФ сумма минимальных

Функция ƒ(x₁,...,x_n) называется цепной (циклической) функцией длины t, если ее сокращенная ДНФ с "геометрической" точки зрения представляет собой цепь (соответственно цикл) из t полседовательно соединенных ребер N₁, N₂, ..., N_t куба Bⁿ.

Цепная ФАЛ ƒ нечетной длины t = 2k - 1 ≥ 3 имеет единственную минимальную ДНФ, которая совпадает с ее ДНФ ΣM и соответствует покрытию N₁ ∪ N₃ ∪ ... ∪ N_t

Формулировка теоремы Журавлева о ДНФ сумма минимальных

Утверждение (теорема Журавлева). При любом n ∈ Ν, n ≥ 3, в P₂(n) существуют ФАЛ ƒ' и ƒ", имеющие общую простую импликанту К, которая входит в ДНФ ∑M одной, но не входит в ДНФ ∑M другой из этих ФАЛ и для которой S_n-3(N_K,ƒ') = S_n-3(N_K,ƒ").

Определение ФАЛ покрытия матрицы и ее свойства, утверждение о КНФ для ФАЛ покрытия

Пусть N = {α₁,...α_s,} - конечное множество, а П = (N₁,...,N_p) - система его подмножеств, образующих покрытие множества N. Сопоставим паре (N,П) матрицу M ∈ B^p,s, для которой M<i,j> = 1 ⇔ α_j ∈ N_i. Будем говорить, что i-я строка матрицы М покрывает ее j-й столбец, если M<i,j> = 1 и что система строк с номерами из I, I ⊆ [1,p], образует покрытие матрицы М, если каждый ее столбец покрывается хотябы одной строкой с номером из I, то есть система подмножеств {N_i}_{i ∈ I} задает покрытие множества N.
Пусть M ∈ B^p,s - матрица без нулевых столбцов. Сопоставим i-й строке матрицы М БП y_i, а каждому набору β ∈ B^p значений этих переменных y = (y₁,...,y_p) - множество строк матрицы М с намерами из множества I = I(β) ⊆ [1,p], где i ∈ I(β) ⇔ β<i> = 1. ФАЛ F(y), для которой F(β) = 1 ⇔ система строк матрицы М с номерами из I(β) образует ее покрытие, будем называть функцией покрытия матрицы М.

Свойства ФАЛ покрытия матрицы

монотонность
ее "нижние единицы" соответствуют тупиковым покрытиям

Утверждение. Функция покрытия F(y₁,...,y_p) матрицы M ∈ B^p,s без нулевых столбцов задается КНФ вида: (*)
Следствие. В результате раскрытия скобок и приведения подобных из КНФ (*) можно получить сокращенную ДНФ ФАЛ F(y), простые импликанты которой взаимно однозначно соответствуют тупиковым покрытиям матрицы М.

Градиентный алгоритм покрытия матрицы и утверждение о длине градиентного покрытия

Градиентный алгоритм: На каждом шаге алгоритма в матрице выбирается и включается в покрытие такая строка, которая покрывает наибольшее число ещё не покрытых столбцов (если таких строк несколько, из них выбирается строка с наименьшим номером). Алгоритм заканчивается свою работу после того шага, на котором получилось покрытие.

Утверждение. Пусть для действительного γ, 0 < γ ≤ 1, в каждом столбце матрицы M, M ∈ B^p,s, имеется не меньше чем γ•p единиц. Тогда покрытие матрицы M, получаемое с помощью градиентного алгоритма, имеет длину не больше, чем , где ln⁺x = ln x, если x ≥ 1 и ln⁺x = 0, если 0 < x ≤ 1.

Определение протыкающего множества для граней единичного куба и верхняя оценка его мощности.

Пусть N = {α₁,...α_s,} - конечное множество, а П = (N₁,...,N_p) - система его подмножеств. Множество, протыкающее систему П - такое подмножество множества N,в котором ∀ i ∈ [1,p] имеется хотябы один элемент из N_i.

Утверждение. При любых натуральных n и m, m ≤ n, в кубе Bⁿ всегда найдется множество мощности не более, чем n×2^m, протыкающее все грани ранга m.

Определение функции Шеннона R(n) для ранга ДНФ и ее значение.

R(n) = max_ƒ∈P₂(n) R(ƒ);
R(n) = n × 2^{n − 1}

Определение функции Шеннона λ(n) для длины ДНФ и ее значение.

λ(n) = max_ƒ∈P₂(n) λ(ƒ);
λ(n) = 2^{n − 1}

Определение длины ДНФ λ(ƒ) для ФАЛ ƒ и ее оценки для почти всех ФАЛ ƒ от n переменных

λ(ƒ) = min_{ДНФ U, реализующим f} λ(U)
Для почти всех ФАЛ из P₂(n) λ(ƒ)<~ (3/4)*2^{n − 1}

Определение ранга ДНФ R(f) для ФАЛ ƒ и ее оценки для почти всех ФАЛ ƒ от n переменных

R(f) = min_{ДНФ U, реализующим f} R(U)
Для почти всех ФАЛ из P₂(n) R(f)<~ (3/4)*n*2^{n − 1}

Определение проверяющего теста матрицы и его ФАЛ, утверждение и КНФ для ФАЛ проверяющего теста

Пусть есть схема Σ₁, которая реализует ФАЛ f₁. Пусть есть источник помех И. Под действием источника И схема Σ может переходить в одно из неисправных состояний Σ₂, …, Σ_s, каждое из которых реализует ФАЛ f_i, i = 2, s.

Пусть (Σ, И) — модель ненадёжной схемы Σ с возможными состояниями Σ₁, …, Σ_s, в которых реализуются ФАЛ f₁, …, f_s, определённые на множестве наборов A = {α₁, …, α_p} ⊆ Bⁿ. Рассмотрим матрицу M ∈ B^{p, s}, M[i, j] = f_j(α_i). Множество строк матрицы M с номерами из T ⊆ [1, p] называется проверяющим тестом матрицы M, если для ∀j ∈ 1, s, ∃t ∈ T такое, что M[t, 1] ≠ M[t, j].

Утверждение. Функция проверяющего теста f(y₁, …, y_p) для отделимой по столбцам матрицы M ∈ B^{p, s} может быть задана с помощью КНФ

где N = {(1, j) | j ∈ 1, s}

Утверждение об оценке длины диагностического теста для произвольной таблицы с заданным числом столбцов

Утверждение. Длина любого тупикового диагностического теста для отделимой по столбцам матрицы из множества B^p,s заключена в пределах от ⌈log s⌉ до (s − 1)

!!! Описание ЧУМ, антицепями которого являются тупиковые ДНФ.

Ранжированное множество длины (n+1) всех граней n-мерного единичного куба с отношением вложения. (не точно, стр. 63)

Основные классы дискретных управляющих систем. Структурные представления и эквивалентные преобразования схем, оценка их числа

Индуктивное определение формулы и реализуемой ею ФАЛ

Любая переменная x_j из X считается формулой глубины 0 над множеством Б, которая реализует функцию x_j. Если φ(x₁,...,x_k) ∈ Б и для каждого i, i ∈ [1,k], определена формула F_i глубины q_i над множеством Б, которая реализует функцию ƒ_i из P_A, то запись F вида

F = φ(F₁,...,F_k)

является формулой глубины q = max{q₁,...,q_k} + 1 над Б, которая реализует функцию ƒ вида ƒ = φ(ƒ₁,...,ƒ_k).

Индуктивное определение π-схемы и нахождение реализуемой ею ФАЛ

Простейшей π-схемой считается любая (1,1)-КС, которая состоит из одного контакта, соединяющего полюса. Если π-схемы ∑₁ и ∑₂ уже определены, то (1,1)-КС ∑₁(∑₂), которая получается в результате их последовательного (параллельного) соединения тоже является π-схемой.

Определение разделительной по входам (выходам) КС и формулировка леммы Шеннона

КС разделительна по входам (выходам), если ФАЛ проводимости для ∀ различных входов (выходов) ≡ 0.

Лемма Шеннона: Пусть Σ = Σ''(Σ') - результат стыковки ⇒ F ≥ F' × F''. F = F' × F'', если Σ'' разделительна по входам, или Σ' разделительна по выходам.

Определение подсхемы Σ' КС ∑ с указанием особенностей, связанных с объявлением вершин Σ' её полюсами. Основное тождество t₄ (введение фиктивной переменной) и вспомогательное тождество t₁₁ (лемма о звезде); обобщенные тождества t₄⁽ⁿ⁾ и t₁₁⁽ⁿ⁾

Определение подсхемы Σ' КС Σ:
Σ' — подсхема схемы Σ ⇔

V(Σ') ⊆ V(Σ)
E(Σ') ⊆ E(Σ)
- ∀ полюс Σ, вошедший в Σ' — полюс Σ'
- ∀ вершина Σ', инцидентная контакту Σ\Σ' - полюс Σ'
- ∀ другая вершина м. б. полюсом Σ'.

t₄
t₁₁

Канонический вид КС от БП x₁,...,x_n и формулировка утверждения о приведении КС от БП x₁,...,x_n к каноническому виду с помощью основных тождеств.

∑^ /*здесь и далее крышка пишется над сигмой*/ - схема канонического вида ⇔ 1) ∀ контакт ∑^ лежит на стандартной цепи порядка n, явл. подсхемой ∑^ с полюсами в конечных вершинах цепи. 2) ∀ внутренняя вершина ∑^ - внутренняя вершина стандартной цепи 3) в ∑^ отсутствуют висячие циклы и || стандартные цепи 4) в ∑^ нет существенных транзитивных проводимостей /*вопрос +-, комментарий лектора: отсутствует утверждение о переходе к КВ*/

∑^ получается из ∑ удалением ∑' (подсхемы) и заменой ∑' на ∑' ' с соотв. присоединением полюсов, эквив. ∑ (принцип эквивалентной замены).

Определение величины ||U^c(L, n)|| и её верхняя оценка

U^c(L, n) — множество приведенных СФЭ Σ = Σ(x₁, …, x_n; z₁) над базисом Б₀, для которых L(Σ) ≤ L.
||U^c(L, n)|| — число попарно неэквивалентных схем в U^c(L, n)

Утверждение. Для любых натуральных n и L выполняется неравенство: ||U^c(L, n)|| ≤ (8(L + n))^{L + 1}.

Определение тождества для формул и его подстановки

Подстановка — вместо переменных функции

F (x 1,..., x n)

подставляем функции:

F (F 1,..., F n)

Тождество — $\hat{t}: F(x)' = F(x)''$ (1)

Если к правой и левой частям (1) применить подстановку, то получим тождество:

$\hat{t} : \hat{F}' = \hat{F}''$

где $\hat{F}' = \hat{F}'(F_1, \ldots ,F_n)$ и $\hat{F}'' = \hat{F}''(F_1, ... ,F_n)$ , которое называется подстановкой для тождества t.

Минимальный набор тождеств, входящих в расширенную основную систему, с помощью которого можно любую формулу преобразовать в формулу с поднятыми отрицаниями

В расширенную основную систему входят следующие тождества: r~^осн = {r^M, r^A, r^К, r^ОП, r^D, r^ПК, t^П} /* как обычно, ~ стоит над r */

r^A = {t^A_&,t^A_∨}
r^K = {t^K_&,t^K_∨}
r^ОП = {t^ОП_&,t^ОП_∨}
r^D = {t^D_&,t^D_∨}
r^ПК = {t^ПК_{0, &}, t^ПК_{0, ∨}, t^ПК_{1, &}, t^ПК_{1, ∨}}

все тождества описаны тут.

!!! Определение КС от БП x₁,...,x_n как помеченного графа и ФАЛ проводимости между её вершинами

(параграф 6 главы 2)

Формулировка утверждения о связи между π-схемами и формулами с поднятыми отрицаниями

Любой π-схеме можно сопоставить эквивалентную ей формулу F из U^Ф с поднятыми отрицаниями такую, что R(F) = L(Σ) и обратно.

!!! Определение эквивалентности КС Σ', Σ" и соответствующего тождества. Основное тождество t₂ (перестановка контактов в цепочке) и вспомогательное тождество t₈ ("расклейка" двух цепочек длины 2 с общим контактом); обобщенные тождества t₂⁽ⁿ⁾ и t₈⁽ⁿ⁾

(параграф 7 главы 2, в самом начале)

!!! Определение суммарного цикломатического числа КС от БП x₁,...,x_n и формулировка утверждения о его изменениях при применении основных тождеств

(глава 2, стр 72)

Определение структуры CФЭ как графа специального вида и изоморфных СФЭ

Под "абстрактной" схемой понимается сеть, часть пометок которой составляют входные переменные и в каждой вершине которой реализуется функция (столбец из функций) от этих переменных. При этом считается, что сама схема реализует систему (матрицу), состоящую из функций (соответственно столбцов функций), реализованных на её выходах. В качестве выходных пометок схемы используются, как правило, специальные выходные переменные, а схема Sigma с входными переменными (входами) x₁,..x_n и выходными переменными z₁,..z_m записывается в виде Sigma=Sigma(x₁,..x_n; z₁,..z_n).

Две СФЭ считаются изоморфными, если они изоморфны как помеченные графы, и эквивалентными, если они реализуют равные системы ФАЛ.

Определение ранга, сложности и глубины формулы, утверждение о соотношениях между ними

R(F) — ранг формулы F — число листьев, связанного с ней дерева
L(F) — сложность формулы F — число остальных вершин, связанного с ней дерева (не листьев)
D(F) — глубина формулы F — глубина корня, связанного с ней дерева
R(F) ≤ L(F) + 1 ≤ 2^D(F)

!!! Понятие подформулы и применение тождества к формуле

Минимальный набор тождеств, входящих в расширенную основную систему, с помощью которого формулу с поднятыми отрицаниями можно преобразовать в формулу со следующим порядком применения базисных функций: ¬, &, ∨

Дистрибутивность t_{&, ∨}^D: x₁ & (x₂ ∨ x₃) = (x₁ & x₂) ∨ (x₁ & x₃)
Коммутативность коньюнкции t_&^К: x₁ & x₂ = x₂ & x₁

!!! Определение матрицы ФАЛ, реализуемой КС с p входами и q выходами, определение и свойства матрицы, реализемой КС с m неразделенными полюсами

Глава 2, стр. 57-58

Определение величины ||U^π(L,n)|| и ее верхняя оценка

||U^π(L,n)|| - число попарно не эквивалентных приведенных π-схем от БП x₁,...,x_n сложности ≤ L

||U^π(L,n)|| ≤ (16n)^L

!!! Определение подстановки тождества для КС, связанной с управляющими БП, и ее применение к КС. Основное тождество t₃ (цепь из противоположных контактов) и вспомогательные тождество t₁₀ (замыкание по транзитивности); обобщенные тождества t₃⁽ⁿ⁾ и t₁₀⁽ⁿ⁾

!!! Примеры моделирования основных тождеств для формул в классе СФЭ, примеры тождеств ветвления и снятия для ФЭ и входов СФЭ. Формулировка утверждения о переходе от КПСТ для ЭП формул к КПСТ для ЭП СФЭ

Синтез, сложность и надежность управляющих систем

!!! Определение сложности L^C(F) системы ФАЛ F = (ƒ₁,...,ƒ_m) и ее тривиальная нижняя оценка для некоторых систем ФАЛ

Определение функции Шеннона L^C(n) и ее верхние оценки, получаемые методом Шеннона и методом О. Б. Лупанова

L^C(n) = max_ƒ∈P₂(n)L^C(ƒ)
Метод Шеннона: L^C(n) <∼ 8•2ⁿ/n
Метод Лупанова: L^C(n) ≤ (2ⁿ/n)•(1 + (5logn + O(1))/n)

Нижняя оценка функции Шеннона L^π(n) и то мощностное соотношение, из которого она выводится

L^π(n) ≥ 2ⁿ / log₂n (Асимптотически больше)
||U^π(L,n)|| ≤ (16n)^L

Определение мультиплексорной ФАЛ M_n порядка n, утверждение о сложности ее реализации в классах π-схем и формул

Функция вида µ_n(x₁,..x_n,y₀,..y_2ⁿ-1) = U _{(a=(a₁,..a_n))} x₁^a₁...x_n^a_ny_v(a) называется мультиплексорной функцией (мультиплексором) порядка n, а переменные x=(x₁,..x_n) называются адресными, y=(y₀,..y_2ⁿ-1) - информационными БП мультиплексора µ_n.

L^п(µ_n) <= 3*2ⁿ-2, L^Ф(µ_n) <= 2ⁿ⁺²-3;

!!! Определение сложности L^K(ƒ) ФАЛ ƒ(x₁...x_n) в классе КС и её тривиальные нижние оценки для ФАЛ ƒ, существенно зависящей от всех своих переменных (с учетом характера этой зависимости)

L^K (f) > n для ФАЛ f, существенно зависящей от всех своих переменных.

Определение функции Шеннона L^π(n) и её верхняя оценка, получаемая с помощью моделирования совершенной ДНФ на основе контактного дерева

L^π(n) = max_ƒ∈P₂(n)L^π(ƒ)
L^π(n) ≤ 2^{n + 1} − 2 //FIXME

Нижняя оценка функции Шеннона L^c(n) и то мощностное соотношение, из которого она выводится

L^C(n) ≥ 2ⁿ / n (Асимптотически больше)
||U^C(L,n)|| ≤ (8(L + n))^{L + 1}

Определение ДУМ и формулировка утверждения о свойствах стандартного ДУМ

Дизъюнктивно-универсальное множество (ДУМ) G порядка n и ранга p ⇔ ∀ g ∈ P₂(n) ∃ g₁,...,g_p ∈ G : g = g₁∪...∪g_p

Утверждение. Пусть m, S, p ∈ N: p * S ≥ 2^m, тогда ∃ ДУМ G порядка m и ранга p:

|G| ≤ p * 2^S
В G ∃ система из p ортогональных функций ψ₁,...,ψ_p : ∀ g ∈ G имплицирует одну из них.

Регулярные разбиения единичного куба и моделирование ФАЛ с помощью БП. Асимптотика сложности контактного дешифратора

Множество δ, δ ⊆ B^q, называется m-регулярным множеством наборов куба B^q, если m < q, |δ| = 2^m и все префиксы длины m наборов из δ различны.

m-регулярное разбиение куба B^q — разбиение этого куба, состоящее из m-регулярных множеств δ₁, …, δ_{q − m}. (???)

моделирование ФАЛ с помощью БП - ???

L^K (Q_n) ~ 2ⁿ

!!! Асимптотически наилучший метод синтеза КС

!!! Построение самокорректирующихся КС

!!! Асимптотически наилучший метод синтеза формул в В₀. Поведение функции Шеннона для глубины ФАЛ

!!! Задача синтеза схем для ФАЛ из специальных классов и индивидуальных ФАЛ. Методы получения верхних и нижних оценок сложности, минимальность некоторых схем

Определение m-регулярного множества наборов

Множество δ, δ ⊆ B^q, называется m-регулярным множеством наборов куба B^q, если m < q, |δ| = 2^m и все префиксы длины m наборов из δ различны.

!!! Определение (p, q)-самокорректирующейся КС. Утверждение о сложности самокорректирующейся КС, получаемой дублированием

Основы Кибернетики

01 02 03 04 05 06 07 08 09 10 11 12 13 14 15 16

Календарь

	пт	пт	пт	пт	пт
Февраль		09	16	26
Март	02	09	16	23	30
Апрель	06	13	20	27
Май	04	11	18	25

Материалы к экзамену

Экзаменационные вопросы 3 потока 2007 (new!) | Алгоритмы решения задач | Теормин | Определения

Получено с http://esyr.nizm.ru/wiki/%D0%9E%D1%81%D0%BD%D0%BE%D0%B2%D1%8B_%D0%BA%D0%B8%D0%B1%D0%B5%D1%80%D0%BD%D0%B5%D1%82%D0%B8%D0%BA%D0%B8%2C_%D0%A2%D0%B5%D0%BE%D1%80%D0%BC%D0%B8%D0%BD

@@ Строка 194: / Строка 194: @@
 ===  Определение тождества для формул и его подстановки ===
-Подстановка - вместо переменных функции <math>F(x_1, ... , x_n)</math> подставляем функции: <math>F(F_1, ... ,F_1)</math><br>
+<div class="definition">'''Подстановка''' &mdash; вместо переменных функции <math>F(x_1, ... , x_n)</math> подставляем функции: <math>F(F_1, ... ,F_n)</math>.</div>
-Тождество - <math>\hat{t}: F(x)' = F(x)''</math>  (1)<br>
+<div align="center">Тождество &mdash; <math>\hat{t}: F(x)' = F(x)''</math>  (1)</div>
 Если к правой и левой частям (1) применить подстановку, то получим тождество:
-<center><math>\hat{t} : \hat{F}' = \hat{F}''</math>      </center>
+<div align="center"><math>\hat{t} : \hat{F}' = \hat{F}''</math></div>
 где <math>\hat{F}' = \hat{F}'(F_1, \ldots ,F_n)</math> и <math>\hat{F}'' = \hat{F}''(F_1, ... ,F_n)</math>, которое называется подстановкой для тождества t.