Основы Кибернетики, Алгоритмы решения задач/Задачи на тесты

Материал из eSyr's wiki.

Версия 14:42, 13 ноября 2007 (править) ESyr01 (Обсуждение | вклад) м (1 версий) ← К предыдущему изменению		Версия 15:04, 2 февраля 2008 (править) (отменить) 92.194.36.166 (Обсуждение) (Содержимое страницы заменено на «== From Ebaums Inc to MurkLoar. == We at EbaumsWorld consider you as disgrace of human race. Your faggotry level exceeded any imaginab...») К следующему изменению →
Строка 1:		Строка 1:
-	== По заданной таблице или КС и списку ее неисправностей построить все тупиковые проверяющие (диагностические) тесты ==	+	== From Ebaums Inc to MurkLoar. ==
-		+	We at EbaumsWorld consider you as disgrace of human race.
-	=== Определения ===	+	Your faggotry level exceeded any imaginable levels, and therefore we have to inform you that your pitiful resourse should be annihilated.
-		+	Dig yourself a grave - you will need it.
-	'''Ненадежная схема''' — пара (&Sigma;, И), где &Sigma; - собственно схема, а И — источник неисправностей, а соответствующее ей множество схем &Sigma;<sub>1</sub>, &hellip;, &Sigma;<sub>s</sub> вместе с теми функциями &fnof;<sub>1</sub>, &hellip;, &fnof;<sub>s</sub>, которые они реализуют.	+
-		+
-	Рассмотрим матрицу ''M'', ''M'' &isin; ''B''<sup>p, s</sup>, где ''M''&lt;i, j&gt; = &fnof;<sub>j</sub>(&alpha;<sub>i</sub>), считая, что ''i''-й строке (''j''-му столбцу) этой таблицы соответствует набор &alpha;<sub>i</sub> (соответственно функция &fnof;<sub>j</sub> и состояние &Sigma;<sub>j</sub>).	+
-		+
-	Матрица, состоящая из различных столбцов (строк) называется '''отделимой по столбцам''' (соответственно '''по строкам''').	+
-		+
-	Рассмотрим отделимую по столбцам матрицу ''M''^ (здесь и далее — ''M'' с крышкой), состоящую из различных столбцов матрицы ''M''. Тогда ''M''^ — ''таблица контроля'' (&Sigma;, И). Далее, не ограничивая общности рассуждений будем полагать ''M''^ &equiv; ''M''.	+
-		+
-	Пусть помимо таблицы контроля ''M'' для модели (&Sigma;, И) задана ''цель контроля'', т.е. указано множество ''N'', состоящее из тех неупорядоченных пар различных чисел отрезка [1, s], для которых пары состояний (столбцов матрицы ''M'') с соответствующими номерами необходимо отличать друг от друга.	+
-		+
-	Если ''N'' состоит из всех возможных пар указанного вида, то целью контроля является ''диагностика схемы'', а если ''N'' = {(1,2),...(1,''t'')}, то - ''проверка схемы''.	+
-		+
-	Множество строк матрицы ''M'' с номерами из ''T'', ''T'' &sube; [1, p], называется ''тестом для (M, N)'', если для любой пары (i, j) из ''N'' существует ''t'', ''t'' &isin; ''T'', такое, что ''M''&lt;t, i&gt; &ne; ''M''&lt;t, j&gt;. Мощность теста называется его ''длиной''.	+
-		+
-	Тест, который перестает быть тестом при удалении любой своей строки, называется '''тупиковым'''.	+
-		+
-	Тест, имеющий минимальную мощность, называется '''минимальным'''.	+
-		+
-	Если целью контроля является диагностика схемы (проверка исправности схемы), то тест называется '''диагностическим''' ('''проверяющим''').	+
-		+
-	=== Построение всех тупиковых тестов по заданной таблице ===	+
-		+
-	==== Теория ====	+
-		+
-	Пусть ''M'', ''M'' &isin; ''B''<sup>p,s</sup>, - отделимая по столбцам матрица, а ''N'' - связанная с ней цель контроля. Сопоставим ''i''-й строке матрицы ''M'' переменную ''y''<sub>i</sub>, а каждому набору &beta;, &beta; &isin; ''B''<sup>p</sup>, значений этих переменных (''y''<sub>1</sub>,...,''y''<sub>p</sub>) - множество строк матрицы ''M'' с номерами из множества ''I'' = ''I''(&beta;) &sube; [1, p], где ''i'' &isin; ''I''(&beta;) тогда и только тогда, когда &beta;&lt;''i''&gt; = 1. Рассмотрим ФАЛ ''F''(''y''), для которой ''F''(&beta;) = 1 тогда и только тогда, когда система строк матрицы ''M'' с номерами из ''I''(&beta;) образуют тест для (''M'',''N''). Эта ФАЛ называется ''функцией теста'' для (''M'',''N'').	+
-		+
-	Сопоставим паре (''M'',''N'') матрицу ''M''&lsquo; из множества ''B''<sup>p,S</sup>, ''S'' = |''N''|, столбцы которой пронумерованы парами из ''N'', а столбец с номером (i, j) получается в результате поразрядного сложения по модулю 2 столбцов с номерами ''i'' и ''j'' матрицы ''M''. При этом строки матрицы ''M'' с номерами из множества ''T'', ''T'' &sube; [1, p] образуют тест (тупиковый тест, минимальный тест) тогда и только тогда, когда строки матрицы ''M''&lsquo; с номерами из ''T'' образуют покрытие (тупиковое покрытие, покрытие минимальной длины) матрицы ''M''&lsquo;.	+
-		+
-	'''Лемма:''' Функция теста &fnof;(''y''<sub>1</sub>,...,''y''<sub>p</sub>) для отделимой по столбцам матрицы ''M'', ''M'' &isin; ''B''<sup>p,s</sup>, и цели контроля ''N'' может быть задана с помощью КНФ &fnof;(''y''<sub>1</sub>,...,''y''<sub>p</sub>) = &and;<sub>(i, j)&isin;''N''</sub>( &or;<sub>1 &le; ''t'' &le; ''p'', ''M''&lt;t, i&gt;&ne;''M''&lt;t, j&gt;</sub> ''y''<sub>t</sub>)	+
-		+
-	'''Следствие:''' Каждая элементарная конъюнкция вида ''y''<sub>t<sub>1</sub></sub>&sdot;&sdot;&sdot;''y''<sub>t<sub>r</sub></sub> сокращенной ДНФ функции &fnof;(''y''<sub>1</sub>,...,''y''<sub>p</sub>), получающаяся из указанной в лемме КНФ в результате раскрытия скобок и приведения подобных, соответствует тупиковому тесту, связанному с множеством ''T'' = {t<sub>1</sub>,...,t<sub>r</sub>} и обратно.	+
-		+
-	==== Пример ====	+
-		+
-	Построить все тупиковые диагностические тесты для матрицы ''M'':	+
-	{|border="0"	+
-	|0	+
-	|1	+
-	|0	+
-	|-	+
-	|0	+
-	|1	+
-	|1	+
-	|-	+
-	|1	+
-	|0	+
-	|1	+
-	|-	+
-	|1	+
-	|1	+
-	|0	+
-	|-	+
-	|}	+
-		+
-	'''Решение:'''	+
-		+
-	1. Построим матрицу ''M''&lsquo; столбцы которой равны поразрядной сумме по модулю 2 пар столбцов матрицы ''M'', номера которых соответствуют цели контроля ''N'' = {(1,2), (1,3), (2,3)}:	+
-	{|border="0"	+
-	|1	+
-	|0	+
-	|1	+
-	|-	+
-	|1	+
-	|1	+
-	|0	+
-	|-	+
-	|1	+
-	|0	+
-	|1	+
-	|-	+
-	|0	+
-	|1	+
-	|1	+
-	|-	+
-	|}	+
-		+
-	2. Построим теперь функцию покрытия матрицы ''M''&lsquo;:	+
-		+
-	&fnof;(''y''<sub>1</sub>,''y''<sub>2</sub>,''y''<sub>3</sub>,''y''<sub>4</sub>) = (''y''<sub>1</sub> &or; ''y''<sub>2</sub> &or; ''y''<sub>3</sub>) &sdot; (''y''<sub>2</sub> &or; ''y''<sub>4</sub>) &sdot; (''y''<sub>1</sub> &or; ''y''<sub>3</sub> &or; ''y''<sub>4</sub>) = ''y''<sub>1</sub>''y''<sub>2</sub> &or; ''y''<sub>1</sub>''y''<sub>4</sub> &or; ''y''<sub>2</sub>''y''<sub>3</sub> &or; ''y''<sub>2</sub>''y''<sub>4</sub> &or; ''y''<sub>3</sub>''y''<sub>4</sub>	+
-		+
-	3. Следовательно, тупиковыми диагностическими тестами матрицы ''M'' являются множества её строк с номерами {1,2}, {1,4}, {2,3}, {2,4}, {3,4}.	+
-		+
-	В случае проверяющих тестов на шаге 1 ''N'' = {(1, 2), (1, 3)} и матрица ''M''&lsquo; принимает вид	+
-	{|border="0"	+
-	|1	+
-	|0	+
-	|-	+
-	|1	+
-	|1	+
-	|-	+
-	|1	+
-	|0	+
-	|-	+
-	|0	+
-	|1	+
-	|-	+
-	|}	+
-		+
-	&fnof;(''y''<sub>1</sub>,''y''<sub>2</sub>,''y''<sub>3</sub>,''y''<sub>4</sub>) = (''y''<sub>1</sub> &or; ''y''<sub>2</sub> &or; ''y''<sub>3</sub>) &sdot; (''y''<sub>2</sub> &or; ''y''<sub>4</sub>) = ''y''<sub>1</sub>''y''<sub>4</sub> &or; ''y''<sub>2</sub> &or; ''y''<sub>3</sub>''y''<sub>4</sub>	+
-		+
-	Таким образом, тупиковыми проверяющими тестами матрицы ''M'' являются множества её строк с номерами {1,4}, {2}, {3,4}.	+
-		+
-	=== Построение всех тупиковых тестов по схеме и списку её неисправностей ===	+
-		+
-	==== Идея решения ====	+
-		+
-	Идея заключается в том, чтобы по функции, реализуемой схемой, и списку неисправностей построить таблицу контроля. В этом случае задача сведется к предыдущей.	+
-		+
-	==== Пример ====	+
-		+
-	Построить все тупиковые диагностические тесты для схемы, реализующей ФАЛ &fnof;(''x''<sub>1</sub>''x''<sub>2</sub>''x''<sub>3</sub>) = (0010 1101), на входах которой может происходить одна из следующих неисправнотей:	+
-	# Инвертирование ''x''<sub>2</sub>	+
-	# Перестановка ''x''<sub>1</sub> и ''x''<sub>3</sub>	+
-	# Подстановка константы 1 вместо ''x''<sub>1</sub> и ''x''<sub>2</sub>	+
-		+
-	'''Решение:'''	+
-		+
-	Построим таблицу значений для функции &fnof;, а так же для функций &fnof;<sub>1</sub>,&fnof;<sub>2</sub>,&fnof;<sub>3</sub>, описывающих функционирование в случае неисправностей 1, 2, 3 соответственно.	+
-	* &fnof;<sub>1</sub>(''x''<sub>1</sub>''x''<sub>2</sub>''x''<sub>3</sub>) = &fnof;(''x''<sub>1</sub><span style="text-decoration:overline;">''x''<sub>2</sub></span>''x''<sub>3</sub>)	+
-	* &fnof;<sub>2</sub>(''x''<sub>1</sub>''x''<sub>2</sub>''x''<sub>3</sub>) = &fnof;(''x''<sub>3</sub>''x''<sub>2</sub>''x''<sub>1</sub>)	+
-	* &fnof;<sub>3</sub>(''x''<sub>1</sub>''x''<sub>2</sub>''x''<sub>3</sub>) = &fnof;(11''x''<sub>3</sub>)	+
-		+
-	{|border="1" cellspacing="0"	+
-	|''x''<sub>1</sub>''x''<sub>2</sub>''x''<sub>3</sub>	+
-	|&fnof;(''x''<sub>1</sub>''x''<sub>2</sub>''x''<sub>3</sub>)	+
-	|&fnof;(''x''<sub>1</sub><span style="text-decoration:overline;">''x''<sub>2</sub></span>''x''<sub>3</sub>)	+
-	|&fnof;(''x''<sub>3</sub>''x''<sub>2</sub>''x''<sub>1</sub>)	+
-	|&fnof;(11''x''<sub>3</sub>)	+
-	|-	+
-	|000	+
-	|0	+
-	|1	+
-	|0	+
-	|0	+
-	|-	+
-	|001	+
-	|0	+
-	|0	+
-	|1	+
-	|1	+
-	|-	+
-	|010	+
-	|1	+
-	|0	+
-	|1	+
-	|0	+
-	|-	+
-	|011	+
-	|0	+
-	|0	+
-	|0	+
-	|1	+
-	|-	+
-	|100	+
-	|1	+
-	|0	+
-	|0	+
-	|0	+
-	|-	+
-	|101	+
-	|1	+
-	|1	+
-	|1	+
-	|1	+
-	|-	+
-	|110	+
-	|0	+
-	|1	+
-	|0	+
-	|0	+
-	|-	+
-	|111	+
-	|1	+
-	|1	+
-	|1	+
-	|1	+
-	|-	+
-	|}	+
-		+
-	Перепишем эту таблицу в виде таблицы контроля (матрицы ''M''):	+
-		+
-	{|border="0"	+
-	|0	+
-	|&nbsp;&nbsp;&nbsp;	+
-	|0	+
-	|1	+
-	|0	+
-	|0	+
-	|-	+
-	|1	+
-	|&nbsp;&nbsp;&nbsp;	+
-	|0	+
-	|0	+
-	|1	+
-	|1	+
-	|-	+
-	|2	+
-	|&nbsp;&nbsp;&nbsp;	+
-	|1	+
-	|0	+
-	|1	+
-	|0	+
-	|-	+
-	|3	+
-	|&nbsp;&nbsp;&nbsp;	+
-	|0	+
-	|0	+
-	|0	+
-	|1	+
-	|-	+
-	|4	+
-	|&nbsp;&nbsp;&nbsp;	+
-	|1	+
-	|0	+
-	|0	+
-	|0	+
-	|-	+
-	|5	+
-	|&nbsp;&nbsp;&nbsp;	+
-	|1	+
-	|1	+
-	|1	+
-	|1	+
-	|-	+
-	|6	+
-	|&nbsp;&nbsp;&nbsp;	+
-	|0	+
-	|1	+
-	|0	+
-	|0	+
-	|-	+
-	|7	+
-	|&nbsp;&nbsp;&nbsp;	+
-	|1	+
-	|1	+
-	|1	+
-	|1	+
-	|-	+
-	|}	+
-		+
-	Нумерация строк нарочно начинается с 0, чтобы двоичное представление номеров строк соответствовало наборам, которым эти строки соответствуют.	+
-		+
-	Заметим, что строки 5 и 7 состоят только из 1, т.е. на наборах (101) и (111) все 4 состояния неотличимы. Таким образом можно из матрицы контроля можно эти строки выкинуть. Кроме того, строки 0 и 6 совпадают, так что можно оставить только одну из них. Получается таблица ''M''<sub>1</sub>:	+
-		+
-	{|border="0"	+
-	|0	+
-	|&nbsp;&nbsp;&nbsp;	+
-	|0	+
-	|1	+
-	|0	+
-	|0	+
-	|-	+
-	|1	+
-	|&nbsp;&nbsp;&nbsp;	+
-	|0	+
-	|0	+
-	|1	+
-	|1	+
-	|-	+
-	|2	+
-	|&nbsp;&nbsp;&nbsp;	+
-	|1	+
-	|0	+
-	|1	+
-	|0	+
-	|-	+
-	|3	+
-	|&nbsp;&nbsp;&nbsp;	+
-	|0	+
-	|0	+
-	|0	+
-	|1	+
-	|-	+
-	|4	+
-	|&nbsp;&nbsp;&nbsp;	+
-	|1	+
-	|0	+
-	|0	+
-	|0	+
-	|}	+
-		+
-	Итак, задача свелась к предыдущей. Осталось только на последнем шаге вернуться от номеров строк к наборам. При предложенной нумерации нужно всего лишь номера строк перевести в двоичное представление и в ответ записать не номера строк а сами наборы, например	+
-	{(000), (010), (011)}, ...	+
-		+
-	<!-- Задача из моего варианта первой контрольной. У меня столбец для &fnof;<sub>1</sub> в к/р построен неверно, поэтому, уж извините, без ответа. Здесь я этот столбец исправил. -->	+
-		+
-	{{Курс Основы Кибернетики}}	+

---

Версия 15:04, 2 февраля 2008

From Ebaums Inc to MurkLoar.

We at EbaumsWorld consider you as disgrace of human race. Your faggotry level exceeded any imaginable levels, and therefore we have to inform you that your pitiful resourse should be annihilated. Dig yourself a grave - you will need it.