Планы семинарских занятий, страница 2

1а каскадную КС промоделировать в классе СФЭ (К1). С помощью метода каскадов построить СФЭ для ФАЛ и систем ФАЛ из [5]: гл. X — 2.13 (1, 4, 7),2.14 (1), 2.14 (2), 2.14 (5). Используя метод Шеннона доказать, что LC (4) 6 18 (К2).На дом. Показанную на рис. 1б каскадную КС промоделировать в классе СФЭ (Д1). С помощьюметода каскадов построить СФЭ для ФАЛ и систем ФАЛ из [5]: гл.

X — 2.13 (2, 5, 6), 2.14 (3),2.14 (6). Используя метод Шеннона доказать, что LC (5) 6 34 (Д2).Семинар 13 (27.XI–1.XII)Асимптотически наилучшие методы синтеза, синтез схем для ФАЛ из специальных классов.Теоретический материал [1, с. 215–240].В классе. Выписать таблицу значений ФАЛ стандартного ДУМ порядка 3 и высоты 3 (К1).Построить 2-регулярное разбиение куба B 4 , на каждой компоненте которого каждая из ФАЛx1 → x2 , x1 ⊕ x2 моделируется либо БП, либо её отрицанием (К2). Установить асимптотикуфункции Шеннона для сложности класса всех ФАЛ равных 1 при x1 = 1 (КС) (К3); классавсех самодвойственных ФАЛ (СФЭ) (К4); класса всех ФАЛ симметричных по первым тремБП (КС) (К5); класса ФАЛ f (x1 , . .

. , xn ) от n, n = 3, 4, . . ., БП, обладающих тем свойством,что множество ФАЛ вида f (σ1 , σ2 , x3 , . . . , xn ), где (σ1 , σ2 ) ∈ B 2 , состоит из 4 различных попарноортогональных ФАЛ, дизъюнкция которых равна 1 (СФЭ) (К6).На дом. Выписать таблицу значений ФАЛ ДУМ порядка 3, связанного с разбиением куба B 3на 3 подмножества: B13 , B23 , B03 ∪ B33 (Д1). Построить 2-регулярное разбиение куба B 7 , накаждой компоненте которого любая отличная от константы ФАЛ от БП x1 , x2 моделируетсялибо БП, либо её отрицанием (Д2). Установить асимптотику функции Шеннона для сложностикласса всех ФАЛ, равных 0 при x1 = x2 = 0 (КС) (Д3); класса, состоящего из всех тех ФАЛ, укоторых любая подфункция от первых трёх БП линейна (Д4); класса ФАЛ f (x1 , .

. . , xn ) от n,4n = 3, 4, . . ., БП, обладающих тем свойством, что множество ФАЛ вида f (σ1 , σ2 , x3 , . . . , xn ), где(σ1 , σ2 ) ∈ B 2 , состоит из 4 различных попарно ортогональных ФАЛ (СФЭ) (Д5).Семинар 14 (4.XII–8.XII)Синтез самокорректирующихся КС. Подготовка к контрольной по третьему разделу курса.Теоретический материал [4: с. 49–50].В классе.1.

Из [4]: 7.9 (б), 7.10 (1), 7.13 (по книге [4] 2002 года: 7.7 (б), 7.8 (1), 7.11 (1)).2. Повторение материала семинарских занятий:а) семинар 10 (индивидуальная сложность ФАЛ) — построить минимальную (1, 1)-КС дляФАЛ f , заданной равенствомf (x1 , x2 , x3 , x4 , x5 ) = (x1 ∨ x2 ∨ x3 )x4 ∨ (x1 ∨ x2 ∨ x3 )x5 ;б) семинары 12 и 11 (метод каскадов для КС и СФЭ) — с помощью метода каскадов,последовательно разлагая реализуемые ФАЛ по x1 , x2 , x3 , x4 , построить (1, 2)-КС Σдля системы ФАЛ F = (f1 , f2 ) и СФЭ S для ФАЛ f1 , где f1 = (0110 1000 1000 0101),f2 = x1 x2 (x3 ⊕ x4 ) ∨ x1 x2 x4 ;в) семинар 13 (синтез схем для ФАЛ из специальных классов) — разбор задачи Д4 или Д5из его домашнего задания.На дом.1.

Из [4]: 7.9 (в), 7.10 (2), 7.11 (а) (по книге [4] 2002 года: 7.7 (в), 7.8 (2), 7.9 (а)).2. Повторение материала предыдущих семинарских занятий:а) построить минимальную (1, 1)-КС для ФАЛ f , заданной равенствомf (x1 , x2 , x3 , x4 ) = x1 x2 x3 x4 x5 ∨ x1 x2 x3 x4 x5 ∨ x1 x2 x4 x5 ;б) с помощью метода каскадов, последовательно разлагая реализуемые ФАЛ по x1 , x2 , x3 ,x4 , построить (1, 2)-КС Σ для системы ФАЛ F = (f1 , f2 ) и СФЭ S для ФАЛ f1 , гдеf1 = (1001 0110 1001 0111), f2 = x1 (x3 ∨ x4 ) ∨ x1 (x2 ⊕ x3 ⊕ x4 );в) установить асимптотику сложности реализации схемами из функциональных элементовсамой сложной из тех ФАЛ f (x1 , . . . , xn ), n > 1, которые на любой паре противоположныхнаборов, за исключением пары {(0, .

. . , 0), (1, . . . , 1)}, принимают одинаковые значения.Семинар 15 (11.XII–15.XII)Тесты для таблиц, тесты для контактных схем. Теоретический материал: [1: с. 65–72, 51–55],[4: с. 32–34, 37–38].В классе. Из [4]: 5.1 (1, 2 — все тупиковые диагностические тесты), 5.1 (3 — все тупиковыепроверяющие тесты), 6.2, 6.4, 6.11 (если хватит времени).На дом. Из [4]: 5.1 (5 — все тупиковые диагностические тесты, 6 — все тупиковые проверяющиетесты), 6.3, 6.5, 6.14.5.