Алгоритмы *

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

Почему собственный? Я искал подобное решение, но не нашел, возможно, оно уже было реализовано, просто плохо поискал. Жду Нобелевскую премию =)

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

Многие задачи, с которыми мы имеем дело при цифровизации производства (неважно какого), – это задачи оптимизации: оптимизация производственного расписания, оптимизация цепочек поставок и размещения объектов, оптимизационное планирование и прочее. Многие из них сводятся к проблемам смешанного линейно-целочисленного типа (MILP – Mixed Integer Linear Problem). Конечно же мы хотим их решать быстрее и эффективнее, поэтому год назад начали разработку ML-модулей для этого. В этой статье мы познакомим вас с концептом одного такого модуля – для упрощения MILP методом обнуления переменных – и расскажем о том, насколько нам удалось с его помощью сократить время работы решателя.

Что такое конечные автоматы?

Простое .NET решение для четких фото: избавьтесь от дымки или тумана на изображениях всего за несколько шагов!

Представьте большой отель с собственным сайтом. Огромное число клиентов: старых, новых и потенциальных. Менеджеров атакуют с вопросами от «а можно забронировать двухместный номер на 5-е число» до «а когда будет завтрак».

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

Всем известна простая истина бизнеса: теряется клиент = теряются деньги.

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

В чем заключалась проблема?

Рассмотрим дело в разрезе чисел. Собрали статистику и выяснили, что недополученная прибыль составила порядка 1 миллиона рублей. Из-за отвлечения на типичные вопросы менеджеры не успевают обрабатывать 30% заказов. С технологической точки зрения процесс не меняется: отель работает в том же режиме, затраты на оплату труда не стали больше или меньше. Но без обработки 100% потока желающих гостиница не получила миллион рублей. Отчет аналитика показал неутешительные выводы: конверсия падает, отель теряет деньги. Было два пути решения этой проблемы: найти новых сотрудников или оптимизировать труд уже нанятых. Искать и обучать новых людей было затратно по времени и финансам, поэтому решили сделать более эффективной работу менеджеров.

Что мы сделали?

Так как вся система отеля находилась в Битрикс24, и там же была установлена связь с виджетом от ChatApp, нам оставалось только настроить автоматизированные ответы на часто задаваемые вопросы - что мы и сделали!

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

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

Нежданно ни гадано, затеяли значит высшие "итишные" силы включить новые заморские очереди Кафка в уже выполненный на 4/3 проект и слава богу, что только для внешних взаимодействий и передачи всякой информации туды-сюды. Главный архитектор дал благословение и понеслось, да не туда, так как нести то некому это невиданное заморское чудо. Что делать, в обозримые сроки не впихнуть и перед боярами чин и обязательства не сдержать. Посидел РП, погоревал, да сдул пыль со знаний древних и ранее опробованных и тут понеслось.

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

Проверка небольших чисел на простоту - популярная подзадача в спортивном программировании. И тест Миллера-Рабина, пожалуй, наиболее популярный из простых алгоритмов для этого.

У меня давно было желание с ним поиграться, стараясь оптимизировать различными способами. Например, векторизовать и посмотреть, станет ли быстрее.

Всем привет! На связи команда Практикума. Недавно мы проводили открытое алгоритмическое собеседование и теперь хотим поделиться записью. Это отличная возможность подсмотреть, каким может быть процесс, научиться на чужих ошибках или взять на примету удачные решения.

Мы попросили Самсонова Ивана рассказать о его критериях оценки кандидатов, а также поделиться советами по подготовке. На видео Иван выступал в роли тимлида, а в обычной жизни он разработчик со степенью в Computer Science и наставник курса «Алгоритмы и структуры данных».

Приветствую. Речь в статье пойдёт про мой опыт реверсинга и написания ботнета для $NotCoin.

Дело было вечером, делать было нечего, подружка села на заборе — и скинула мне ссылку на ноткоин в альфе.
Посмотрел, потыкал, недолго думая, я забыл про него на месяц.
И вот он уже набрал аудиторию и я подумал, что всё же стоит посмотреть что там да как.

Суть игры в одном слове: кликер.

И что же нужно делать?
— У тебя есть монетка, на неё нужно кликать, чем больше монет - тем лучше.

Привет, Хабр! Меня зовут Илья Ненахов, я руковожу разработкой платформы для продвижения товаров на Яндекс Маркете. Предлагаю взглянуть на площадку немного с другой стороны, а именно — как на механизм, который пытается найти оптимальную точку в пространстве с тремя измерениями:  интересы пользователя, интересы магазинов и интересы самого сервиса.

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

Всем привет. В этой статье я расскажу про дерево отрезков. Очень мощной структуры данных, которая позволяет делать много разных операций над массивом чисел. Я постараюсь по полочкам разложить эту тему и объяснить возможности дерева отрезков. Также я разберу несколько нетривиальных задач на дерево отрезков. Помимо самого дерева отрезков я расскажу и про связанные темы: дерево Фенвика и разреженные таблицы.

Продолжаем говорить о производительности и оптимизации кода. Сегодня поговорим о том, как и зачем оценивать сложность алгоритмов,  а также наглядно покажем, как эта сложность влияет на производительность кода.

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

Меня зовут Андрей Сюткин, и я отвечаю за ML-трек в Нейро. В этой статье покажу, как выглядит архитектура Нейро и как формируются ответы на технологическом уровне. Ну и, конечно же, поговорим о нейросетях, в том числе о YandexGPT 3, без обучения которых новый сервис просто не увидел бы свет.

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

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

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

Чтобы понять преимущества ЦОС, давайте сначала рассмотрим традиционный метод обработки сигналов, то есть аналоговую обработку сигналов.

Это статья сделана совместно с автором курса по Цифровой обработке сигналов в INZHENERKA.TECH Волченковым Владимиром, доцентом кафедры телекоммуникаций и основ радиотехники ФГБОУ ВО «РГРУ им. В.Ф. Уткина» и научным сотрудником ООО «Лаборатория Сфера». Больше информации в нашем сообществе инженеров.

Аналоговая обработка сигналов

Возможно, самым простым примером аналоговой обработки сигналов является знакомая RC-цепь, показанная на рисунке 1.

Привет! Меня зовут Дмитрий Королёв, я бэкенд-разработчик в Авито. В этой статье я расскажу про ключевые аспекты и концепции работы с наиболее популярными алгоритмами и структурами данных. Это поможет и в реальных проектах, и чтобы глубже понять алгоритмические принципы. Статья подойдёт специалистам, которые хотят углубить свои знания в программировании, и укрепить навыки нахождения оптимальных решений алгоритмических задач.

Задача о сумме подмножеств в общей формулировке звучит так:

Существует множество S чисел, вопрос состоит в том, будет ли сумма некоторого подмножества от S равна заданному числу Т.

Известно, что данная задача NP-полная.

Мы будем решать эквивалентную задачу, где все числа являются натуральными.

Частным случаем задачи о сумме подмножеств является задача разбиения множества чисел:

Множество чисел S необходимо разбить на два подмножества S1 и S2, где сумма S1 равна сумме S2.

(От задачи о сумме подмножеств текущая отличается только тем, что T = SUM(S1) / 2 = SUM(S2) / 2)

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

Одной из самых распространённых задач аналитики является формирование суждений о большой совокупности (например, о миллионах пользователей приложения), опираясь на данные лишь небольшой части этой совокупности - выборке. Можно ли сделать вывод о миллионной аудитории крупного мобильного приложения, собрав данные 100 пользователей? Или стоит собрать данные о 1000 пользователях? Какую вероятность ошибиться при анализе мы можем допустить: 5% или 1%? Относятся ли две выборки к одной совокупности, или между ними есть ощутимая значимая разница и они относятся к разным совокупностям? Точность прогноза и вероятность ошибки при ответе на эти и другие вопросы поддаются вполне конкретным расчётам и могут корректироваться в зависимости от потребностей продукта и бизнеса на этапе планирования и подготовки эксперимента. Рассмотрим подробнее, как параметры эксперимента и статистические критерии оказывают влияние на результаты анализа и выводы обо всей совокупности, а для этого смоделируем тысячу A/A, A/B и A/B/C/D тестов.