Data Science: Алгоритмы и Структуры данных

Шахматные программы VII. Основной перебор Stockfish

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

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

https://habr.com/ru/articles/1039732/

Алгоритмы и Структуры данных

Царский путь к пониманию комплексных чисел. Часть II

В предыдущей части была рассмотрена предыстория комплексных чисел: от их первого открытия до понимания и умения их широко использовать в науке прошли сотни лет. Комплексные числа впервые возникли как артефакт вычислений в работе Кардано 1545-го года и вплоть до конца XVIII века их статус оставался нестабильным, шли научные дискуссии об уместности их употребления и интерпретации.
Современные изложения теории комплексных чисел выглядят «магически» и непонятно для многих людей именно потому, что, как правило, разрыв между непониманием XVIII века и теориями XIX века не покрыт. Сначала предлагается изучить основы теории комплексных чисел в том виде, в которой они были сформулированы в середине XVIII века, а потом сразу делается скачок к теориям, созданным в середине XIX века.

https://habr.com/ru/articles/981814/

Алгоритмы и Структуры данных

ЕСППД-ИИ. Как описывать бизнес-процессы для работы с искусственным интеллектом

Я руковожу компанией, которая с 2012 года занимается описанием бизнес-процессов и внедрением систем класса ERP. За это время мы не раз сталкивались с одной и той же проблемой: бизнес-процесс вроде бы можно описать словами, можно нарисовать схему, можно составить таблицу операций, но в момент проверки выясняется, что документ не держит реальное исполнение. В нём не хватает предметов, состояний, источников, ролей, переходов, прикладных носителей, исключений и проверок. Такой документ выглядит убедительно, но не позволяет понять, как именно процесс должен работать в системе и как его проверить.

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

https://habr.com/ru/articles/1041856/

Алгоритмы и Структуры данных

Как работает размытие в видеоиграх

Размытие — базовый строительный блок множества эффектов постобработки в видеоиграх, без него не обходятся красивые современные GUI. Оно используется в эффектах Depth of Field, Bloom или панелях с эффектом матового стекла современных пользовательских интерфейсов.

https://habr.com/ru/articles/1041710/

Алгоритмы и Структуры данных

Квантовые компьютеры — не угроза 128-битным симметричным ключам

Надвигающаяся угроза для криптографии со стороны квантовых компьютеров заставила срочно менять действующие примитивы асимметричной криптографии — обмен ключами (ECDH) и цифровые подписи (RSA, ECDSA, EdDSA) — которые уязвимы для квантового алгоритма Шора. Однако существующих симметричных методов криптографии (AES, SHA-2, SHA-3) или уровней их стойкости это не коснулось.
В индустрии бытует заблуждение, что квантовые компьютеры вдвое ослабят безопасность симметричных ключей, и для обеспечения того же 128-битного уровня защиты потребуется перейти на 256-битные ключи. Это неточная интерпретация ускорения, которое несут в себе квантовые алгоритмы. Она не отражена ни в одном из нормативных стандартов и рискует отвлечь внимание от реально необходимой работы по переходу к постквантовой системе криптографии. Обычно это заблуждение происходит из недопонимания применимости другого квантового метода — алгоритма Гровера.

https://habr.com/ru/companies/ruvds/articles/1040544/

Алгоритмы и Структуры данных

Как работает адаптивный RAG, которому вообще не нужна LLM

Один из самых популярных способов снизить процент галлюцинаций языковых моделей — метод RAG, то есть схема, в которой модель при необходимости обращается к внешним данным, а не опирается исключительно на внутренние знания. Все LLM текущего поколения работают с RAG, но он делает систему затратнее по вычислениям и сам по себе может допускать ошибки, если внешний контекст оказался плохим или нерелевантным. 
Сегодня я разберу исследование LLM-Independent Adaptive RAG: Let the Question Speak for Itself, в котором ученые из MWS AI, AIRI, Сколтеха и еще нескольких университетов предлагают решение этой проблемы через новый подход к adaptive retrieval, когда RAG запускается не автоматом, а только при необходимости.

https://habr.com/ru/companies/mts_ai/articles/1041078/

Алгоритмы и Структуры данных

Не все якори одинаково полезны, или как I2I-рекомендации свежими сохранять

Привет, Хабр! Меня зовут Иван Воробьев, я работаю в команде рекомендаций VK Видео, AI VK. В данной статье хочу рассказать, как и зачем я переделывал систему построения I2I-рекомендаций. Поговорим о том, какие решения были поставлены в её основу, насколько они оправдались, а также причём тут якори и как они связаны со свежестью рекомендаций.

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

https://habr.com/ru/companies/vk/articles/1040306/

Алгоритмы и Структуры данных

Понятие о конечных автоматах: руководство разработчика по предсказуемой логике приложений

Вы когда-нибудь отлаживали такой компонент пользовательского интерфейса, где достаточно нажать в неверном порядке несколько кнопок – и приложение валится? А не доводилось ли вам ломать голову, пытаясь отследить, почему в некоторых случаях форма отправляется нормально, а в других — отказывает? Такие неприятные сценарии зачастую возникают по одной базовой причине: непредсказуемое управление состоянием. Мы привыкли полагаться на булевы флаги, рассеянные по коду инструкции if-else, тем временем надеясь, что наше приложение будет правильно работать, чего бы пользователь ни делал в интерфейсе.
Аккуратно справиться с таким хаосом помогают конечные автоматы. Они не позволяют вашему приложению скатиться в какие-то неопределённые состояния, а предоставляют формальную модель, в которой явно прописываются все возможные состояния, в которых может оказаться ваша система, а также в точности указывается, как организуются переходы между этими состояниями. Можете считать, что пишете контракт, в котором регулируется поведение вашего приложения. В этой статье разобрано, что представляют собой конечные автоматы, почему они важны и как научиться ими пользоваться, чтобы создавать более надёжные приложения.

https://habr.com/ru/companies/piter/articles/1039106/

Алгоритмы и Структуры данных

Встречаем маршруты «Прогулочный» и «Оживлённый» в Яндекс Картах, или Как мы учили модель понимать предпочтения людей

Год назад я рассказывал, как Яндекс Карты научились учитывать рельеф и лестницы при построении пешеходных маршрутов. Но альтернативные варианты по-прежнему выглядели для пользователя как просто «ещё один путь, только дольше» — и люди не раздумывая выбирали самый быстрый. Теперь у каждого альтернативного маршрута появилось имя и характер: например, «Быстрый», «Прогулочный», «Оживлённый» или «Без лестниц».
Простые категории посчитать несложно. А вот «Прогулочный» и «Оживлённый» — это субъективные характеристики: в хорошую погоду хочется пройти через парк или вдоль набережной, а в тёмное время — по освещённым улицам, подальше от дворов и промзон. Для этого с помощью LLM мы обучили легковесную модель, которую и применили в сервисе. Как именно — читайте в статье. Сам путь разработки оказался совсем не «Быстрым» и далеко не «Прогулочным» — с тупиками и неожиданными поворотами там, где их не ждали.

https://habr.com/ru/companies/yandex/articles/1040764/

Алгоритмы и Структуры данных

Один простой механизм управляет практически всем в игре Cities: Skylines

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

https://habr.com/ru/articles/1040580/

Алгоритмы и Структуры данных

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

Недавно один хороший знакомый набирал команду в стартап. Он приверженец подхода AI first и попросил меня помочь с наймом.

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

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

https://habr.com/ru/articles/1040690/

Алгоритмы и Структуры данных

Нейросети уже заменяют носителей языка.

В Telegram быстро набирает популярность ИИ-девушка Chatty, с которой можно голосом практиковать живой разговорный английский и ещё 12 языков на основе новейших моделей искусственного интеллекта. Попробовать можно бесплатно.

🇬🇧 Английский: @ChattyTutorBot
🇩🇪 Немецкий: @ChattyGermanBot
🇪🇸 Испанский: @ChattySpanishBot
🇫🇷 Французский: @ChattyFrenchBot
🇮🇹 Итальянский: @ChattyItalianBot
🇵🇹 Португальский: @ChattyPortugueseBot
🇨🇳 Китайский: @ChattyChineseBot
🇯🇵 Японский: @ChattyJapaneseBot
🇰🇷 Корейский: @ChattyKoreanBot
🇸🇦 Арабский: @ChattyArabicBot
🇹🇷 Турецкий: @ChattyTurkishBot
🇷🇺 Русский: @ChattyRussianBot
🇵🇱 Польский: @ChattyPolandBot

Шахматные программы VI. Структура поиска Stockfish

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

https://habr.com/ru/articles/1039220/

Алгоритмы и Структуры данных

Ключ к вычислимости ℵ₋₁ [алеф-минус-один]

Сколько нужно бит, чтобы представить одно число из континуума ℵ₁ чисел?

Ответ: ℵ₀ бит.

https://habr.com/ru/articles/1040352/

Алгоритмы и Структуры данных

Языковые модели без машинного обучения

Эта статья про мои эксперименты с языковыми моделями, в которых не используется машинное обучение и аппаратное ускорение. Чтобы избежать недопонимания поясню, что я имею ввиду под языковой моделью (ЯМ).

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

Если свериться с Википедией на английском и на русском языках, или с многочисленными публикациями про (Large/Small) Language Models, то мои определение и понимание… несколько неканонические. Поскольку я экспериментирую для себя (я сам себе работодатель), то заранее соглашусь с любыми мнениями о неканоничности моего определения ЯМ.

https://habr.com/ru/articles/1039976/

Алгоритмы и Структуры данных

Планирование движения для ровера на ходовой Ackerman'а

Несмотря на прогресс в технологиях и развитие микроэлектроники, задача поиска оптимального пути по-прежнему является весьма тяжёлой для современных вычислителей — будь то CPU или GPU. Горизонт планирования у многих локальных алгоритмов (например, DWA, TEB, MPPI на CPU) как правило не превышает нескольких метров, а иногда и дециметров. Однако планирование на большой временной интервал и дистанцию позволяет алгоритмам лучше находить пути в насыщенных препятствиями средах и является важным элементом системы уклонения от движущихся, динамических препятствий. Для решения задачи создания модуля поиска пути с дальним горизонтом планирования в этой статье будет рассмотрен пакет локального планировщика MPPI-Generic, работающий на GPU. Он может работать в связке с планировщиком State Lattice Planner из ROS NAV2, но в этой демонстрации будет использоваться отдельно от него — как «универсальный планер». Тесты работы обоих пакетов планирования будут проводиться в самодельном Qt-OpenGL симуляторе автомобиля (пикапа), выполненном на C++ для более плотной интеграции с симулятором и удобного обращения к CUDA-ядрам MPPI-Generic.

https://habr.com/ru/articles/1039784/

Алгоритмы и Структуры данных

Я хотел повторить Growing Neural CA за вечер. Ушёл месяц

Месяц назад я прочитал на Хабре статью про нейронные клеточные автоматы. Маленькие нейросети управляют клетками на сетке, клетки сами собираются в букву T или крест, и всё это обучается без учителя через что-то вроде эволюции. Я подумал: круто, повторю за пару вечеров, посмотрю как себя ведёт.

Эта статья — про то, что было дальше. Спойлер: пара вечеров превратилась в месяц, я провёл 22 эксперимента, упёрся в потолок IoU 0.44 на простой букве T, и главное чему научился — это вообще не про нейросети.

https://habr.com/ru/articles/1039694/

Алгоритмы и Структуры данных

Как у меня НЕ получился торговый бот на Polymarket

Привет, Хабр. Видел в интернете кейс. где сделали бота с LLM для торговли на Polymarket и он сделал $10k из $1k за месяц. Ну и чо бы не попробовать что то такое же сделать! Побочный проект, чисто по приколу. Вооружил его вирутальным стартовым капиталом — $100 нарисованных.

И вот на второй день этот несерьёзный проект показал +9% на счёте.

https://habr.com/ru/articles/1039642/

Алгоритмы и Структуры данных

Только 17% всех 64-битных целых чисел можно разложить на два 32-битных

В разработке ПО произведение двух целых чисел часто вычисляется до фиксированного количества битов с переполнением. Возьмём для примера 8-битные целые. Если умножить 127 на 127, то мы получим число 1 в виде 8-битного беззнакового целого с переполнением. Реальное полное произведение равно 16129. Для представления 16129 обычно используются 16 бит точности.

Таким образом у нас появляется понятие полного произведения. Полное произведение двух 32-битных чисел обычно представляется при помощи 64 бит. У меня возник вопрос, какую долю всех 64-битных чисел можно записать как произведение двух 32-битных целых.

https://habr.com/ru/articles/1039552/

Алгоритмы и Структуры данных

Трекинг посетителей на fisheye-камерах: задача “со звездочкой”

Всем привет, на связи команда NeuroCore. Сегодня расскажем про кейс разработки системы видеоаналитики для магазинов самообслуживания: почему fisheye-камеры - настоящее проклятие, почему SORT и DeepSORT не справились с задачей, как мы выстроили конвейер от детекции до бизнес-событий, и какие инженерные решения позволили добиться стабильной работы в продакшене.

Дано: магазины самообслуживания, которые работают без кассиров и продавцов. Покупатель входит по QR, выбирает товары, рассчитывается и выходит. Заказчику нужна автоматизированная система отслеживания: кто находится внутри, сколько времени, в каких зонах, а также распознает несанкционированный доступ и вход группами. В случае нарушений, система должна генерировать алерты по 7 типам событий.

Что есть: одна потолочная fisheye-камера, которая покрывает весь зал. Это идеальный выбор для ритейла: угол обзора 180 градусов, не нужно ставить десятки обычных камер, не нужно сшивать панорамы. Но за этот комфорт приходится платить.

https://habr.com/ru/articles/1039354/

Алгоритмы и Структуры данных