задачка, компьютерное
Feb. 14th, 2010 02:18 pm![[personal profile]](https://www.dreamwidth.org/img/silk/identity/user.png){kind=small}
avvaУбил на нее немало времени сегодня, но очень понравилась:
Придумайте схему, у которой есть три входа A, B, C и три выхода not-A, not-B, not-C. Можно пользоваться элементами AND, OR и NOT, но AND и OR сколько угодно, а NOT не более двух штук.
Я на время постараюсь скрывать правильные ответы. Но у меня есть предложение: если вы уже знаете решение, или нашли его компьютерным перебором, не пишите его в комментах - напишите просто, что нашли, например. Нет ничего плохого в компьютерном переборе, но не всем интересно. Мне хотелось именно найти решение самому аналитическим путем.
Придумайте схему, у которой есть три входа A, B, C и три выхода not-A, not-B, not-C. Можно пользоваться элементами AND, OR и NOT, но AND и OR сколько угодно, а NOT не более двух штук.
Я на время постараюсь скрывать правильные ответы. Но у меня есть предложение: если вы уже знаете решение, или нашли его компьютерным перебором, не пишите его в комментах - напишите просто, что нашли, например. Нет ничего плохого в компьютерном переборе, но не всем интересно. Мне хотелось именно найти решение самому аналитическим путем.
![[identity profile]](https://www.dreamwidth.org/img/silk/identity/openid.png){kind=small}
no subject
Date: 2010-02-14 02:44 pm (UTC)no subject
Date: 2010-02-14 02:45 pm (UTC)no subject
Date: 2010-02-14 03:08 pm (UTC)no subject
Date: 2010-02-14 07:08 pm (UTC)no subject
Date: 2010-02-14 08:27 pm (UTC)no subject
Date: 2010-02-14 08:47 pm (UTC)Если, например, автор журнала не разбирался в этих алгоритмах, то почему с помощью алгоритма с 25 операциями можно умножать матрицы быстрее, чем с помощью алгоритма с 12 операциями, может быть не столь очевидным. Ну если я зря попытался это пояснить, то извиняйте :-)
no subject
Date: 2010-02-14 07:17 pm (UTC)no subject
Date: 2010-02-14 08:26 pm (UTC)no subject
Date: 2010-02-14 08:41 pm (UTC)Например, сейчас известен алгоритм умножения матриц 3х3, использующий 23 операции умножения вместо 27, если умножать по определению. Народ вот считает, что это не оптимально (лучшая нижняя оценка - 19). А избавиться от хотя бы одного умножения с 1973 года не могут. И потом в задаче с инверторами на самом деле никакого избавления не идёт, а строится принципиально другая конструкция, основанная на поясковых функциях. Ни один инвертор при этом непосредственно к входной переменной не применяется, как в наивной процедуре с 3 инверторами.
В алгоритмах Карацубы, Тоома, Шёнхаге-Штрассена, Фюрера (это фамилия), Штрассена, Копперсмита-Винограда и проч. по сути никакого избавления даже не идёт. Ни один из этих алгоритмов не берёт стандартную процедуру и не избавляет её от арифметической операции. Быстрые алгоритмы для более или менее содержательных задач вообще редко когда получаются локальной модификацией какой-либо менее эффективной вычислительной процедуры.
Насчёт искусственности это вопрос :-) Задача в общем случае формулируется как задача реализации функции в немонотонном базисе. Насчёт железячных применений ничего сказать не могу (как известно, даже буфер в КМОП-логике сложнее инвертора), но как математическая или информатическая задача формулируется вполне естественно.
no subject
Date: 2010-02-15 07:53 pm (UTC)no subject
Date: 2010-02-15 08:06 pm (UTC)А давайте, вы мне не относящиеся к теме поста вопросы будете задавать не здесь, а, например, на формспринге.
no subject
Date: 2010-02-15 08:48 pm (UTC)Может, мейл?
no subject
Date: 2010-02-15 09:00 pm (UTC)Даны 3 точки: (a1, b1, c1), (a2, b2, c2), (a3, b3, c3), в каждой тройке есть хотя бы один не ноль. Если
a1*b2*c3 + a3*b1*c2 + a2*b3*c1 - a1*b3*c2 - a3*b2*c1 - a2*b1*c3 = 0, то точки лежат на одной прямой. Иначе - нет. Формула справедлива для проективной плоскости над произвольным полем. Определитель можно немного эффективнее вычислить.
Чтобы не засорять журнал хозяина, давайте я здесь больше на такие вопросы отвечать не буду :-)
no subject
Date: 2010-02-15 11:40 pm (UTC)no subject
Date: 2010-02-16 06:23 am (UTC)no subject
Date: 2010-02-16 08:41 am (UTC)x1/x0 = y1/y0
x2/x0 = y2/y0
Домножим на x0y0, получим условие совпадения X и Y с помощью четырех умножений:
x1y0 = y1x0
x2y0 = y2x0
Для совпадения X и Z еще 4 умножения, всего 8. Я думаю, что можно уложиться в семь. Это и есть задачка, которую я хотел предложить
no subject
Date: 2010-02-16 08:56 am (UTC)Как человек, по роду деятельности занимающийся алгебраической теорией сложности, могу сказать, что эта задача научного интереса не представляет и максимум тянет на домашнее задание на первом курсе. На статью совсем не тянет, уж извините :-)
no subject
Date: 2010-02-16 09:49 pm (UTC)a11, a12, a21, a22, b11, b12, b21, b22.
На выходе четыре выражения, в которых восемь умножений:
a11b11 + a12b21, a11b12 + a12b22, a21b11 + a22b21, a21b12 + a22b22.
Задача алгоритма:
выразить эти выражения с помощью семи умножений.
В задаче о трех совпадающих точках на входе девять чисел:
x0, x1, x2, y0, y1, y2, z0, z1, z2.
На выходе четыре выражения, в которых восемь умножений:
x0y1 - x1y0, x0y2 - x2y0, x0z1 - x1z0, x0z2 - x2z0.
Задача алгоритма:
выразить эти выражения с помощью семи умножений.
Сходство разительное. Я считаю, что это возможно - это не уверенность, а мое мнение. Научного интереса подобные задачи представляют только своими приложениями. Я не исключаю, что у задачи о трех совпадающих точках может найтись приложение в графике. Там часто используют проективные координаты (чтобы матрицы преобразований были кватернионами, вроде как).
no subject
Date: 2010-02-16 10:38 pm (UTC)Реплика из зала:
Чтобы операции сдвига, поворота и проектирования на плоскость описывались единообразно. Соответственно, так их легко комбинировать (как в хардвере, так и в софтвере).
Бонус: операции с цветами подгоняются под эту же схему, благодаря трихроматичности зрения.
no subject
Date: 2010-02-17 05:29 am (UTC)no subject
Date: 2010-02-17 05:37 am (UTC)1) Произведения выглядят по-другому, имеет место симметрия определителей. Числа-входы не независимы, как у Штрассена.
2) Нужно вычислять не произведение матриц, а 6 определителей (2 вы не выписали, неявно приняв, что первая координата не равна нулю у всех трёх, но вообще говоря, этого недостаточно).
3) Ваш алгоритм условный, потому что начинает работу с проверки на нуль координаты, следовательно, если брать модель без ветвлений, то алгоритм использует деления. С двумя делениями и 4 умножениями задача решается тривиально. Алгоритм Штрассена формулируется вообще в другой модели - он безусловный, там нет ветвлений.
У меня последний вопрос: это ваше хобби? :-)
no subject
Date: 2010-02-17 07:39 pm (UTC)Эти алгоритмы никогда не были моим хобби. Курсе на втором я с ними познакомился, даже походил на семинар к Матиясевичу и почти все забыл. Много лет спустя я изучал основы графических API и применение в них проективных координат и кватернионов. Я понял, что проверка совпадения трех точек может оказаться любопытной задачей, очень похожей на алгоритм Штрассена. И вот,
Да, если Вас интересует конвенциональное образование, то у меня PhD по математике (MSc - теорвер, PhD - алгебраическая геометрия) и достаточное количество поводов для нескромности и научного снобизма. :)
no subject
Date: 2010-02-17 08:54 pm (UTC)Вы хотя бы одну трактовку алгоритма Штрассена знаете? Он кишит симметриями, см. работы de Groote 1978 года.
Может быть, и любопытная задача для приложений. На теоретическую конференцию такую не примут.
Чем эта задача может быть похожа на алгоритм Штрассена, кроме того, что вычисляются билинейные формы и там, и там, и что тривиальный алгоритм требует 8 умножений и там и там (см., кстати, ниже) - ума не приложу :-) Вот определитель и детерминант тоже ой как похожи, а для первого есть субкубический алгоритм вычисления, для второго - ничего лучше экспоненциального.
Далее, алгоритм Штрассена не использует ветвлений. Вы же начали с того, что допустили, не умаляя общности, что первая координата у всех точек ненулевая. Если вы уж хотите полную аналогию со Штрассеном, то избавьтесь от условных операторов в алгоритме. Вообще говоря, вам нужно будет тогда вычислить больше билинейных форм. Так что попробуйте для начала там добиться меньше 12 умножений, что уже не так тривиально.
Если вы настаиваете на прикладном аспекте, то для 3 точек вам мало будет скостить одно умножение. Во всех известных мне сегодняшних реальных системах умножения уже не являются намного более тяжёлыми, чем сложения. И убрать 1 умножение, добавив, скажем, 10 сложений обернётся общим проигрышем.
Повторюсь: на мой взгляд,
1) аналогия задачи вычисления 3 отрицаний с 2 инверторами с эффективными билинейными алгоритмами - абсолютно искусственная. Экономится не "1 отрицание", как у Штрассена или Карацубы, а "n-]log(n+1)[", модель абсолютно другая, эффекты в одном случае чисто дискретные на гиперкубе, в другом - чисто алгебраические, метод решения абсолютно другой, рекурсия строится совсем на другом принципе;
2) никакой аналогии вашей задачи с билинейными алгоритмами умножения я не вижу, увы. У меня есть основания считать, что я уже могу рассуждать на таком макроуровне.
Желаю успехов в решении :-) Для повышения уровня (ну или для понижения самооценки, если вы свой уже считаете слишком высоким :-) рекомендую почитать Peter Bürgisser, Michael Clausen, M. Amin Shokrollahi "Algebraic Complexity Theory", классная книжка. Там вам и про матрицы, и про полиномы, и про принадлежности точек многообразиям. А ваше алгебраикогеометрическое образование вам в этом сильно поможет. Мне вот пришлось штудировать Хартшорна самостоятельно через большое "нехочу", пока не достал Шафаревича :-)
no subject
Date: 2010-02-18 07:05 am (UTC)