Алгоритмы

Долгожданный шаг в сторону сложно структурированных документов (+видео)

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

Источник

Я получил от Кнута чек на 0x$3,00

Дональд Кнут — учёный в области информатики, который настолько заботится о правильности своих книг, что предлагает
один шестнадцатеричный доллар ($2,56, 0x$1,00) за любую найденную «ошибку», где ошибкой считается всё, что «технически, исторически, типографически или политически неправильно». Я очень хотел получить чек от Кнута, поэтому решил поискать ошибки в его выдающемся труде
«Искусство программирования» (TAOCP). Удалось найти три. Верный слову, Кнут прислал чек на
0x$3,00.



Как видите, это не настоящий чек. Раньше Кнут отправлял реальные чеки, но прекратил в 2008 году из-за
безудержного мошенничества. Теперь он рассылает «личные депозитные сертификаты» в
банке Сан-Серрифф (BoSS). Он говорит, что готов выслать реальные деньги в случае необходимости, но, похоже, это слишком хлопотно.

Источник

MIMO spatial diversity: Аламоути, DET и прочее пространственное разнесение

Чтобы передать сообщение от базовой станции мобильному устройству (и наоборот), электромагнитной волне приходится преодолевать значительное количество препон: отражения, преломления, рассеивания, затенения, доплеровские смещения частот и так далее. Во-первых, все эти воздействия принято называть мультипликативными (от англ. multiplication — умножение) — по математической модели таких воздействий. А, во-вторых, можно собрать под общим термином замирания (fading).

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

И некоторые решения нашли широкое распространение. Скажем больше: почти все из них, так или иначе, связаны с понятием разнесения (diversity).

Источник

Эволюция архитектуры торгово-клиринговой системы Московской биржи. Часть 2

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

Источник

Как нужно решать задачу коммивояжёра? Часть третья

Начало

Предыдущая

Наиболее сложными типами графов для алгоритмов группы Lin & Kernighan (а, значит, и для нашего тоже) являются те, у которых даже в оптимальном туре встречаются очень большие (относительно средней) длины рёбер. Про один из таких графов (fl3795) мы уже успели «поплакаться в жилетку». Как оказалось, проблема эта настолько серьёзная, что тот самый DIMACS TSP Challenge (Center for Discrete Mathematics and Theoretical Computer Science) содержит целую серию подобных графов

Источник

Долгожданный шаг в сторону сложно структурированных документов (+видео)

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

Источник

Нахождение объектов на картинках

Мы занимаемся закупкой трафика из Adwords (рекламная площадка от Google). Одна из регулярных задач в этой области – создание новых баннеров. Тесты показывают, что баннеры теряют эффективность с течением времени, так как пользователи привыкают к баннеру; меняются сезоны и тренды. Кроме того, у нас есть цель захватить разные ниши аудитории, а узко таргетированные баннеры работают лучше.

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

Это выглядит как задача, которую несложно автоматизировать. Для этого достаточно сделать программу, которая будет накладывать на болванку баннера локализованную цену на «ценник» и call to action (фразу типа «купить сейчас») на кнопку. Если печать текста на картинке реализовать достаточно просто, то определение положения, куда нужно его поставить — не всегда тривиально. Перчинки добавляет то, что кнопка бывает разных цветов, и немного отличается по форме.

Этому и посвящена статья: как найти указанный объект на картинке? Будут разобраны популярные методы; приведены области применения, особенности, плюсы и минусы. Приведенные методы можно применять и для других целей: разработки программ для камер слежения, автоматизации тестирования UI, и подобных. Описанные трудности можно встретить и в других задачах, а использованные приёмы использовать и для других целей. Например, Canny Edge Detector часто используется для предобработки изображений, а количество ключевых точек (keypoints) можно использовать для оценки визуальной “сложности” изображения.

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

Источник

Краткий гайд по созданию оракулов, богов из машины и ошибкам второго рода

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

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



Что это такое? В двух словах — «человек ищет подтверждение своей модели, а не её опровержение». Единственный шанс объяснить лучше, это примеры-примеры-примеры и опыт. Лишь так можно развить чувство что «что-то тут не так».

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

Источник

Как волонтёры со всего мира создают прямой эфир ICPC-2019

Меня зовут Лида Перовская, я работаю в Яндексе, а ещё с 2015 года помогаю организовывать прямой эфир International Collegiate Programming Contest. ICPC — студенческий чемпионат мира по программированию — проводится ежегодно с 1970-х. Это чуть ли не единственная олимпиада подобного уровня, которое развивается благодаря усилиям сотен волонтёров со всего мира. Сегодня я расскажу читателям Хабра о том, как устроена моя работа на ICPC изнутри. А ещё приглашаю посмотреть
трансляцию мероприятия (4-го апреля в 12:00 по московскому времени) и попробовать собственные силы в решении задачек одновременно с участниками.

Для нас — волонтёров — важно, чтобы мероприятие было интересным и полезным и для участников, и для зрителей. Но сделать это непросто. На один только финал заявлено 135 команд из 110 стран, в каждой команде по три человека, и все они участвуют одновременно! Кого, когда и как пускать в эфир? Какой код показывать? Как комментировать, чтобы это было полезно?

Источник

Прямая трансляция и расписание конференции SmartMail Conf: Machine Learning

Друзья, осталось всего три дня до SmartMail Conf — нашей первой конференции по машинному обучению. Программа выступления чуть более чем полностью состоит из докладов наших коллег из Почты Mail.ru. Они расскажут много интересного про обработку естественных языков, про компьютерное зрение и обучение моделей борьбе со спамом. Причём расскажут не в отрыве от реальности, а на практических примерах использования в наших собственных проектах и технологиях.

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

Источник

Работаем с нейросетями: чек-лист для отладки

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

Эта статья посвящена алгоритму отладки ваших нейронных сетей.

Источник

Разбираемся в протоколе консенсуса Stellar

Протокол консенсуса Stellar впервые описан в
научной статье Дэвида Мазьера в 2015 году. Это «федеративная система византийского соглашения», которая позволяет децентрализованным вычислительным сетям без лидеров эффективно достигать консенсуса по какому-либо решению. Платёжная сеть Stellar использует Stellar Consensus Protocol (SCP) для ведения согласованной истории транзакций, которую видят все участники.

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

Источник

Автороцентричное ранжирование. Доклад Яндекса о поиске релевантной аудитории для авторов Дзена

Важнее всего для сервиса Яндекс.Дзен — развивать и поддерживать платформу, которая соединяет аудитории с авторами. Чтобы быть привлекательной платформой для хороших авторов, Дзен должен уметь находить релевантную аудиторию для каналов, пишущих на любые темы, в том числе на самые узкие. Руководитель группы счастья авторов Борис Шарчилев рассказал про автороцентричное ранжирование, которое подбирает для авторов наиболее релевантных пользователей. Из доклада можно узнать о том, чем такой подход отличается от подбора релевантных айтемов — более популярного в рекомендательных системах.

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

Источник

Подсчет конечных нулей факториала числа в любой системе счисления

Как я могу посчитать количество конечных нулей факториала числа в определенной системе счисления?

Давайте рассмотрим случай, когда мы находимся в 10-й системе счисления, а затем посмотрим, как мы можем обобщить это в универсальное решение. Нам дано число N и для его факториала нужно найти количество конечных нулей. Решение будет довольно простым — сумма:

Math.floor(N/5) + Math.floor(N/25) + Math.floor(N/125) + Math.floor(N/625) + ...

Её мы можем обобщить в такую формулу:

Почему 5? Это просто. Конечный ноль получается только тогда, когда в составе факториала число имеет 10. Таким образом, посчитав количество десяток в факториале, мы узнаем количество конечных нулей.

Источник

XXH3: новый рекордсмен по скорости хеширования

Бенчмарки сделаны в программе SMHasher на Core 2 Duo 3,0 ГГц

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

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

Источник