Вопросы, типы задач и список литературы к экзамену (1186173)
Текст из файла
Список вопросов к экзамену по курсу «Элементы теории синтеза,надёжности и контроля дискретных управляющих систем»(осенний семестр 2016-2017 уч. года; группа 512/2;лекторы – проф. Ложкин С.А. и доц. Романов Д.С.)I.Геометрическая реализация схем на примере клеточных СФЭ1. Клеточные СФЭ как «грубая» топологическая модель СБИС. Реализация дешифраторов,мультиплексоров и поведение функции Шеннона (ФШ) для площади клеточных СФЭ.См. [1]2. Асимптотика площади клеточного дешифратора, антагонизм его площади и сложности.См.
[1]II. Методы синтеза и асимптотические оценки высокой степени точности для сложностисхем из некоторых классов3. Верхние оцени числа усилительных СФЭ и формул в произвольном базисе; уточнённыеверхние оценки числа усилительных СФЭ и формул в некоторых базисах. См. [2: §2]4. Уточнённые верхние оценки числа схем контактного типа. См.
[2: §1]5. Уточнённые нижние мощностные оценки ФШ для сложности схем контактного типа, длясложности формул, СФЭ и усилительных СФЭ в произвольном базисе, а также сложностиусилительных СФЭ и формул в некоторых базисах. См. [2: §§1,2]6. Универсальные системы ФАЛ и их построение на основе селекторных разбиенийпеременных. См. [2: §3]7. Селекторные разбиения переменных некоторых ФАЛ. Синтез усилительных СФЭ внекоторых базисах и асимптотические оценки высокой степени точности (АОВСТ) ФШ дляих сложности. См. [2: §5]8. АОВСТ ФШ для сложности формул в некоторых базисах.
См. [10: §6]9. АОВСТ ФШ для сложности итеративных контактных схем и контактных схем в некоторыхбазисах. См. [2: §4]10. Мультиплексорные ФАЛ и их обобщённое разложение, оценки глубины еговспомогательных ФАЛ. См. [2: §7]11. Оптимальная по задержке реализация мультиплексорных ФАЛ в произвольном базисе иАОВСТ ФШ для задержки ФАЛ в нём. См. [3]III. Контроль и надёжность дискретных управляющих систем12. Тесты для входов схем. Оценки функции Шеннона длины полного проверяющего теста приконстантных неисправностях на входах схем. См. [5: c. 117-119].13. Оценки функции Шеннона длины единичного диагностического теста при константныхнеисправностях на входах схем. См. [5: с.
120-122].14. Оценки функции Шеннона длины диагностического теста при кратных константныхнеисправностях на входах схем. См. [8: с. 72-76].15. Верхняя оценка функции Шеннона длины проверяющего теста при инверсиях входов схем.См. [6: с. 47-50].16.
Нижняя оценка функции Шеннона длины проверяющего теста при инверсиях входов схем.См. [6: с. 50-52].17. Теорема Редди о единичных проверяющих тестах для схем из функциональных элементов(СФЭ) в базисе полиномов Жегалкина при константных неисправностях на входах ивыходах элементов. См. [5: с. 109-116].18. Полный проверяющий тест длины 2 при однотипных константных неисправностях навыходах элементов (для СФЭ в стандартном базисе). См. [9].19. Единичный диагностический тест при инверсных неисправностях на выходах элементов вбазисе Жегалкина. См. [10].20.
Теорема Пиппенджера о возможности построения надежных (в слабом смысле) схем безпорядкового ухудшения сложности. См. [5: с. 48-55].21. Нижняя логарифмическая оценка избыточности для некоторых булевых функций приинверсных неисправностях на входах элементов. См. [12: с. 594-598].1Типовые задачи к экзаменуII. Задачи на методы синтеза и асимптотические оценки высокой степени точности длясложности схем из некоторых классов1. Построить по заданной («внешней») ФАЛ на основе селекторного разбиения её БПсоответствующее -универсальное множество функций.2. Найти внутренние ФАЛ обобщённого разложения заданной мультиплексорной ФАЛ позаданной внешней ФАЛ этого разложения.3.
Построить регулярное моделирующее заданную систему ФАЛ разбиение единичного кубазаданной размерности.4. Установить нижние (верхние) АОВСТ функции Шеннона для заданного класса схем.III. Задачи на контроль и надёжность дискретных управляющих систем5. Найти длину минимального теста заданного типа для заданной схемы.6.
Построить для заданной булевой функции реализующую ее СФЭ, допускающую тестзаданного типа, имеющий длину, не превосходящую указанной величины.7. Подсчитать по заданной схеме ее надежность (в указанном смысле) относительнозаданного источника неисправностей.8. Построить в базисе с указанными режимами работы элементов последовательность схем,реализующих заданную булеву функцию сколь угодно надежно.ЛитератураI раздел:1. Ложкин С.А. Клеточные схемы из функциональных элементов: лекционные слайды(http://mk.cs.msu.ru/index.php/Элементы_теории_синтеза,_надежности_и_контроля_дискретных_управляющих_систем).II раздел:2. Ложкин С.А.
Дополнительные главы кибернетики (Электронные версии лекций последнихлет можно найти по адресу http://mk.cs.msu.ru/index.php/Дополнительные_главы_кибернетики_и_теории_управляющих_систем)3. Ложкин С.А. О глубине функций алгебры логики в произвольном полном базисе // ВестникМоск. ун-та. Сер. 1. Математика. Механика. 1996, №2.
С. 80-82.III раздел:4. Яблонский С.В. Элементы математической кибернетики. М.: Высшая школа, 2007. 188 с.5. Редькин Н.П. Надежность и диагностика схем. М.: МГУ, 1992. 192 с.6. Кудрявцев В.Б., Гасанов Э.Э., Долотова О.А. Теория тестирования логических устройств.М.: Физматлит, 2006. 160 с.7.
Ложкин С.А. Лекции по основам кибернетики. М.: МАКС Пресс, 2004. 256 с.8. Носков В.Н. Диагностические тесты для входов логических устройств // Дискретныйанализ. Вып. 26. Новосибирск: Изд-во ИМ СО АН СССР, 1974. С. 72-83.9. Бородина Ю.В. О синтезе легкотестируемых схем в случае однотипных константныхнеисправностей на выходах элементов // Вестник Моск. ун-та. Сер. 15. Вычисл. матем. икиберн. 2008, №1. С. 40-44.10. Романов Д.С. Метод синтеза неизбыточных схем в базисе Жегалкина, допускающихединичные диагностические тесты длины один // Известия высших учебных заведений.Поволжский регион.
Физико-математические науки. 2015, № 4. С. 38-54.11. Pippenger N. On networks of noisy gates // Proc. 26th Ann. Symp. Foundations Comput. Sci.1985. P. 30-36.12. Gál A. Lower bounds for the complexity of reliable Boolean circuits with noisy gates // Proc. 32ndAnn. Symp. Foundations Comput. Sci. 1991. P. 594-601.2.
Характеристики
Тип файла PDF
PDF-формат наиболее широко используется для просмотра любого типа файлов на любом устройстве. В него можно сохранить документ, таблицы, презентацию, текст, чертежи, вычисления, графики и всё остальное, что можно показать на экране любого устройства. Именно его лучше всего использовать для печати.
Например, если Вам нужно распечатать чертёж из автокада, Вы сохраните чертёж на флешку, но будет ли автокад в пункте печати? А если будет, то нужная версия с нужными библиотеками? Именно для этого и нужен формат PDF - в нём точно будет показано верно вне зависимости от того, в какой программе создали PDF-файл и есть ли нужная программа для его просмотра.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
