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

Привет!

Этим постом начинается обзор задачек по алгоритмам, которые крупные IT-компании (Яндекс, Гугл и тп) так любят давать кандидатам на собеседованиях (если плохо пройти собеседование по алгоритмам, то шансы устроиться на работу в компанию мечты, увы, стремятся к нулю). В первую очередь этот пост предназначается для тех, кто не имеет в своем арсенале опыта олимпиадного программирования, тяжеловесных курсов по типу ШАДа или ЛКШ, в которых тематика алгоритмов разобрана достаточно серьезно, но кто хочет начать подготовку к собеседованиям или же тем, кто хочет освежить свои знания в какой-то то определенной теме.

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

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

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

Здравствуйте, уважаемые читатели. В этой статье речь пойдет об одном подходе к автоматическому порождению программ по блочной модели задачи, к решению обратной задачи (восстановления модели исходной проблемы по уже порожденной программе), а также к решению проблемы верификации порожденных программ. Сама по себе тема очень серьезная, но статью я, по возможности, постараюсь сделать популярной (без тяжеловесного обзора аналогов, строго оформленной теоретической части и прочих сложностей), с примерами и описанием различных применений.
Читать полностью »

«Цель этого курса — подготовить вас к вашему техническому будущему.»

imageОсталось опубликовать 2 главы…

Моделирование — III

Я продолжу общее направление, заданное в предыдущей главе, но на этот раз я сконцентрируюсь на старом выражении «Мусор на входе – мусор на выходе», которое часто сокращают как GIGO (garbage in, garbage out). Идея в том, что если вы поместите неаккуратно собранные данные и неверно определенные выражения на вход, то на выходе вы можете получить только некорректные результаты. Так же неявно предполагается и обратное: из наличия точных входных данных следует и получение корректного результата. Я покажу, что оба эти предположения могут быть ложными.
Читать полностью »

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

В статье предложен оригинальный математический аппарат «набор автоэнкодеров с общим латентным пространством», который позволяет выделять абстрактные понятия из входных данных и демонстрирует способность к «one-shot learning». Кроме того, с его помощью можно преодолеть многие фундаментальные проблемы современных алгоритмов машинного обучения, основанных на многослойных сетях и подходе «Deep learning».
Читать полностью »

С 10 по 22 сентября пройдет конкурс Яндекс.Блиц по мобильной разработке. Регистрация открыта. Блиц — это короткий путь в Яндекс: участникам топ-5 будет достаточно успешно пройти одну секцию собеседования вместо стандартных четырех.

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

Как писать программы на стыке мобильной разработки и алгоритмов? Конкурс и истории Яндекса - 1

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

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

image

Привет! В прошлой статье «бесконечный узор на основе простых чисел» я рассказал про алгоритм, который позволяет генерировать бесконечные красивые узоры, похожие то ли на инопланетные рисунки, то ли на нечто технологическое, подобно устройству микросхем. Однако, алгоритм для генерирования 2D узоров можно так же использовать и для создания мелодий. Подробнее под катом.
Читать полностью »

Всем привет! Меня зовут Миша Каменщиков, я занимаюсь Data Science и разработкой микросервисов в команде рекомендаций Авито. В этой статье я расскажу про наши рекомендации похожих объявлений и о том, как мы улучшаем их при помощи многоруких бандитов. С докладом на эту тему я выступал на конференции Highload++ Siberia и на мероприятии «Data & Science: Маркетинг».

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

Работа с числовыми матрицами в целом и решение систем линейных алгебраических уравнений в частности — классическая математическая и алгоритмическая задача, широко используемая при моделировании и расчёте огромного класса бизнес-процессов (например, при расчёте себестоимости). При создании и эксплуатации конфигураций «1С:Предприятия» многие разработчики сталкивались с необходимостью вручную реализовывать алгоритмы расчёта СЛАУ, а после — с проблемой длительного ожидания решения.
«1С:Предприятие» 8.3.14 будет содержать функционал, позволяющий значительно сократить время решения систем линейных уравнений за счёт использования алгоритма, основанного на теории графов.
Он оптимизирован для использования на данных, имеющих разреженную структуру (то есть содержащие не более 10% ненулевых коэффициентов в уравнениях) и в среднем и в лучшем случаях демонстрирует асимптотику Θ(n⋅log(n)⋅log(n)), где n — количество переменных, а в худшем (при заполненности системы ~100%) его асимптотика сопоставима с классическими алгоритмами ( Θ(n3)). При этом на системах, имеющих ~105 неизвестных, алгоритм показывает ускорение в сотни раз по сравнению с реализованными в специализированных библиотеках линейной алгебры (например, superlu или lapack).
Важно: статья и описанный алгоритм требуют понимания линейной алгебры и теории графов на уровне первого курса университета.
Читать полностью »

Построение орбит небесных тел средствами Python - 1

Системы отсчёта для определения орбиты

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

Используя данное предположение, рассмотрим движение одной и той же точки в двух различных системах отсчета К и К', из которых вторая движется относительно первой с произвольной скоростью Построение орбит небесных тел средствами Python - 2 — радиус-вектор, описывающий положение точки начала системы координат К' относительно системы отсчета К).

Будем описывать движение точки в системе К' радиус-вектором Построение орбит небесных тел средствами Python - 3, направленным из начала координат системы К' в текущее положение точки. Тогда движение рассматриваемой точки относительно системы отсчета К описывается радиус-вектором Построение орбит небесных тел средствами Python - 4:

Построение орбит небесных тел средствами Python - 5 (1)

а относительная скорость Построение орбит небесных тел средствами Python - 6

Построение орбит небесных тел средствами Python - 7 (2)
Читать полностью »

image Сейчас в прессе часто встречаются новости вида “AI научился писать в стиле автора Х”, или “ML создает искусство”. Посмотрев на это, мы решили – было бы здорово, если эти громкие заявления можно было бы проверить на деле.

Можно ли устроить борьбу ботов по написанию стихотворений? Можно ли сделать из этого понятную и воспроизводимую соревновательную историю? Теперь можно точно сказать, что это возможно. А о том, как написать свой первый алгоритм по генерации стихотворений, читайте дальше.
Читать полностью »