?

Log in

No account? Create an account

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

Oct. 12th, 2015

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

Previous Entry Share Next Entry

Comments:

[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)
[User Picture]
From:mtve
Date:November 1st, 2015 08:28 am (UTC)
(Link)
моё решение по схеме 5,+1,5,...

abcde01321221122123101221231023103003
mndef33111111323221212222222221213210
ghijk13312113211302202113022002203002
qrjkp12010101231212122312120112232312
nqtfl13300221300221133013210202301321
ostfv22311111121222221212222220200000
24 23 22 21


возможно у меня перепутаны msb/lsb, в понедельник всё проверю
(Reply) (Parent) (Thread) (Expand)