Как вам известно, вчера завершился очередной чемпионат ACM ICPC. Поздравляем студентов МФТИ, ИТМО, УрФУ и ННГУ с отличным выступлением, ребят из СПбГУ — с 1-м местом. Теперь мы приглашаем всех желающих принять участие в Яндекс.Алгоритме 2016. В этом году финал чемпионата пройдет в Минске.



В этом году впервые помимо традиционных призов победители получат возможность попасть на стажировку в Яндекс. 22 мая регистрация закроется и останется только следить за другими участниками в отборочных раундах. Квалификационный раунд продлится в этом году двое суток — с 21 по 22 мая. Раунды вновь будут оцениваться по системе TCM/Time. Для тех, кому интересно, какой сложности задачи их ждут, мы разобрали тур прошлогодней квалификации. Также у вас есть возможность потренироваться на нем.

UPDATE: Уже начался квалификационный раунд Яндекс.Алгоритма 2016, приходите порешать задачи, которые мы обязательно разберем в будущем. На наш взгляд, задачки не хуже, чем в прошлом году.

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

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

По мере изучения вопроса я обнаружил, что идея сама по себе не то чтобы очень нова – в нью-йоркской подземке аналогичные соревнования проходят с 1966 года. Что же касается московского метро, то ЖЖ-пользователь estrella-de-sur полгода назад проехал его за 12 часов 36 минут (расчётное время – 11 часов 50 минут) по правилу «один шаг на каждую станцию». Но у нас была другая задача – мы хотели выйти на каждой станции и по возможности красиво её сфотографировать. Это означало, что нам в большинстве случаев придётся ждать на ней следующего поезда. Исходя из этого я и строил расчёт.

Предупреждение: если вы умеете решать задачу коммивояжёра на 200 узлах (с помощью генетических алгоритмов или без них) – вас, скорее всего, ждут в другом месте. Можете просто пролистать пост и посмотреть картинки.

Какие алгоритмы используют социальные сети, чтобы осуществлять поиск по графу друзей? Как телекомпании выбирают, какую рекламу показывать, чтобы максимизировать прибыль? Как собрать геном из миллионов фрагментов? Как вычислить кратчайший путь из Нью-Йорка в Маунтин Вью в тысячи раз быстрее, чем это делают классические алгоритмы?

На Coursera появилась еще одна полезная специализация, созданная при участии Яндекса, — «Алгоритмы и структуры данных». Среди преподавателей не только представители Яндекса, Вышки, петербургского Computer Science Center, но и лекторы Калифорнийского университета в Сан-Диего, поэтому на этот раз все курсы специализации англоязычные.



Всего их пять, в конце слушателей ждет финальный проект. Один из них связан с биоинформатикой, второй — с поиском кратчайших путей в настоящих дорожных сетях и графах. В формате специализации все материалы доступны бесплатно. Оплата понадобится только в том случае, если вы захотите отправлять домашние задания на проверку и получить сертификат. Тогда вам нужно будет запрограммировать и сдать около 100 задач в тестирующую систему. Сделать это можно на C, C++, C#, Haskell, Java, JavaScript, Python2, Python3, Ruby и Scala.

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

Лето 2015 года. Сессия успешно сдана. Нормальный человек, наверное, скажет: «Ура! Свобода! Целый день буду играть в футбол и слетаю на море в Турцию». Но только не настоящий исследователь с пытливым умом. Я решил, что в любом случае буду работать над каким-нибудь собственным проектом… Но время непродуктивно со свистом неслось вперед. И тут мне в голову пришла светлая мысль: а почему бы не пойти на стажировку в Яндекс? Наверняка у них есть куча интересных исследовательских задач, к тому же это бесценный опыт работы в огромной компании с множеством профессионалов в своих областях, у которых есть чему поучиться. Тем, как попасть на стажировку в Яндекс, чем там можно заниматься и что вас ждет потом, я и хочу сегодня поделиться.

Для начала пару слов о себе. Зовут меня Муаммар, 21 год от роду, на данный момент являюсь студентом пятого курса мехмата МГУ. А еще я выпускник ШАДа, ведущий семинаров по Natural Language Processing в ШАДе и младший разработчик в команде речевых технологий Яндекса. Какой-то супергениальностью не отличаюсь, но люблю и умею работать. Пожалуй, хватит себя расхваливать, поговорим о стажировке. Кому интересно — добро пожаловать под кат!

Последние полгода всем знакомый интерфейс поисковой выдачи Яндекса (Search Engine Result Page — SERP) переезжает на новую архитектуру, с которой разработка неспецифичных фич становится очень быстрой, а разработка специфичных фич — прогнозируемой. Для большой распределенной команды из 40 фронтендеров это большой успех. Когда все было почти готово и новый код начали обкатывать в production экспериментах, оказалось, что серверная JS-шаблонизация в новой архитектуре ощутимо замедлилась.

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

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

Сегодня в питерском офисе Яндекса пройдет встреча со специалистами по параллельному программированию. К нам придут Жоэль Фальку из французской Лаборатории исследований в области информатики, Гор Нишанов из Microsoft и Кирк Шуп, который работает над Microsoft Azure. Специально для читателей Хабра мы попросили Гора Нишанова и Кирка Шупа рассказать об их личном опыте, отношении к C++, проблемах и развитии языка.


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

Сегодня мы расскажем вам историю об одном интересном баге в Яндекс.Браузере, исправление которого привело к значительному ускорению отрисовки во всем проекте Chromium. И помогут мне в этом Кирилл drBasic Плешивцев и Вадим Lof Петров, специалисты из нашей команды, которым и посчастливилось разбираться с проблемой. Передаю им слово.



Один не совсем обычный баг

Меня зовут Кирилл, я работаю в группе внутренних компонентов Яндекс.Браузера в Новосибирске. В один не совсем прекрасный день коллеги из тестирования Яндекс.Браузера воспроизвели проблему с проигрыванием видео через Flash Player. И поскольку именно наша группа отвечает за эту часть браузера (медиа, кодеки, вот это все), задача досталась мне. Баг, скажем так, не претендовал на оригинальность. Клик по кнопке Play приводил к черному прямоугольнику вместо корректного воспроизведения видео. Этот симптом я встречал и раньше, поэтому рассчитывал на достаточно быструю локализацию проблемы. Но я ошибался.

В начале года на Coursera открылся курс по машинному обучению от Яндекса и Вышки, о котором мы уже рассказывали. К моменту старта на него записались 14000 человек. Через час после открытия пользователи создали канал в Slack, где стали обсуждать программу. Сейчас слушателей уже 21000.



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

Специализация «Машинное обучение и анализ данных» состоит из пяти курсов и работой над собственным проектом. Обучение будет длиться несколько месяцев. Записаться на него можно до 19 февраля. Если вы не успеете это сделать, с 14 марта можно будет записаться на второй поток.

Авторы курса — сотрудники Яндекса, специалисты Yandex Data Factory, которые преподают на Физтехе. Константин Воронцов тоже среди них. Мы попросили некоторых из коллег рассказать, кому может быть полезна специализация и для чего она нужна. Также под катом — программа всех курсов.

Яндекс.Метрика сегодня это не только система веб-аналитики, но и AppMetrica — система аналитики для приложений. На входе в Метрику мы имеем поток данных — событий, происходящих на сайтах или в приложениях. Наша задача — обработать эти данные и представить их в подходящем для анализа виде.



Но обработка данных — это не проблема. Проблема в том, как и в каком виде сохранять результаты обработки, чтобы с ними можно было удобно работать. В процессе разработки нам приходилось несколько раз полностью менять подход к организации хранения данных. Мы начинали с таблиц MyISAM, использовали LSM-деревья и в конце концов пришли к column-oriented базе данных. В этой статье я хочу рассказать, что нас вынуждало это делать.

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

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

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



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

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

Сейчас в мире есть несколько основных моделей, по которым предсказывают погоду. Например, модель с открытым исходным кодом WRF, модель GFS, которые изначально являлись американской разработкой. Сейчас ее развитием занимается агентство NOAA.

Сегодня, 13 ноября, Международный день слепых. Он приурочен ко дню рождения педагога Валентина Гаюи, который в 1784 году открыл на личные средства первую в мире школу для незрячих детей. Это не праздник, а памятная дата, призванная напоминать обществу о существовании рядом людей с нарушениями зрения. В современном мире большая часть жизни людей переместилась в on-line, что открыло перед людьми с ограничениями здоровья новые возможности, но и породило новые вызовы.



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

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

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

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



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

Поводом для этого поста можете считать то, что мы добавили в приложения Яндекс.Музыки возможность слушать треки в высоком качестве (320kbps). А можете не считать. Итак.

Некоторое время назад коллеги стали получать от пользователей жалобы на то, что иногда при использовании Поиска и Яндекс.Браузера они видят ошибку SSL connection error. Расследование того, почему это происходило, на мой взгляд, получилось интересным, поэтому я хочу поделиться им с вами. В процессе разбора ситуации мы несколько раз меняли «подозреваемый» софт, изучили множество дампов, вспомнили устройство машины состояний TLS и в итоге даже разбирались в коде Хромиума. Надеюсь, вам будет интересно это читать не меньше, чем нам было исследовать. Итак.



Через некоторое время у нас были записи логов ошибок и pcap-файлы со схожим содержимым:



Всё выглядит так, будто сервер ответил некорректно и клиент прекратил хендшейк. Проанализировав «корректные» (принятые клиентом) и «некорректные» ответы сервера, мы поняли, что они идентичны.

Сегодня Яндекс вместе с организаторами конференции ZeroNights запускает конкурс по поиску уязвимостей в Яндекс.Браузере. Его участники смогут не только помочь миллионам пользователей, но и побороться за вполне материальные призы.

Публиковать пост на Хабрахабре только ради анонса конкурса было бы слишком скучно, поэтому я совмещу полезное с полезным и расскажу вам, почему наша команда внедряет в браузер дополнительные технологии защиты (например, проксирование трафика открытого wi-fi), а не ограничивается лишь закрытием уязвимостей. Было бы интересно обсудить с вами наше видение.



Конкурс
Уверен, читатели Хабра согласятся, что безопасность это не конечный результат, а процесс постоянного поиска и исправления проблем. Какую бы защиту вы ни разработали, рано или поздно ее кто-то пробьет. И чем больше у вашего продукта пользователей, тем чаще защиту будут испытывать на прочность.

Когда-то мы публиковали на Хабре курс по машинному обучению от Константина Воронцова из Школы анализа данных. Нам тогда предлагали сделать из этого полноценный курс с домашними заданиями и разместить его на Курсере.

И сегодня мы хотим сказать, что наконец можем выполнить все эти пожелания. В январе на Курсере пройдёт курс, организованный совместно Яндексом (Школой анализа данных) и ВШЭ. Записаться на него можно уже сейчас: www.coursera.org/learn/introduction-machine-learning.


Сооснователь Coursera Дафна Коллер в офисе Яндекса

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

Кроме того, мы верим, что после прохождения курса у человека должна остаться не только теория в голове, но и скилл «в пальцах». Поэтому все практические задания построены вокруг использования библиотеки scikit-learn (Python). Получается, что после прохождения нашего курса человек сможет сам решать задачи анализа данных, и ему будет проще развиваться дальше.

Под катом можно прочитать подробнее обо всех авторах курса и узнать его примерное содержание.

Любой специалист, причастный к тестированию веб-приложений, знает, что большинство рутинных действий на сервисах умеет делать фреймворк Selenium. В Яндексе в день выполняются миллионы автотестов, использующих Selenium для работы с браузерами, поэтому нам нужны тысячи различных браузеров, доступных одновременно и 24/7. И вот тут начинается самое интересное.



Selenium с большим количеством браузеров имеет много проблем с масштабированием и отказоустойчивостью. После нескольких попыток у нас получилось элегантное и простое в обслуживании решение, и мы хотим поделиться им с вами. Наш проект gridrouter позволяет организовать отказоустойчивый Selenium-грид из любого количества браузеров. Код выложен в open-source и доступен на Github. Под катом я расскажу, на какие недостатки Selenium мы обращали внимание, как пришли к нашему решению, и объясню, как его настроить.

БЭМ набирает популярность и становится актуальнее — например, недавно Google выпустил новую библиотеку блоков под названием Material Design Lite, реализованную по БЭМ-методологии. Команда БЭМ тоже не сидела без дела — мы выпустили новую версию библиотеки bem-components, на базе которой построены сайты и проекты не только Яндекса, но и других разработчиков.

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



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

Если вы хотите узнать на примерах, как мы пришли к нашим принципам разработки, добро пожаловать под кат.

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



Прошлой осенью в МФТИ, где я учился, на базовой кафедре Яндекса нам читали курс «Создание новых интернет-продуктов». Он задумывался как некий стартаперский практикум, в рамках которого нужно было придумать что-то, что успешно бы решало существующую проблему с помощью технологий Яндекса. Мы с несколькими моими однокурсниками подумали, что коммуникация людей, выключенных из привычного общения голосом с остальным слышащим миром, – задача, которая подходит под такие критерии. Согласно Всемирной организации здравоохранения, 10% жителей Земли имеют проблемы со слухом, 1,5-2% из них страдают тяжелыми нарушениями. В России их — 2,2 млн. Было бы здорово сделать что-то, что могло бы помочь этим людям в повседневной жизни.

Сегодня я хочу рассказать вам о новой технологии Яндекс.Браузера, которая защищает трафик при использовании публичного WiFi. А в ближайшее время в рамках конкурса на конференции ZeroNights любой желающий сможет попробовать найти в ней уязвимость. Но обо всем по порядку.



Небезопасный WiFi

Про риски, которые несет открытый или слабозащищенный WiFi, можно на Хабре и не рассказывать. Достаточно вспомнить самую крупную в истории утечку банковских данных, когда потеря миллионов номеров кредитных карт стала возможно во многом из-за использования ненадежного протокола WEP в WiFi-сетях. С тех пор прошло десять лет, но ситуация не стала лучше, ведь сейчас нас всюду окружают точки вообще без какого-либо шифрования. Их можно найти в кафе, в аэропортах и даже на автобусных остановках. При этом перехват такого WiFi может освоить любой школьник со сниффером. А простейшие устройства для взлома вообще продаются в интернете за считанные доллары.

Понятно, зачем теоретики находят эффективные алгоритмы решения задач какого-то класса, а потом практики их реализуют. Но теоретики стараются также доказать, что для некоторых задач эффективных алгоритмов (и даже вообще никаких алгоритмов) не существует. Что при этом им удаётся и не удаётся, и зачем это может быть нужно? В лекции речь идет о «проблеме остановки» и задачах, к которым она сводится, о знаменитом классе NP, а также о простых нижних оценках.



Лекция был прочитана в Малой Школе анализа данных, которую Яндекс организует для старшеклассников. Автор — Александр Шень. Окончил мехмат МГУ, под руководством Владимира Успенского, ученика Колмогорова, защитил диссертацию «Алгоритмические варианты понятия энтропии». Сейчас является сотрудником Института проблем передачи информации им. А.А. Харкевича РАН и Лаборатории Национального центра научных исследований Франции. Научные интересы: алгоритмы, колмогоровская сложность, логика, теория информации. Почти все книги, которые Александр Ханиевич написал о математике и программированию, находятся в свободном доступе.

Под катом — расшифровка лекции.