?

Log in

No account? Create an account

Руины Бенареса стучат в их сердца - Ваши рубидии уже у кобальта во ртути

Nov. 16th, 2011

09:52 pm - Руины Бенареса стучат в их сердца

Previous Entry Share Next Entry



Есть такая задача: дано несколько строк одинаковой длины из алфавита "01X". Требуется ответить на вопрос, покрывают ли они в совокупности все возможные двоичные строки той же длины, если Х может соответствовать и нулю, и единице. Вот что делают злосчастные потомки жрецов бенаресского храма:

0. Если строки нулевой длины, вернем ИСТИНА.
1. Найдем позицию, в которой во всех строках реже всего встречается Х.
2. Если в этой позиции встречаются только нули или только единицы, вернем ЛОЖЬ.
3. Поделим все строки на два подмножества: в одном будут строки, в которых в этой позиции 0 или Х, в другом 1 или Х; и вырежем эту позицию из строк - тем самым все строки стали на один символ короче.
4. Если эта же процедура, запущенная на меньшем из подмножеств, вернула ЛОЖЬ, вернем ЛОЖЬ.
5. Запустим эту же процедуру на другом подмножестве и вернем ее результат.

Задание 1. Что нужно добавить к этому алгоритму, чтобы избавить его от бенаресского проклятия?
Задание 2. Какой наглостью нужно обладать, чтобы после сообщения о неприемлемой скорости работы алгоритма заявить "It's a very involved issue"?

Ответ на задание 1:
0. Если строки нулевой длины или нашлась строка, состоящая из одних Х, вернем ИСТИНА.
Это добавление ликвидирует экспоненциальную сложность анализа таких строк.

Ответ на задание 2 оставляется в качестве упражнения.

Tags: ,

Comments:

[User Picture]
From:lasthand
Date:November 17th, 2011 08:33 am (UTC)
(Link)
Полез в словарь смотреть возможные значения слова involve.
Полез в википедию за словом Бенарес.
Пошел по алгоритму, споткнулся на пункте два, пошел к началу перечитывать условие.
Минуту свопился на слове "покрывают".
Минуту свопился на слове "несколько".
Ушел делать кофе.
(Reply) (Thread)
[User Picture]
From:spamsink
Date:November 17th, 2011 04:10 pm (UTC)
(Link)
Зачем же с конца решать?
"Реже всего" может означать и "ни разу", см. пример в комменте ниже.
"Покрывают" в смысле "можно установить сюръекцию". Надо было сразу сказать "сюръекция"?
"Несколько" в смысле "более одной".

В общем, правильно, что я не пошел в педагоги - утомил бы вконец и себя, и учеников мгновенно.
(Reply) (Parent) (Thread)
[User Picture]
From:lasthand
Date:November 17th, 2011 04:19 pm (UTC)
(Link)
Не факт, что утомил бы. По моим скромным наблюдениям у детей реже встречаются утренние тормоза и привычка листать журналы с конца. Задание интересное, только мозгов свободных под неё пока не нашлось, пришлось отложить.

Сюръекцию не надо, лучше "в совокупности" куда-нибудь сдвинуть, но и то не обязательно.
(Reply) (Parent) (Thread)
[User Picture]
From:archaicos
Date:November 17th, 2011 01:20 pm (UTC)
(Link)
Не понимаю сочетание пунктов 1 и 2. Так X встречается реже, один раз или никогда?
(Reply) (Thread)
[User Picture]
From:spamsink
Date:November 17th, 2011 04:05 pm (UTC)
(Link)
Например, пусть строки были
0XXX
10XX
110X
111X
Х реже всего (а именно 0 раз) встречается в первой позиции, поэтому поделим строки на два подмножества в зависимости от символа в ней и удалим первую позицию. Получим (ХХХ) и (0XX, 10X, 11X). И т.п.
(Reply) (Parent) (Thread)
[User Picture]
From:archaicos
Date:November 21st, 2011 09:21 am (UTC)

что-то торможу

(Link)
Пункт 3:
- что нам разрешает неглядя ни на что больше вырезать позицию из всех строк?
- что нам разрешает неглядя ни на что больше разбить список строк на два?
(Reply) (Parent) (Thread)
[User Picture]
From:spamsink
Date:November 21st, 2011 09:25 am (UTC)

Re: что-то торможу

(Link)
Вырезать позицию нужно, чтобы рекурсивные вызовы процедуры больше на нее не смотрели.
Разбить список строк на два и сделать два рекурсивных вызова нужно, чтобы проверить, что и при нуле, и при единице в данной позиции все остальные позиции удовлетворяют условию.
(Reply) (Parent) (Thread)
[User Picture]
From:archaicos
Date:November 21st, 2011 09:40 am (UTC)

Re: что-то торможу

(Link)
Понятно, что это нужно для "сходимости". Вопрос не в том, для чего нужно, а почему это правильно делать именно так.
(Reply) (Parent) (Thread)
[User Picture]
From:spamsink
Date:November 21st, 2011 03:42 pm (UTC)

Re: что-то торможу

(Link)
Если бы позиции рассматривались от старшей к младшей, было бы очевидно, что алгоритм честно проверяет на наличие соответствия для всех 2N комбинаций, и что как только мы увидим все Х, нужно тут же возвращать true. Но увы, premature optimization is the root of all evil.
(Reply) (Parent) (Thread)
[User Picture]
From:sab123
Date:November 17th, 2011 04:24 pm (UTC)
(Link)
Надо не добавить, а убрать :-) Вроде, всех делов:

0. Завести два битовых массива той же длины, изначально заполненных нулями. Первый массив будет считать покрытость нулями, второй - единичками.
1. Для каждой строки из множества, проходим поэлементно, и если там содержится 0, устанавливаем соответствующий бит в 1-м массиве, если 1 - во 2-м массиве, если Х - то в обоих двух.
2. Смотрим, все ли биты в полученных массивах стали содержать "1". Если да, то все покрыто. Иначе будут "0" в непокрытых позициях.
(Reply) (Thread)
[User Picture]
From:spamsink
Date:November 17th, 2011 04:36 pm (UTC)
(Link)
Отлично. Строки
000000
111111
устанавливают все биты в обоих массивах, но 64 комбинации никак не покрывают.
(Reply) (Parent) (Thread)
[User Picture]
From:sab123
Date:November 17th, 2011 07:16 pm (UTC)
(Link)
Чего это не покрывают? Все возможные биты покрывают. Ну, комбинации - ладно, не покрывают.
(Reply) (Parent) (Thread)