О том, как алгоритм Дейкстры реализовывал и некоторых его применениях

В этой статье я попробую реализовать алгоритм Дейкстры, что называется "в лоб" согласно описанию на википедии с использованием очереди c приоритетом (PriorityQueue) для хранения непосещённых вершин и применить его для нахождение кратчайшего пути между двумя вершинами связного взвешенного графа. А в качестве бонуса попробую запустить алгоритм для нахождения оптимального маршрута между двумя точками на 3D поверхности и посмотреть на полученные результаты.

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

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

Улучшаем маршруты обхода на складе силами веб-программиста и математики

Сразу к сути: есть склад, где все бизнес-процессы уже отлажены и в целом всех всё устраивает. Ничего, что даст рост в 30%, сделать уже невозможно, но хочется. Поставлена цель: оптимизировать маршрут, по которому идёт сборщик товаров, чтобы товар собирался быстрее. Результат 2-3% роста вполне устроит.

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

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

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

Как построить прогноз спроса и не потерять голову

Представьте себе ситуацию: ваша уютная маленькая команда Data Science занимается прогнозированием спроса для пары десятков дарксторов с помощью какого-нибудь коробочного Prophet. И в один прекрасный день к ней приходит бизнес. Бизнес садится, закидывает ногу на ногу, закуривает сигару и говорит:

https://habr.com/ru/companies/ecom_tech/articles/698118/

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

API для Инвестиций, или Как написать торгового робота

На связи команда Тинькофф Инвестиций. В этой статье разберем, как клиенты с минимальными навыками программирования создают торговых роботов. Базой будет API брокера Тинькофф Инвестиций — Tinkoff Invest API. Добро пожаловать на борт!

https://habr.com/ru/companies/tbank/articles/699624/

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

Ускорение LLM: универсальные методы для популярных архитектур

ML‑модели применяются в сервисах Яндекса уже много лет, мы накопили большой опыт в их обучении. Статьи об этом коллеги регулярно публикуют, в том числе на Хабре. Но сегодня хочу обсудить другую не менее важную задачу — ускорение инференса (процесса работы на конечном устройстве) моделей. Скорость зависит от разных условий, главным образом от архитектуры и железа, но есть множество интересных способов повлиять на неё. Особенно актуальна проблема тяжёлого инференса при использовании больших языковых моделей (LLM) — на то они и large!

Для команды YandexGPT, в которой я и тружусь вместе со своими коллегами, тема инференса LLM находится в разряде вечных вопросов. С предыдущей статьи прошёл уже почти год, опыта у нас стало больше — получилось протестировать новые подходы, которыми и хочется поделиться сегодня.

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

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

SQL HowTo: играем в сокобан с помощью json-карты и типа point (Advent of Code 2024, Day 15: Warehouse Woes)

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

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

Многие слышали о классической игре сокобан, а кто-то наверняка играл в "Мудрого крота" из Роботландии. В этой части мы будем двигать ящики по складу, используя возможности json[b] и геометрического типа point.

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

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

Оптическая криптография: нейронные сети, голограммы, лазеры и этанол

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

https://habr.com/ru/companies/ua-hosting/articles/879288/

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

Нестандартная обобщённая хеш-таблица на чистом Си

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

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

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

Алгоритм Кнута-Морриса-Пратта для поиска подстрок на Go

Поиск подстроки в строке — важная задачка в текстовой обработке. В Go стандартная библиотека имеет strings.Index, но он использует простой перебор символов, который работает с O(n × m) в худшем случае, где n — длина текста, m — длина подстроки.

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

https://habr.com/ru/companies/otus/articles/878812/

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

Программная генерация костюма на основе биологических параметров человека

Предупреждение! Эта публикация сыра, как воды мирового океана!
!Эта публикация - размышление, публикация концепт!

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

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

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

Алгоритмы из теории графов: решаем сложную задачу из курса Яндекс Практикума

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

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

https://habr.com/ru/companies/yandex_praktikum/articles/877964/

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

Algorithmatic — социальный ресурс алгоритмов

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

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

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

Используем нейросеть для генерации стихов в стиле «Евгения Онегина»

Мне нравится концепция, согласно которой речь – это, в первую очередь, не способ коммуникации, а отражение сознания. В таком случае стихи - это отражение красоты сознания. Но сможет ли нейросеть сгенерировать стихотворения, похожие на рукотворные? Давайте попробуем сделать такой алгоритм.

https://habr.com/ru/companies/amvera/articles/699058/

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

Мой личный опыт восстановления старых фотографий с помощью нейросетей

Но мало кто знает, что радиоактивное облако распространилось на тысячи километров. К сожалению, это затронуло и деревню моей бабушки недалеко от Гомеля. Жителей эвакуировали далеко не сразу, но когда пришло время уезжать, то фотографии, которые были приклеены на стене пришлось отклеивать варварским способом. Время потрепало эти фотографии, но попробуем восcтановить.

Для примера я взял только две фотографии. На первой, мой двоюродный брат бабушки и какой-то человек на лошади. На второй — мой прадедушка.

Как можно дать вторую жизнь этим фотографиям?

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

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

Сферический БПЛА в воздухе

Обычно, когда мы говорим о беспилотных летательных аппаратах (БПЛА) [1], на ум сразу приходит квадрокоптер (или другой представитель класса мультикоптеров, например, гекса- или октокоптер). Но строго говоря, беспилотник не обязательно должен быть мультикоптером – он может быть выполнен в виде любой механической схемы, которая ранее была разработана для пилотируемого полёта.

Например, это может быть летательный аппарат легче воздуха, то есть аэростат (воздушный шар) или дирижабль [2]. Данной статьёй мы открываем цикл публикаций, в котором расскажем в режиме «хроник лаборатории» о ходе нашего сайд-проекта по сборке БПЛА в виде стратостата [3]. Но прежде, чем что-то собирать, нужно хорошо разобраться в предмете, в его теоретической части. Поэтому мы решили начать с того, чтобы изучить динамику вертикального полёта воздушного шара.

https://habr.com/ru/companies/singularis/articles/697440/

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

Пришло время программистов-самоучек

Среди самых успешных людей в мире есть программисты-самоучки. Так, Барак Обама наградил Маргарет Гамильтон (одну из них) Президентской медалью свободы за ее вклад в работу над лунным проектом «Аполлон». Стив Возняк еще в старших классах купил книгу по Фортрану и сам научился программировать. Впоследствии он изобрел персональный компьютер и стал сооснователем Apple, крупнейшей компании в мире. Самоучками являются и сооснователь Twitter и Square Джек Дорси, и Кевин Систром, сооснователь Instagram, и Дэвид Карп, основатель Tumblr.

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

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

Как математика помогает логистике быть точнее. Опыт ПГК

Цифровые алгоритмы помогают решать реальные бизнес-задачи в самых разных сферах. Логистика — не исключение. Главные инструменты логиста — вовсе не карта, линейка и калькулятор, а сложные IT-системы, которые основаны на математическом моделировании и алгоритмах искусственного интеллекта. Эксперты в этой области ориентируются в цифровых продуктах, умеют их использовать и извлекать выгоду для компании. Почему? Потому что основная задача логиста – экономия. Он критически оценивает существующие процессы и предлагает способы их оптимизации. Ольга Умнова, Product Owner ПГК, и Дмитрий Алимин, руководитель направления в управлении развития цифровых продуктов компании, рассказывают, как ПГК использует математический подход в бизнесе.

https://habr.com/ru/companies/pgk/articles/697278/

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

Как подготовиться к собеседованию в Samsung Advanced Computing Lab

Я работаю проектировщиком аппаратного блока графического процессора в телефонах Samsung, в рамках совместного проекта с AMD. Сейчас наш менеджмент расширяет команду и поощряет инженеров распостранять информацию о новых позициях среди своих знакомых. Я решил написать это пост для более широкой аудитории, так как множество людей, способных пройти интервью на RTL или DV позицию - больше, чем множество моих знакомых. Если вы сможете прислать мне ответ на задачку в моем посте вместе с вашим резюме, я перешлю его нанимающему менеджеру и рекрутеру нашей группы (в комментах прошу ответ не писать). Если резюме им понравится, вам нужно будет пройти стандартное собеседование на несколько часов, с несколькими инженерами, у каждого из которых свой набор задачек.

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

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

Алгоритм генерации волн врагов в рогалике

Недавно в ранний доступ в Steam вышла наша игра Clayers: Prologue. Это рогалик в глиняном стиле, где нужно подбирать и смешивать цвета, чтобы убивать врагов. В этой статье разберём наш подход к генерации волн с учётом сложности противников.

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

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

Что делать, если твой временной ряд растёт вширь

Есть мнение, что прогнозирование временных рядов - сложная задача. Но не будем расстраиваться, ведь есть и плюсы - существует ещё большое количество задач, когда рядов сразу несколько, и такие задачи ещё сложнее! Когда начинаем сравнивать, понимаем, что прогнозировать одномерные временные ряды не так уж и сложно. А вот что делать с ситуацией, когда временной ряд обрастает параллельно идущими с ним последовательностями других параметров (многомерный ряд), какие методы и алгоритмы использовать, и что делать, если задача прогнозировать такие ряды есть, а опыта не очень много (спойлер - используйте AutoML, а пока он работает восполните пробел прочитав пару статей по теме), разбираем под катом.

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

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

Как преобразовать правило .gitignore в регулярное выражение

Возникла идея сделать свою систему контроля версий. А чтобы всё было по взрослому, то она должна поддерживать систему исключений. Для чего было бы очень полезно использовать синтаксис git, а именно его правила в файлах .gitignore.

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

Поэтому решил что сделаю свою реализацию и выложу в открытый доступ. Однако в результате реализации стал замечать, что этот функционал я уже к своему коду "прибиваю гвоздями". Поэтому вместо готового кода решил выложить алгоритм преобразования правила .gitignore в регулярное выражение. Это позволит любому сделать реализацию на нужном ему языке программирования.

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

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