Алгоритмы *

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

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

Пару лет назад на Хабре проскакивало две статьи, в которых упоминался интересный алгоритм. Статьи, правда, были написаны нечитабильно. В стилистике «новости»(1, 2), но ссылка на сайт присутствовала, подробно можно было разобраться на месте (алгоритм за авторством MIT). А там была магия. Абсолютно волшебный алгоритм, позволяющий увидеть незримое. Оба автора на Хабре этого не заметили и сфокусировались на том, что алгоритм позволял увидеть пульс. Пропустив самое главное.



Алгоритм позволял усиливать движения, невидные глазу, показать вещи, которые никто никогда не видел живьём. Видео чуть выше – презентация c сайта MIT второй части алгоритма. Микросаккады, которые приведены начиная с 29ой секунды, раньше наблюдались только как отражения установленных на зрачках зеркалах. А тут они видны глазами.
Пару недель назад я опять натолкнулся на те статьи. Мне сразу стало любопытно: а что народ сделал за эти два года готового? Но… Пустота. Это определило развлечение на следующие полторы недели. Хочу сделать такой же алгоритм и разобраться, что с ним можно сделать и почему его до сих пор нет в каждом смартфоне, как минимум для измерения пульса.

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

На Хабре много статей по этой теме, но они не рассматривают практических задач. Я попытаюсь исправить это досадное недоразумение. Формула Байеса применяется для фильтрации спама, в рекомендательных сервисах и в рейтингах. Без нее значительное число алгоритмов нечеткого поиска было бы невозможно. Кроме того, это формула явилась причиной холивара среди математиков.

1 августа в офисе Яндекса, открывшемся недавно в Берлине, состоялся финал нашего чемпионата по программированию. И его победителем снова стал известный всем, кто интересуется спортивным программированием, Геннадий Короткевич.

Задания для Алгоритма готовила международная команда. В нее вошли программисты из России, Беларуси, Польши и США. Это специалисты МГУ имени М.В. Ломоносова, Университета Карнеги-Меллон, сотрудники Яндекса и Google. В Яндексе задачи составляли разработчики минского и киевского офиса, а потом проверяли их на своих коллегах. Один из составителей в прошлом году сам был финалистом Алгоритма. Специально для Хабрахабра мы разобрали с авторами все задачи. Кстати, несмотря на то, что соревнование завершено, вы можете попробовать себя в вирутальном контесте.



На победу претендовали многие финалисты. Среди них были победители и призеры АСМ ICPC и TopCoder Open, разработчики Google и Facebook. В финальном раунде сражались призёры Алгоритма-2013 Евгений Капун и Ши Бисюнь, чемпион АСМ ICPC Михаил Кевер, а также один из самых титулованных спортивных программистов мира Пётр Митричев. В этом году побороться за приз решил также Макото Соэдзимо — составитель заданий для Алгоритма-2013 и администратор TopCoder Open.

Борьба за первое место разгорелась между Геннадием Короткевичем и Хосакой Кадзухиро из Токийского университета. Лучший результат — четыре задачи при 66 минутах штрафного времени — показал Короткевич, подтвердив титул чемпиона. Кадзухиро решил столько же задач, но набрал больше штрафного времени (90 минут) и занял второе место. Третье место завоевал Ван Циньши из университета Цинхуа: он решил четыре задачи при 125 минутах штрафа.

Привет, Хабр! Решил побаловаться графоманством и поделиться результатом развлечения прошедших выходных (только эти выходные прошли давно и статья писалась гораздо дольше, чем развлечение. Как говорится, делу время — потехе час).

Я расскажу про так называемые алгоритмы расщепления (в частности, про DPLL-алгоритм), про теорему и числа Ван-дер-Вардена, а в заключение статьи мы напишем свой собственный алгоритм расщепления и за полчаса вычислений докажем, что число w(2; 5) равно 178 (первооткрывателям в 1978 году на это потребовалось более 8 дней вычислений).

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

По крайней мере, таков план.

Но как же именно вам, как разработчику игры, отрендерить такой эффект?

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

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

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

Доброго времени суток.

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

• Подсветка синтаксиса
• Использование отступов
• Вертикальное выравнивание

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

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

Помните эти задачи «при помощи циркуля и линейки постройте...»? Вот здесь можно поупражняться в таких построениях.

20 уровней построены по принципу «от простого к сложному». Предыдущие достижения (к примеру, умение строить равносторонний треугольник) на следующих уровнях доступны уже в виде инструментов.

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

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

Привет, Хабр! Мой предыдущий пост, посвященный программированию графики, был благодушно воспринят сообществом, и я отважился ещё на один. Сегодня я расскажу об алгоритме рендеринга теней Parallel-Split Shadow Mapping (PSSM), с которым я впервые столкнулся, когда возникла рабочая необходимость отображать тени на большом расстоянии от игрока. Тогда я был ограничен набором возможностей Direct3D 10, сейчас я реализовал алгоритм на Direct3D 11 и OpenGL 4.3. Подробнее алгоритм PSSM описывается в GPU Gems 3 как с математической точки зрения, так и с точки зрения реализации на Direct3D 9 и 10. За подробностями прошу под кат.

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

Настало время подробно рассказать, как работает наша реализация алгоритма распознавания номеров: что оказалось удачным решением, что работало весьма скверно. И просто отчитаться перед Хабра-пользователями — ведь вы с помощью Android приложения Recognitor помогли нам набрать приличного размера базу снимков номеров, снятых совершенно непредвзято, без объяснения как снимать, а как нет. А база снимков при разработке алгоритмов распознавания самое важное!

Сделала это программа, которая убедила людей, что является 13-летним мальчиком из украинской Одессы.



Согласно условиям теста Тьюринга, он считается пройденным, если программе удастся убедить в своей человечности хотя бы 30% судей в процессе 5-минутного текстового общения.

Сегодня в App Store вышло обновленное приложение Яндекс.Перевода для iOS. Теперь в нем есть возможность полнотекстового перевода в офлайн-режиме. Машинный перевод прошел путь от мейнфреймов, занимавших целые комнаты и этажи, до мобильных устройств, помещающихся в карман. Сегодня полнотекстовый статистический машинный перевод, требовавший ранее огромных ресурсов, стал доступен любому пользователю мобильного устройства – даже без подключения к сети. Люди давно мечтают о «вавилонской рыбке» – универсальном компактном переводчике, который всегда можно взять с собой. И, кажется, мечта эта постепенно начинает сбываться. Мы решили, воспользовавшись подходящим случаем, подготовить небольшой экскурс в историю машинного перевода и рассказать о том, как развивалась эта интереснейшая область на стыке лингвистики, математики и информатики.



«Это все делает машина», «Электронный мозг переводит с русского на английский», «Робот-билингва» – такие газетные заголовки увидели читатели ликующей прессы 8 января 1954 года. А днем ранее, 7 января, научный компьютер IBM 701 принял участие в знаменитом Джорджтаунском эксперименте, переведя около шестидесяти русских фраз на английский. «Семьсот-первый» использовал словарь из 250 слов и шесть синтаксических правил. И, конечно же, очень тщательно подобранный набор предложений, на которых проводилось тестирование. Вышло настолько убедительно, что восторженные журналисты со ссылками на ученых заявляли о том, что через несколько лет машинный перевод почти полностью заменит классический «ручной».

Сегодня речь пойдет о том, какую роль в Интернет-поиске играет лингвистика. Чтобы поместить это в контекст, начну с того, как связаны между собой лингвисты и большая поисковая компания, например, «Яндекс» (более 5000 чел.), «Гугл» (более 50 000 чел.), «Байду» (более 20 000). От трети до половины этих людей работают непосредственно на поиск. Лингвисты внутри этих компаний примерно поровну делятся между поиском и остальными направлениями — новостями, переводом и т.д.



Я сегодня буду говорить о той части лингвистов, которая пересекается с поиском. На диаграмме она обозначена штриховкой. Возможно, в Google и других компаниях все устроено немножко иначе, чем у нас, тем не менее, общая картина примерно такая: лингвистика является важным, но не определяющим направлением работы поисковых компаний. Еще одно важное дополнение: в жизни, конечно, границы расплывчаты – невозможно сказать, например, где заканчивается лингвистика и начинается машинное обучение. Каждый лингвист, работающий в поиске, немного занимается программированием, немного — машинным обучением.

Реализацию порядко-независимой прозрачности (order-independent transparency, OIT), наверное, можно считать классической задачей программирования компьютерной графики. По сути, алгоритмы OIT решают одну простую прикладную задачу – как нарисовать набор полупрозрачных объектов так, чтобы не беспокоиться о порядке их рисования. Правила смешивания цветов при рендеринге требуют он нас, чтобы полупрозрачные объекты рисовались в порядке от дальнего к ближнему, однако этого сложно добиться в случае протяженных объектов или объектов сложной формы. Реализация одного из самых современных алгоритмов, OIT с использованием связных списков, была представлена AMD для Direct3D 11 еще в 2010 году. Скажу откровенно, производительность алгоритма на широко доступных графических картах тех лет не произвела на меня должного впечатления. Прошло 4 года, я откопал презентацию AMD и решил реализовать алгоритм не только на Direct3D 11, но и на OpenGL 4.3. Тех, кому интересно, что получилось из этой затеи, прошу под кат.

Реми Кулом (слева) с компьютерной программой Crazy Stone против гроссмейстера Норимото Ёды

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

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

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

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



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

Что такое «Инверсная кинематика»?

Задачей инверсной кинематики является поиск такого набора конфигураций сочленений, который обеспечил бы максимально мягкое, быстрое и точное движение к заданным точкам. Однако, множество существующих ныне методов страдают от таких недостатков как высокая вычислительная сложность и неестественность результирующих поз. В этой статье описан новый (вероятно, на момент написания статьи — 2010 г.) эвристический метод под названием «Метод прямого и обратного следования» ( Forward and Backward Reaching Inverse Kinematics, далее просто FABRIK),
FABRIK избегает использования вращений и матриц в пользу непосредственного получения точки на прямой. Благораря этому, дело обходится всего несколькими итерациями, имеет низкую стоимость вычислений и визуально естественную позу в результате. FABRIK так-же без проблем справляется с наложением ограничений а так-же использованием нескольких цепей и/или конечных точек. Именно об этом методе этот пост.