IV. Надёжность и контроль управляющих систем (23.IV, 30.IV)
23. Задача контроля схем и тесты для таблиц. Построение всех тупиковых тестов, оценки длины диагностического теста. См. [1:гл.1,§8]. (23.IV)
24. Самокорректирующиеся КС и методы их построения. Асимптотически наилучший метод синтеза КС, корректирующих 1 обрыв (1 замыкание). См. [4:§7], [2: ч. III, р. 2, §1]. (30.IV)
V. Некоторые вопросы сложности алгоритмов и классы схем, имеющие отношение к их программно-аппаратной реализации (11.III, 1.IV и 7, 17.V)
25. Доказательство теоремы Кука. Примеры NP-полных проблем, связанных с графами. См. [6:§§4-6]. (11.III)
26. Некоторые модификации основных классов схем (BDD, вычисляющие программы, схемы на КМОП-транзисторах и др.), ориентированные на программно-аппаратную реализацию ФАЛ. См. [1:гл.2,§§4,6,7]. (17.V)
27. Реализация автоматных функций схемами из функциональных элементов и элементов задержки, схемы с «мгновенными» обратными связями. См. [7:§8], [2: ч. I, р. I, гл. 3, §§2-3]. (7.V)
28. Задачи логического и топологического синтеза СБИС, основные этапы и методы их решения. См. [1:гл.2,§7], [9]. (17.V)
Типовые задачи к экзамену
I. Задачи на ДНФ
1. По заданной ФАЛ построить её сокращённую ДНФ, ДНФ Квайна, ДНФ сумма тупиковых, все тупиковые ДНФ.
II. Задачи на структурное моделирование и эквивалентные преобразования
2. По заданной формуле построить подобную ей формулу минимальной глубины.
3. По заданной формуле с поднятыми отрицаниями построить моделирующую её πсхему и обратно.
|
|
4. По заданным эквивалентным формулам или КС построить эквивалентное преобразование, переводящее их друг в друга с помощью основных тождеств.
III. Задачи на синтез схем
5. По данной каскадной КС построить инверсную каскадную КС.
6. По заданной ФАЛ с помощью простейших методов, метода каскадов или метода Шеннона построить реализующую её СФЭ или КС.
7. Оценить сверху и снизу сложность конкретной ФАЛ или сложность самой сложной ФАЛ из заданного множества в заданном классе схем.
IV. Задачи на самокоррекцию и тесты.
8. По заданной КС построить эквивалентную ей самокорректирующуюся КС.
9. По заданной таблице или КС и списку её неисправностей построить все тупиковые проверяющие (диагностические) тесты.
Планы семинарских занятий и даты их проведения
Общий план содержит 8 семинарских занятий, 7 из которых проходят по пятницам один раз в две недели. Основная часть занятий проводится в каждой группе по основному расписанию (ОР), а оставшаяся часть – либо по дополнительному расписанию (ДР), отличающемуся от ОР только чётностью недели, и, возможно, переносом на 2-ю пару, либо вне ОР и ДР. В приведённом ниже графике занятия, по умолчанию, проходят по ОР. При этом в группах I недели (323, 324 и 327 гр.) пройдет 3, а в группах II недели (320, 321, 235 и 328 гр.) – 1 семинар по ДР.
|
|
Семинар 1 (8.II и 15.II)
Представление ФАЛ с помощью ДНФ, импликанты и простые импликанты ФАЛ. Сокращённая ДНФ и методы её построения.
Теоретический материал [1: с. 27-35], [5: с. 47, 296-298].
В классе. Из [5]: гл. I – 2.3 (3); гл. IX – 2.1 (1,2), 2.5 (1,5), 2.6 (1,5), 2.3 (1,2), 2.2 (1,2), 2.9 (1,2).
На дом. Из [5]: гл. I – 2.3 (4); гл. IX – 2.1 (3), 2.5 (2,6), 2.6 (2,6), 2.2 (3,4), 2.3 (3,4), 2.9 (6).
Семинар 2 (22.II и 1.III)
Ядро и ДНФ Квайна, ДНФ сумма тупиковых. Построение всех тупиковых ДНФ.
Теоретический материал [1: с. 38-43, 51-55], [5: с. 301-302].
В классе. Из [5, гл. IX]: 3.1 (1, 5), 3.3 (1, 2 – построить ядро, ДНФ Квайна и ДНФ сумма тупиковых), 3.4 (3), 3.6 (1, 4, 7).
На дом. Из [5, гл. IX]: 3.1 (4, 6), 3.3 (3, 4 – построить ядро, ДНФ Квайна и ДНФ сумма тупиковых), 3.4 (4), 3.6 (3, 6, 8).
Семинар 3 (15.III, гр. I недели – ДР)
Эквивалентные преобразования формул.
Теоретический материал [1: с. 146-148, 156-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).
Семинар 4 (29.III, гр. I недели – ДР)
Моделирование формул и π-схем. Эквивалентные преобразования КС.
Теоретический материал [1: с. 169-185].
В классе. Промоделировать π-схемой какую-нибудь формулу с поднятыми отрицаниями. Промоделировать формулой какую-нибудь π-схему. Из [4]: 4.1 (2, 4, 6–8), 4.3 (1).
|
|
На дом. Промоделировать π-схемой какую-нибудь формулу с поднятыми отрицаниями. Промоделировать формулой какую-нибудь π-схему. Из [4]: 4.1 (9–12), 4.3 (3).
Семинар 5 (5.IV и 12.IV)
Сложность ФАЛ и методы синтеза схем на основе ДНФ.
Теоретический материал [1: с. 186-210].
В классе. Из [5: гл. X]: 1.1 (2, 3, 4, ФАЛ – как в классе СФЭ, так и в классе КС, а также ФАЛ – в классе КС); 2.4 (1); доказать минимальность некоторых из построенных в предыдущих задачах схем.
На дом. Из [5: гл. X]: 1.1 (5-7), 2.4 (2); доказать минимальность некоторых из построенных в предыдущих задачах схем.
Дата добавления: 2019-03-09; просмотров: 202; Мы поможем в написании вашей работы! |
Мы поможем в написании ваших работ!