алгоритм - Самое интересное в блогах
Чтобы решать «нерешаемые» задачи, нужно знать алгоритмы
Артем Мурадов — Senior Software Development Engineer в Amazon и автор курса «Алгоритмы: roadmap для работы и собеседований». Уже больше 14 лет он использует алгоритмы для решения рабочих задач и прохождения собеседований. С помощью алгоритмов он повышал производительность приложений, побеждал в спорах с коллегами и ускорял исследование ДНК. Даже попасть в Amazon ему помогло знание алгоритмов.
Мы пообщались с Артемом, чтобы узнать о его опыте. Он подробно рассказал, как изучал алгоритмы и как они помогали ему в работе.
[Перевод - recovery mode ] Алгоритм поиска самой длинной подстроки палиндрома
Поиск самого длинного палиндрома в строке за O(n).
Реализация алгоритма Краскала на С#
В данной статье для реализации алгоритма будут рассмотрены:
1. Система хранения графа на основе List<>
2. Сортировка рёбер графа по весу
3. Система непересекающихся множеств
На просторах интернета есть множество ресурсов, посвященных данному алгоритму, однако все варианты реализации, встреченные мной, показались слишком сложными для понимания и использования. Хочу предложить более приближенный к реальности вариант.
План действий
1. Сортируем имеющиеся рёбра по весу.
2. Создаём новое множество и добавляем в него первое ребро.
3. Затем пытаемся добавить каждое новое ребро в имеющееся множество, если возникает цикл - пропускаем.
4. Итоговое множество рёбер и есть искомое минимальное остовное дерево.
По сути, это и есть формулировка алгоритма Краскала. Звучит совсем просто.
Самый весёлый пункт из имеющихся - третий. Потому что проверка на появление циклов на каждом шаге будет не сильно простым занятием. Его мы модифицируем при помощи системы непересекающихся множеств.
Но для начала давайте рассмотрим систему хранения графа в программе.
Градиентный бустинг с CatBoost (часть 2/3)
В первой части статьи я рассказал про понятие градиентного бустинга, библиотеки, с помощью которых можно реализовать данный алгоритм и углубились в одну из этих библиотек. Сегодня продолжим разговор о CatBoost и рассмотрим Cross Validation, Overfitting Detector, ROC-AUC, SnapShot и Predict. Поехали!
До этого момента мы мерили качество на каком-то конкретном fold’e (конкретной выборке), то есть взяли разделили нашу выборку на обучающую и тестовую, это не совсем корректно, вдруг мы взяли какой-то непрезентативный кусок нашего датасета, на этом самом куске мы получим хорошее качество, а когда модель будет работать с реальными данными, то с качеством все будет крайне грустно. Дабы избежать этого, необходимо использовать Cross Validation.
Разобьём наш датасет на кусочки и дальше будем обучать модель столько раз, сколько у нас будет кусочков. Сначала обучаем модель на все кусках кроме первого, нам нем будет происходить валидация, потом на втором будет происходить такая же ситуация и все это дело будет повторяться до последнего кусочка нашей выборки:
Распознаем фигуры по массиву точек: эллипсы и не выпуклые фигуры
Данная статья является продолжением предыдущей статьи о распознавании простых многоугольников по нарисованной линии. В данной части будут рассмотрены алгоритмы распознавания эллипсов и алгоритм распознавания невыпуклых многоугольников.
Как муравьи решают проблемы коммивояжёров
В математике и программировании порой используются необычные названия явлений, объектов и алгоритмов. Но почти всегда такие названия позволяют быстро понять суть описываемых сущностей. Возьмём, к примеру, широко известную задачу о коммивояжёре — найти кратчайший путь между заданными точками. И действительно, сразу представляется себе коммивояжёр, которому нужно обойти все дома в небольшом городке, но при этом затратить минимум усилий и времени. Для решения этой задачи используются разные алгоритмы, один из них называется «муравьиным». Для того, чтобы разобраться с этим алгоритмом, нам для начала нужно присмотреться к поведению муравьёв в их необычном организованном мире.
Проникающий взгляд: что в мешке у Деда Мороза?
Новый Год - чудесный праздник: веселый, сказочный, волшебный. Наряженные елки, запах мандаринов в воздухе. Идут последние недели декабря, настроение праздничное, и на работе тоже пора заниматься праздничными делами. Вот мы и решили побаловать наших читателей новогодней томографической статьей. Самая прекрасная традиция - дарить подарки на Новый год. Ко всем детям на планете приходят Дед Мороз, Санта Клаус и другие герои культурного наследия и приносят разные подарки. Вот и под нашим пристальным рентгеновским взором оказались новогодние игрушки - детские подарки. В статье мы расскажем об ожиданиях, полученных результатах и наконец ответим на вопрос, что же скрывается в мешке у Деда Мороза.
Распознаем простые фигуры по массиву точек
В данной статье рассматривается простой алгоритм распознавания нарисованного пользователем многоугольника. Алгоритм преобразует набор точек, предоставленный пользователем, в точки многоугольника, удаляя точки находящиеся на прямых. Так же алгоритм может на базовом уровне распознавать окружности.
Данный алгоритм не претендует на уникальность. Однако, я постарался детально расписать как он работает без сложной математики, за исключением, быть может свертки.
Закат эпохи алгоритма MD5?
Почему алгоритм хеширования MD5 постепенно выходит из использования? Разберёмся в его работе и поймём, что же нужно солить.
[Перевод] Когда босс — алгоритм, который заставляет работать с полшестого утра
Курьеры сделали самоизоляцию возможной, и это не преувеличение. Как в России, так и за рубежом благодаря им народ смог пережить самые жесткие ограничения во время пандемии. Но обычные люди даже не догадываются, что работа курьера куда сложнее, чем кажется на первый взгляд.
На сайте Mother Jones я с интересом прочитал историю девушки-курьера, которую чуть не сломал компьютерный алгоритм. Работая давно в IT, мы еще никогда не смотрели на рабочие сервисы и программы под таким углом. Поэтому посчитали своим долгом сделать перевод статьи и поделиться им с вами.
Цифровой водяной знак на основе дискретного Wavelet-преобразования
Цифровой водяной знак на основе дискретного Wavelet-преобразовании.
Python: самое короткое решение 41 задачи из проекта Эйлера
Сегодня мы решим 41-ю задачу из Проекта Эйлера в 6 строк кода. Сделаем это сначала в развёрнутом виде, а потом максимально сократим решение.
Получение патента на свой алгоритм: личный опыт
Вам нравится изображение выше? А насколько? Что такое «привлекательность изображения» и как она раскладывается в математические формулы? Можно ли алгоритмически определить, какое из двух изображений больше понравится людям? А можно ли это запатентовать?
Меня зовут Михаил Диченко, я аналитик компании «Люксофт». Ранее я задался подобными вопросами, а в итоге получил американский патент на свой алгоритм и выпустил основанное на нём приложение. А поскольку на Хабре мало у кого есть опыт патентования своих наработок, решил поделиться своим.