План ответов на билеты (1133265)
Текст из файла
1Минимизациядизъюнктивныхнормальныхформ и связанные с ней задачи.1.1Единичный куб и его ширина. Функции алгебры логики(ФАЛ), их представление с помощью дизъюнктивных(конъюнктивных) нормальных форм ([1:гл.1,§2]).Единичный n-мерный куб (гиперкуб)Отношение лексикографического порядкаОтношение частичного порядкаЧастично упорядоченное множествоЦепьАнтицепьНеуплотняемая цепьДлина ЧУМШирина ЧУМРанжированное ЧУМ–Множество БПАлфавитФАЛСистема ФАЛФормулаХарактеристическое множествоЭлементарная конъюнкция ранга rЭлементарная дизъюнкция ранга rДНФКНФ1.1.1ДополнительноЯрусУтверждение о ярусах в ранжированном ЧУМГрань (ранг, размерность)Количество граней ранга rОбщее количество граней–Суперпозиция ФАЛБазис Б0совершенная ДНФсовершенная КНФразложение Шеннонамультиплексорная ФАЛ порядка n1.2Сокращеннаядизъюнктивнаянормальная(ДНФ) и способы ее построения ([1:гл.1,§3]).Импликанта/Допустимая грань1формаПростая импликанта/Максимальная граньСокращенная ДНФНеприводимая ДНФУтверждение о конъюнкции двух сокращенных ДНФСледствие: получение сокращенной ДНФ из КНФТождество обобщенного склеиванияРасширениеСтрогое расширениеНерасширяемая ДНФУтверждение о неприводимой и нерасширяемой ДНФПолучение сокращенной ДНФ из произвольной1.2.1ДополнительноТождества приведения подобных1.3Тупиковые и минимальные ДНФ, ядро и ДНФ Квайна.Критерий вхождения простых импликант в тупиковыеДНФ, его локальность ([1:гл.1,§4]).Ранг ДНФДлина ДНФТупиковая ДНФМинимальная ДНФКратчайшая ДНФУтверждение о существовании кратчайшей ДНФЯдровая точка/импликанта/граньМаксимальность ядровой грани, простота ядровой импликантыУтверждение о составе ДНФ пересечение тупиковыхДНФ КвайнаПучекРегулярная точкаРегулярная граньУтверждение о ЭК, из которых состоит ДНФ сумма тупиковых (теорема Журавлева)Окрестность порядка r грани N ФАЛ fУтверждение о локальности вопроса вхождения простой импликанты в ДНФсумма/пересечение тупиковых1.4Особенности ДНФ для ФАЛ из некоторых классов (линейных, монотонных и др.).
Теорема Ю.И. Журавлевао ДНФ сумма минимальных ([1:гл.1,§5]).Линейная функцияСоседние наборыУтверждение о ДНФ функции без соседних наборовМонотонность по переменнойУтверждение о составе простых импликант монотонной функции2Нижняя единица монотонной функцииУтверждение об особенностях сокращенной ДНФ монотонной функцииЦепная ФАЛЦиклическая ФАЛТеорема Журавлева о ДНФ сумма минимальных.1.5Функция покрытия, таблица Квайна и построение всехтупиковых ДНФ. Градиентный алгоритм и оценка длины градиентного покрытия ([1:гл.1,§6]).Таблица КвайнаПокрытие строки столбцаНеприводимое покрытиеТупиковое покрытиеФункция покрытияСвойства функции покрытияКНФ функции покрытияСокращенная ДНФ функции покрытия и ее свойстваГрадиентный алгоритмОценка длины градиентного покрытия1.6Задача минимизации ДНФ.
Поведение функций Шеннона и оценки типичных значений для ранга и длиныДНФ ([1:гл.1,§7]).Функция сложности ДНФРанг ДНФДлина ДНФЗадача минимизации ДНФМинимальная ДНФКратчайшая ДНФФункция ШеннонаОценки для функции Шеннона относительно длины и ранга ДНФУтверждение о ранге и длине для почти всех ФАЛ1.7Алгоритмические трудности минимизации ДНФ и оценки максимальных значений некоторых связанных с нейпараметров ([1:гл.1,§7]).Проблема задачи построения ДНФ в классе локальных алгоритмовВычисление КНФНижняя оценка функции Шеннона для числа тупиковых ДНФ и числа минимальных ДНФСимметричная ФАЛПоясковая ФАЛНижняя оценка функции Шеннона для длины сокращенной ДНФУтверждение о ярусах в ранжированном ЧУМВерхняя оценка числа тупиковых ДНФ и длины сокращенной ДНФ32Основные классы дискретных управляющих систем.
Оценка числа схем, их структурные представления и эквивалентные преобразования.2.1Сети и оценка их числа, свойства матриц достижимости сетей. Схемы, их изоморфизм и эквивалентность ([1:гл.2, §§1,6]).Сеть(p,q) Контактная схемаОценка числа попарно неизоморфных (1,1)-КССхема из функциональных элементов (СФЭ) над базисом БМатрица достижимостиРефлексивность матрицыТранзитивность матрицыСвойства отношения достижимости (2.5 штуки)Изоморфизм помеченных графовСхемаИзоморфизм схемЭквивалентность схем2.2Задание формул деревьями, схемы из функциональныхэлементов (СФЭ). Оценка числа формул и СФЭ в базисеБ0 (гл.2,§§2,3]).Формулы над БПодформулаЗадание формулой упорядоченного ориентированного помеченного дереваСФЭ над базисом БВисячая вершинаПриведенная СФЭСоотношение между рангом, сложностью и глубиной формулыСоотношение между рангом, сложностью и глубиной приведенной СФЭ с одним выходомОценка числа формул в Б0 (по глубине/по сложности)Оценка числа СФЭ в Б02.3Задача эквивалентных преобразований на примере формул ([1:гл.3,§1]).
Оптимизация подобных формул по глубине ([1:гл.2§2]).Эквивалентное преобразование (ЭП)Принцип эквивалентной заменыОбратимость ЭПОднократная/многократная выводимостьПолная система тождествФормула с поднятыми отрицаниями4Тождества де МорганаАльтернирование формулы Alt(F)Оценка максимального значения глубины для формулы, эквивалентной формуле с поднятыми отрицаниямиСледствия для ЭК, ЭД, КНФ, ДНФ2.4Полнота системы основных тождеств для эквивалентных преобразований формул базиса Б0 ([1:гл.3,§2]).Полная система тождествТождества• ассоциативности• коммутативности• отождествления БП• дистрибутивности• де Моргана (2х)• подстановки констант (4х)• поглощенияВыводимость совершенной ДНФ из любой формулыВыводимость τ̃осн из τоснПолнота системы τосн2.5Эквивалентные преобразования СФЭ, моделированиеэквивалентных преобразований формул в классе СФЭ.Моделирование эквивалентных преобразований в различных базисах, теорема перехода.
([1:гл.3, §§1,3]).Эквивалентность СФЭПодсхемаПринцип эквивалентной замены для схемПеренос ЭП формул на СФЭТри дополнительных тождестваТеорема о КПСТ для СФЭСтруктурное моделированиеТеорема перехода2.6Контактные схемы (КС) и π -схемы, оценка их числа. Особенности функционирования многополюсных КС([1:гл.2,§§5,6]).Контакт (замыкающий/размыкающий)(p,q)-Контактная схема5Сложность КСπ -схемаСуществование формулы по π -схемеОценка числа КСОценка числа π -схемМатрица проводимости для многополюсных КСТеорема о существовании схемы для матрицы2.6.1ДополнительноФункция проводимости между двумя узламиИзоморфность/эквивалентностьКаноническая КСПриведенная КС2.7Эквивалентные преобразования КС. Основные тождества, вывод вспомогательных и обобщенных тождеств([1:гл.3,§4]).Подстановка для КС6 основных тождеств для КС5 вспомогательных тождеств для КС10 обобщенных тождеств порядка nСистема всех основных тождеств τ∞2.8Полнота системы основных тождеств.
Отсутствие конечной полной системы тождеств в классе всех КС([1:гл.3,§5]).Каноническая цепь порядка nКаноническая КС (тогда и только тогда - 3 пункта)Теорема о выводимости канонической КСТеорема о полноте системы основных тождествТеорема о (не)существовании КПСТ для КС33.1Синтез и сложность управляющих систем.Задача синтеза. Простейшие методы синтеза схем иоценки сложности функций ([1:гл.4,§§1,2]).Задача синтезаФункция ШеннонаЭффект ШеннонаВзаимосвязь между сложностями в классе схем и его подклассеОценка сложности для системы ФАЛСинтез на основе совершенной ДНФВерхняя оценка сложности и глубины формулы, сложности схемы.6Следствие: Верхняя оценка функции Шеннона для сложностей СФЭ, формулы, КС, π -схемы, глубины формулыВерхняя оценка сложности формулы и схемы (через характеристическое множество)Следствие: Верхняя оценка функции Шеннона для сложностей СФЭ, формулы, КС, π -схемы.3.2Метод каскадов для КС и СФЭ, примеры его применения ([1:гл.4,§3]).Висячая вершинаСторого приведенная СФЭМетод каскадов.3.3Регулярные разбиения единичного куба и моделирование ФАЛ переменными.
Оценки сложности некоторыхдешифраторов и мультиплексоров ([1:гл.4,§§6,7]).Характеристическая ФАЛm-регулярное разбиениеДва свойства регулярных разбиенийПараллельнй переносТеорема о существовании m-регулярного разбиения для системы ФАЛВерхняя оценка сложности системы конъюнктивных дешифраторовСледствие: верхняя оценка сложности π -схемы и СФЭ для мультиплексорнойФАЛОценка сложности и глубины формулы для мультиплексора3.4Операция суперпозиции схем и её корректность. Разделительные КС и лемма Шеннона.
Метод Шеннона дляКС и СФЭ ([1: гл.2, §§1,6; гл.4,§3]).Операция суперпозиции4 частных случая суперпозицииПравильная суперпозицияКорректная суперпозицияРазделительная КСЛемма ШеннонаРазложение ШеннонаУниверсальный многополюсник, мультиплексор и моделирование разложенияШеннонаВерхняя оценка функции Шеннона для сложности КС и СФЭ3.4.1ДополнителноФАЛ проводимостиМатрица проводимости73.5Нижние мощностные оценки функций Шеннона. Задача синтеза схем для ФАЛ из специальных классов([1:гл.4,§4]).Нижняя оценка сложности формул, СФЭ, КС, π -схем, глубины формулЗадача синтеза схем ФАЛ из спец.
классовНижняя оценка сложности СФЭ для ФАЛ из спец. классовНижняя оценка сложности КС для ФАЛ из спец. классов3.6Дизъюнктивно-универсальные множества ФАЛ. Асимптотически наилучший метод О.Б. Лупанова для синтезаСФЭ в базисе Б0 ([1:гл.4,§5]).ДУМРазбиениеСтандартное ДУММетод ЛупановаОценка сложности СФЭ при синтезе методом Лупанова3.7Асимптотически наилучший метод синтеза формул в базисе Б0 , поведение функции Шеннона для глубины ФАЛ([1:гл.4,§6]).Верхняя оценка сложности и глубины формулы3.8Асимптотически([1:гл.4,§7]).наилучшийметодсинтезаКСВерхняя оценка сложности КС3.9Инвариантные классы С.В. Яблонского и их свойства.Синтез схем для ФАЛ из инвариантных и некоторыхдругих классов ФАЛ ([2: раздел 2]).Инвариантный классХарактеристика инвариантного классаАссимптотика функции Шеннона для СФЭ инвариантных классов (нулевой/ненулевой)3.10Методы получения оценок сложности индивидуальныхФАЛ, минимальность некоторых схем ([1: гл.4, §2], [2:раздел 3], [6: §§5-7], [10]).Нижняя оценка сложности существенной ФАЛ для СФЭ и КСНижняя оценка сложности для системы ФАЛ для СФЭ и КСВерхняя и нижняя оценки сложности СФЭ и КС для конъюнктивного дешифратора8Верхняя и нижняя оценки сложности СФЭ и КС для дизъюнктивного дешифратораВерхняя и нижняя оценки сложности для мультиплексораКаскадная КСПолная КСНижняя оценка сложности (1, m)-КС3.11Реализация автоматных функций схемами из функциональных элементов и элементов задержки, схемыс «мгновенными» обратными связями ([6: §8], [2:гл.3,§§2-3]).АвтоматДискретная шакала времениЭлемент единичной задержки4Надежность и контроль управляющих систем.4.1Модели ненадежных схем, надежность СФЭ и теоремаНеймана.
Характеристики
Тип файла PDF
PDF-формат наиболее широко используется для просмотра любого типа файлов на любом устройстве. В него можно сохранить документ, таблицы, презентацию, текст, чертежи, вычисления, графики и всё остальное, что можно показать на экране любого устройства. Именно его лучше всего использовать для печати.
Например, если Вам нужно распечатать чертёж из автокада, Вы сохраните чертёж на флешку, но будет ли автокад в пункте печати? А если будет, то нужная версия с нужными библиотеками? Именно для этого и нужен формат PDF - в нём точно будет показано верно вне зависимости от того, в какой программе создали PDF-файл и есть ли нужная программа для его просмотра.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
