Блог Яндекса Голосов: 7 Адрес блога: http://company.yandex.ru/blog/ Добавлен: 2007-12-13 21:24:18 блограйдером Luber

Первый год факультета компьютерных наук

2015-04-28 12:59:03 (читать в оригинале)

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

Михаил Левин, руководитель службы анализа больших данных в Яндексе, один из преподавателей факультета компьютерных наук ВШЭ:

На факультет поступило неожиданно много студентов. Сначала на «Прикладной математике и информатике» у нас было сто бюджетных мест. Однако к середине июля мы получили куда больше ста заявлений только от олимпиадников, которые могли рассчитывать на поступление без экзаменов. В итоге за счёт ВШЭ увеличили количество бюджетных мест и набрали около двухсот человек — почти в два раза больше, чем собирались. Вместо одного лекционного потока сформировали два.

В первом и втором модулях студенты изучали программирование на Python и C++, в третьем начался базовый курс алгоритмов. Кроме того, первокурсникам преподавали математический анализ, дискретную математику, линейную алгебру и геометрию (на сайте ВШЭ можно изучить общую программу бакалавриата целиком). Многие семинаристы — сотрудники Яндекса. Лекторами по некоторым курсам также были специалисты из Яндекса, а кроме того мы пригласили хороших лекторов из НМУ, с мехмата. Большинство наших семинаристов и лекторов получили от студентов высокие оценки.

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


С первого курса студенты ПМИ ФКН начинают проектную работу. Проектный семинар стартовал в третьем модуле. Индивидуальными проектами наших студентов руководят более 25 менторов из IT-индустрии и науки. Темы проектов простираются от приближенных решений задачи коммивояжера, архиватора и написания ботов, хорошо играющих в 2048, до веб-схемы метро с поиском маршрута, распознавателя капчи, кластеризации раковых транскриптов и сервиса статистического анализа истории рыночных цен финансовых активов, в общем — смотрите сами. В конце третьего модуля студенты сдали промежуточные отчёты, и сейчас у большинства из них уже есть работающие прототипы.

С первых дней на факультете начал работу центр студенческих олимпиад ВШЭ под руководством Михаила Густокашина. Тренировки проходят два раза в неделю — на факультете и в Яндексе. К нам поступили очень сильные олимпиадники, имеющие опыт в спортивном программировании, и результаты не заставили себя ждать. Две команды дошли до полуфинала международного студенческого чемпионата по программированию ACM ICPC, одна из них вышла в финал. Это очень сильный результат: команда состояла целиком из первокурсников, и ребята выступили лучше всех команд первокурсников в России.

Конечно, на факультете есть не только бакалаврские программы. У нас продолжает работать магистратура, в которой, в том числе, есть отделение ШАДа. Была разработана новая магистерская программа — «Математические методы оптимизации и стохастики», под руководством Владимира Спокойного. Также мы организовали аспирантскую школу по компьютерным наукам со своим научным семинаром.

В этом году на ФКН были созданы Коллоквиум и IT-лекторий. Коллоквиум — научное мероприятие, на нём выступали с лекциями различные российские и зарубежные ученые, например, Александр Шень, Штефан Хаар, Дмитрий Ветров, Илья Разенштейн, Глеб Гусев, Макс Канович, Владимир Спокойный и другие. IT-лекторий — место, где выступают специалисты их разных компаний и рассказывают об интересных проектах в IT-индустрии. Нас посетили представители Яндекса, Facebook, ВКонтакте, Одноклассников, Крока, SAP и других компаний.

Кроме того, Яндекс учредил стипендию имени Ильи Сегаловича, которая присуждается ежегодно трём аспирантам, трём магистрам и 10 бакалаврам факультета компьютерных наук. Недавно стали известны имена первых лауреатов стипендии.



В этом году приём документов в бакалавриат факультета компьютерных наук начнётся 20 июня, в магистратуру — 2 июня. С критериями приема можно ознакомиться на сайте приёмной комиссии Высшей школы экономики. Порядок приёма победителей и призёров олимпиад школьников на 2015 год будет опубликован не позднее 1 июня.

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

---

Яндекс.Алгоритм-2015

2015-04-21 12:37:35 (читать в оригинале)

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

Яндекс.Алгоритм состоит из нескольких отборочных раундов, в каждом из которых нужно решить пять задач за 100 минут. В финал, который состоится 6 августа, выйдут 25 лучших по результатам отбора. Призёров ждут денежные призы: 300 тысяч рублей за первое место, 150 — за второе и 90 — за третье. Кроме того, 512 сильнейших участников Алгоритма получат футболки от Яндекса.

Спортивное программирование — область, в которой нужно уметь решать очень сложные задачи за очень короткое время. Насколько это умение нужно программисту при написании промышленного кода? Мы задали этот вопрос сотрудникам Яндекса, которые занимались или занимаются спортивным программированием, и узнали, как этот опыт помогает (или мешает) им в работе.


Яндекс.Алгоритм проводится в третий раз. В 2013 и 2014 годах победу в чемпионате одержал белорус Геннадий Короткевич. Разбор задач чемпионатов прошлых лет можно найти в нашем техноблоге на Хабрахабре (задачи Яндекс.Алгоритма-2013 и Яндекс.Алгоритма-2014).

---

Колдунщик цветов: возвращение

2015-04-16 13:55:54 (читать в оригинале)

Если вы когда-нибудь задавались вопросом, какого цвета бедро испуганной нимфы, недоумевали, о каком таком «перванше» идёт речь в любимой книге, или хотели перекодировать нужный оттенок из RGB в HSV, вы уже наверняка знакомы с колдунщиком цветов Яндекса. Если нет, то вот он, просим любить и жаловать.


Колдунщик цветов появился в 2008 году. К нему быстро привыкли: кому-то он помогал в работе, кому-то просто нравилось вращать барабан и узнавать о существовании цветов вроде «бисмарк-фуриозо». Но летом прошлого года страница результатов поиска поменяла интерфейс, и некоторыми возможностями пришлось временно пожертвовать — в том числе и колдунщиком цветов. Зато вернулся он в улучшенном виде.

Старый колдунщик знал 234 цвета. В новом их стало 1010: мы взяли за основу несколько существующих списков именованных цветов (это те, за которыми закреплены конкретное название и координаты в стандартных цветовых моделях вроде RGB) и добавили несколько оттенков, названия для которых придумали сами. Теперь нужно было разложить эти цвета по порядку — чтобы людям было удобно пользоваться колдунщиком, переходы между соседними цветами должны быть плавными. Надо ли говорить, что это оказалось и сложнее, и интереснее, чем мы думали.

Так выглядел наш набор цветов до сортировки.


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

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

Такая физиология человеческого восприятия отражена в цветовой модели RGB. Это трёхмерное пространство, заданное осями, по которым увеличивается интенсивность красной (red), зеленой (green) и синей (blue) компонент. Поместить наши цвета в это пространство никакой проблемы не составляет — их координаты известны. Проблема — в плавности переходов от одного цвета к другому.


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

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

Одна из моделей, в которых визуальная однородность достигается математическими средствами, назвается CIELAB — в ней-то мы и решали нашу задачу. По своему устройству CIELAB принципиально отличается от RGB: оси координат в ней задают яркость и две пары противоположных цветов (красный — зеленый, синий — жёлтый).


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

Тут напрашивается решение с помощью алгоритма «ближайшего соседа»: выбираем точку, которая к нам ближе всего, добравшись до неё, ищем новую ближайшую точку и так далее. Однако алгоритм «ближайшего соседа» решает только локальную задачу, игнорируя картину в целом. Представьте себе архипелаг, острова которого разбросаны так же неравномерно, как 1010 цветов в нашем пространстве. Если путешествовать по ним, каждый раз двигаясь к ближайшему острову, мы в результате рискуем очень скоро оказаться, например, на южном краю архипелага, оставив не охваченными еще десять островов на севере. Тогда нам придется совершить длинный перелет, или, в нашем случае, — резкий переход от одного цвета к другому. Так что это решение нам не подходит.

Задача, с которой мы столкнулись, улучшая колдунщик цветов, представляет собой частный случай одной из самых известных задач комбинаторной оптимизации — задачи коммивояжёра. В классическом виде она заключается в том, чтобы найти самый короткий маршрут, который позволил бы коммивояжёру хотя бы раз оказаться в каждом из городов в его списке, а в конце пути вернуться в исходную точку. Правда, мы имели дело не с плоской картой, а с трёхмерным пространством, но в остальном картина похожа: коммивояжёру предстояло посетить пляж Бонди, пески пустыни, горный луг, Мичиганский университет и ещё 1006 пунктов и при этом пройти по оптимальному маршруту. Как и для большинства классических задач, для задачи коммивояжёра существуют готовые алгоритмы оптимизации. Применив их к нашему случаю, мы получили вот такой цветной путь коммивояжёра в 3D.


Теперь повторить путь коммивояжёра в цветовом пространстве CIELAB вы можете на странице результатов поиска. Просто поищите, например, [цвет Яндекса].

---

Новое Яндекс.Метро

2015-04-15 12:24:20 (читать в оригинале)

Сегодня мы выпустили обновлённое приложение Яндекс.Метро для Android. Теперь с его помощью жители Москвы могут пополнить транспортную карту «Тройка», а петербужцы — карту «Подорожник». Это позволит не тратить время в очереди в кассу. Средства поступают на карту сразу, перед поездкой её нужно только активировать: приложить к жёлтому информационному терминалу в московском метро или к визуализатору — в Петербурге. К оплате принимаются банковские карты Visa и MasterCard, а сам платёж обеспечивают Яндекс.Деньги. При пополнении «Подорожника» комиссия составит 3%, для карты «Тройка» комиссии нет.

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


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

Яндекс.Метро для Android доступно в Google Play. Обновлённая версия Метро для iOS появится в App Store в ближайшее время.

---

Яндекс.Карты на улицах городов

2015-04-10 13:39:09 (читать в оригинале)

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

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

Яндекс.Карты в Омске. Макет в полном размере

Немного другой проект мы запустили в Казани вместе с городским Комитетом по транспорту. Там стояла задача рассказать о маршрутах общественного транспорта, чтобы людям было проще выбрать нужный автобус или трамвай. И в декабре прошлого года на остановках Казани  появились макеты, созданные на основе Яндекс.Карт. На каждом макете представлена схема движения транспорта, который следует через остановку, и карта местности в радиусе 1,5-2 километров от неё. Прохожие могут не только выбрать подходящий транспорт, но и узнать о находящихся поблизости объектах — магазинах, школах и так далее. Макеты подготовлены на русском и английском языках, чтобы ими могли пользоваться и местные жители, и иностранные гости.

Яндекс.Карты в Казани. Макет в полном размере

Подобные проекты делаем не только мы. Иногда к нам приходят общественные организации или компании, которые хотят напечатать карту с расположением определенных объектов. И мы с удовольствием помогаем всем, кто делает полезные для городов проекты. А чтобы с нами было удобнее работать, мы создали сайт «Карты в городе». Там есть примеры уже готовых проектов и удобные формы для отправки запроса. Если у вас есть хорошая идея и для её реализации нужна карта, напишите нам через сайт. Мы или бесплатно выгрузим вам нужный фрагмент карты, или предложим другой формат сотрудничества.
 

Команда Яндекс.Карт