?

Log in

No account? Create an account

Алло, мы ищем логических дизайнеров! - Ваши рубидии уже у кобальта во ртути

Oct. 12th, 2015

07:13 pm - Алло, мы ищем логических дизайнеров!

Previous Entry Share Next Entry

Comments:

[User Picture]
From:mtve
Date:October 13th, 2015 09:56 am (UTC)
(Link)
очень коряво у них сформулировано, "надо мягше"...

например, считаются разные функции или кол-во использованных функций?
(Reply) (Thread)
[User Picture]
From:spamsink
Date:October 13th, 2015 02:38 pm (UTC)
(Link)
Количество. А как было бы лучше, и чтобы без хардверного жаргона?
(Reply) (Parent) (Thread)
[User Picture]
From:mtve
Date:October 14th, 2015 11:52 am (UTC)
(Link)
Мне было бы понятней как-то так:

"Есть булевы функции, n бит на входе, m бит на выходе, назовём их n->m.

Закодируем такую функцию в виде перечня входов, и значений выходов для всех вариантов входов.

Например, если n=3 и m=2, то для трёх входов a, b и c будет 8 вариантов их значений (000, 001 и т.д.), и для всех вариантов входов можно закодировать выходы как какие-то значения функции (например 00, 10, 01, ...) десятичным цифрами, тем самым представить такую функцию можно в виде abc02113302 (где 0 это 00, 2 это 10, и т.д.). Первый бит является самым старшим.

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

Например, [тут описание примера с компаратором]
acd02113302
bef21133123
7 8


Задача: нужно из нескольких произвольных функций 5->2 составить функцию 12->4, которая бы вычисляла сумму входных значений, то есть сделать сумматор. Чем меньше используется функций 5->2 тем лучше, их должно быть не больше 9.

Формат: [тут чёткое описание в каком формате присылать решения]"

И, кстати, когда функций больше 8, то строчных английских букв для выходов не хватит, если например в 9-й функции использовать результаты 8-й, то есть формат немного недодуман]
(Reply) (Parent) (Thread)
[User Picture]
From:mtve
Date:October 14th, 2015 12:20 pm (UTC)
(Link)
хотя наверное нет, снимаются все возражения. если такой тупой что не понял задачи, незачем и соваться)
(Reply) (Parent) (Thread)
[User Picture]
From:spamsink
Date:October 14th, 2015 03:54 pm (UTC)
(Link)
Идея смешивать описание задачи и описание желаемого представления ответа представляется мне не очень удачной, хотя...

И, кстати, когда функций больше 8, то строчных английских букв для выходов не хватит, если например в 9-й функции использовать результаты 8-й, то есть формат немного недодуман]

...с другой стороны, формат является подсказкой, какое количество функций или их соединений очевидно неоптимально. :)
(Reply) (Parent) (Thread)
[User Picture]
From:mtve
Date:October 14th, 2015 08:27 pm (UTC)
(Link)
Думаю что верифицируют ответ они всё-таки формально.

Это интересная и сложная хорошая задача. Просто странное описание иногда отталкивает, возникает ощущение снобизма у авторов "догадайся что мы имели в виду". Без Вашей наводки, например, в эту - я даже не стал бы вчитываться, ещё раз спасибо.

Сочинения учили писать так: введение, основная часть, заключение, и всегда радуешься хорошо сформулированной задаче.
(Reply) (Parent) (Thread)
[User Picture]
From:spamsink
Date:October 14th, 2015 08:49 pm (UTC)
(Link)
Да, хотя бы из вежливости могли сказать, что входами должны считаться переменные a-l (если это так). А то ведь вполне может оказаться, что выходами очередной функции оказываются переменные, следующие за последней как-либо использованной до сих пор, а входами считаются переменные, которые до сих пор ни разу не упоминались, и не являющиеся выходами предыдущих функций.

Я теперь жду-не дождусь увидеть ответы из 5 и 6 функций.
(Reply) (Parent) (Thread)
[User Picture]
From:mtve
Date:October 19th, 2015 03:23 pm (UTC)
(Link)
осилил из 7 функций, действительно крайне непонятно как сделать 6 и тем более 5.
(Reply) (Parent) (Thread)
[User Picture]
From:spamsink
Date:October 19th, 2015 05:01 pm (UTC)
(Link)
Насчет 5 функций нас обманули, там была опечатка. Сегодня на странице 3 звездочки там, где раньше было 4.
(Reply) (Parent) (Thread)
[User Picture]
From:spamsink
Date:October 21st, 2015 02:09 am (UTC)
(Link)
Сообщив о том, что он сделал 6 функций, ftdf меня подбодрил, и я тоже сделал, причем у нас оказались разные методы.
(Reply) (Parent) (Thread)
[User Picture]
From:mtve
Date:October 26th, 2015 04:13 pm (UTC)
(Link)
осилил 6. неделю играл с SAT формулами, наконец дожал.
(Reply) (Parent) (Thread)
[User Picture]
From:spamsink
Date:October 26th, 2015 04:23 pm (UTC)
(Link)
В смысле, что решение получилось (полу)автоматически?
(Reply) (Parent) (Thread)
[User Picture]
From:mtve
Date:October 26th, 2015 08:01 pm (UTC)
(Link)
да, силовой метод, если можно так сказать) верификация отдельных гипотез и перебор. cryptominisat рулит!
(Reply) (Parent) (Thread)
[User Picture]
From:spamsink
Date:October 26th, 2015 08:07 pm (UTC)
(Link)
Интересно будет через неделю, когда официальный ответ будет уже объявлен, посмотреть на Ваш. У нас с ftdf получилось вручную, разными способами. Что забавно, его путь решения я ошибочно отверг практически сразу, когда еще решал в уме, поэтому в ту сторону больше не думал. Если бы решал сразу на бумажке или компьютере, скорее всего, окончательный результат получился бы гораздо быстрее.
(Reply) (Parent) (Thread)
[User Picture]
From:mtve
Date:October 27th, 2015 11:59 am (UTC)
(Link)
я помогал решателю с топологией (фиксировал часть соединений), т.к. полный перебор за пределами ресурсов. получив решение, я его проверил, но не разбирался как оно работает, сам повторить его не могу.

md5 моего решения 24e4e0de0c60050887396d545dd4e17d

хочу втиснуть слово "mtve", но пока одна буква не влезает.
(Reply) (Parent) (Thread) (Expand)