Алгоритмы *

Сегодня, дорогой Хабр, я расскажу тебе историю о комбинаторной оптимизации.
Издревле (как минимум, с начала прошлого века) математики задавались вопросом, как оптимально разместить некоторое количество пива нужных и полезных предметов в рюкзаке. Была сформулирована задача о ранце и ее подзадачи — тысячи их! — которые заинтересовали информатиков, криптографов и даже лингвистов.

От задачи о ранце отпочковалась задача об упаковке в контейнеры (Bin Packing Problem), одной из разновидностей которых является задача двумерной упаковки (2-Dimensional Bin Packing). Снова отбросив несколько вариаций, мы наконец придем к двумерной упаковке в полуограниченную полосу (2-Dimensional Strip Packing, 2DSP). Чувствуете, сколько интересного уже осталось за кадром? Но мы еще не закончили продираться сквозь классификацию. У 2DSP есть два варианта входных данных: когда набор упаковываемых объектов известен заранее (offline-проблема) и когда данные поступают порциями (online-проблема).

В этой статье рассматриваются алгоритмы решения offline-варианта 2DSP. Под катом немного матчасти и много картинок с цветными квадратиками.

В чем, собственно, проблема?

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

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

Типичная величина одного интервала — 25,6 мс. Соседние интервалы берутся со смещением относительно предыдущего интервала. Применяемая величина перекрытия интервалов равна 10 мс. В результате предварительной проработки каждого из указанных интервалов получаем вектор из нескольких десятков спектральных значений.

Прошло уже больше года после завершения конкурса "Интернет-математика: Яндекс.Карты", но нас до сих пор спрашивают об алгоритме, который принёс нам победу в этом конкурсе. Узнав о том, что недавно Яндекс объявил о старте очередной "Интернет-математики", мы решили поделиться опытом нашего прошлогоднего участия и описать наш подход. Разработанный алгоритм смог с точностью 99.44% правильно определить лишние изображения в сериях панорамных снимков, например, как здесь:



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

Исходный код нашего решения доступен на github (C++ с использованием OpenCV).

Доброго времени суток, уважаемые читатели.
Многие из вас наверняка знают о том, что на протяжении нескольких лет NIST проводил конкурс среди хеш-функций с целью принятия нового стандарта SHA-3. И в этом году награда нашла своего героя. Новый стандарт был благополучно принят.
Ну а раз стандарт уже принят, самое время посмотреть что же он из себя представляет.
И тихим, субботним вечером, я обложившись мануалами открыв в браузере google.com начал свое небольшое исследование.

Понадобилось мне как-то сделать интерфейс для загрузки в микроконтроллер график функции «сопротивление -> температура» (график решили задавать по нескольким точкам, а потом их интерполировать). По ходу дела выяснилось, что график будет оч-чень нелинейным (180 Ом -> 100^o, 6 000 Ом -> 0^o, 30 000 Ом -> -30^o). Поэтому пришлось мне погрузиться в тему логарифмических шкал… и сразу вынырнуть, так как я не нашел того, что мне нужно. А нужно-то мне было всего лишь понять математику (и реализацию на С++) таких дел. ЧуднО — вроде такая нужная тема, а не расписано! Ну да ладно — мозги заскрипели и вспомнили высшую математику из университета, и программа была написана. Решил описать я свои мытарства тут — может, кому пригодится.

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

Осторожно: в тексте много графики!

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

Корни истории уходят в те годы, когда один из кланов древней текстовой игры «Бойцовский клуб» заказал у меня, молодого программиста на Perl, капчу для игры. Пара бессонных ночей — и четыре ровных цифры готовы вместе с проверкой ввода.



Через несколько дней пришёл другой, не менее уважаемый клан, и заказал парсер той самой капчи. Для её разбора пришлось потратить гораздо больше времени, никакого Ocrad тогда ещё не было, но был найден очень простой и рабочий способ.

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







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

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

Обычно мы пишем про хостинги, в частности про зарубежный shared хостинг в США. Но чтобы писать, нужно иметь аналитические данные под рукой. Вот как раз тут требуется помощь Google Docs, если файл получится предположительно меньше 400 000 строк.

За несколько месяцев работы с таблицами Google пришлось много раз анализировать посредством формул разного рода данные. Как и ожидалось — то, что можно было решить в MS Excel, можно реализовать и в Google таблицах. Но многочисленные попытки решить проблемы с помощью любимого поисковика приводили только к новым вопросам и почти к нулевым ответам.
Посему, было решено облегчить жизни другим и прославить себя.

Кратко о главном

Для того чтоб Excel, либо spreadsheet (таблица Google) поняли что написанное — это формула, необходимо поставить знак "=" в строку формул (Рисунок 1).


Рисунок 1
Далее, начинаем писать формулу с клавиатуры либо выделяем мышкой те ячейки, с которыми мы собираемся работать.

В функциональных языках программирования есть возможность генерировать бесконечные последовательности значений (как правило чисел) и оперировать этими последовательностями. Реализуется это функцией, которая, не прерывая свою работу, генерирует значения одно за другим на основе своего внутреннего состояния.
Но, к сожалению, в обычных языках нет возможности «вернуть» значения в место вызова не выходя из функции. Один вызов — один результат.
Генераторы удобно было бы использовать совместно с возможностью Delphi по перечислению значений (GetEnumerator/MoveNext/GetCurrent). В этой статье мы создадим функцию-генератор (может даже бесконечную) и будем использовать ее с таким объектом для перечисления, чтобы всё работало прозрачно без необходимости вникать в реализацию.

Вчера мы рассказали о том, что объявляем конкурс на создание демонстрационного приложения на основе OpenCV для слежения за несколькими объектами, где в качестве приза будет поездка вместе с нашей командой на Шри-Ланку, а также предложение о работе в нашей компании.

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

Доброе утро всем, кто уже читает Хабрахабр!

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

Хотя в итоге библиотека HabraAuth, о которой пойдет речь в топике, не была использована, но она использует тот же принцип авторизации, что и на habra-adm.ru — пользователь вводит свой ник на Хабре, и с аккаунта почтового робота или с аккаунта разработчика ему приходит особая ссылка по Хабропочте, перейдя по которой он и подтверждает владение своим аккаунтом.

Для конечного пользователя при использовании HabraAuth авторизация выглядит и того проще: он вводит свой ник, жмет «Войти» и сервер перекидывает его в Хабропочту, где ему остается только нажать ссылку «Войти» еще раз.

Однажды, пролистывая популярный Q&A по математике (math.stackexchange.com), я обнаружил вопрос про расчет мультиномиальных коэффициентов и он меня заинтересовал. На заметку, для тех, кто не знает что это такое, существует статья в википедии. Итак, нужно вычислить следующее выражение:



Казалось, зачем на хабре выкладывать решение такой простой задачи? Ответ заключается в том, что самый простой наивный способ, заключающийся в перемножении факториала суммы с последующим делением его на произведение факториалов, не подойдет из-за того, что промежуточные вычисления выйдут за разрядную сетку типа uint и даже ulong, хотя результат может оказаться в пределах значений этих типов. Мне понравилась эта задача, и я сразу же сел за ее решение и придумал три способа. Остальные два способа я позаимствовал из других ответов. Итак, статья будет об описании и сравнении всех реализованных мною методов на C# под .NET.

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

Яндекс готов дать официальный старт новой «Интернет-математике». Регистрация участников продлится до 15 декабря, а прием решений – до 22 декабря. Сайт конкурса: switchdetect.yandex.ru.

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

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

Отчеты лучших команд будут представлены на семинаре WSCD 2013, который проводится совместно с конференцией WSDM 2013.

Удачи в конкурсе!

Приветствую вас, хабражители!

В продолжение поста «Аналог игры «Жизнь» — Evo» хотелось бы дать более подробное описание команд «языка генов», который используется в Evo, и поделиться своими соображениями по методам скрещивания особей в этой игре.

Приветствую вас, хабражители!

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

• жизнь развивается на поле 256*256 клеток;
• на поле могут размещаться объекты трёх типов: живность, пища(назовем её травой) и камень (препятствие);
• живность представляет собой фактически модифицированную машину Тьюринга, если точнее, то это больше похоже на Автомат с магазинной памятью, т.е. живность является «процессором», выполняющим свой «генетический» код;
• живность имеет возможность совершать определенные действия (двигаться, есть, размножаться (пока только клонированием, мутации будут со дня на день, скрещивание в перспективе)), отдавая соответствующие команды;
• наступив на траву, живность её вытаптывает;
• для поглощения еды надо дать команду «Ешь в этом направлении!», находясь в соседней клетке;
• живность имеет память, что позволяет строить циклы, условия и т.п., т.е. полная по Тьюрингу (поправьте меня, если не прав!), объем памяти неограничен;
• живность может складывать и вычитать значения в уме, разрядность ограничена одним байтом;
• существует возможность реализации генетических алгоритмов (пока не реализовано).

Кому интересны подробности, прошу под кат!

Пару недель назад, необходимо было освежить информацию в голове информацию по структурам данных и алгоритмам для собеседования. Первым делом полез на www.coursera.org, где хотел пробежаться по некоторым лекциям курса Алгоритмы, там же были две сводные таблички, которые в процессе изучения курса взял на заметку — отлично помогали запомнить сложность операций. Но, к моему удивлению, материалы пройденного курса стали недоступны. Быстрое гугление, в надежде, что кто-нибудь выложил лекции на торрентах, к сожалению, не дало результатов. В итоге, я нашел полную коллекцию слайдов по данному курсу. Спешу поделиться. Самое главное, что взял из этих слайдов, — это вышеупомянутые сводные таблички. Думаю многим пригодится.

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

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