Алгоритмы *

В 2012 году вся общественность, более или менее причастная к информационной безопасности, пристально следила за выборами нового стандарта хеширования данных SHA-3. На хабре достаточно широко освещалось это важное событие: публиковались результаты каждого раунда конкурса (раз, два, три), приводилось описание нового стандарта, и даже объяснялось почему новый стандарт так крут.
Однако, за всем этим ажиотажем совсем незамеченным осталось другое, не менее значимое событие: 1 января 2013 года в РФ также сменился стандарт хеш-функции.
Итак, встречайте: полное описание нового стандарта и его реализация на C#. Как говорится, лучше поздно, чем никогда.

Эта статья рассказывает о времени выполнения и о расходе памяти большинства алгоритмов используемых в информатике. В прошлом, когда я готовился к прохождению собеседования я потратил много времени исследуя интернет для поиска информации о лучшем, среднем и худшем случае работы алгоритмов поиска и сортировки, чтобы заданный вопрос на собеседовании не поставил меня в тупик. За последние несколько лет я проходил интервью в нескольких стартапах из Силиконовой долины, а также в некоторых крупных компаниях таких как Yahoo, eBay, LinkedIn и Google и каждый раз, когда я готовился к интервью, я подумал: «Почему никто не создал хорошую шпаргалку по асимптотической сложности алгоритмов? ». Чтобы сохранить ваше время я создал такую шпаргалку. Наслаждайтесь!

55-летний американский математик Тереза Кристи (Theresa Christy) работает в компании Otis Elevator Co. и считается одним из лучших специалистов по вертикальному транспорту. Двадцать пять лет своей жизни она посвятила разработке и оптимизации алгоритмов для лифтов. Именно её привлекли во время недавней реконструкции Empire State Building стоимостью $550 млн. Тереза Кристи увеличила скорость лифтов на 20% до 6 м/c, так что они теперь проходят первые 80 этажей всего за 48 секунд.

TCP (Transmission Control Protocol) — основной протокол интернета. Одна из его главных задач — бороться с перегрузками в сети (network congestion), когда возникают заторы из пакетов. Регулирование осуществляется путём взаимной подстройки скорости отправки запросов, причём для этого существует множество хитрых методов. Например, в Linux используется алгоритм под названием TCP Cubic, а под Windows — Compound TCP. Кроме них, существуют ещё TCP Tahoe, Reno, NewReno, Vegas, FAST, BIC и др.

Специалисты из Массачусетского технологического института разработали программу Remy, которая методом проб и ошибок пыталась улучшить существующие алгоритмы подавления заторов TCP. Результат превзошёл все ожидания. Эффективность алгоритмов RemyCC превзошла и TCP Cubic, и Compound TCP, и остальных «конкурентов» в различных сетевых условиях. Проблема только в том, что учёные не совсем понимают, за счёт чего именно Remy удалось показать такой феноменальный результат.

Disclaimer Данная статья публикуется исключительно в ознакомительных целях, за использование материалов, опубликованных в данной статье автор ответственности не несет.
Так же хочу сразу предупредить, что если вы рассчитываете найти в этой статье пошаговое руководство к прослушиванию GSM трафика или надеетесь, прочитав данную статью, получить доступ к телефонным разговорам ваших друзей, знакомых, домашних животных, то лучше проигнорируйте ее. Здесь вы не найдете ничего интересного. Нет правда, не ходите под кат, там скука.

На прошедшем неделю назад чемпионате мира по командному программированию ACM ICPC 2013 было 11 задач, одну из которых за отведённое время не смогла решить правильно ни одна из команд.

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

В этом году на ACM ICPC был 21 аналитик из Швеции, Нидерландов, США, Словакии, Беларуси и России. И 10 из них были из Яндекса. Все они в разные годы были призёрами ICPC. Специально для Хабра они разобрали все задания чемпионата.

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

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

Как же быть? Есть один трюк — непериодические мозаики. Они лишены проблемы повторяемости и достаточно просты в реализации. Одну из таких мозаик придумал китайский математик Ван Хао в 1961 году. Элементы этой мозаики можно представить в виде прямоугольников с разноцветными гранями. Но чтобы понять принцип её работы, надо сначала разобраться в классическом методе заполнения площадей текстурами.

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

Группа американских учёных, получив финансирование от исследовательского центра Национальной разведки США (IARPA) разработала высокоуровневый язык программирования Quipper. Он создан на основе Haskell и лучше подходит для реализации квантовых алгоритмов, чем QCL (основан на C).

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

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

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

На что вы сейчас смотрите? Если вы не из параллельной вселенной, где все сидят за векторными мониторами, то перед вами растровое изображение. Поглядите на эту полоску: /. Если придвинуться поближе к монитору, то можно увидеть пиксельные ступеньки, которые пытаются притвориться векторной линией. Для этой цели существует целая куча всевозможных алгоритмов растеризации, но я бы хотел рассказать об алгоритме Брезенхема и алгоритме У, которые находят приближение векторного отрезка в растровых координатах.

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

«Как автоматизировать сочинение музыки?» — этот вопрос тревожит умы музыкантов еще со времен средневековья. Кеплер превращал траектории движения планет в музыку; Моцарт и его современники изобрели игру в «музыкальные кости» — они броском кубиков выбирали из большой таблицы такты и составляли из них менуэты. Но только с появлением компьютеров алгоритмическая генерация музыки получила настоящее развитие. Теория вероятности, марковские цепи, искусственные нейронные сети — все это стало инструментами создания музыки.

Возможно, вам доводилось видеть игру Box Car 2D — автогонки машинок, сгенерированных с помощью генетического алгоритма. Игра работает на платформе Flash и использует физический движок box2d. За тем, как из бесформенных уродцев через несколько десятков поколений развиваются вполне приличные гоночные автомобили, можно наблюдать часами. Игра существует уже несколько лет, а её фанаты соревнуются в выведении новых «пород» машинок на разных типах трасс. Недавно в сети появился клон этой игры под названием Genetic Cars, написанный на HTML5 и JavaScript. Хотя в нем ещё многого не хватает (например, редактора машинок), некоторые вещи сделаны гораздо лучше, чем в оригинале. Например, есть возможность наблюдать заезд всех машинок одновременно. И самое главное — можно ковыряться в исходниках!

Отгадайте загадку: в четырёх измерениях сидит и комплексными числами воротит?

Подсказка: это вектор со скаляром. И вещественная матрица. И придумал его Гамильтон.

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

И снова здравствуйте! После перерыва в месяц продолжаем экскурсию по форматам изображений и алгоритмам сжатия. Где мы остановились? Ах, да, восьмидесятые годы.

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

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

Однако взятые крепости уже не манят. Естественно теперь задачу обобщить — например, сделать, чтобы маленький круг ездил внутри не окружности, а фигуры посложнее, допустим, эллипса.

Выставите любой палец левой руки вперед. Давайте, не стесняйтесь, никто не будет над вами смеяться. Это нужно для важного эксперимента. Выставили? Теперь представьте что вы — это ваш палец (ну и бред). Повернитесь под прямым углом направо, затем наверх, и наконец налево. Где вы оказались? Правильно, в том же месте, но уже на спине.

С некоторой натяжкой именно так работает вращение с помощью углов Эйлера. Немного непредсказуемо и неудобно, не правда ли? Углы Эйлера имеют несколько недостатков, но есть одно особенно нехорошее свойство из-за которого вы не захотите с ними связываться. Его имя — Gimbal lock.

В русском языке gimbal lock называют по-разному: шарнирный замок, блокировка осей, складывание рамок. К сожалению, по запросам в поисковике с такими ключевыми словами выдаётся много мусора, а статья в Википедии оставляет желать лучшего, поэтому я сам расскажу вам об этом феномене и предложу как с ним бороться.

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

Seam carving это алгоритм для изменения размера картинки, сохраняющий важный контент и удаляющий менее значимый. Он был описан в статье S. Avidan & A. Shamir. Он дает лучший результат, чем обычное растягивание изображения ввиду того, что не меняет пропорций значимых элементов изображения. Две фотографии ниже демонстрируют работу алгоритма – исходное изображение имеет размер 332x480, в то время как модифицированное seam carving'ом 272x400.


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

Древний холивар о том, нужна ли программисту математика, получил неожиданное продолжение в спорах о ЕГЭ. Активно начала продвигаться идея о том, что вообще не надо проверять знания, а надо проверять умение быстро искать ответы. Ну и как вывод – замена ЕГЭ на чемпионат по поиску в Гугле/Яндексе. На мой взгляд, с тем же успехом можно проводить экзамен в виде поиска по школьной библиотеке. Почему-то никто не замечает такой очевидной истины, что быстро находит ответы те, кто знают, что искать, то есть как раз обладают знаниями. Для подтверждения этой идеи я составил 3 задачки для программистов, алгоритмы решения которых я нашел бы за пару минут.

Конкурс ImageNet состоялся в октябре 2012 года и был посвящен классификации объектов на фотографиях. В конкурсе требовалось распознавание образов в 1000 категорий.

Команда Хинтона использовала методы deep learning и сверточных нейронных сетей, а также инфраструктуру, созданную в Google под руководством Jeff Dean и Andrew Ng. В марте 2013 года Google инвестировал в стартап Хинтона, основанный при университете Торонто, тем самым получив все права на технологию. В течение шести месяцев был разработан сервис поиска по фотографиям photos.google.com.

Spatial hashing это простая техника, которая используется в базах данных, физических и графических движках, симуляциях частиц и вообще везде, где нужно быстро что-то найти. Если в кратце, то суть в том, что мы разбиваем пространство с объектами на ячейки и складываем в них объекты. Затем вместо поиска по значению очень быстро ищем по хэшу.

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