где требуются спецы по оптимизации ?

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

 

Осталось объявить это всему миру.


Guru_of_Zen, а Вам зачем соб-но?
Спецы нужны. Много. Умных.

Более конкретный разговор вести смысла не вижу, ибо тема из оперы "попендеть".

Но вот неск. тестовых заданий, одной фирмы, чтобы иметь возможность прийти на собеседование. (офлайн тест)


---------------------
Еще одна задачка на построение оптимальных сравнений – более сложная и интересная. Помимо операций из предыдущего задания в этом задании Вы можете воспользоваться следующими 32-разрядными двухаргументными операциями вычисления предикатов:

Мнемоника Эквивалентная операция языка Си Комментарий
cmpe(x,y) x == y сравнение на равенство
cmpls(x,y) ((signed)x) < ((signed)y) знаковое срванение на «меньше»
cmplse(x,y) ((signed)x) <= ((signed)y) знаковое сравнение на «меньше или равно»
cmplu(x,y) ((unsigned)x) < ((unsigned)y) беззнаковое срванение на «меньше»
cmplue(x,y) ((unsigned)x) <= ((unsigned)y) беззнаковое сравнение на «меньше или равно»
cmpande(x,y) (x & y) == 0 AND над двумя числами и сравнение результата с нулем

а также двухаргументными операциями над предикатами:

Мнемоника Эквивалентная операция языка Си Комментарий
andp(p1,p2) p1 && p2 AND над двумя предикатами
andpn(p1,p2) p1 && (~p2) AND над двумя предикатами с инверсией второго аргумента
andpnn(p1,p2) (~p1) && (~p2) AND над двумя предикатами с инверсией обоих аргументов
orp(p1,p2) p1 || p2 OR над двумя предикатами
orpn(p1,p2) p1 && (~p2) OR над двумя предикатами с инверсией второго аргумента
orpnn(p1,p2) (~p1) && (~p2) OR над двумя предикатами с инверсией обоих аргументов

Вполне возможно, что раньше Вы не сталкивались с операциями над предикатами. Поэтому приведем пример вычисления предиката равенства числа X одной из констант 1, 3 или 5 с использованием пяти операций:

P1 = cmpe( X, 1); P2 = cmpe( X, 3); P3 = cmpe( X, 5);
P4 = orp( P1, P2);
Pres = orp( P4, P3);

Эквивалентная запись без промежуточных переменных:

Pres = orp( orp( cmpe( X, 1), cmpe( X, 3) ), cmpe( X, 5) );

Для полной ясности приведем и эквивалентную запись на Си:

Pres = ( (X == 1) || (X == 3) || (X == 5) );

Но все-таки лучше использовать запись на псевдокоде а не на Си так как не все доступные операции описываются как одна операция в нотации Си (например, cmpande).

Теперь собственно задание. Для нижеприведенного набора констант сформировать предикат равенства произвольного знакового 32-разрядного числа (представленного в дополнительном коде) одной из констант. Набор констант содержит 19 элементов:

0, 3, 7, 14, 16, 21, 22, 23, 29, 32, 128, 256, 257, 258, 259, 260, 512, 1024, 2048

Проблемы такого рода возникают перед компилятором, например, при оптимизации конструкции switch. Если вычислять предикат так как, в вышеприведенном примере, то на это потребуется 37 операций (19 операций сравнения и 18 операций над предикатами). Для указанного набора констант известен способ вычисления предиката с использованием 12 операций из множества операций приведенных в этом и предыдущем заданиях. Но если Вы получите 20 и меньше операций, то это уже неплохой результат.

В задании подобном этому можно много чего напридумывать, поэтому будет неплохо, если Вы кроме формулы приведете и ее короткое объяснение.


-------------------

Попробуем порассуждать о рекурсивных вызовах. Сразу уточним, что в этом задании мы не рассматриваем рекурсию с математической точки зрения (мы не хотим углубляться в рассмотрение частично рекурсивных функций, лямбда-исчисления etc). Мы рассматриваем конструкции вызова конкретного языка (например, Си). Соответственно вопросы этого задания не предполагают строгого математического доказательства.

Очевидно, что некоторые случаи прямой рекурсии (то есть вызова из процедуры самой себя) могут быть заменены циклом. Например, простейшая функция поиска элемента списка содержащего некоторое значение может быть представлена в виде прямо рекурсивной процедуры:

int find_elem( list, data)
{
if ( list == NULL )
return NULL;
if ( get_data( list) == data )
return list;
return find_elem( get_next( list), data);
}

и в виде цикла (обратите внимание на то, что нам не пришлось вводить дополнительных стековых структур данных):

res = NULL;
while ( list != NULL )
{
if ( get_data( list) == data )
{
res = list;
break;
}
list = get_next( list);
}

Какие из утверждений относительно прямо рекурсивных вызовов с Вашей точки зрения являются правильными:

а. Любая прямая рекурсия может быть запрограммирована в виде цикла с использованием дополнительной памяти

б. Любая прямая рекурсия может быть запрограммирована в виде цикла без использования дополнительной памяти

в. Для преобразования любой рекурсии в цикл необходимо знать максимальную глубину рекурсивных вызовов

г. Процедура, содержащая более одного вызова самой себя, не может быть запрограммирована в виде цикла без использования дополнительных стеков.

д. Любой цикл может быть запрограммирован в виде рекурсии

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

-------------------------------------------------

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

Более строгое определение: нетривиальная сильно связанная компонента есть подмножество узлов графа таких, что каждый достижим из каждого (в том числе и каждый из себя самого). При этом если два узла достижимы друг из друга, то они должны принадлежать одной компоненте.

Тривиальные компоненты (то есть отдельные узлы не достижимые сами из себя) мы не рассматриваем и далее под компонентой понимаем именно нетривиальную компоненту.

Определение сильно связанных компонент не содержит произвола – номенклатура сильно связанных компонент и принадлежащих им узлов для любого графа определяются однозначно.

Попробуйте проанализировать свойства предложенного Вами (или найденного в литературе) алгоритма топологической сортировки и определите какие из ниже перечисленных свойств выполняются для топологической сортировки на произвольном графе:

а. Если из графа удалить все дуги, которые сортировка определила как обратные, в графе не останется ни одной сильно связанной компоненты (в дальнейшем просто компоненты)

б. Для узлов принадлежащих одной компоненте наименьший номер будет иметь тот узел, в который обход графа во время нумерации зашел первым (узел компоненты с наименьшим среди всех узлов компоненты номером назовем головой компоненты)

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

г. Узлы любой компоненты пронумерованы компактно (то есть компонента имеющая голову с номером H и содержащая узел с номером K при любом варианте топологической сортировки содержит узлы с номерами от H до K).

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

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

ж. Все обратные дуги входят в головы сильно связанных компонент

з. Голова любой компоненты имеет по меньшей мере одну входную обратную дугу

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

==================================================

Если Вы в теме и Вас интересует работа "оптимизатором" - дерзайте.

 

в _сильно_ эмбеддед (да и вообще в эмбеддед) приложениях связанных с обработкой изображений и звука нужны хорошие алгоритмисты. такие люди без труда распаралелят инструкции на ассемблере уделив час-два на чтение соответствующего _справочника_. здесь самое важное - это светлая голова, незашоренные мозги и матан.
хорошие мозги и алгоритмы еще очень требуются в low latency trading & finance. за соответствующие скиллсы хорошо платят (например здесь в Ау от 150к и выше).
спасибо за внимание.