Алгоритмы *

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

Когда математики Джефф Кан и Гиль Калаи в 2006 году впервые выдвинули свою гипотезу о «пороге ожидания», они сами в нее не поверили. Их тезис – широкое утверждение о природе математических объектов, именуемых «случайными графами» — казался слишком категоричным, слишком всеобъемлющим, слишком смелым, чтобы претендовать на истинность. Казалось, что он скорее выдает желаемое за действительное, чем отражает математическую истину. Даже с такими оговорками, никто не смог опровергнуть эту гипотезу, и она быстро стала одной из важнейших нерешенных задач в своей области.

Теперь, более 15 лет спустя, двое молодых математиков из Стэнфордского университета сделали то, что, по мнению Кана и Калаи, граничит с невозможным. В В на удивление кратком препринте, выложенном в онлайне всего несколько недель назад, Джинён Пак и Гью Туан Фам дали полное доказательство этой гипотезы.

«Оно получилось поразительно простым и изобретательным», —  сказал Калаи, —  «Завораживающим. Чудесным».

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

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

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

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

В декабре 2021 года Github объявил, что открывает общий доступ к точной навигации по коду для всех публичных и приватных репозиториев с Python на сайте GitHub.com. Точную навигацию в коде обеспечивают стековые графы, новый фреймвввооорк с открытым исходным кодом, созданный в Github и позволяющий устанавливать правила привязки имен для языка программирования при помощи декларативного предметно-ориентированного языка (DSL). Стековые графы позволяют генерировать данные о навигации по стеку для конкретного репозитория, не требуя при этом какого-либо участия в конфигурировании со стороны владельца репозитория и не вмешиваясь в процесс сборки или другие задания, связанные с непрерывной интеграцией. В этом посте будет подробно рассказано, как работают стековые графы, и как с их помощью достигаются такие результаты.

(Этот пост написан на основе доклада, прочитанного автором на конференции Strange Loop в октябре 2021 года. Есть видео с этим докладом, там рассказано гораздо больше!)

О чем и для кого эта книга

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

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

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

Какой консенсус лучше для блокчейна, proof-of-work или proof-of-stake? Многие спорят об этом и приводят разные аргументы. В этой статье я рассмотрю основные преимущества и недостатки каждого варианта.

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

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

Всем привет! Если перед вами стоит задача проведения А/Б тестирования, то я помогу вам понять, как с помощью python сформировать однородные группы с помощью алгоритмов сходства объектов на основе косинусного и взвешенного косинусного расстояния для его проведения.

Любое натуральное число можно выразить через уникальное множество простых чисел, перемножение которых даёт исходное число. Для простых чисел это множество состоит из одного элемента – самого этого числа. Такую композицию можно называть мультипликативной, она очень хорошо известна и изучена.

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

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

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

C#. Guid.NewGuid(). Linux. Windows. Randomness or Uniqueness. RNG and PRNG. Performance. Benchmarking.

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

Всем привет!
Итак, тема статьи - кривые, их разбор, собственные примеры и как их можно использовать в геймдев.

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

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

Самые популярные функции высшего порядка - это map, filter и reduce. Мы все используем их, так как думаем, что синтаксис намного лучше, и писать их даже быстрее, чем старый способ for-in loop. Но так ли это на самом деле? Задумывались ли вы когда-нибудь о производительности этих встроенных функций? Они встроенные, поэтому, естественно, они должны быть лучше, не правда ли? Давайте погрузимся в эти функции вместе, чтобы выяснить, так ли это на самом деле.

В прошлый раз мы с вами разобрали Алгоритм Кнута — Морриса — Пратта, сегодня мы разберем не менее интересный, а на мой личный взгляд, даже наиболее любопытный и изящный алгоритм поиска подстрок в тексте, который подкупает своей гениальной простотой.

В данной статье мы рассказываем о том, как беспроводные сети могут помочь беспилотным машинам справляться с некоторыми “edge case” ситуациями и описываем подход для упрощения операции поиска объектов, влияющие на свойства беспроводных каналов. 

Итак, начнем!

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

В этом туториале описан алгоритм поиска в глубину (depth first search, DFS) с псевдокодом и примерами. Кроме того, расписаны способы реализации поиска в глубину в C, Java, Python и C++.

“Поиск в глубину” или “обход в глубину” — это рекурсивный алгоритм по поиску всех вершин графа или дерева. Обход подразумевает под собой посещение всех вершин графа.

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