Алгоритмы *

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

Владимир Мегре



Статья посвящается Зацепину П.М., выдающемуся инженеру Алтайского государственного университета, под чьим чутким руководством многие студенты, включая автора статьи, постигали магию инженерного творчества.

Введение

Спор о возможности использования в программах оператора GOTO ведётся уже очень давно (официальным его началом признана статья Дейкстры «О вреде оператора GOTO», опубликованная в 1968 году [2]). Через три года мы будем праздновать 50-летний юбилей этого спора. Это хороший повод, чтобы наконец-то «расставить все точки над i» и прекратить спор.

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

Давайте займём в этом споре нейтральную сторону, и беспристрастно во всём разберёмся. Рассмотрим доводы «противников» и «защитников» оператора GOTO и решим, «кто из них прав, а кто виноват».

Профессор математики Нью-Йоркского Университета и эксперт по финансовым рынкам Марко Авелланеда (Marco Avellaneda) составил презентацию, в которой рассказал о том, как с помощью алгоритмов крупные инвесторы «скрывают» свои масштабные сделки, а другие трейдеры занимаются предсказанием изменений цен акций.

В нашем сегодняшнем материале — основные моменты этой работы.

Программа, способная к логическим выводам в рамках поставленной задачи, может казаться техническим чудом и воплощением Скайнета. Но, как можно убедиться ниже, на сегодняшний день создать такую программу на языке Python не составит труда, если использовать семантические технологии. Мы остановимся на наглядном примере онтологий — родословных — и для любого члена семьи в родословной сможем выводить его родственные отношения произвольной сложности (она ограничена вычислительными ресурсами). К примеру, на фамильном древе семьи Романовых ниже показан внучатый двоюродный племянник (first cousin twice removed) российского императора Петра II.



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

Мы рады сообщить о начале очередного международного чемпионата по программированию искусственного интеллекта — Russian AI Cup. В этот раз чемпионат получил название CodeRacing. Храбрецам, которые отважатся принять участие, предстоит программировать искусственный интеллект для управления гоночным автомобилем. Но он должен будет не просто исполнять роль водителя, но и одновременно расстреливать соперников. В «игровом» мире предусмотрено четыре типа юнитов: кодемобили, снаряды, бонусы и лужи мазута. Самые «грязные» приёмы на трассе будут только поощряться: можно толкать чужие машины, повреждать их и ломать.

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

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

UPDATE: Опубликованы итоги конкурса.

Компания Hola снова объявляет конкурс по программированию на JS с солидным призовым фондом:

1. Первое место: 1500 USD
2. Второе место: 1000 USD
3. Третье место: 500 USD
4. Возможно, мы решим отметить чьё-то чрезвычайно оригинальное решение специальным призом в 350 USD.
5. Если Вы отправите кому-то ссылку на этот конкурс, поставив наш адрес в CC, и этот человек займёт призовое место, Вы получите такую же сумму, как и он.

Мы ищем талантливых программистов, поэтому авторы интересных решений будут приглашены на собеседования.

Правила

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

Условия конкурса на английском языке размещены на нашем сайте. Ниже — перевод на русский язык.

Соревнование Back to the Code закончилось и мы получили огромное удовольствие от просмотра различных повторов игр и изучения стратегий в каждой. Мы увидели достаточное количество хороших идей и мы надеемся вы насладились игрой в той же степени, что и мы.

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

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

Известный автор книг по занимательной математике Е. Я. Гик в своей книге "Занимательные математические игры" опубликовал такое 16-ходовое решение, как из мухи сделать слона: муха-мура-тура-тара-кара-каре-кафе-кафр-каюр-каюк-крюк-урюк-урок-срок-сток-стон-слон.



И вот, в один прекрасный день мне довелось заняться решением этой задачи в программном виде.

Высокочастотный трейдинг [англ. High-frequency trading, HFT-trading] сегодня оказывает большое влияние на современные финансовые рынки. Еще 20 лет назад большая часть торгов проходила на биржах, к примеру, на Нью-Йоркской фондовой бирже, где люди, одетые в яркие костюмы, активно жестикулировали и выкрикивали свои предложения о покупке или продаже ценных бумаг. Сегодня торговля, как правило, осуществляется с помощью электронных серверов в дата-центрах, где компьютеры обмениваются предложениями о покупке и продаже путем передачи сообщений по сети. Этот переход от торговли в операционном здании биржи к электронным платформам был особенно выгоден HFT-компаниям, которые инвестировали много средств в необходимую для торговли инфраструктуру.

Несмотря на то, что место и участники торговли внешне сильно изменились, цель трейдеров – как электронных, так и обычных – осталась неизменной – приобрести актив у одного предприятия/трейдера и продать его другому предприятию/трейдеру по более высокой цене. Основное отличие традиционного трейдера от HFT-трейдера состоит в том, что последний может торговать быстрее и чаще, и время удержания портфеля у такого трейдера очень низкое. Одна операция стандартного HFT-алгоритма занимает долю миллисекунды, с чем не могут сравниться традиционные трейдеры, так как человек моргает примерно раз в 300 миллисекунд. По мере того, как HFT-алгоритмы конкурируют между собой, они сталкиваются с двумя проблемами:

• Каждую микросекунду они обрабатывают большой объем данных;
• Им нужно уметь очень быстро реагировать на основе этих данных, потому что прибыль, которую они могут извлечь из принимаемых ими сигналов, снижается очень быстро.

Онлайн-алгоритмы представляют собой обычный класс алгоритмов, которые можно применять в HFT-трейдинге. В таких алгоритмах новые входные переменные поступают последовательно. После обработки каждой новой входной переменной алгоритм должен принять конкретное решение, например, выставлять ли заявку на покупку/продажу. В этом и состоит главное отличие онлайн-алгоритмов от офлайн-алгоритмов, в которых считается, что все входные данные доступны в момент принятия решения. Большинство задач практической оптимизации в таких областях, как информатика и методы исследования операций – это именно онлайн-задачи [1].

В этом году компания Itseez провела сразу два летних мероприятия для студентов, интересующихся тематикой компьютерного зрения — Межвузовскую школу и Летнюю стажировку. Здесь мы расскажем об обоих прошедших мероприятиях: о Школе, которая проводилась совместно с институтом ИТММ ННГУ им. Н.И. Лобачевского, и Стажировке, которую ребята проходили непосредственно в компании Itseez.
Мы поделимся тем, как велась подготовка, как производился отбор участников и вообще о том, как это все происходило. Зимой планируется очередное мероприятие для студентов — зимняя школа по оптимизации производительности приложений компьютерного зрения. Поэтому настоящая статья может быть особенно интересна тем, кто хотел бы принять участие в будущих образовательных активностях Itseez.

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

Для работы над Яндекс.Музыкой нам всегда важно помнить о разных тонкостях, которые таит в себе звук. Что такое громкость, как она меняется и от чего зависит? Как работают звуковые фильтры? Какие бывают шумы? Как меняется звук? Как люди его воспринимают.



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

Поводом для этого поста можете считать то, что мы добавили в приложения Яндекс.Музыки возможность слушать треки в высоком качестве (320kbps). А можете не считать. Итак.

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



В первом случае поиск занимает A?ⁿAⁿ времени, во втором — Aⁿ.

Степени обозначают повторяемость строк, то есть A?³A³ — это то же самое, что и A?A?A?AAA. Графики отражают время, требуемое для поиска через регулярные выражения.

Обратите внимание, что в Perl для поиска строки из 29 символов требуется более 60 секунд. А при втором методе — 20 микросекунд. Это не ошибка. При поиске 29-символьной строки Thompson NFA работает примерно в миллион раз быстрее. Если нужно найти 100-символьную строку, то Thompson NFA справится менее чем за 200 микросекунд, а Perl понадобится более 10¹⁵ лет. Причём он взят лишь для примера, во многих других языках наблюдается та же картина — в Python, PHP, Ruby и т. д. Ниже мы рассмотрим этот вопрос более детально.

Наверняка вам трудно поверить приведённым данным. Если вы работали с Perl, то вряд ли подмечали за ним низкую производительность при работе с регулярными выражениями. Дело в том, что в большинстве случаев Perl обращается с ними достаточно быстро. Однако, как следует из графика, можно столкнуться с так называемыми патологическими регулярными выражениями, на которых Perl начинает буксовать. В то же время у Thompson NFA такой проблемы нет.

Возникает логичный вопрос: а почему бы в Perl не использовать метод Thompson NFA? Это возможно и следует делать, и об этом пойдёт далее речь.

Задача № 1 для ритейлера — понять, кто конкретно совершает покупки в магазине, изучить поведение покупателей, выделить типичные модели, и с помощью этих знаний влиять на количество и качество покупок.

Решение возможно, используя такие подходы:

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

Перефразируя второй подход — какие товары покупатель положил в свою корзину?

Когда мне понадобилось реализовать ярлыки для Java «как в веб-два-ноль», гугление не помогло найти ни одной библиотеки, содержащей в себе подобный тип коллекции.

Решил сделать сам.

Итак, нам надо хранить объекты в коллекции данного типа (назовем его, скажем, LabelsMultiMap). Как объекты, так и ярлыки могут быть произвольного типа. Количество ярлыков сверху не ограничено, равно как и количество объектов. Одним и тем же набором ярлыков могут быть описаны более 1 объекта. У одного объекта один ярлык может встретиться только 1 раз.

Пример валидных ярлыков:

Ярлыки	Объекты
green, wooden, alive	tree
green, wooden, lifeless	bench
green, alive, croak	frog

Коллекция должна позволять:

1. put() — помещать в неё объекты со списком прикрепленных меток
2. getValues() — возвращать объекты, содержащиеся в коллекции
3. findValues() — осуществлять поиск объектов, ярлыки которых содержат запрашиваемый набор ярлыков
4. findValuesOnlyIn() — осуществлять поиск только тех объектов, все ярлыки которых входят в запрашиваемый набор ярлыков

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

• Утечки приватных данных в процессе их обработки на внешнем устройстве или в процессе передачи данных;
• Возможность наличия искажений в получаемых результатах вычислений на внешнем устройстве или в процессе передачи данных. При этом, даже многократный повтор вычислений с одними и теми же исходными данными не позволит обнаружить наличие этих искажений если они носят системный, а не случайный характер.

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

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

Помимо рассказов о собственном опыте работы над оптимизацией различных сервисов нашего IaaS-провайдера мы анализируем западный опыт. От управления проектами до технологических кейсов, о которых рассказывают другие ИТ-компании.

Сегодня мы решили взглянуть на профессию, которая связана с непосредственной работой с данными, и обратили внимание на заметку Филиппа Гуо (Philipp Guo), который работает в университете Рочестера «ученым по данным».

Привет, Хабр.

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

И в этот момент под моим пристальным взглядом оказалась незаметная строчка «native code», которая так или иначе появляется перед глазами любого JS разработчика в консоли Chrome или Node.js:

[].sort.toString();
"function sort() { [native code] }"

Итак, кому интересно, какая реализация сортировки скрывается в V8 за надписью [native code] — добро пожаловать под кат.

Сейчас я работаю над senjin/gglsl — библиотекой для программирования шейдеров с помощью Groovy, о которой недавно писал.

Здесь я опишу три подхода к анализу AST (abstract syntax tree), все на примерах под-задач, вытекающих одна из другой и связанных общим контекстом: рекурсивные функции, паттерн Visitor, и паттерн-матчинг.
Паттерн-матчинг реализован на Java и доступен на GitHub.

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

array.sort()

И все. Кому нужен вообще какой-то алгоритм. В задании было установлено ограничение от 0 до 100, мы же не лентяи, сделаем в общем виде, для любых значений и с повторениями чисел. Немного подумав, пришел вот к такому решению:

Доброго времени суток. Так сложилась жизнь что я от недавнего времени стал гордым студентом одного из лучших вузов своей страны. Хорошо или плохо это вопрос спорный, но это не суть. Самое забавное это то, что на лабораторных работах преподаватель то ли для развлечения, то ли для того, что бы в очередной раз напомнить мне что я весьма паскудно разбираюсь в алгоритмике, время от времени выдает задания отличные от того, что получает оставшаяся группа. Одно из последних, которое, как по мне, достойно вашего внимания является сортировка массива без использования условных операторов (if, switch и тому подобных).