База ответов ИНТУИТ

Моделирование, тестирование и диагностика цифровых устройств

<<- Назад к вопросам

Жадный алгоритм поиска масок, описанный в лекции 31,базируется на применении конструкции дерева решений. Проиллюстрируйте конструкцию классического дерева решений для решения следующей задачи: имеется 8 одинаковых монет, среди которых одна фальшивая (она легче, чем стандартная). Монеты пронумерованы числами 1,2,…,8. Требуется найти фальшивую монету, используя равновесные весы с двумя чашками (пусть левая чашка имеет №1, правая - №2).

(Отметьте один правильный вариант ответа.)

Варианты ответа
на чашку №1 кладутся монеты 1-4, на чашку №2 - монеты 5-8 и производится первое взвешивание. Если чашка №1 легче, то на чашку №1 кладутся монеты 1,2, а на чашку №2 -монеты 3,4 и производится второе взвешивание. Если чашка №1 легче, то на чашку №1 кладется монета 1, на чашку №2 - монета 2 и производится третье взвешивание. Если чашка №1 легче, то монета 1-фальшивая, в противном случае монета 2-фальшивая. Аналогичные действия производятся с монетам 5-8 после первого взвешивания, если чашка №2 оказалась легче (Верный ответ)
на чашки весов последовательно кладутся монеты 1 и 2, затем 3 и 4 и т.д. Алгоритм определения фальшивой монеты при таком взвешивании очевиден
Похожие вопросы
Для некоторого ЦУ задается СПР в виде таблицы, где S=\{s_0,s_1,\ldots,s_r\} - множество технических состояний ЦУ, T_1, T_2, T_3, T_4- диагностический тест для этого ЦУ. Используя жадный алгоритм поиска индивидуальных масок, изложенный в лекции 32, найти для заданного СПР множество индивидуальных масок минимального суммарного объема. Решить задачу для СПР, заданного табл.
T_1T_2T_3T_4
s_001100100
s_100010010
s_200001011
s_301001010
s_411011110
s_510001010
s_610011101
s_710001110
s_801000110
Для некоторого ЦУ задается СПР в виде таблицы, где S=\{s_0,s_1,\ldots,s_r\} - множество технических состояний ЦУ, T_1, T_2, T_3, T_4- диагностический тест для этого ЦУ. Используя жадный алгоритм поиска индивидуальных масок, изложенный в лекции 32, найти для заданного СПР множество индивидуальных масок минимального суммарного объема. Решить задачу для СПР, заданного табл.
T_1T_2T_3T_4
s_010011110
s_110101110
s_200111110
s_300000011
s_401001010
s_501000110
s_601000100
s_710001010
s_811111110
Для некоторого ЦУ задается СПР в виде таблицы, где S=\{s_0,s_1,\ldots,s_r\}- множество технических состояний ЦУ, T_1, T_2, T_3, T_4- диагностический тест для этого ЦУ. Используя жадный алгоритм поиска масок, изложенный в лекции 31, найти для заданного СПР единую маску минимального объема.Решить задачу для СПР, заданного табл.
T_1T_2T_3T_4
s_010011110
s_110101110
s_200111110
s_300000011
s_401001010
s_501000110
s_601000100
s_710001010
s_811111110
Для некоторого ЦУ задается СПР в виде таблицы, где S=\{s_0,s_1,\ldots,s_r\}- множество технических состояний ЦУ, T_1, T_2, T_3, T_4- диагностический тест для этого ЦУ. Используя жадный алгоритм поиска масок, изложенный в лекции 31, найти для заданного СПР единую маску минимального объема.Решить задачу для СПР, заданного табл
T_1T_2T_3T_4
s_001100100
s_100010010
s_200001011
s_301001010
s_411011110
s_510001010
s_610011101
s_710001110
s_801000110
Чем отличается прямое различающее дерево от дерева преемников состояний?
Представленная ниже таблица - словарь полной реакции (СПР) некоторого ЦУ на тест T_1,T_2,T_3,T_4 Пусть S- разбиение множества состояний ЦУ (s_0- исправное ЦУ, s_i- ЦУ с i-ой неисправностью), а s_j- элементы этого разбиения. Каждому состоянию S_jсоответствует маска h_j, и пусть H- множество всех масок h_j Предполагается, что каждое S_jсодержит одно состояние s_jТребуется построить СПР_Ндля различных типов масок (общих и индивидуальных) при заданном множестве H
T_1T_2T_3T_4
s_011001110
s_110101110
s_200001110
s_300000010
s_401000010
s_501000110
s_601000100
s_710001010
s_811111110
Построить СПР_Н, где множество Hсодержит следующие маски:h_0=h_1=\{1:1,2:1,3:1,4:2\},h_2=\{2:2,4:1\},h_3=h_4=h_5=\{3:2,4:1\},h_6=\{1:2,3:2,4:2\},h_7=\{3:2\},h_8=\{1:2,2:1,4:1\}
Представленная ниже таблица - словарь полной реакции (СПР) некоторого ЦУ на тест T_1,T_2,T_3,T_4 Пусть S- разбиение множества состояний ЦУ (s_0- исправное ЦУ, s_i- ЦУ с i-ой неисправностью), а s_j- элементы этого разбиения. Каждому состоянию S_jсоответствует маска h_j, и пусть H- множество всех масок h_j Предполагается, что каждое S_jсодержит одно состояние s_jТребуется построить СПР_Ндля различных типов масок (общих и индивидуальных) при заданном множестве H
T_1T_2T_3T_4
s_011001110
s_110101110
s_200001110
s_300000010
s_401000010
s_501000110
s_601000100
s_710001010
s_811111110
Построить СПР_Н, где множество Hсодержит единую (общую) маску для всех s_jи эта маска h=\{1:1,2:1,3:1,4:1\}
Что необходимо определить для решения задачи с помощью генетического алгоритма?
От чего зависит в первую очередь сложность решения задачи выполнимости КНФ?
Сколько этапов имеет алгоритм обнаружения состязаний Эйхельбергера?