Алгоритмы *

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

Меня зовут Паймеров Владимир, я Data Scientist и участник профессионального сообщества NTA.

Компьютерное зрение (computer vision, CV) — активно развивающаяся научная область,
связанная с анализом изображений и видео. В последнее время данному направлению
уделяется большое внимание, так как CV позволяет решать множество задач, таких как
детекцию объектов, классификацию изображений, распознавание лиц и т. д., которые
в свою очередь применяются в разных сферах жизни от мобильных приложений для
наложения масок на лицо во время звонка до построения систем безопасности,
поиска преступников и мошенников. Сейчас есть инструменты, позволяющие
хранить большой объем данных и обрабатывать изображения, поэтому появилось
множество инструментов для решения различных задач. Об одной из таких задач
будет рассказано в данном посте.

Сейчас я интервьирую кандидатов которые приходят на позиции в RTL design / проектировщики микросхем на уровне регистровых передач. Но 5 лет назад я интервьировал студентов и других инженеров на позиции в DV / Design Verification / верификаторы блоков микросхем.

Моим стандартным вопросом было написать маркером на доске псевдокод для упрощенного драйвера модели шины (Bus Functional Model - BFM) для протокола AXI. На этом вопросе у ~80% кандидатов наступала агония - они как ужи на сковородке пытались натянуть сову на глобус - приспособить решение для последовательной шины а-ля APB, которое они прочитали в каком-нибудь тьюториале - к шине AXI, которая во-первых конвейерная, а во-вторых, допускает внеочередные ответы на запросы чтения с разными идентификаторами.

Аналогия из другой области: представьте, что кто-то пытается обходить дерево или решить "ханойские башни" - не зная концепций рекурсии и стека. Или написать GUI интерфейс, не зная концепции cобытийно-ориентированной архитектуры.

Когда‑то давно ко мне пришла идея реализовать алгоритм основанный на цепочках символов. Этот алгоритм выделяет в тексте несколько последовательностей символов, и таким образом производит его анализ. Этот алгоритм в какой‑то мере похож на метод построения N‑грамной модели, разница лишь в том, что он строит последовательности символов переменной длины. Как это делается я расскажу немного ниже. В результате алгоритм мог сравнивать тексты друг с другом и находить степень похожести между ними. Я приспособил его для того, чтобы отсеивать ранее известные тексты, и выбирать только те, которые обладают наибольшей уникальностью на момент анализа. Результат работы алгоритма можно посмотреть здесь: http://luksian.ru

Расскажу вкратце суть идеи. Например, у нас есть текст ABCABD. Из этого текста можно выделить следующие последовательности из двух символов: AB, BC, CA, AB, BD. Здесь видно что последовательность AB встречается два раза, а за этой последовательностью в каждом случае следуют разные символы. Такая ситуация считается конфликтом который необходимо разрешить. Для этого создаются новые последовательности символов: ABC и ABD. Последовательности из этих трех символов в тексте встречаются по одному разу, поэтому конфликт считается разрешенным, больше неоднозначностей в тексте не наблюдается. Разумеется, в обычном тексте написанном на простом человеческом языке для разрешения конфликтов иногда может потребоваться построить гораздо более длинные цепочки символов чтобы можно было найти между ними разницу. И вот недавно я вспомнил об этом алгоритме и попробовал его исследовать поподробнее.

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

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

Меня зовут Владимир Точилин, я работаю в группе развития рекламных продуктов и стабильности. Вместе со своим коллегой, Александром Самусенко, я расскажу, как мы создали новый инструмент realtime-детекции разладок в проде рекламных технологий. Мы работаем с системой, где на отдельные кластеры нагрузка превышает 1000000 RPS. 

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

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

Одним из интересных (на мой субъективный взгляд) эзолэнгов является FRACTRAN, концепция которого была предложена Джоном Конвеем (известным в первую очередь конечно же благодаря игре «Жизнь»).

В этой статье я расскажу про клёвую математику, лежащую в основе этого эзотерического языка программирования, разберу несколько простых программ на нём, и, наконец, покажу связь FRACTRAN'а с гипотезой Коллатца. Статья во многом является вольным пересказом соответствующей главы книги Strange Code: Esoteric Languages That Make Programming Fun Again (которую я бы рекомендовал всем, кто хочет взглянуть на программирование под другим углом).

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

С вами Максим Алёшин, Data Scientist и участник профессионального сообщества NTA.

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

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

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

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

Найдутся ли среди новых методов конкуренты старому доброму SIFT?

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

В сфере грузоподъемной техники система противораскачивания довольно популярная и полезная штука. Эта система полезна тем, что, к примеру, оператор крана не обязан корректировать движение крана самостоятельно, чтобы не происходило раскачивание груза и не было рисков возникновения аварийных ситуаций. Многие производители предлагают свои системы на базе ПЛК (программируемых промышленных контроллеров) либо на базе ПЧ (преобразователей частоты). Мы в нашем инженерном центре тоже решили не стоять в стороне и делать свою систему. Погружение в теорию привело нас к пространству состояний. Таким образом целью статьи является рассказать, как возможно решить задачу противораскачивания груза в пространстве состояний.

В программных продуктах для работы с STL, таких как Geomatix Design X, Wrap, NX и др., функционал обязательно включает сегментацию STL модели на отдельные грани. В свободно распространяемом ПО, однако, инструменты для сегментации зачастую отсутствуют. В данной статье хочу рассказать о реализованном мной на Python алгоритме разбиения STL на отдельные грани.

1 декабря я в очередной раз поучаствовал в Advent of Code, написав программу на Rust. Если интересно — код можно найти на GitHub. Тут мне хотелось бы рассказать о моём решении задачи, предлагавшейся во 2 день мероприятия, так как это решение, с одной стороны, сверх всякой меры оптимизировано, а с другой — демонстрирует кое-какие полезные приёмы. Чтобы не усложнять себе жизнь — мы рассмотрим лишь первую часть задачи, но те же приёмы можно применить и к её второй части.

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

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

Сначала будет приведён алгоритм поиска паттернов рекуррентным перебором, потом его быстрая модификация с минимальным отсечением.

Примеры кода написаны на C++, исходники всей библиотеки лежат здесь. Также написана копия библиотеки на Java, исходники лежат здесь.

Привет Хабр! В прошлой статье мы векторизировали данные, теперь нам осталось написать модель и протестировать её

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

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

Самое популярное подобное расширение конфигурации известно как Larger than Life, или просто LtL. Его мы и рассмотрим.

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

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

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