Алгоритмы *

Привет, Хабр! Сразу хочу сказать, что в первую очередь задачи я решал для себя. Хочу поделиться моим опытом взаимодействия с этой платформой и насколько мне это помогло. Каждый по прочтению этой статьи решит для себя сам, стоит начинать или же нет. А началось мое знакомство в далеком январе 2022 года. За все время я решил почти 200-ти задач и имею 4kyu. Мне кажется главное, что стоит понять, что сайт делится на две категории — базовый и продвинутый. Большинство задач на 6, 7, 8 kyu — базовые. Всё, что меньше — продвинутый.

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

Меня зовут Алексей Гуляев. Я архитектор решений в команде VK Tech. В этой статье я расскажу об онтологии в ИТ, вариантах ее использования и нашем кейсе применения онтологического подхода для решения внутренней задачи.

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

Оказалось, что форумы кишат людьми, которые не до конца понимают, как компьютеры манипулируют числами. Например, мемасик с КПДВ я стянул с реддита (перечеркнул его я). Кто-то настолько был напуган страшными ошибками округления чисел с плавающей точкой, что даже смешную картинку смастерил. Только вот проблема в том, что 0.5 + 0.5 в точности равно 1.0.

Таким образом, я решил засучить рукава, и изобрести велосипед. То есть, написать самую неоптимизированную C++ библиотеку для эмуляции IEEE754 32-битных чисел с плавающей точкой при помощи исключительно 32-битной целочисленной арифметики. Библиотека уложится в несколько сотен строк кода, и в ней не будет никакого битхакинга. Задача написать понятный код, а не быстрый. А заодно хорошенько его документировать серией статей.

Итак, этим полукреслом мастер Гамбс начинает новую партию мебели, или статья первая: поговорим о числах и компьютерах.

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

Меня зовут Владимир Быстрицкий, я руковожу группой AI-картографирования. В этой статье расскажу о процессе детектирования дорожных знаков в картопроизводстве Яндекса: с чего всё началось, как развивалось, какие технологии использовались. Ну и попробую ответить на самый, на мой взгляд, главный вопрос в любой ML-задаче: как собрать датасет и не разориться?

OpenCV — популярная библиотека, включающая множество алгоритмов компьютерного зрения и функций для них. Оптимизация их под RISC-V — большая и интересная задача, которой в рамках Зимней школы RISC-V YADRO сезона 2024–2025 занимались студенты Университета Лобачевского (ННГУ). В этой статье они подробно расскажут о своей работе.

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

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

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

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

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

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

Предупреждение о возможном конфликте интересов: автор этого документа также является соавтором реализаций ipnsort и driftsort, используемых в стандартной библиотеке Rust.

Сценарий

Компоненту ПО передаются данные для сортировки. Известно, что значения могут иметь низкую кардинальность. Несмотря на тип u64, способный хранить 2⁶⁴ уникальных значений, в данных наблюдается всего четыре уникальных значения. Учитывая такие серьёзные ограничения, разработчик может разумно решить использовать специализированную реализацию сортировки, а не ту, которая есть в библиотеке, потому что он знает о данных больше, чем способна знать обобщённая реализация.

На прошлой неделе я опубликовал запутанный код на Python, который генерирует мозаику Пенроуза. Сегодня я объясню базовый алгоритм, лежащий в основе этого скрипта на Python, и поделюсь его не запутанной версией.

При про­ектировании RAG-системы инженер каждый раз сталкивается со множеством вопросов: какую базу данных использовать, как организовать получение релевантной информации, да даже выбор эмбеддера может занять приличное время, а это лишь вершина айсберга. Что хорошо работает в одной сфере, например в техподдержке, может полностью провалиться в другой — например, при анализе юридических документов. Поэтому задачей инженера является выявление особенностей предметной области и адаптации RAG системы к ним. Однако, чтобы это сделать, необходимо не только понимать, какие приёмы можно использовать, но и знать насколько они эффективны.

В данной статье мы разберём основные RAG техники, посмотрим их сильные и слабые стороны, сферы применения, а также немного поэкспериментируем. В следующей части статьи мы проведём тестирование этих техник на реальных пользовательских запросах из датасета Natural Questions и оценим качество работы с помощью RAGAS и BertScore, посмотрим на графики и разойдёмся, чтобы обдумать всё написанное. Поэтому предлагаю начать!

Приветствуем любителей компьютерных наук! Хотим рассказать про новую инициативу: 1 марта в Санкт-Петербурге запустился Computer Science Space — открытый научно-технологический клуб для всех заинтересованных в современных и классических областях CS.

Сегодня поговорим про реализации решения конфликтов подходов local / offline-first – это когда ваше приложение позволяет пользователям работать полностью или частично оффлайн, а когда они выходят в сеть, синхронизировать все их изменения.

Примеры таких приложений: Notion-like редакторы, Figma-like вайтборды или Linear-like таск менеджеры.

Основная идея – коллаборация, а коллаборация несет за собой конфликты, разберем очень наглядный пример:

Недавно у меня появилась возможность прочитать книгу Себастьяна Рашки «Строим LLM с нуля», и, начав читать, я просто не мог её отложить.

Эта книга увлекательно сочетает исчерпывающую теорию, практическую реализацию кода и прекрасно и доходчиво объясняет одну из самых актуальных тем в области современного искусственного интеллекта: большие языковые модели (LLM). Как человек, который любит разбираться в тонкостях моделей ИИ, я считаю эту книгу настоящей жемчужиной. Ее обязательно нужно прочитать всем, кто серьезно интересуется LLM. Хочу отметить, что я никак не связан с автором или издателем; эта рецензия является исключительно отражением моего восхищения содержанием книги.

Вы когда-нибудь задумывались, что поиск футболки в шкафу — это O(N), а приготовление ужина — многопоточный процесс с I/O blocking?

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

Станьте архитектором не только кода, но и своей жизни!

Я разработала интерактивный макет для создания композиций цветов. Проблема свелась к задаче упаковки кругов в круг и её автоматизированному решению методом отжига. Расскажу теорию и математически обосную практику с визуальными пояснениями.

Нотация Big O («О» большое) — это способ описания производительности функции без измерения времени ее выполнения. Вместо того, чтобы засекать, сколько секунд выполняется функция от начала до конца, Big O показывает, как меняется время ее выполнения по мере увеличения размера входных данных. Этот подход помогает понять, как программа будет вести себя при разных объемах входящей информации.

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

Приветствую, Хабр!

Структура криптографических алгоритмов, названная ее авторами «губкой» (sponge), была предложена в 2007 году. С тех пор на базе структуры криптографической губки было разработано достаточно много известных криптоалгоритмов.

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

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

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

Привет! Меня зовут Серёжа Синягин, я старший разработчик в Яндекс Еде и пишу на C++. В этой статье расскажу о задаче, с которой столкнулся в работе: как мы определяем, какие рестораны доступны пользователю для заказа. По пути заглянем во внутреннюю кухню, обсудим библиотеку H3 от Uber и разберём, как устроены R‑деревья и как мы используем их у себя.

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

В этом тексте я произвел разбор решения LeetCode задачи 480. Sliding Window Median в контексте реализации на языке программирования Си.