о разных алгоритмах

[avva]

(интересно будет только программистам)

1. Неплохое описание схемы работы с большими массивами без инициализации, при том, что в них может лежать мусор. Это красивый трюк, и изредка действительно полезный; я додумался до него сам как-то в процессе решения какой-то задачи в университете (подробностей не помню, может, задача именно так и была сформулирована), но ни разу не применял его на практике.

2. Я зашел на Project Euler впервые после долгого перерыва, и решил две последние задачки. Получил огромное удовольствие, хоть и написал решения на C не вполне понятно почему. В одной из них мне пригодился фокус из HAKMEM (перебор всех способов выбрать k элементов из n, с помощью битмаски), а в другой - disjoint-set, которым я тоже не пользовался очень давно.

Вообще disjoint-set - волшебно красивая штука. Я помню, что у меня затаило дыхание, когда я впервые увидел. Это алгоритм из Книги, поистине.

3. В связи с одной из задач наткнулся на страничку про MiniSat. Я не знал, что есть соревнования по решению SAT! Хочется найти время и почитать этот, вроде бы относительно простой и тем не менее эффективный, алгоритм. Исходники там есть.

4. Я тут узнал, что не все знают о Project Euler. Друзья, если вы получаете удовольствие от программирования, вам прямая дорога туда. Почти в каждой задаче там надо придумать способ ее решить, который даст ответ достаточно быстро - но суть не в бездумных оптимизациях, а в алгоритмах и структурах данных. Это, может, звучит сухо, но на деле невероятно увлекательно; а еще - умный ход - когда правильно решаешь задачу, получаешь доступ на тему на форуме, где уже решившие обсуждают свои решения и делятся кодом.

Comments

[djuffin.livejournal.com]

А как вы относитесь к Top Coder (http://topcoder.com/tc)?

[arno1251.livejournal.com]

Как, интересно, можно точно перевести disjoint-set на русский?

[spamsink.livejournal.com]

1. (This would drive valgrind nuts.) Вот именно. :)

2. Сколько-то лет назад я был горд собой, когда существенно сократил время работы программы, реализовав компрессию при поиске в структуре, аналогичной disjoint set, но что у нее есть умное название, узнал только сегодня. :(

[flaass.livejournal.com]

Классы эквивалентности.
Я этот алгоритм узнал из "Дисциплины программирования" Дейкстры; там он приписан Мартину Рему. Странно, что в Вики об этом не упомянуто.

[pawa.livejournal.com]

Система непересекающихся множеств. См. русский перевод книжки Кормена, Лейзерсона и Ривеста.

[pawa.livejournal.com]

Самое клевое в disjoin-set это то что его можно реализовать буквально в несколько строчек:

...
for (int i = 0; i < N; i++) P[i] = i;
...

int get(int i) {
if (P[i] == i) return i;
else return get(P[i]);
}

void unite(int i, int j) {
if (rand() % 2 == 0) P[get(i)] = get(j);
else P[get(j)] = get(i);
}


Конечно, тут вместо эвристики с рангами случайная балансировка, но для целей подобных Project Euler этого более чем достаточно.

[pawa.livejournal.com]

строчку "return get(P[i]);" следует читать как "return P[i] = get(P[i])" - сюда эвристика сжатия путей запихана.

[tnt23.livejournal.com]

Спасибо за ссылку по инициализации массивов. (В цитате из Jon Bentley's 1986 book занятное - it should be considered only when space is cheap, time is dear)

[avva.livejournal.com]

Ага. Красиво, спасибо.

[mikkim08.livejournal.com]

А это точно тот же самый алгоритм ?

[ilya-dogolazky.livejournal.com]

Спасибо! Очень забавный сайт с задачками. (просмотр комментов к первой задаче (которая имени Гаусса, 1+…+N) несколько расстраивает: язык программирования «бумажка с карандашом» вышел из моды)

[flaass.livejournal.com]

Насколько я помню, в точности.
Может, описан слегка по-другому, но ключевые идеи все те же.

[eterevsky.livejournal.com]

На Project Euler задачки по-моему, слишком простые, некоторые кажутся взятыми с потолка, а некоторые можно решить, только зная соответсвующую теорию (например, как решать уравнения Пелля).

Я бы порекомендовал spoj.pl (http://www.spoj.pl/), их там больше, они интереснее и сложнее + есть задачки challenge, в которых нужно написать самое быстрое или самое короткое решение. :)

Что до SAT -- в лаборатории в ПОМИ, где я учился рядом стояли кубки за лучшую реализацию SAT-решателя из за самую короткую SAT-задачу, которую никому не удалось решить. Собственно, edwardahirsch, которому принадлежит второй из кубков, является автором лучшего на данный момент алгоритма для решения SAT.

[eterevsky.livejournal.com]

К примеру, самое короткое решение этой задачи (http://www.spoj.pl/problems/SIZECON/) занимает 6 непробельных символов на перле.

[arno1251.livejournal.com]

Спасибо!

[arno1251.livejournal.com]

+++ break them up or partition them into a number of separate, nonoverlapping sets +++
Не очень удачный выбор термина, это пример definitio per idem (тождесловия). Выше дано определение как "классы эквивалентности" -- по-моему, то, что надо.

[netp-npokon.livejournal.com]

Комментариев к той задаче не читал, но наверняка народ меряется наиболее красивыми способами написать суммирование чисел. Это тоже своего рода искусство :)

[ilya-dogolazky.livejournal.com]

Там в основном какие-то циклы и массивы, но я их не читал. Насчитал всего 6 обычных решений из 4 страниц комментов и бросил. И одна программа на форте --- мелочь, но приятно.

[yasha.livejournal.com]

"Затаило дыхание"?

MiniSAT

[(Anonymous)]

I've tried an extension of SAT solver (with first-order logic for linear ineqalites) YICES just as a search engine for computing long gray codes( e.g. snakes, necklaces): sometimes it helps to break records

iz.

[http://users.livejournal.com/malfet_/]

В очередной раз спасибо за ссылку! Про Project Euler не знал - попробую выкраивать по нескольку часов на решение задачек..

[avva.livejournal.com]

Как-то не для меня все эти соревнования на скорость. Не люблю.

[avva.livejournal.com]

Вот, например, задачи типа "уместиться в поменьше символов" мне неинтересны. Когда-то увлекался, но прошло.

[avva.livejournal.com]

Перехватило?

[avva.livejournal.com]

Ага, это отличное место.

[yasha.livejournal.com]

Ага. Или "затаил дыхание".

[eterevsky.livejournal.com]

Мне они интересны главным образом "со стороны" -- решать я их толком не умею.

Re: MiniSAT

[(Anonymous)]

and one more thing about MiniSAT I forgot: Ed Clark (recent Turing award) has the papers where they applied MiniSAT for the search of bugs in C codes. I know his co-auther who works here in Switzerland on this topic: she visited Israel (IBM or Google) where she gave the presentation of the method. iz.

Re: MiniSAT

[avva.livejournal.com]

How do you apply MiniSAT to searching bugs? Do you have a link to her paper?

Re: MiniSAT

[(Anonymous)]

my understanding (but I am not in this business so may be wrong) is that they convert C/C++ code into a database of a special format. The format is convenient to run MiniSAT (or other SAT solver) over. The (assumed) bug (e.g. memory overflow etc.) itself is represented as a Boolean formula (in fact, it is negation of the statement that there is NO such bug). SAT searches satisfying assignment ( which is a counterexample) of this formula using the database as a context (i.e. set of the restrictions on the search space). If there is such assignment, it is decoded back into the fragment of the original C code and identifies the bug.

it's better to ask her, of course

webpage:

http://www.inf.unisi.ch/faculty/sharygina/

there are even some tools for such debugging on the webpage...

iz.

Re: MiniSAT

[avva.livejournal.com]

Alright, thanks a lot!

[oxfv.livejournal.com]

Собрался наконец с силами и поборолся с projecteuler - спасибо за толчок. Решил последнюю задачку, буду решать еще (time permitting).

[avva.livejournal.com]

Ура!

[(Anonymous)]

Неприятно, что вместо обсуждения алгоритмов они просто выкладывают код на этом форуме.

[(Anonymous)]

немного бесят решения некоторых задач, которые перестают работать даже при небольшом усложнении суть проблемы или даже при изменении данных

вновь баланс versatility vs. speed

[(Anonymous)]

ещё по сравнению с spoj, на projecteuler очень легко понять задачу, но о сложности решения это ничего не говорит

там как бы и отмечено, в целях проекта, что math [should be presented] as an entertaining subject.

[(Anonymous)]

проследите за тем, чтоб не перевалило за несколько часиков...

[(Anonymous)]

ещё здорово, что быстро привыкаешь к синтаксису других языков просматривая решения

[eterevsky.livejournal.com]

Я, кстати, готов признать, что был не прав, объявляя все задачи с Эйлера слишком простыми. Как оказалось, во второй сотне там есть что порешать.

На счёт интересности -- для многих задач соглашусь, но есть там и тупая техника или применение готовой формулы. Если не знать, как строится рациональное приближение, или как решается уравнение Пелля или простую формулу для мат. ожидания количества бросков кубика прежде чем выпадут все грани, то придумать это самому почти невозможно. В результате, решение задачи сводится к упражнению по поиску в википедии.

[nikat.livejournal.com]

Мда.
Спасибо огромное за ссылку на Project Euler.
Только вот вошёл во вкус, что-то у них там стряслось и сайт остановили. К сожалению.

[ilya-dogolazky.livejournal.com]

Про теорию Вы не совсем правы: конечно, если решать задачу №66 вне контекста и «по-честному» (то есть не только выдать правильный ответ, но и доказать, что он правильный), то придётся с ней очень помучаться. Но взгляните на №№64,65 --- прочтя их условия, немедленно понимаешь, что именно следует делать с номером 66. В кружке же тоже так часто делают: дают несколько задач сразу, так что их легко решить вместе, хотя по-отдельности это было бы очень и очень сложно.

Расскажите пожалуйста, как решить задачу на перле с шестью непробельными символами :-)

[ilya-dogolazky.livejournal.com]

Можно конечно и в википедию лезть, но я обошёлся без этого («неспортивно», да и зачем? :-), а формул по теории вероятности и вовсе никаких не знаю, но решить задачу (кстати, а о которой Вы говорите?) это не помешало.

[ilya-dogolazky.livejournal.com]

Я как раз сейчас читаю роман Даниэля Кельмана «Die Vermessung der Welt», там один персонаж складывает в школе натуральные числа от единицы до тысячи. У него очень ловко получается :-)

[eterevsky.livejournal.com]

Гм. Я решал 64, 65, 66 не подряд, так что не заметил совпадения. В принципе да, для решения 66-й задачи достаточно мысли о том, что хорошее рациональное приближение иррационального числа получается из цепной дроби.

Мда, надо наконец дорешать Эйлера. 50 задач всего осталось. :-)

За 6 непробельных символов я не умею. У меня лучшее решение получилось с 11-ю, что ли. Да и вообще, я не специалист по перлу и по подобного рода задачам. :-)

[eterevsky.livejournal.com]

Теория вероятности тут не причём. Это комбинаторика.

Задача такая (номер не помню). Есть кубик (dice, а не cube) c n сторонами. Каково матожидание количества бросков, после которых выпадут все его стороны?

Ещё была какая-то задача в которой в ответе фигурировала рекурентная последовательность x(n) = x(n-1) + x(n-2) - x(n-3) - x(n-4) + x(n-5) + x(n-6) - ... В упор не помню, что это была за задача, но по-моему, там эту формулу тоже придумать не зная почти не возможно.