Answers (почти все билеты на 22 страницы), страница 2

не ∃ окрестности рассмотрением которой можно ограничиться.5. Градиентный алгоритм. Оценка сложности (величины) покрытия, получаемогоградиентным алгоритмом. Использование градиентного алгоритма для построениятупиковой ДНФ.Комментарий речь идет об эвристическом алгоритме позволяющем получать «не оченьдлиные» ДНФ.Градиентный алгоритм. На каждом шаге в матрице выбирается и включается впокрытие такая строка, которая покрывает наибольшее число еще не покрытых столбцов(если таких несколько из них выбирается строка с наименьшим номером).

После этого тестолбца которые были покрыты, удаляются из рассмотрения. Алгоритм продолжаетработу пока есть столбцы – на его выходе «не очень длинная» тупиковая ДНФ.Оценка сложности Пусть размер матриц MxN. Пусть P минимальная доля строкпокрывающих столбец (среди всех столбцов). Выбрали строчку – покрыли PN столбцов(не меньше), осталось матрица (M-1)x(1-P)N. Пусть s шагов. Необходимое условие1(1 − P) s N ≤ 1 откуда получаем оценку для s ≥ log1− PN6. Нижняя оценка функции Шеннона для СФЭ.Опр.

Схемой из функциональных элементов над базисом Б называетсяориентированный (пары вершин (дуги) рассматриваются как упорядоченные)ациклический (не содержит ориентированных циклов) упорядоченный (дуги входящие вкаждую его вершину пронумерованы) граф Σ, вершины которого помечены следующимобразом:ƒ Каждый исток (вершина в которую не входит ни одна дуга) помечен некоторой БПиз Х, причем различные истоки помечены различными БП;ƒ Каждая отличная от истока вершина ν схемы Σ помечена ФС (алфавитфункциональных символов) ϕi где ki = d + (ν ) ;ƒ Некоторые вершины Σ помечены выходными БП из Z так, что одной и той жевершине может быть сопоставлена одна и та же БП.

При этом входные (выходные)БП, которые приписаны каким-либо вершинм Σ, считаются входными(соответственно выходными) БП Σ, а те вершины которым они сопоставлены –входами (выходами) СФЭ Σ.Где Х – входные БП, а Z – выходные БП.Опр. Число ФЭ в СФЭ назовем ее сложностью.Опр. Функцией Шеннона для класса СФЭ над базисом Б назовем функцию натуральногоаргумента n которая равна максимуму сложности по всем функциям от n переменных.Функция Шеннона характеризует сложность самой сложной ФАЛ.Лемма Для любой ФАЛ от n перменных существует СФЭ реализующая f со сложностьюне более чем n * 2 n +1Утв.

Число схем с n входами и одним выходом содержащим h элементов базиса Б( ¬,∧,∨ ),1те S (n,1, h) ≤ 3 n (n + h) 2 h +1h!2nТеорема L(n) >nДок-во1S (n,1, h) ≤ 3 n (n + h) 2 h +1h!hh111S (n, p, h) = ∑ S (n,1, i ) ≤ ∑ 3n (i + n) 2i +1 ≤ (h + 1) 3n (h + n) 2 h +1 ≤ 3n (h + n) 2 h + 2h!h!i =1i = 0 i!c2nЕсли h=n S (n,1, h) ≤ ( ) h 3h (2h) 2 h +1 = (ch) h , где с = const. Пусть h = , тогдаnn2n2nS (n,1, h) ≤ (c ) n , верхняя грань кол-во функций которые реализует схема сложности hn2nn2n2nне хватает длядля ФАЛ от n БП. (c ) n < 22 при n → ∞ .

Так что сложности h =nn2nреализации всех ФАЛ, следовательно L(n) > .n7. Ассимптотически наилучший метод О.Б.Лупанова синтеза СФЭ в базисе ( ¬,∧,∨ ).Теорема для СФЭ в базисе ( ¬,∧,∨ ) можно построить ассимптотически наилучший методсинтеза и L(n) ~2n.nДок-во Произвольная ФАЛ задается с помощю таблицы размера 2k 2n − k . Строкинумеруются по наборам значений первых k переменных, столбцы по оствшимся n-k.Столбец с номером σ k +1σ k + 2 ...σ n задает функцию F ( x1 x2 ...xkσ k +1σ k + 2 ...σ n ) которая в своюочередь является компонентой разложения исходной функции f (в СДНФ).

Напересечении строки σ 1σ 2 ...σ k и столбца σ k +1σ k + 2 ...σ n помещаем значение f в этой точке.Возбмем целое число 1 < s < 2n и разрежим таблицу на полосы шириной s, которыезанумеруем. Рассмотрим полосу с номером i. Она распадается на короткие столбцывысотой s видов которых не более чем 2 s , пронумеруем их. Пусть γ 1γ 2 ...γ s столбец jого⎧γ , (σ σ ...σ ) = (σ 1 (l )σ 2 (l )...σ k (l )), l = 1..sсорта, обозначим за Fik ( x1 x2 ...xk ) = ⎨ l 1 2 k0, (σ 1σ 2 ...σ k ) ∉ iой полосе⎩8. Контактные схемы.

Схемы для медианы. Схемы Кардо.Опр. Контактная схема – не ориентированный граф. Ребрам приписываем литералы.Если ребру приписан х то говорят что ребро проводит при х = 1 и не проводит при х = 0.Ребра называются контактами. Если ребро помечено литералом без отрицания то ононазывается замыкающим контактом, с отрицанием – размыкающим. В схеме выделяют2 и более вершины полюсы.

Они образуют сеть.Опр. Сложность схемы – число контактов.Опр. Медиана,реализуетфункцию:F = xy∨yz∨zxОпр. Схема Кардо:Сумма по модулю «2», логический смысл чтобы оказаться наверху надо перепрыгивать поединице. Сложность: 4n-49. Нижняя оценка порядка функции Шеннона для контактных схем.L(n) = max min ( L(∑))f ∈P2 n∑ реализfКак оценить снизу функцию Шеннона для КС: LKC (n) ?Введем функионал S(L, n) – число схем от n БП сложностью не выше L.nS ( L, n) ≤ LL2 (2nL2 ) L и должно выполнятся S ( L, n) ≥ 2 2 (иначе схем не хватит)Логарифмируем и поучаем оценку: 3 log L + L(log 2n + 2 log L) ≥ 2 nУтв. Неравенство нарушается если: L ~ <2n 1( − ε ) при n → ∞n 2Комментарий S ( L, n) ≤ LL2 (2nL2 ) L1.

первая L собственно сложность2. Число вершин не больше чем на L больше числа контактов если схема связная –отсюда L23. 2nL2 - варианты выбора контактов.4. степень L так как L раз ставим 2 контакта в схему.10. Метод Шеннона для синтеза контактных схем.Утв для любого n можно построить универсальный многополюсник Un (схемаnреализующая все ФАЛ от n-1 переменной). L(Un) <= 2 * 22Теорема Шеннона Существует алгоритм который позволяет построить схему со2nдля любой ФАЛ от n переменных.сложностью L(n) <= 8 *n11. Метод каскадов для КС и СФЭ12. Самокорректирующаяся контактная схема, схемы с исправлением одногозамыкания (размыкания).Задачи: собрать схему которая будет:ƒ легко обнаруживать неисправности;ƒ работать даже при наличии неисправности;2nи почти всеТеорема Для любой ФАЛ найдется схема Sn порядка сложности не болееnконтакты расположенные в однородных метелках размера Θ( n )Следствие При одной ошибке сложность ассимптотически не увеличивается.13.

Асимптотически наилучший метод синтеза СФЭ корректирующихнеисправность фиксированного числа ненадежных элементов.14. Эквивалентные преобразования формул в базисе ∨,&,¬,0,1,х.Опр. Формулы Ф1 и Ф2 эквивалентны если задают равны е функции.Эквивалентность можно определить перебором значений, выписав СДНФ,Рассмотрим (∨,&,¬,0,1,х):1. Коммутативность х∨у = у∨х; х&у = у&х;2. Ассоциативность х∨(у∨z) = (х∨у)∨z; х&(у&z) = (х&у)&z;3. 0 = ¬x&x; 1 = ¬x∨x;4.

¬(x&y) = ¬x∨¬y; ¬(x∨y)= ¬x&¬y;5. x&(y∨z) = x&y∨x&z; x∨(y&z) = (x∨y)&(x∨z);15. Теорема переходаСокращение конечной полной системы тождеств (КПСТ)Наличие конечной полной системы множеств не зависит от базиса для замкнутого класса.16. Пример Линдона17. Проблема контроля управляющих систем. Тесты для таблиц. Тривиальныеоценки. Верхняя оценка длины диагностического теста для почти всех таблиц.Мера задачи – кол-во наборов достаточное чтобы сделать вывод.18. Градинтный алгоритм.

Алгоритм построения всех тупиковых тестов.19. Полный диагностический тест для контактных схем.20. Проблема NP полноты. Теорема Кука (формулировка). NP полнота языкаКЛИКА.21. NP Поднота языка 3-ВЫП и полиномиальность языка 2-ВЫП22. Задача о кратчайшем остовном дереве. Жадный алгоритм для нее.23. NP-полнота языка ВП. Свойство жадного алгоритма для задачи МВП..