Рубрика «Алгоритмы»

Доказательство на стыке чистой математики и теории алгоритмов возвышает «квантовую запутанность» на совершенно новый уровень.
Насколько запутанна квантовая система? Ответ может быть невычислим - 1
Квантовая запутанность находится в сердце нового математического доказательства.Credit: Victor De Schwanberg/Science Photo Library

Читать полностью »

Введение

Здравствуйте! Я хочу рассказать Вам об идее алгоритма для генерации перестановок. Отмечу сразу, чтобы не показаться человеком открывающим Америку, я «гуглил» алгоритмы перестановок и их реализация отличалась. Если такой алгоритм уже существует, то пусть эта статья будет туториалом.
Читать полностью »

В преддверии старта курса «Алгоритмы для разработчиков» подготовили очередной перевод интересной статьи.


Задача: Дан граф и начальная вершина src в графе, необходимо найти кратчайшие пути от src до всех вершин в данном графе. В графе могут присутствовать ребра с отрицательными весами.

Мы уже обсуждали алгоритм Дейкстры в качестве способа решения этой задачи. Алгоритм Дейкстры является жадным алгоритмом, а его сложность равна O(VLogV) (с использованием кучи Фибоначчи). Однако Дейкстра не работает для графов с отрицательными весами ребер, тогда как Беллман-Форд — вполне. Алгоритм Беллмана-Форда даже проще, чем алгоритм Дейкстры, и хорошо подходит для распределенных систем. В то же время сложность его равна O(VE), что больше, чем показатель для алгоритма Дейкстры.

Рекомендация: Прежде, чем двигаться к просмотру решения, попробуйте попрактиковаться самостоятельно.
Читать полностью »

Скандал на конкурсе Kaggle: победитель сжульничал, алгоритм плохо оценивает шанс бездомных животных найти хозяев - 1

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

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

Как посчитать «похожесть» номеров в паспортах. И найти одинаковые даже с опечатками - 1

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

Раньше мы сравнивали номера документов строго: одинаковые — отлично, нет — извините. На ручной разбор из-за опечатки в номере уходили даже те карточки, у которых совпадали ФИО и адреса́ проживания. Такой подход излишне нагружал персонал заказчиков.

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

Это небольшое подведение итогов на пост “Быстрее, чем C++; медленнее, чем PHP”

Неблагодарное дело — «спорить» в комментариях, поэтому формулирую несколько мыслей в отдельный пост. Автор утверждал тут, тут, и еще много где, что у него большой стаж и богатый опыт в программировании на С++.
Читать полностью »

Привет!

Данный пост написан для новичков в олимпиадном программировании и начинающих разработчиков, готовящихся к прохождению алгоритмических интервью. В конце бонусная задачка. Если заинтересовал, прошу под кат :)
Читать полностью »

Привет! Представляю вам перевод статьи 6 Github Repos for web developers you should have a look at автора lampewebdev.

Однажды я пролистывал ленту dev.to и наткнулся на пост 6 GitHub проектов для быстрой прокачки знаний.

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

Поэтому, вот список моих любимых проектов GitHub для быстрой прокачки знаний, но созданный специально для веб-разработчиков.
Читать полностью »

Рассмотрим, как работают алгоритмы в банковском скоринге, какие метрики используются и какие параметры заемщика влияют на то, выдадут кредит или нет. В статье описывается прошедший конкурс с kaggle по предсказанию вероятности дефолта и приводятся влияющие на риск дефолта параметры.

Ошибка первого и второго рода

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

Для банка это — ошибка первого рода.

Но если банк будет вести жесткую политику, и никому не выдает кредиты, даже тем, кто вернул бы деньги, то банк не заработает на процентах. Отказ в кредите ответственному заемщику – ошибка второго рода.

Для оценки качества принимаемых алгоритмом решений, используется коэффициент Джини (GINI). В экономике и в Data Science коэффициент Gini имеет разную интерпретацию. Для кредитного скоринга он рассчитывается, как

GINI = 2 ROC AUC — 1

Для оценки банковского скоринга используется стандартная ROC AUC кривая!

Что влияет на выдачу кредита. Обзор соревнования Home Credit Default Risk - 1
Читать полностью »

Гибридные сортировки - 1

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

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


https://ajax.googleapis.com/ajax/libs/jquery/3.4.1/jquery.min.js