Алгоритмы *

Всем привет! Это Сергей Качеев, старший разработчик в отделе сетевой инфраструктуры Yandex Infrastructure. Наша команда создаёт технологии, на которых работают сервисы Яндекса. В прошлый раз я рассказал целый сетевой детектив о том, как мы искали баг, который убивал DNS‑сервер Unbound. И сегодня я расскажу не менее интересную историю.

Мне на развитие попала XDP eBPF‑программа, которая защищает DNS‑серверы от выхода из строя под слишком большой нагрузкой (другими словами, от DDoS). На ядре 5.4 алгоритм защиты был основан на EWMA‑статистике с вероятностными дропами, которые постоянно контролировались из Control Plane. Это делало eBPF‑программу неавтономной. К тому же если Control Plane падал, то сервер оставался в состоянии последнего удачного обновления eBPF. Это нужно было исправлять — было решено заменить это всё на Token Bucket. Этот момент и будем считать отправной точкой в нашей истории.

Некоторые головоломки можно решать на SQL just for fun, а часть получается выразить на этом декларативном языке даже эффективнее других, императивных.

Попробовать сделать более наглядное решение, а заодно познакомить с некоторыми нетривиальными возможностями PostgreSQL меня натолкнул пост о решении на Python задачи Black and White.

Black and White — одна из интересных головоломок игры Puzzle Hunt Мельбурнского Университета 2010 года. По сюжету игры вы преследуете загадочного участника ТВ‑шоу в надежде раскрыть его личность. Вам удается пробраться сначала на студию, а затем и в его гримерку. Там в его одежде вы находите клочок бумаги. Одну из его сторон занимает сообщение, другую — головоломка и набор инструкций к ней.

«Разложите каждую из диаграмм ниже на полоски размером 1×1, 1×2 или 1×3 таким образом, чтобы ни одна сетка не содержала полосок с одинаковым черно‑белым паттерном, включая повороты».

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

Но после этого я, по инерции, решил ковыряться дальше. Факультативно, так сказать.

Всем привет! Меня зовут Алексей Староверов, я научный сотрудник группы «Embodied agents» в AIRI. К числу моих научных интересов в основном относятся алгоритмы обучения с подкреплением (RL) и их применение для робототехнических систем. В этом году в рамках конференции ICRA 2024 мы с коллегами из МФТИ представили статью на тему автономной навигации мобильных роботов, о которой я бы и хотел вам рассказать.

Разберём основы компьютерного зрения на примерах с котиками, узнаем, почему CV на самом деле совсем не про зрение и научимся делать свёртку.

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

Продолжаем публикацию лекций по предмету "Управление в Технических устройствах" Автор Олега Степановича Козлова. Кафедра "Ядерные энергетические установки" МГТУ им. Н.Э. Баумана. Это пожалуй первая лекция, гда теория автоматеского управления применяется непосредственно к таким устройствам как ядерные реакторы. Более того имеенно на это лекции объясняется что такое 1D моделирование.

В предыдущих сериях:

1. Введение в теорию автоматического управления.2. Математическое описание систем автоматического управления 2.1 — 2.3, 2.3 — 2.8, 2.9 — 2.13. 

3. Частотные характеристики звеньев и систем автоматического управления регулирования. 3.1. Амплитудно-фазовая частотная характеристика: годограф, АФЧХ, ЛАХ, ФЧХ. 3.2. Типовые звенья систем автоматического управления регулирования. Классификация типовых звеньев. Простейшие типовые звенья. 3.3. Апериодическое звено 1–го порядка инерционное звено. На примере входной камеры ядерного реактора. 3.4. Апериодическое звено 2-го порядка. 3.5. Колебательное звено. 3.6. Инерционно-дифференцирующее звено. 3.7. Форсирующее звено.  3.8. Инерционно-интегрирующее звено (интегрирующее звено с замедлением). 3.9. Изодромное звено (изодром). 3.10 Минимально-фазовые и не минимально-фазовые звенья. 3.11 Математическая модель кинетики нейтронов в «точечном» реакторе «нулевой» мощности. 

4. Структурные преобразования систем автоматического регулирования.

5. Передаточные функции и уравнения динамики замкнутых систем автоматического регулирования (САР).

6. Устойчивость систем автоматического регулирования. 6.1 Понятие об устойчивости САР. Теорема Ляпунова. 6.2 Необходимые условия устойчивости линейных и линеаризованных САР. 6.3 Алгебраический критерий устойчивости Гурвица. 6.4 Частотный критерий устойчивости Михайлова. 6.5 Критерий Найквиста.

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

Я прошел через череду осознаний и озарений, прежде чем достичь просветления, и теперь предлагаю вам пройти этот путь вместе со мной.

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

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

Привет! Меня зовут Ольга Зайкова, в Яндексе я руковожу группой автоматической генерации рекламы. Сегодня расскажу о соединении тяжёлых процессингов и GPU‑вычислений. Обсудим, как мы реализовали высоконагруженный процессинг, который обрабатывает миллиарды товаров и превращает их в объявления, используя тяжёлые модели, такие как YandexGPT, DSSM, CatBoost и другие. И, конечно, не обойду стороной тему проблем с нагрузкой: они возникали почти на каждом шагу.

Пару дней назад был опубликован пост с решением на MySQL загадки Джиндоша (она же загадка Эйнштейна).

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

Поэтому я попробовал решить эту задачу "в общем виде", используя возможности PostgreSQL, и вот что из этого получилось.

Привет! Меня зовут Александр Телепов, я — исследователь в Институте AIRI. Наша команда занимается применением глубокого обучения в науках о жизни. В сферу наших интересов входят такие задачи, как дизайн материалов, анализ растворимости или поиск новых лекарственных препаратов. Про последнее я бы хотел поговорить поподробнее.

О том, что сегодня для поиска новых соединений используют нейросети, слышали многие. Взять хотя бы нашумевший AlphaFold 3 от DeepMind, решающий задачу генерации трехмерной структуры разнообразных молекулярных комплексов. Существуют и другие задачи, в которых нейросети преуспели над классическими численными методами. Ярчайший пример — генерация молекул‑лекарств. Одним из самых заметных подходов к этой задаче стал фреймворк генерации молекул‑лекарств на основе методов обучения с подкреплением FREED. Но и он оказался далёк от идеала.

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

Привет, Хабр! Меня зовут Евгений Буевич, я работаю в Рунити. Как-то раз у меня возникла непреодолимая потребность умножать матрицы определенного размера, смотреть, что получится и умножать опять до тех пор, пока что-нибудь не получится.

Остановился на BLIS, скомпилировал, подключил, и было мне счастье. Матрицы стали подрастать в числе и размере, скорость процесса, как ей и положено, падала в кубе от размера и кратно от числа. В конце концов стало ощущаться, что на ЦПУ 486,4 GFLOPS и ни флопсом больше, а замеры показывали, что на самом деле их около 350.

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

Карта видимости - это достаточно простой механизм в СУБД PostgreSQL, но даже он имеет множество интересных тайн, если погрузиться в детали реализации.

В этой статье мы выясним:

1. Какие особенности есть у механизма сбрасывания и установки бита полной видимости.

2. Как Index only scan использует бит полной видимости.

3. Зачем записывать информацию об изменении карты видимости в WAL.

4. Каким образом карта видимости участвует в оптимизации предвыборки Bitmap scan.

5. Зачем механизму оценки селективности нужна карта видимости.

Начну с небольшой шутки:

"Знаете ли вы, что до изобретения часов людям приходилось активно ходить повсюду и спрашивать время?"

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

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

Индивидуально оптимальная позиция: то, что особь считает наилучшим для себя.

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

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

Данный алгоритм известен как оптимизация роем частиц (Particle Swarm Optimization, PSO). Возможно, это звучит несколько сложно. Что подразумевается под "оптимизацией"? Какова роль математики в этом процессе? Что именно оптимизируется? В статье я постараюсь подробно разъяснить все эти моменты. Более того, мы применим ООП на Python для создания собственного класса ParticleSwarmOptimizer(). И таким образом, мы пройдем путь от теоретических основ PSO до их практической реализации.

Итак, приступим! Желаю приятного чтения.

Привет, друзья!

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

• Первая часть
• Вторая часть
• Третья часть
• Четвертая часть

Сегодня мы рассмотрим систему непересекающихся множеств, фильтр Блума и кэш актуальных данных.

Код, представленный в этой и других статьях серии, можно найти в этом репозитории.

Интересно? Тогда прошу под кат.

В 1970-х годах известный программист Эдгар Кодд разработал математически выверенную теорию организации данных в виде таблиц (реляций). С тех пор утекло немало воды — появилось большое количество различных коммерческих и open-source реляционных систем управления базами данных (РСУБД). Скоро стало понятно, что эффективное получение данных из базы — задача далеко не тривиальная. Если говорить прямо, она нелинейная и в общем случае NP-сложная.

Когда SQL-запрос становится немного сложнее: SELECT * FROM table, у нас появляется огромная вариативность его исполнения внутри системы — и не всегда понятно, какой из возможных вариантов эффективнее как по памяти, так и по скорости. Чтобы сократить огромное количество вариантов до приемлемого, обычно используются так называемые эвристики — эмпирические правила, которые придуманы человеком для сокращения пространства поиска на несколько порядков. Понятное дело, эти правила могут отсечь и сам оптимальный план выполнения запроса, но позволяют получить хоть что-то приемлемое за адекватное время.

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