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

Курс «Основы кибернетики»для бакалавров (интегрированных магистров)направления 01400 «Прикладная математика иинформатика» профиля «Математические методыобработки информации и принятия решений»9.Планы семинарских занятий на осенний семестр 2017-2018 уч.

года иориентировочный график их проведенияСеминар 1 (4.IX–8.IX)Комбинаторика граней единичного булева куба. Представление ФАЛ с помощью ДНФ и его «геометрическая» интерпретация, совершенная ДНФ. Сокращённая ДНФ и «геометрические» методыеё построения, карта Карно. Теоретический материал [1: с.

19–32], [5: с. 290–292, 296–298].В классе. Из [5]: гл. IX — 1.2 (1-6); гл. I — 2.3 (3). Найти число тех ФАЛ от n, n > 2, БП,совершенная ДНФ которых является их единственной ДНФ и имеет длину 2 (К1); доказать,что длина совершенной ДНФ от БП x1 , . . . , xn , являющейся единственной ДНФ реализуемойею ФАЛ, не больше, чем 2n−1 (К2). Из [5]: гл. IX — 2.1 (1,2), 2.5 (1,5), 2.6 (1,5).На дом. Из [5]: гл. IX — 1.2 (7,9); гл. I — 2.3 (4). Найти число тех ФАЛ от БП x1 , .

. . , xn , n > 2,совершенная ДНФ которых является их единственной ДНФ длины 2n−1 (Д1) и длины 3 (Д2).Из [5]: гл. IX — 2.1 (3), 2.5 (2,6), 2.6 (2,6).Семинар 2 (11.IX–15.IX)Алгебраические методы построения сокращённой ДНФ. Тупиковые ДНФ, ядро и ДНФ пересечение тупиковых. Теоретический материал [1: с. 32–36, 38–41], [5: с. 296–298, 301–303].В классе.T Из [5]: гл. IX — 2.3 (1,2), 2.2 (1,2), 2.9 (3), 2.14 (1,2), 3.3 (1,2) — построить ядро иДНФ T , 2.12 (3).TНа дом. Из [5]: гл.

IX — 2.3 (3,4), 2.2 (3,4), 2.9 (5), 3.3 (3,4) — построить ядро и ДНФ T ,2.12 (6), 2.13.Семинар 3 (18.IX–23.IX)ДНФ Квайна и ДНФ сумма тупиковых. Таблица Квайна, методы построения всех тупиковых(минимальных, кратчайших) ДНФ. Теоретический материал [1: с. 41–44, 51–55], [5: с. 301–303].PВ классе. Из [5]: гл. IX — 3.1 (1,5), 3.3 (1,2) — построить ДНФ Квайна и ДНФ T , 3.4 (3),3.6 (1,4,7).PНа дом.

Из [5]: гл. IX — 3.1 (4,6), 3.3 (3,4) — построить ДНФ Квайна и ДНФ T , 3.4 (4),3.6 (3,6,8).Семинар 4 (25.IX–29.IX)Особенности ДНФ для некоторых типов ФАЛ, оценки числа тупиковых (минимальных) ДНФ.Разбор задач к контрольной №1. Теоретический материал [1: с. 44–50, 59–65], [5: с. 301–303].В классе. Построить совершенную и сокращённую ДНФ ФАЛ f (x1 , x2 , x3 ), если известно, чтоона линейно зависит от БП x1 и Nf ⊇ {(000), (101)}, N f ⊇ {(110), (011)} (К1). Из [5]: гл.

IX —2.9 (2). Построить сокращённую ДНФ монотонной ФАЛ из P2 (4), нижними единицами которойявляются наборы (0101), (1011), (1100), (0110) (К2). Из [5]: гл. IX — 2.12 (2), 3.7 (2).1На дом. Построить совершенную и сокращённую ДНФ ФАЛ f (x1 , x2 , x3 , x4 ), если известно,что она линейно зависит от БП x1 , x2 и Nf ⊇ {(0100), (1001)}, N f ⊇ {(1010), (1111)} (Д1). Построить сокращённую ДНФ монотонной ФАЛ из P2 (4), нижними единицами которой являютсянаборы (1010), (0100), (0011), (1001) (Д2).

Из [5]: гл. IX — 2.9 (8), 2.12 (8), 3.7 (4).Семинар 5 (2.X–6.X)Эквивалентные преобразования формул. Теоретический материал [1: с. 86–90, 146–161], [4: с. 19].В классе. Из [4]: 3.1 (1), 3.3 (1,4), 3.8 (1–3), 3.9 (1).˙На дом. Из [4]: 3.1(2),3.3 (3,6), 3.8 (5–9), 3.9 (2).Семинар 6 (9.X–13.X)Задание формул деревьями, оптимизация подобных формул по глубине. Контактные схемы иπ-схемы, моделирование формул и π-схем. Теоретический материал [1: гл. 2, §§2, 5].В классе.1. Построить по заданной формуле F, F = (x1 ∨ x2 ) ∨ x3 x1 (x3 ∨ x4 ) ∨ x1 (x3 x4 ) ∨ (x1 ∨∨ x2 )(x1 ∨ x2 ) , соответствующее ей дерево, а затем перейти от него к дереву (формуле)минимальной сложности с использованием многовходовых ФЭ &, ∨, которая соответствуетклассу всех формул базиса Б0 , подобных исходной; найти число всех таких формул.2. Построить в Б0 формулу минимальной глубины, подобную формуле F, F = x1 x2 x3 ∨ x1 x3 ∨∨ x2 x4 x5 ∨ x4 x5 x6 , (минимальность обосновать).3.

С помощью различных приёмов (просмотр всех наборов, нахождение всех простых проводящих цепей, а также всех тупиковых неединичных сечений) построить таблицу истинностиФАЛ, реализуемых КС, показанными на рис. 10 и 12 из [4].4. Построить π-схемы, моделирующие: а) конкретные ДНФ и КНФ; б) сокращённую ДНФмультиплексорной ФАЛ µn (на базе КД); в) совершенную ДНФ ФАЛ f (x1 , x2 , x3 ), столбецзначений которой имеет вид α̃f = (0110 1100) (на базе КД).На дом. В соответствии с приведёнными выше пунктами 1–4:1.

F = (x1 x2 ∨ x3 )(x1 ∨ x2 ∨ x4 ) ∨ x1 (x2 ∨ x3 )(x3 ∨ x4 ).2. F = x1 ∨ x2 x3 x4 x5 ∨ x2 x3 x4 ∨ x4 x5 ∨ x5 x6 .3. Рис. 13, 14, 17 из [4].4. в) α̃f = (1101 1001 0111 1001).Семинар 7 (16.X–20.X)Эквивалентные преобразования КС. Теоретический материал [1: с. 169–185].В классе. Из [4]: 4.1 (2,4,6–8), 4.3 (1).На дом. Из [4]: 4.1 (9–12), 4.3 (3).Семинар 8 (23.X–27.X)Эквивалентные преобразования КС (окончание). Схемы из функциональных элементов (СФЭ),их эквивалентные преобразования (ЭП) с помощью основных тождеств путём моделированияЭП соответствующих формул. Теоретический материал [1: с. 169–185, 146–156].2В классе.τm1. Для заданных эквивалентных КС Σ0 , Σ00 от БП X(n) и m 6 n построить ЭП Σ0 |⇒ Σ00 , аτkзатем доказать, что Σ0 |6⇒ Σ00 при k < m:а) m = n = 3, а Σ0 и Σ00 — КС из задачи 4.1 (9) домашнего задания семианара 7;б) m = n = 3, а Σ0 и Σ00 — π-схемы, моделирующие левую и правую части тождества tД∨,& ;в) m = 2, n = 3, Σ0 — первая (левая) КС из задачи 4.1 (10) домашнего задания семинара 7,а КС Σ00 получается из второй (правой) КС этой задачи перестановкой контактов x, z ипроведением цепи из контактов y, z, соединяющей неполюсные вершины;г) m = n = 2, а Σ0 — первая (левая) КС из задачи 4.1 (11) домашнего задания семинара 7, аКС Σ00 получается из второй (правой) КС этой задачи проведением цепи из контактов x,y, соединяющей полюса 1 и 2.2.

Для формулы F построить соответствующее ей квазидерево, а затем перейти от него к более«компактной» СФЭ, применяя операцию «отождествления» максимальных по включениюизоморфных квазиподдеревьев до тех пор, пока это возможно:F = (x1 x2 ) ∨ x3 x2 x3 ∨ x1 x4 ∨ x1 x2 ∨ (x1 x4 .3. Вывести формульное тождество t из системы тождеств τ , а затем промоделировать этотвывод в классе СФЭ:ДОПАКt = tП , τ = {tПК1& , t&∨ , t∨ , τ , τ }.На дом.

В соответствии с приведёнными выше пунктами 1–3:1. а) m = n = 3, а Σ0 и Σ00 — π-схемы, моделирующие две части формульного тождества(x1 ∨ x1 x2 )(x2 ∨ x3 ) = x2 ∨ x1 x3 ;б) m = n = 3, а Σ0 и Σ00 — КС от БП X(3) с полюсами 1, 2, 3 такие, что в КС Σ0 полюс сномером i, i = 1, 2, 3, соединён с её единственной внутренней вершиной контактом xi ,а в КС Σ00 , не имеющей внутренних вершин, он соединён с полюсом j, 1 6 i < j 6 3,цепочкой контактов xi xj ;2.

F = (x1 (x2 x3 ))(x4 ∨ x1 ∨ x3 ) ∨ x2 x3 (x4 ∨ x1 );3. t — тождество обобщённого склеивания, τ = τ̃осн — расширенная система основных тождеств.Семинар 9 (30.X–3.XI)Повторение материала 5, 7 и 8 семинарских занятий. Подготовка к контрольной по второмуразделу (контрольная работа №2).Семинар 10 (7.XI–10.XI)Сложность ФАЛ и методы синтеза схем на основе ДНФ. Теоретический материал [1: с.

186–210].В классе. Из [5]: гл. X — 1.1 (2, 3, 4, ФАЛ µ1 (x1 , x2 ∨ x3 , x4 · x5 ) = x1 (x2 ∨ x3 ) ∨ x1 (x4 · x5 ) — какв классе СФЭ (К1), так и в классе КС (К2), а также ФАЛ (x1 ∨ x2 )x3 ∨ (x1 ∨ x2 )x4 — в классеКС (К3)); 2.4 (1); доказать минимальность некоторых из построенных в предыдущих задачахсхем.На дом. Из [5]: гл. X — 1.1 (5–7), 2.4 (2); доказать минимальность некоторых из построенных впредыдущих задачах схем.3•x11x4•x31x5••x3••x3x5x4x3x2x4•x1•x2••x4x2x1x32x12x5x4•x2•x3•x5x4(а) В классе.(б) На дом.Рис. 1. Каскадные контактные схемы к семинарам 11 и 12.Семинар 11 (13.XI–17.XI)Каскадные КС и инверсные КС, метод каскадов для КС. Метод Шеннона.

Теоретическийматериал [1: с. 186–210].В классе. Для заданной на рис. 1а каскадной КС построить инверсную к ней КС (К1). Из [5]:гл. X — 2.13 (1, 4, 7), 2.14 (1), 2.14 (2 — с оптимизацией сложности за счёт выбора порядка БПразложения), 2.14 (5). Разлагая ФАЛ от 3 или 4 БП по всем БП, кроме последней, построитьдля неё КС (К2) и СФЭ (К3) по методу Шеннона.На дом. Для заданной на рис. 1б каскадной КС построить инверсную к ней КС (Д1).

Из [5]:гл. X — 2.13 (2, 5, 6), 2.14 (3 — с оптимизацией сложности за счёт выбора порядка БПразложения), 2.14 (6). Разлагая ФАЛ от 3 или 4 БП по всем БП, кроме последней, построитьдля неё КС (Д2) и СФЭ (Д3) по методу Шеннона.Семинар 12 (20.XI–24.XI)Моделирование каскадных КС в классе СФЭ. Метод каскадов и метод Шеннона для СФЭ.Теоретический материал [1: с. 186–210].В классе. Показанную на рис.