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

И всё же прогресс в квантовых технологиях заметен хотя бы по тому, какое внимание им уделяют крупнейшие корпорации. IBM ещё в 2018 году рапортовали о сотне тысяч пользователей платформы Quantum Experience, Microsoft создаёт quantum development kit, и даже J.P. Morgan пытается развить в компании quantum culture. Любопытно, что сейчас всё больше говорят о связи квантовых вычислений и искусственного интеллекта.

В конце ноября 2020 года я встретился с Алексеем Фёдоровым, одним из ведущих российских специалистов в области квантовых технологий, автором десятков научных публикаций, руководителем научной группы Российского квантового центра, профессором МФТИ и обладателем бесчисленного множества других регалий. Он многое рассказал о состоянии современной квантовой науки, о грядущих технологических внедрениях и об интересных задачах, которые можно решать прямо сейчас. Видеозапись интервью смотрите на YouTube, там же доступна и запись последующего доклада на конференции YaTalks.

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

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

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

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

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

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

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

Кластеризация — это такая магическая штука: она превращает большой объём неструктурированных данных в потенциально обозримый набор кластеров, анализ которых позволяет делать выводы о содержании этих данных.

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

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

Две леммы о разрастании — утверждения, использующиеся для доказательства ограниченности важных классов формальных языков: регулярных и контекстно-свободных. Важность этих классов для программистов понять легко: регулярные выражения (один из видов описания регулярных языков) в работе используются достаточно часто, а уж языки программирования, синтаксис которых описывается контекстно-свободными грамматиками, и подавно.

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

План такой: разбираемся, что такое регулярные языки и какова связь между регулярными выражениями и конечными автоматами, формулируем и доказываем лемму о разрастании для регулярных языков, используем её для доказательства нерегулярности нескольких языков. Затем похожий трюк проделываем с контекстно-свободными языками, по пути выясняя, как они связаны с регулярными языками и как обходить обнаруженные ограничения при помощи грамматик общего вида. Поехали!

КДПВ иллюстрирует процесс разрастания для КС-грамматик

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

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

В статье четыре примера. Два на C++, один на TypeScript и один на Python. Способность быстро писать относительно простые алгоритмы без багов — общая необходимость, она не зависит от специализации разработчика.

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

Меж тем, именно левый график получен при помощи «честного» генератора случайных чисел. Правый график тоже содержит сплошь случайные точки; но эти точки сгенерированы так, чтобы все маленькие квадраты содержали равное количество точек.

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

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

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

Пусть есть два игрока, A и B, которые многократно разыгрывают некоторую игру. Каждый игрок в каждом розыгрыше придерживается одной из нескольких стратегий — для простоты будем считать, что количество стратегий для обоих игроков совпадает и равняется $$. При выборе $$-й стратегии первым игроком и $$-й стратегии вторым игроком первый игрок получит выигрыш $$, а второй игрок получит такой же проигрыш — так уж устроены антагонистичные игры. Эти выигрыши можно записать в виде квадратной матрицы $$:

Игроки разыгрывают игру многократно и могут использовать разные стратегии в разных розыгрышах. Смешанная стратегия — это вектор вероятностей, сопоставленных каждой из чистых стратегий игрока. Каждый игрок выбирает одну из стратегий в очередном розыгрыше в соответствии с вероятность, определённой для неё его смешанной стратегией. Если обозначить через $$ и $$ смешанные стратегии игроков, то математическое ожидание выигрыша первого игрока будет равняться

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

Вот поиском таких равновесий мы сейчас и займёмся.

Коронавирус вносит свои коррективы в студенческую жизнь, но, пока ВУЗы решают, что им делать и как переходить на дистанционное обучение, прогрессивная часть преподавательского корпуса должна брать ситуацию в свои руки. Вот я и решил, что не буду ждать, пока мой alma mater придумает, как быть, а решил мгновенно перевести лекции в дистанционный режим.

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

TLDR: Вполне хватает связки ноутбук + планшет с пером + Zoom. Но есть нюансы.

Функция Аккермана — одна из самых знаменитых функций в Computer Science. С ней связан как минимум один фундаментальный результат и как минимум один просто важный. Фундаментальный результат, говоря аккуратно и непонятно, таков: существует всюду определённая вычислимая функция, не являющаяся примитивно-рекурсивной. Важный результат заключается в том, что лес непересекающихся множеств (также известный как disjoint set union) работает очень быстро.

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

Из текста ниже вы узнаете, что такое примитивно-рекурсивные функции и как выяснить, что функция Аккермана к таковым не относится. И, конечно, этот текст убедит вас в том, что это невероятно красивая конструкция и невероятно красивое рассуждение!

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

Недавно я побывал в гостях у Михаила Сергеевича Гельфа́нда в Институте проблем передачи информации. Мы поговорили о том, что такое биоинформатика, о её интересных приложениях, о том, чем могут быть полезны IT-специалисты в биоинформатике и что им для этого нужно выучить.

Под катом этой статьи вы найдете полную расшифровку нашего разговора, а видео можно посмотреть на YouTube.

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

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

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

Чтобы разобраться в этом, мы решили узнать мнения спикеров нашей конференции YaTalks, которая пройдёт в Москве 30 ноября. Среди наших спикеров — Александр krainov Крайнов, Андрей yafinder Плахов, Андрей styskin Стыскин, Евгений eross Россинский, Роман romas1982 Ивлиев. А вот и вопросы, на которые они сегодня отвечают:

— Какие события в мире IT за последний год запомнились тебе больше всего? Что интересного случилось, какие сейчас есть интересные тренды, на которые стоит обратить внимание?

— Какие важные книги/статьи/выступления на тему разработки случились за последний год? Что порекомендуешь изучить тем, кто хочет быть в теме?

— Что посоветуешь действующим разработчикам и тем, кто только учится? Чем заняться прямо сейчас, чтобы через год (два, пять, десять) быть востребованным на рынке труда?

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

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

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

Поэтому я не буду публиковать разборы всех 24 задач. Вместо этого я разберу шесть задач одного из квалификационных вариантов: другие решаются похожим образом.

Поисковые подсказки (саджест) — это не только пользовательский сервис, но ещё и очень мощная языковая модель, хранящая миллиарды поисковых запросов, поддерживающая нечёткий поиск, персонализацию и многое другое. Мы научились использовать саджест для того, чтобы предугадывать итоговый запрос пользователя и загружать поисковую выдачу до нажатия кнопки «Найти».

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

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

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

Мы решили посвятить процессам разработки наш следующий Team Leader Meetup, который пройдёт вечером 17 июня в московском офисе Яндекса. Регистрация открыта!

Нашими экспертами согласились быть:

• Анатолий anatolix Орлов, CTO, Ozon
• Алексей Катаев deusdeorum, Head of Software Development, SkyEng
• Александр Гутман, CTO, JoomPay
• Евгений Парамонов, руководитель разработки поисковых подмешиваний, Яндекс
• Андрей Плахов yafinder, руководитель отдела функциональности поиска, Яндекс

Сегодня они отвечают на некоторые вопросы, чтобы подготовить будущую дискуссию:

1. На какой основе построены процессы у вас в компании?
2. По вашему опыту, какой процент успеха команды определяется правильными процессами, а какой индивидуальным мастерством?
3. Бывают ли ситуации, в которых тимлид имеет полное право игнорировать любые процессы?
4. Расскажите какую-нибудь страшную историю из вашего опыта со словом «процесс»

Под катом — много огня, сарказм в адрес авторов вопросов, максимально различные мнения и, конечно, страшные истории.

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

Так что мы подготовили для вас следующие материалы:

• Специальный контест, содержащий задачи, похожие на те, что мы даём на интервью.
• Этот пост. В нём рассказывается, почему нужно проводить такие секции, а также разбираются все задачи контеста.
• Два видео, в которых разбираются задачи из контеста: в первом — задача попроще, во втором — две задачи посложнее. Из этих видео вы узнаете о типичных ошибках, допускаемых и при прохождении алгоритмических секций, и при написании продакшен-кода.

Когда кто-либо становится руководителем разработки, на него непременно обрушивается огромное количество новых, неожиданных задач, и для адаптации непременно требуется время. Однако период адаптации однажды завершится, и тогда встанет вопрос, как же развиваться дальше. Не менее актуальным является вопрос подготовки сотрудника к будущей роли руководителя. Как работать с разработчиком, чтобы из него как можно быстрее получился будущий лидер?

Мы выбрали пути развития руководителей разработки темой следующего Team Leader Meetup, который пройдёт вечером 28 ноября в московском офисе Яндекса. Обсудить эту тему можно будет с экспертами из крупных IT-компаний. Регистрация ещё открыта.

В этот раз нашими экспертами стали:

• Николай Крапивный, руководитель бекенд-разработки, Badoo
• Роман romas1982 Ивлиев, CTO, mos.ru
• Александр Поломодов, руководитель отдела исследований и разработки, Tinkoff.ru
• Борис Тоботрас, директор центра программных решений, Инфосистемы Джет
• Виктор Ламбурт, руководитель направления рекомендательных продуктов, Яндекс
• Игорь Кураленок, генеральный директор, Лига Экспертов

Сегодня на Хабре мы задаём им ряд вопросов, чтобы задать тон будущей дискуссии:

1. Какие советы вы бы дали вашему коллеге – сильному разработчику, который недавно, буквально вчера, стал тимлидом? С каких конкретных, понятных действий ему стоило бы начать свою работу в новой должности?
2. Какие книги или статьи вы бы порекомендовали прочитать руководителю разработки? А какие ресурсы имеет смысл изучать на регулярной основе?
3. Сколько времени стоит уделять работе над техническими задачами, а сколько – над задачами, связанными с управлением коллективом? На что ещё может или должен тратить своё время тимлид?

С момента прошлого большого обновления «Королёв» прошло больше года. Идеи, вошедшие в тот релиз, получили за это время дальнейшее развитие и нашли новые применения. В обновлении «Андромеда» мы сфокусировались на тех аспектах работы поисковой системы, которые позволяют нашим пользователям решать как можно больше задач быстро и удобно.

Сегодня мы традиционно расскажем читателям Хабра о проделанной нами работе.

24 января 2018 года в Яндексе прошёл первый Team Leader meetup. Мероприятие посетили в общей сложности порядка семидесяти руководителей разработки из различных компаний.

Мы хотели, чтобы участники встречи были активно вовлечены в дискуссию, поэтому сразу выбрали в качестве основного формат панельной дискуссии в противовес стандартным презентациям. Таким образом, в разговоре участвовали сразу несколько экспертов из ведущих IT-компаний: Яндекса, Mail.Ru, Skolkovo Foundation, Phillips Innivation Labs RUS, 1C GAMES STUDIO. У слушателей в зале была возможность реагировать на высказывания экспертов при помощи специального бота, который демонстрировал их эмоции в реальном времени на специальном экране, расположенном прямо в зале.

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

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