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

а) Покажите, что если неисправно более n / 2 микросхем, то с помощью какой бы то ни было стратегии, основанной на попарном тестировании, профессор не сможет точно определить, какие микросхемы исправны. (Предполагается, что неисправные микросхемы не смогут тайно сговориться, чтобы обмануть профессора.)

б) Рассмотрим задачу о поиске одной исправной микросхемы среди п микросхем, если предполагается, что исправно более половины всех микросхем. Покажите, что [n/2] попарных тестирований достаточно для сведения этой задачи к подзадаче, размер которой приблизительно в два раза меньше.

в) Покажите, что можно найти все исправные микросхемы с помощью тета от (n) попарных тестирований, если предполагается, что более половины микросхем исправны. Сформулируйте и решите рекуррентное соотношение, описывающее количество тестирований.

Буду ОЧЕНЬ благодарен, если кто-то сможет помочь

задан 11 Авг 11:09

изменен 11 Авг 11:10

10|600 символов нужно символов осталось
1

Пункт а) вроде ясен. Предъявим стратегию "игры за противника", то есть за неисправные микросхемы. Пусть, если в тестер загружены две неисправные микросхемы, они всегда друг про друга говорят, что обе исправны, а когда в тестер загружены одна исправная и одна неисправная, то неисправная тоже будет отвечать, что вторая микросхема неисправна.

Тогда с точки зрения испытателя, множества исправных и неисправных микросхем друг от друга неотличимы - мы можем разбить все микросхемы на два класса смежности (построить два полных подграфа), но ничто не может помочь нам с выбором, в каком из этих классов микросхемы исправны, а в каком - нет.

б) Тоже вроде всё разжевали прямо в условии. Разбиваем все микросхемы на пары, делаем по одному тестированию для каждой пары. Так как исправных микросхем больше половины, то хотя бы в одной паре будут две исправных. Ясно, что в такой паре тестер получит от обеих микросхем ответ "другая микросхема исправна" (И,И). [Возможно, что точно такие же ответы будут получены и в тех парах, где обе микросхемы неисправны.] Во всех парах, где одна микросхема исправна а другая нет, мы точно получим ответы (И,Н) или (Н,Н). [И такие же ответы будут получены и в тех парах, где обе микросхемы неисправны]

Как теперь уменьшить размер задачи вдвое? Выбросим все микросхемы, оказавшиеся в парах (Н,Н) (конечно, таких может и не быть). В парах (И,Н) выбросим только неисправные микросхемы. В парах (И,И) выбросим одну из двух микросхем наугад. Утверждение: в оставшемся множестве микросхем исправных по-прежнему более половины.

ссылка

отвечен 11 Авг 11:46

изменен 11 Авг 21:13

1

@knop: Во всех парах, где одна микросхема исправна а другая нет, мы точно получим ответы (И,Н). -- почему в такой паре не может быть НН?

(11 Авг 13:08) falcao

@falcao, спасибо, поправил. Да, может быть и НН. На оценку не влияет

(11 Авг 21:13) knop
10|600 символов нужно символов осталось
Ваш ответ

Если вы не нашли ответ, задайте вопрос.

Здравствуйте

Математика - это совместно редактируемый форум вопросов и ответов для начинающих и опытных математиков, с особенным акцентом на компьютерные науки.

Присоединяйтесь!

отмечен:

×502
×276
×72
×32
×5

задан
11 Авг 11:09

показан
132 раза

обновлен
11 Авг 21:13

Отслеживать вопрос

по почте:

Зарегистрировавшись, вы сможете подписаться на любые обновления

по RSS:

Ответы

Ответы и Комментарии

Дизайн сайта/логотип © «Сеть Знаний». Контент распространяется под лицензией cc by-sa 3.0 с обязательным указанием авторства.
Рейтинг@Mail.ru