Обновить
238.79

Алгоритмы *

Все об алгоритмах

Сначала показывать
Порог рейтинга
Уровень сложности

Deep Learning — не только котики на мобилках или как мы производим дефектовку тележек локомотивов

Время на прочтение5 мин
Охват и читатели25K

Буквально пару дней назад компания Aurorai передала в опытную эксплуатация систему распознавания дефектов и контроля состояния тележек для локомотивов Ермак. Задача нетривиальная и очень интересная, первым этапом которой было предложено оценить состояние тормозных колодок и ширины бандажа. Нам удалось решить задачу с точность до 1мм при скорости локоматива до 30 км/ч! Хочу отметить, что благодаря специфики можно было использовать “TTA (test-time augmentation)” – яркий пример kaggle-style хака из соревнований, который плохо ложится на прод и семантическую сегментацию на базе se_resnext50 encoder, которая даёт поразительный по точности результат в предсказании маски.

Мат слоном и конём. Метод TWIX

Время на прочтение13 мин
Охват и читатели82K

Ушенина (на фото слева, играет белыми) — Гиря (на фото справа, играет чёрными). Ничья.
Гран-При среди женщин, 4-й тур
6 мая 2013 года, Женева


В 2013 ходу российский гроссмейстер Ольга Гиря в безнадёжной позиции, вместо того, чтобы сдаться, применила нестандартное читерство.

Имея на две фигуры меньше, она нашла остроумный способ добиться ничьей с чемпионкой мира (на тот момент) Анной Ушениной. Ольга просто разменяла всё, что только можно и свела партию к эндшпилю «король + слон + конь VS король». Украинская шахматистка полсотни ходов безуспешно пыталась заматовать вражеского короля, после чего результат партии был признан ничейным.

Обидная ничья существенно повлияла на результат Ушениной в турнире. Она заняла 5-6 место, а выигрыш позволил бы разделить бронзу (3-5 место).
А если бы знала метод TWIX - всё было бы иначе

Фракталы в иррациональных числах

Время на прочтение9 мин
Охват и читатели20K
Статья является продолжением моей первой статьи «Фракталы в простых числах».

Следующая статья: Фракталы в иррациональных числах. Часть 2.



В предыдущей статье мы научились рисовать самоподобные паттерны с помощью взаимно простых чисел. В этой статье покажу фрактальную природу числа $\sqrt{2}$.
Без предисловия. Под кат.
Читать дальше →

Знакомство с Neural ODE

Время на прочтение20 мин
Охват и читатели43K

Neural Ordinary Differential Equations


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

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

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

На последней NIPS-конференции была представлена одна очень интересная статья, которая может помочь решить эту проблему. Авторы предлагают подход, который они назвали Нейронные Обыкновенные Дифференциальные Уравнения (Neural ODE).

Здесь я постарался воспроизвести и кратко изложить результаты этой статьи, чтобы сделать знакомство с ее идеей чуть более простым. Мне кажется, что эта новая архитектура вполне может найти место в стандартном инструментарии дата-сайентиста наряду со сверточными и рекуррентными сетями.


Читать дальше →

Жизнь на частицах

Время на прочтение4 мин
Охват и читатели73K
Всем привет! Сегодня я расскажу о своих экспериментах с системами частиц. Основной целью было нахождение простых правил, которые бы порождали интересное поведение.

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

Под катом много мегабайт гифок.

Читать дальше →

Неожиданная эффективность квазислучайных последовательностей

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


Рисунок 1. Сравнение различных квазислучайных последовательностей с низким расхождением. Заметьте, что предлагаемая мной $R$-последовательность создаёт более равномерно распределённые точки, чем все остальные методы. Более того, все остальные методы требуют тщательного подбора базовых параметров, а в случае неправильного подбора приводят к вырожденности (например справа вверху)

Рассматриваемые в статье темы

  • Последовательности с низким расхождением в одном измерении
  • Методы с низким расхождением в двух измерениях
  • Расстояние упаковки
  • Множества с многоклассовым низким расхождением
  • Квазислучайные последовательности на поверхности сферы
  • Квазипериодический тайлинг плоскости
  • Маски дизеринга в компьютерной графике

Какое-то время назад этот пост был выложен на главной странице Hacker News. Можете прочитать там его обсуждение.

Разработчик SearchFace о возможностях алгоритма

Время на прочтение2 мин
Охват и читатели108K
Всем привет, я один из разработчиков сервиса SearchFace и готов поговорить о нём в комментариях.



Из-за шумихи с иском ВК на второй план отошло то важное, ради чего мы запустили сервис — чтобы протестировать возможности поиска. А раз уж теперь сервис доступен широкой публике, хочется продемонстрировать всем, на что способны наши алгоритмы распознавания.
Читать дальше →

Как превратить спутниковые снимки в карты. Компьютерное зрение в Яндексе

Время на прочтение10 мин
Охват и читатели37K
Один из главных источников данных для сервиса Яндекс.Карты — спутниковые снимки. Чтобы с картой было удобно работать, на снимках многоугольниками размечаются объекты: леса, водоёмы, улицы, дома и т. п. Обычно разметкой занимаются специалисты-картографы. Мы решили помочь им и научить компьютер добавлять многоугольники домов без участия людей.

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

Читать дальше →

Введение в программирование: простой 3D-шутер с нуля за выходные, часть 2

Время на прочтение4 мин
Охват и читатели39K
Продолжаем разговор про 3Д шутер за выходные. Если что, то напоминаю, что это вторая половина:


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


К сожалению, большинство студентов выбирает простые игры типа 2Д платформеров. Я пишу эту статью для того, чтобы показать, что создание иллюзии трёхмерного мира ничуть не сложнее клонирования марио броз.
Читать дальше →

Введение в программирование: простой 3D-шутер с нуля за выходные, часть 1

Время на прочтение8 мин
Охват и читатели87K
Этот текст предназначен для тех, кто только осваивает программирование. Основная идея в том, чтобы показать этап за этапом, как можно самостоятельно сделать игру à la Wolfenstein 3D. Внимание, я совершенно не собираюсь соревноваться с Кармаком, он гений и его код прекрасен. Я же целюсь совсем в другое место: я использую огромную вычислительную мощность современных компьютеров для того, чтобы студенты могли создавать забавные проекты за несколько дней, не погрязая в дебрях оптимизации. Я специально пишу медленный код, так как он существенно короче и просто понятнее. Кармак пишет 0x5f3759df, я же пишу 1/sqrt(x). Мы преследуем разные цели.

Я убеждён, что хороший программист получается только из того, кто кодит дома в своё удовольствие, а не только просиживает штаны на парах в университете. В нашем университете программистов учат на бесконечной череде всяких библиотечных каталогов и прочей скукоте. Брр. Моя цель — показать примеры проектов, которые интересно программировать. Это замкнутый круг: если интересно делать проект, то человек проводит над ним немало времени, набирается опыта, и видит вокруг ещё больше интересного (оно же стало доступнее!), и снова погружается в новый проект. Это называется проектное обучение, вокруг сплошной профит.

Простыня получилась длинная, поэтому я разбил текст на две части:


Выполнение кода из моего репозитория выглядит вот так:


Это не законченная игра, но только заготовка для студентов. Пример законченной игры, написанной двумя первокурсниками, смотрите во второй части.
Читать дальше →

Как устроен штрихкод?

Время на прочтение7 мин
Охват и читатели118K
Привет, Хабр!

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

Как устроен баркод, и что закодировано на этой картинке?



Попробуем разобраться, заодно напишем декодер таких кодов.
Читать дальше →

Пишем XGBoost с нуля — часть 2: градиентный бустинг

Время на прочтение13 мин
Охват и читатели31K

Всем привет!

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

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


Итак, поехали!

Как мы распределяем заказы между водителями в Яндекс.Такси

Время на прочтение5 мин
Охват и читатели190K
image

Одна из главных задач в Яндекс.Такси — как сделать так, чтобы к пользователю быстро приезжала машина, а у водителя сокращалось время «холостого пробега» (то есть время, когда он на линии без пассажира). Казалось бы, всё просто: пользователь выбирает тариф, указывает дополнительные пожелания (детское кресло, например). Остаётся отфильтровать водителей на линии по этим критериям, выбрать ближайшего и предложить ему заказ. Однако всё так просто только на первый взгляд.

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

Ближайшие события

Пишем XGBoost с нуля — часть 1: деревья решений

Время на прочтение13 мин
Охват и читатели38K


Привет, Хабр!

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

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


Читать дальше →

Реверс-инжиниринг. История. Моя

Время на прочтение9 мин
Охват и читатели55K


Всем привет,


На этот раз статья будет не технической (хотя в ней и будут попадаться какие-то технические термины/моменты), а скорее автобиографической, если так можно выразиться. Эта статья о том, как я докатился до такой жизни пришёл в реверс-инжиниринг, что читал, чем интересовался, где применял, и т.д. И, я почему-то уверен, что моя история будет иметь множество отличий от твоей. Поехали…

Читать дальше →

«Современный» C++: сеанс плача с причитаниями

Время на прочтение18 мин
Охват и читатели65K

Здесь будет длиннющая стена текста, с типа случайными мыслями. Основные идеи:


  1. В C++ очень важно время компиляции,
  2. Производительность сборки без оптимизаций тоже важна,
  3. Когнитивная нагрузка ещё важней. Вот по этому пункту особо распространяться не буду, но если язык программирования заставляет меня чувствовать себя тупым, вряд ли я его буду использовать или тем более — любить. C++ делает это со мной постоянно.

Блогпост «Standard Ranges» Эрика Ниблера, посвященный ренжам в C++20, недавно облетел всю твиттерную вселенную, сопровождаясь кучей не очень лестных комментариев (это ещё мягко сказано!) о состоянии современного C++.



Даже я внёс свою лепту (ссылка):


Этот пример пифагоровых троек на ренжах C++20, по моему, выглядит чудовищно. И да, я понимаю, что ренжи могут быть полезны, проекции могут быть полезны и так далее. Тем не менее, пример жуткий. Зачем кому-то может понадобиться такое?

Давайте подробно разберём всё это под катом.

Читать дальше →

Коллапс волновой функции: алгоритм, вдохновлённый квантовой механикой

Время на прочтение11 мин
Охват и читатели36K
image

Алгоритм Wave Function Collapse генерирует битовые изображения, локально подобные входному битовому изображению.

Локальное подобие означает, что

  • (C1) Каждый паттерн NxN пикселей в выходных данных должен хотя бы раз встречаться во входных данных.
  • (Слабое условие C2) Распределение паттернов NxN во входных данных должно быть подобным распределению паттернов NxN в значительно большом количестве наборов выходных данных. Другими словами, вероятность встречи определённого паттерна в выходных данных должна быть близка к плотности таких паттернов во входных данных.
Читать дальше →

Эволюция переключения контекста x86 в Linux

Время на прочтение43 мин
Охват и читатели28K


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

Задача: проследить, как изменялось переключение контекста в ядре Linux от первой (0.01) до последней версии LTS (4.14.67), с особым акцентом на первую и последнюю версии.
Читать дальше →

Выигрышная стратегия Гомоку – 35 ходов

Время на прочтение11 мин
Охват и читатели44K
При игре по стандартным правилам Гомоку для выигрыша черным требуется не более 35 ходов. В статье Вашему вниманию представлена полная выигрышная стратегия и соответствующий алгоритм игры.

Демонстрация полного решения – здесь – можно поиграть и найти самые длинные варианты. Программа всегда выигрывает и затрачивает на это не более 35 ходов. Исходные тексты приложения, само решение и примеры партий в конце статьи.
Читать дальше →

Внутри Quake: определение видимых поверхностей

Время на прочтение17 мин
Охват и читатели35K
image

Ветеран программирования трёхмерной графики Майкл Абраш на примере разработки первого Quake рассказывает о необходимости творческого мышления в программировании.

Много лет назад я работал в теперь уже не существующей компании-производителе видеоадаптеров Video Seven. Там я помогал в разработке клона VGA. Мой коллега Том Уилсон, долгие месяцы круглосуточно работавший над разработкой VGA-чипа Video Seven, стремился сделать VGA как можно более быстрым, и был уверен, что его производительность оптимизирована почти по максимуму. Однако когда Том уже вносил в конструкцию чипа последние штрихи, до нас донеслись слухи, что наш конкурент Paradise достиг ещё большей производительности в своём разрабатываемом клоне, добавив в него FIFO.

На этом слухи заканчивались — мы не знали, ни что это за FIFO, ни насколько он помог, ничего другого. Тем не менее, Том, обычно приветливый и расслабленный человек, превратился в активного, одержимого фанатика со слишком большим процентом кофеина в крови. Исходя из этих крупиц информации, он пытался выяснить, что же удалось сделать Paradise. В конце концов он пришёл к выводу, что Paradise вероятно вставил FIFO-буфер записи между системной шиной и VGA, чтобы когда ЦП выполнял запись в видеопамять, записываемые данные сразу же попадали в FIFO, и это позволяло ЦП продолжать обработку, а не простаивать каждый раз, когда он выполнял запись в память дисплея.

У Тома не было ни логических элементов, ни достаточно времени на реализацию полного FIFO, но ему удалось реализовать FIFO глубиной в одну операцию, что позволяло процессору обгонять VGA-чип на одну операцию записи. Том не был уверен, что это даст хорошие результаты, но это было единственное, что он смог сделать, поэтому он реализовал эту систему и передал чип в производство.
Читать дальше →

Вклад авторов