4 (1132840)

Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла

Московский государственный университетимени М. В. ЛомоносоваФакультет вычислительной математики и кибернетикиС. А. ЛожкинЛекции по основамкибернетикиВариант 2017 г. (гр. 320–328), глава 4Москва 2017ОглавлениеВведение34 Надежность и контроль управляющих систем 6§1 Задача контроля схем и тесты для таблиц.Построение всех тупиковых тестов, оценкидлины диагностического теста . . . . .

. . . . . 6§2 Самокорректирующиеся контактные схемы иметоды их постороения. Асимптотическинаилучший метод синтеза контактных схем,корректирующих один обрыв (одно замыкание) 13Литература182ВведениеКурс «Основы кибернетики» (ранее «Элементы кибернетики»), создателем и основным лектором которого былчл.-корр. РАН С. В. Яблонский, читается на факультетеВМК МГУ с первых лет его существования. В настоящеевремя он читается в 6–8 семестрах и является обязательнымдля всех бакалавров (интегрированных магистров) направления 01400 — «Прикладная математика и информатика».При этом объем и, в некоторой степени, программа курса«Основы кибернетики» варьируются в зависимости от профиля.Курс «Основы кибернетики» посвящен изложению теории дискретных управляющих систем, которая представляет собой часть дискретной математики и математическойкибернетики.

В ней разрабатываются и изучаются дискретные математические модели, описывающие функционирование и структуру сложных систем преобразования информации (интегральных схем, программ и т. п.). В основе этихмоделей лежат различные способы задания функционирования управляющих систем с помощью дискретных функцийи их структурная реализация в тех или иных классах графов (классах схем). При исследовании управляющих системставятся и решаются две основные задачи: задача анализаи задача синтеза.Задача анализа состоит в нахождении функционирования данной схемы, а задача синтеза — в построении схемы,имеющей (реализующей) заданное функционирование. Каждая из этих задач может рассматриваться либо как индивидуальная задача, и тогда ее решением является конкрет34Введениеное функционирование (схема), либо как массовая задача,и тогда ее решением должен быть алгоритм нахожденияфункционирования (схемы).

Задача синтеза имеет, как правило, множество решений, из которых выбирают решение,оптимальное по какому-либо критерию. Чаще всего в качестве такого критерия выступает сложность схемы, понимаемая как сумма сложностей составляющих ее элементовили задержка схемы, понимаемая как максимальная сумма задержек для последовательно соединенных элементовсхемы.С содержательной точки зрения различные критерии оптимальности отражают различные параметры моделируемых электронных схем или программ. Так, например, сложность может характеризовать стоимость, размеры или потребляемую мощность СБИС, а также время выполненияпрограммы на одном процессоре.

При этом задержка схемыхарактеризует время срабатывания СБИС или время выполнения программы на параллельных процессорах и т. п.Если задача синтеза решена в одной модели, можно пытаться перенести это решение в другие модели с помощьюструктурного моделирования. Кроме того, полученное решение можно «улучшить» с помощью эквивалентных преобразований. С другой стороны, если задача синтеза решенадля одних функций, можно пытаться «разбить» (декомпозировать) новую функцию на уже рассмотренные и построитьиз синтезированных для них схем схему для новой функциис помощью операции суперпозиции.Указанные выше задачи рассматриваются в лекциях длявсех основных классов схем (дизъюнктивные нормальныеформы, формулы и схемы из функциональных элементов,контактные схемы), а также для некоторых модификацийэтих классов.Первая глава посвящена различным вопросам представления функций алгебры логики с помощью таблиц и дизъюн-Введение5ктивных нормальных форм (минимизация дизъюнктивныхнормальных форм).Вторая глава содержит описание структуры и функционирования схем из основных классов управляющих систем,а также из некоторых классов, представляющих собой ихобобщения или модификации.

В ней устанавливаются верхние оценки числа схем различных типов, рассматриваютсянекоторые вопросы их структурного моделирования.Во второй главе изучаются также эквивалентные преобразования схем на основе тождеств во всех основных классах управляющих систем. Для каждого из них приводитсясистема «основных» тождеств, доказывается полнота этойсистемы и изучаются вопросы ее избыточности.В третьей главе подробно рассматривается задача синтеза управляющих систем, а также изучаются особенностиприменения операции суперпозиции в различных классахсхем.

В ней приводится целый спектр методов синтеза схем(от простейших до асимптотически оптимальных), устанавливаются нижние мощностные оценки функций Шеннона иоценки сложности ряда конкретных функций, доказываетсяминимальность некоторых схем.В четвертой главе представлены некоторые вопросы надежности и контроля схем (построение теств для таблиц,синтез самокорректирующихся контактных схем).Глава 4Надежность и контроль управляющихсистем§1Задача контроля схем и тесты для таблиц.Построение всех тупиковых тестов, оценкидлины диагностического тестаДля управляющей системы (схемы) без памяти, функционирование которой описывается дискретной функцией или,в общем случае, вектор-функцией, может быть сформулирована следующая модель, в рамках которой обычно рассматриваются вопросы ее надежности и контроля (см.

[29,27, 30]). Предполагается, что имеется некоторый «внешний»источник неисправностей (источник помех) И, под действием которого рассматриваемая схема Σ может переходить водно из своих «неисправных состояний» (схем), определяемых этим источником. Пусть схеме Σ = Σ1 , реализующейфункцию f = f1 от входных переменных x = (x1 , . . . , xn ), иисточнику неисправностей И соответствуют «неисправные»состояния (схемы) Σ2 , . . . , Σs , где схема Σi , i = 2, . . . , s, реализует функцию fi от переменных x.

При этом все состояния (как исправное Σ = Σ1 , так и неисправные Σ2 , . . . , Σs )разбиваются на классы (функционально) неотличимых состояний, то есть классы эквивалентности по отношению равенства реализуемых функций, и рассматриваются далее сточностью до неотличимости. В дальнейшем, говоря о нена6Введение7дежной схеме Σ, будем иметь в виду пару (Σ, И) и (или)соответствующее ей множество схем вместе с теми функциями, которые они реализуют. Для простоты рассмотрения будем считать, что все переменные и функции являютсябулевскими, хотя многие излагаемые далее результаты безсущественных изменений переносятся на случай многозначных функций, случай вектор-функций и другие более общиеслучаи.Пусть (Σ, И) — указанная выше модель ненадежной схемыΣ с возможными состояниями Σ = Σ1 , Σ2 , .

. . , Σs , в которыхреализуются ФАЛ f = f1 , f2 , . . . , fs соответственно от БПX (n), определенные на множестве наборов A== {α1 , . . . , αp } ⊆ B n . Рассмотрим матрицу M, M ∈ B p,s ,гдеM hi, ji = fj (αi ) ,считая, что i-й строке (j-му столбцу) этой таблицы соответствует набор αi (соответственно функция fj и состояние Σj ). Матрица, состоящая из различных столбцов (строк)называется отделимой по столбцам (соответственно строкам) матрицей. Заметим, что каждому классу неотличимыхсостояний модели (Σ, И) соответствует группа одинаковыхстолбцов матрицы M и рассмотрим отделимую по столбцамc, состоящую из всех различных столбцов матриматрицу Mцы M . При этом будем считать, что каждый столбец матриc связан с соответствующим классом неотличимости соцы Mc таблицей констояний модели (Σ, И), и будем называть Mтроля данной модели.

Для простоты будем, как правило,предполагать, что все состояния модели (Σ, И) попарно отc. Это предположение, очевидно, неличимы, то есть, M = Mограничивает общности рассуждений.Пусть, далее, помимо таблицы контроля M для модели (Σ, И) задана цель контроля, то есть указано множествоN, состоящее из тех неупорядоченных пар различных чиселотрезка [1, s], для которых пары состояний (столбцов матри-8Введениецы M ) с соответствующими номерами необходимо отличатьдруг от друга, сравнивая значения, расположенные в техили иных строках данной пары столбцов.

В частности, еслиN состоит из всех пар указанного вида, то целью контроляявляется диагностика схемы, а если N = {(1, 2) , . . . , (1, t)},то — проверка исправности схемы. Множество строк матрицы M с номерами из T, T ⊆ [1, p], называется тестомдля матрицы M относительно множества N, или, иначе,тестом для (M, N), если для любой пары (i, j) из N существует t, t ∈ T , такое, что M ht, ii =6 M ht, ji. Мощностьтеста называется также его длиной.Заметим, что множество, состоящее из всех строк таблицы контроля, всегда образует тест. Тест, который перестаетбыть тестом при удалении любой своей строки, называется тупиковым, а тест, который имеет минимальнуюмощность, — минимальным.

В том случае, когда целью контроля является диагностика схемы (проверка исправностисхемы), тест называется диагностическим (соответственнопроверяющим).Будем говорить, что множество наборов τ, τ ⊆ A, образует тест для модели (Σ, И) относительно цели контроля N, или, иначе, тест для (Σ, И, N), если соответствующие наборам из τ строки матрицы M образуют тест для(M, N). Все введенные выше понятия, которые касаются тестов для таблиц, без изменений переносятся на случай тестов для ненадежных схем.Для описания тестов можно ввести функцию, аналогичную функции покрытия из §6 главы 1. Пусть M, M ∈ B p,s ,— отделимая по столбцам матрица, а N — связанная с нейцель контроля. Сопоставим i-й строке, i ∈ [1, p], матрицыM БП yi , а каждому набору β, β ∈ B p , значений этих переменных y = (y1 , . . .

Характеристики

Тип файла PDF

PDF-формат наиболее широко используется для просмотра любого типа файлов на любом устройстве. В него можно сохранить документ, таблицы, презентацию, текст, чертежи, вычисления, графики и всё остальное, что можно показать на экране любого устройства. Именно его лучше всего использовать для печати.

Например, если Вам нужно распечатать чертёж из автокада, Вы сохраните чертёж на флешку, но будет ли автокад в пункте печати? А если будет, то нужная версия с нужными библиотеками? Именно для этого и нужен формат PDF - в нём точно будет показано верно вне зависимости от того, в какой программе создали PDF-файл и есть ли нужная программа для его просмотра.

Список файлов лекций