Парсим строки с SMT-решателем

Этот пост о том, как можно разобрать строку по контектстно-свободной грамматике с помощью SMT-решателя. Здесь будет введение, описание принципа работы и ссылка на github с работающей программой.

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

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

Суффиксное дерево на python

Суффиксное дерево (Suffix Tree, ST) – это структура данных, которая позволяет "проиндексировать" строку за линейное время от её длины, чтобы потом быстро находить подстроки (за время О(длина искомой подстроки)).

Тема построения ST и его применения хорошо раскрыта в интернет (википедия, статья на хабр про алгоритм Вейнера, язык Си, и статья на хабр про алгоритм Укконена).
Но всегда есть соблазн поучаствовать в соревновании "написать проще и яснее", хотя шансов мало. Тем не менее, рискну.

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

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

Вычисления с плавающей запятой: сравниваем вывод в разных языках

С вашим языком программирования все в порядке — он просто производит вычисления с плавающей запятой. Изначально компьютеры могут хранить только целые числа, так что им нужен какой-то способ представления десятичных чисел. Это представление не совсем точное. Именно поэтому, чаще всего, 0.1 + 0.2 != 0.3.

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

Предлагаем хабрасообществу наш перевод этого материала. Обращаем ваше внимание, что позиция автора не всегда может совпадать с мнением МойОфис.

https://habr.com/ru/companies/ncloudtech/articles/683114/

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

Быстрая свёртка множеств (алгоритм)

Эту статью меня вдохновила написать задача с codeforces. В статье будет разобран алгоритм для решения задачи.

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

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

Алгоритмы для веб-разработчиков простыми словами

В этой статье мы поговорим о том, зачем вообще их нужно знать веб-разработчикам, и затронем тему оценки сложности алгоритмов и Big O нотации.

https://habr.com/ru/companies/gnivc/articles/683128/

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

Детектирование позы человека при помощи библиотеки OpenPose

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

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

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

Персональное ранжирование на Авто.ру: как не потерять главный смысл поиска по параметрам

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

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

На скриншоте видно: с помощью параметров можно указать марку, модель автомобиля и другие, в том числе мельчайшие характеристики. Также можно ввести запрос текстом, в этом случае он будет разбит на токены и преобразуется в набор параметров. Ещё одно важное отличие — объявления на Авто.ру могут публиковать и частные продавцы, и дилеры. Эти особенности поиска вновь ставят под сомнение возможную пользу от машинного обучения. Действительно, зачем использовать ML, когда поисковые фильтры могут дать однозначный ответ на запрос?

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

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

Теория алгоритма лежащего в основе разума

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

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

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

SQL HowTo: моделирование против подсчета (Advent of Code 2024, Day 21: Keypad Conundrum)

В этой челлендж-серии статей попробуем использовать PostgreSQL как среду для решения задач Advent of Code 2024.

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

Пробуем смоделировать преобразования строк "в лоб", а потом - организовать подсчет и решить более сложную задачу в разы быстрее простой!

https://habr.com/ru/companies/tensor/articles/891522/

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

Программный код в Big data и Power law

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

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

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

Тестирование: быстрый старт в IT за 0₽

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

Прямо сейчас Skillbox отдает пятидневный курс по тестированию бесплатно.

Переходите по ссылке и участвуйте в тест-драйве профессии. Акция продлится до 19 марта: https://go.redav.online/3ce9ac7270bf9c50?erid=2VfnxxcSezk&m=1

Камеры трясутся, шум зашкаливает, а сравнивать нужно: как справляются алгоритмы?

Каждый день миллионы изображений, видео и аудиофайлов загружаются в интернет. Мы смотрим фильмы, слушаем музыку, листаем соцсети, даже не задумываясь о том, какие алгоритмы стоят за тем, чтобы контент отображался корректно и не повторялся. Но что, если вам нужно сравнивать медиаконтент автоматически? Как понять, одинаковые ли две фотографии, если одна немного темнее? Как сравнить два видео, если они сняты под разными углами? А что делать, если вам нужно найти дубликат аудиофайла, но на одной записи есть шум?

Если эти вопросы вам интересны – добро пожаловать в мир сравнения медиаконтента! Сегодня мы разберем, какие бывают методы, их плюсы и минусы, а главное – расскажем о наших экспериментах, где мы проверили, какие алгоритмы лучше справляются с реальными проблемами.

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

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

PowerShell: обход и визуализация HTML-дерева из файла

Ранее я написал скрипт для программы-оболочки «Windows PowerShell» версии 5.1 (или для «PowerShell» версии 7), работающей в операционной системе «Windows 10». Этот скрипт получает текст из текстового файла с кодом на языке HTML (в кодировке UTF-8 без метки BOM) и помещает его в переменную $html типа System.String. После этого с помощью библиотеки «HTML Agility Pack» содержимое переменной $html конвертируется в объект $dom, содержащий HTML-дерево:

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

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

Поиск нечетких дубликатов. Алгоритм шинглов для веб-документов

Ранее я показал элементарную реализацию алгоритма шинглов, позволяющую определять, являются ли два документа почти дубликатами или нет. В этот раз я поясню реализацию алгоритма, описанную Зеленковым Ю. Г. и Сегаловичем И.В. в публикации «Сравнительный анализ методов определения нечетких дубликатов для Web-документов».
Этим я начинаю серию из трех теоретических статей, в которых постараюсь доступным языком описать принцип алгоритмов шинглов, супершинглов и мегашинглов для сравнение веб-документов.

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

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

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

А не пора ли нам подкрепиться?

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

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

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

Сортировка слиянием на CUDA

Я решил изучить, как повысится производительность алгоритмов сортировки при их реализации на CUDA. Моя цель — понять, как можно использовать мощь параллельных вычислений для ускорения алгоритмов сортировки.

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

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

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

Моя история подготовки к интервью в FAANG

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

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

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

Армения посреди Америки, Китая и России: отчет с EDA Connect 2025

Мысль, что Армения удобна тем, что соединяется и с Америкой, и с Китаем - высказал мне один из китайских участников конференции EDA Connect. А мысль, что Армения соединяется еще и с Россией - возникала естественно при просмотре докладов о логическом синтезаторе, статическом анализаторе и верификации с помощью UVM.

Помимо докладов, при конференции прошел хакатон по Verilog и FPGA, на который пришли студенты из Ереванского университета, русско-армянского университета, американо-армянского, французско-армянского, европейско-армянского, и других университетов. Занятно, что второй день хакатона проходил в комнате напротив зала, где большое начальство встречалось с Премьер-Министром Армении. Один из студентов хакатона перепутал дверь, и его перенаправила секьюрити.

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

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

Дедупликация объявлений: как мы боремся с одинаковыми размещениями

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

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

https://habr.com/ru/companies/cian/articles/892650/

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

Шахматы на C++

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

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

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

Кривые в компьютерной графике. Урок 1: Анимации

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

https://habr.com/ru/companies/unigine/articles/680996/

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