Алгоритмы

Дискретная математика для WMS: алгоритм сжатия товаров в ячейках (часть 2)

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

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

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

Источник

Разбор квалификации чемпионата по программированию среди бэкенд-разработчиков

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

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

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

Поэтому я не буду публиковать разборы всех 24 задач. Вместо этого я разберу шесть задач одного из квалификационных вариантов: другие решаются похожим образом.

Источник

Используем данные на практике

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

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



Источник

Uber: Обзор главных алгоритмов управления платформой

1. Введение

Онлайн-платформы пассажироперевозок, такие как Uber, DiDi и Yandex возникли достаточно недавно, при этом они быстро достигли внушительных размеров и, несмотря на свой небольшой возраст, существенно видоизменили и дополнили систему городского транспорта. Технологии и теоретические модели, используемые этими платформами (или разрабатываемые для них), на данный момент являются областью активных исследований для широкого спектра специалистов научного сообщества: экономистов, математиков, программистов и инженеров.

В этой статье мы (как представители команды Uber Marketplace Optimization) коротко представим взгляд изнутри на главные рычаги управления эффективностью онлайн-платформ: алгоритмы, отвечающие за диспетчерские решения (matching), динамическое ценообразование (dynamic pricing), а также представим одну из новых концепций — динамическое время назначения автомобиля (dynamic waiting). Основываясь на реальном практическом опыте, мы покажем, что все три алгоритма играют важную роль для создания системы с высокой производительностью и низким временем ожидания заказов как для пассажиров, так и для водителей.

Представленное описание алгоритмов будет носить ознакомительных характер и намеренно лишено технической глубины и строгости. Заинтересовавшийся читатель приглашается изучить оригинал статьи (
Dynamic Pricing and Matching in Ride-Hailing Platforms —
N.Korolko, D.Woodard, C.Yan, H.Zhu — 2019), опубликованной исследователями из отдела Uber Marketplace, по мотивам которой этот краткий ознакомительный обзор и создан.

Источник

Обход дерева в несколько потоков

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

Что такое дерево, смотрим
Википедию.



Рис.1 Пример дерева.

Источник

Как устроен формат JPEG

Изображения формата JPEG встречаются повсюду в нашей цифровой жизни, но за этим покровом осведомлённости скрываются алгоритмы, устраняющие детали, не воспринимаемые человеческим глазом. В итоге получается высочайшее визуальное качество при наименьшем размере файла – но как конкретно всё это работает? Давайте посмотрим, чего именно не видят наши глаза!



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

Источник

Город без пробок

Глава первая.

Искусство разумно применять светофоры

Маленькое предисловие

Каждый день, оказываясь рядом с перекрестком, мы наблюдаем одну и ту же картину, как на зеленый свет машины мчатся вперед, а на красный — они скапливаются перед светофором в длинные очереди бесполезного ожидания. Но насколько привычное является одновременно необходимым и можно ли сделать так, чтобы в своем путешествии по городу автомобилистам почти не приходилось «стоять» на красный свет? Я думаю, многие из нас слышал о мифических «зеленых волнах». Попав в такую волну и поддерживая определенную скорость, автомобилист чудесным образом будет подъезжать к каждому перекрестку как раз в то время, когда светофор горит в его сторону зеленым светом. Довольно просто организовать распространение таких «волн» вдоль одной изолированной дороги, но совсем не очевидно, можно ли это сделать на дорогах всего города сразу.

Источник

Книга «Машинное обучение: алгоритмы для бизнеса»

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

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

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

Источник

Rekko Challenge — как занять 2-е место в конкурсе по созданию рекомендательных систем

Всем привет. Моя команда в Тинькофф занимается построением рекомендательных систем. Если вы довольны вашим ежемесячным кэшбэком, то это наших рук дело. Также мы построили рекомендательную систему спецпредложений от партнеров и занимаемся индивидуальными подборками Stories в приложении Tinkoff. А еще мы любим участвовать в соревнованиях по машинному обучению чтобы держать себя в тонусе.

На Boosters.pro в течении двух месяцев с 18 февраля по 18 апреля проходило соревнование по построению рекомендательной системы на реальных данных одного из крупнейших российских онлайн-кинотеатров Okko. Организаторы преследовали цель улучшить существующую рекомендательную систему. На данный момент соревнование доступно в режиме песочницы, в которой вы можете проверить свои подходы и отточить навыки в построении рекомендательных систем.

Источник

Всё, что вы знали о word2vec, неправда

Классическое объяснение word2vec как архитектуры Skip-gram с отрицательной выборкой в оригинальной научной статье и бесчисленных блог-постах выглядит так:

while(1) {
   1. vf = vector of focus word
   2. vc = vector of focus word
   3. train such that (vc . vf = 1)
   4. for(0 <= i <= negative samples):
           vneg = vector of word *not* in context
           train such that (vf . vneg = 0)
}

Действительно, если погуглить [word2vec skipgram], что мы видим:

• Страница Википедии, которая описывает алгоритм на высоком уровне
  
• Страница Tensorflow с тем же объяснением
  
• Блог Towards Data Science c описанием того же алгоритма, и список продолжается.

Но все эти реализации ошибочны.

Источник

Ричард Хэмминг: Глава 13. Теория информации

Мы это сделали!

«Цель этого курса — подготовить вас к вашему техническому будущему.»

Привет, Хабр. Помните офигенную статью
«Вы и ваша работа» (+219, 2588 в закладки, 429k прочтений)?

Так вот у Хэмминга (да, да, самоконтролирующиеся и самокорректирующиеся
коды Хэмминга) есть целая
книга, написанная по мотивам его лекций. Мы ее переводим, ведь мужик дело говорит.

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

За перевод спасибо Андрею Пахомову.

Теория Информации была разработана К. Э. Шенноном в конце 1940х годов. Руководство Лабораторий Белла настаивало, чтобы он назвал ее «Теория Связи», т.к. это намного более точное название. По очевидным причинам, название «Теория Информации» обладает значительно большим воздействием на публику, поэтому Шеннон выбрал именно его, и именно оно известно нам по сей день. Само название предполагает, что теория имеет дело с информацией, это и делает ее важной, поскольку мы все глубже проникаем в информационную эпоху. В этой главе я затрону несколько основных выводов из этой теории, приведу не строгие, а скорее интуитивно понятные доказательства некоторых отдельных положений этой теории, чтобы вы поняли, чем на самом деле является «Теория Информации», где вы можете ее применять, а где нет.

Источник

Вопросы приоритета: Найквист, Шеннон или Котельников?

О приоритете работ в области передачи информации.

Первопроходцем в этом современном вопросе является В.А.Котельников. Во время аспирантуры в МЭИ были опубликованы в 1932г. работы, одна из которых называлась «О пропускной способности „эфира“ и проволоки в электросвязи» и заявлена к докладу I Всесоюзного съезда по вопросам технической реконструкции дела связи и развития слаботочной промышленности. Съезд не состоялся. Была опубликована в 1933г. как материал к докладу (принят к печати в

ноябре 1932г.).

Источник

Анализ частоты появления цифр в хеше MD5

Все мы знаем, как выглядит хеш, но задавались ли вы вопросом, как часто встречается тот или иной символ в хеше? Я задался. И решил проверить. Набросал скрипт на Python для подсчета, и вот что из этого вышло.

Источник

Соревнование по программированию Kotlin Heroes

JetBrains начала сотрудничество с
Codeforces в продвижении языка
Kotlin среди любителей спортивного программирования. Codeforces предоставляет Kotlin-разработчикам платформу, на которой можно посостязаться в алгоритмическом программировании и отточить свое мастерство. Вместе с Codeforces мы запускаем серию соревнований под названием
Kotlin Heroes.



Источник

О странном методе экономии места на жестком диске

Очередной пользователь хочет записать на жесткий диск новый кусок данных, но ему не хватает свободного места для этого. Удалять тоже ничего не хочется, так как «все очень важное и нужное». И что нам с ним делать?

Такая проблема встает ни у него одного. На наших жестких дисках покоятся терабайты информации, и это количество не стремится уменьшаться. Но насколько она уникальна? В конце-концов, ведь все файлы это лишь наборы бит определенной длины и, скорее всего, новая не сильно отличается от той, что уже хранится.

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

TL;DR — вторая попытка рассказать о странном методе оптимизации данных с помощью JPEG-файлов, теперь в более понятной форме.

Источник