• Алгоритмическая теория информации и случайность индивидуальных объектов

      Понятие энтропии в середине XX века ввёл Клод Шеннон. Её можно интуитивно описать как «среднее количестве битов информации в одном значении случайной величины». Но её нельзя применить к индивидуальным объектам (скажем, к тексту романа или ДНК) — где нет ансамбля многих однородных объектов, нет и случайных величин.



      В середине 1960-х годов разным людям (Колмогоров, Соломонов, Левин, Чейтин) стало понятно, что можно определять количество информации (сложность) индивидуального объекта как минимальную длину программы, которая этот объект порождает (при естественных ограничениях на язык программирования). Возникла алгоритмическая теория информации, которая оказалась связанной с разными областями: от философских вопросов оснований теории вероятностей (когда мы отвергаем статистические гипотезы?) до комбинаторики (неравенства, связывающие размеры множеств и их проекций) и теории вычислимости.

      Лекцию, которую мы выбрали для вас сегодня, читал на факультете компьютерных наук Вышки известный математик Александр Шень. Когда-то он под руководством Владимира Успенского, ученика Колмогорова, защитил диссертацию «Алгоритмические варианты понятия энтропии».
      Читать дальше →
      • +34
      • 18,8k
      • 5
    • Как решать вступительный экзамен в Школу анализа данных Яндекса

        Лето — время вступительных экзаменов. Прямо сейчас завершается отбор в Школу анализа данных Яндекса — идут собеседования для тех, кто уже сдал экзамен. В ШАД преподают машинное обучение, компьютерное зрение, анализ текстов на естественном языке и другие направления современной Computer Science. Два года студенты изучают предметы, которые обычно не входят в университетские программы, хотя пользуются огромным спросом как в науке, так и в индустрии. Учиться можно не только в Москве — у Школы открыты филиалы в Екатеринбурге, Минске, Киеве, Новосибирске, Санкт-Петербурге. Есть и заочное отделение, на котором можно обучаться, смотря видеолекции и переписываясь с преподавателями московской Школы по почте.



        Но для того, чтобы поступить в ШАД, нужно успешно пройти три этапа — заполнить анкету на сайте, сдать вступительный экзамен и прийти на собеседование. Ежегодно в ШАД поступают старшекурсники, выпускники и аспиранты МГУ, МФТИ, ВШЭ, ИТМО, СПбГУ, УрФУ, НГУ и не все они справляются с нашими испытаниями. В этом году мы получили анкеты от 3500 человек, 1000 из которых была допущена к экзамену, и только 350 сдали его успешно.

        Для тех, кто хочет попробовать себя и понять, на что он способен, мы подготовили разбор вступительного экзамена этого года. С вариантом, который мы выбрали для вас, справились 56% решавших его. В этой таблице вы можете увидеть, сколько человек смогли решить каждое из заданий в нём.
        Задание 1 2 3 4 5 6 7 8
        Решило 57% 68% 40% 35% 29% 12% 20% 6%

        Но для начала хотелось бы объяснить, что мы проверяем экзаменом и как подходим к его составлению. В самые первые годы существования ШАД письменного экзамена не было, так как заявок было ещё немного, и со всеми, кто прошёл онлайн-тестирование, получалось поговорить лично. Но зато и собеседования были дольше; некоторые выпускники вспоминают, как с ними беседовали по шесть часов, предлагая много сложных задач. Потом поступающих стало больше – и в 2012 году появился письменный экзамен.
        Читать дальше →
      • Как мы работали над редизайном Яндекс.Денег

          Меня зовут Дарья Калинина, и в Яндекс.Деньгах я отвечаю за развитие интерфейсов. Сейчас мы кардинально меняем внешний вид нашего сайта для авторизованных пользователей (мы называем этот раздел сайта кошельком — по сути это наш «интернет-банкинг»). И я хочу рассказать вам о том, как и почему мы пришли к таким визуальным решениям и что планируем делать дальше.

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



          Мы приступили к редизайну в начале 2014 года после большого исследования с юзабилити-тестированием и анализом статистики.
          Читать дальше →
        • Как устроен цвет

            Почему формальное определение цвета то ли есть, то ли нет, и связано ли это с тем, что его дал тот самый Шрёдингер? Что имел в виду Вейнберг, когда назвал свою революционную статью «Геометрия цветов»? Почему у цветового треугольника два угла, хотя интуитивно кажется, что должен быть один? Почему обычный детский рисунок показывает, что у автора всё в порядке с цветовосприятием, и зачем художник-академист всю жизнь учится его отключать? Почему в цветовом пространстве находятся кластеры, но они не находятся? Почему любая женщина знает о явлении метамерии окрасок, а ученые всё время забывают? Сколько должно быть цветовых каналов у хорошего фотоаппарата? А у монитора? А почему ответ разный? А красок у принтера?

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



            Лектор — Дмитрий Николаев, заведующий сектором зрительных систем в Институте проблем передачи информации им. А.А. Харкевича РАН. Кандидат физико-математических наук, защитил диссертацию на тему «Алгоритмы цветовой сегментации, применимые в условиях сложного освещения сцены».
            Читать дальше →
          • Как сделать кэш браузера не таким бесполезным, как обычно

              Хочу рассказать вам о том, как мы в Яндекс.Браузере попытались сделать кэш не таким бесполезным для пользователей, как обычно. В недавно вышедшей новой бете Яндекс.Браузера для Android (планируем и для других ОС) можно получить доступ к недавно посещенным сайтам даже при отсутствии соединения с интернетом. Причём работать это должно гораздо надёжнее и удобнее, чем всё, что вы видели до этого.



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

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







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

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

                  Но сам я местный, и сегодня расскажу вам страшную историю, о том, что мешало спать (лично мне) долгие годы. И это не налоги (с ними все нормально), это — геокодер Яндекс.Карт!
                  Геокодер — это один из HTTP-сервисов Яндекс.Карт, получающий в запросе текстовое представление адреса и возвращающий в ответе найденные на его основании объекты. Либо наоборот: получающий координаты и отвечающий адресом.

                  Именно геокодер подскажет, где на карте находится чудная страна Краковия. И именно он будет главным героем этой истории, завязка которой была описана совершенно в другой книге — в древнем фолианте Пользовательское соглашение API Яндекс.Карт. Легенда гласит, что существует ограничение на количество запросов к функции геокодирования. Максимально допустимо делать в сутки не более 25 000 запросов к HTTP и JS геокодеру в сутки. Или овсянка, сэр.

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



                  Что делать? Для наглядности достанем из кустов рояль — 8 лет назад на Хабре засветился проект «еСоседи» — «Карта интересных мест». Все эти годы я продолжаю работать над ним.
                  Читать дальше →
                  • +28
                  • 36,2k
                  • 9
                • Разбор всех задач финального раунда Яндекс.Алгоритма 2015

                    Сегодня завершился финал Яндекс.Алгоритма — ежегодного чемпионата по спортивному программированию, который организует Яндекс. В 2015 году состязание проходило полностью в онлайне — на платформе Яндекс.Контест. Заявки на участие подали программисты из 73 стран. Больше всего участников — из России, Украины, Беларуси, Казахстана, Индии, США, Японии и Китая, но вообще география чемпионата крайне обширна — Бразилия, Индонезия, Перу, Доминиканская Республика, Мозамбик, Сенегал, Каймановы острова. 8,9% зарегистрировавшихся — девушки. Примерно половина всех участников — студенты. Всего мы получили заявки от 3722 человек, из которых до финала дошли 28.

                    А победителем Яндекс.Алгоритма-2015 стал Геннадий Короткевич. Он по привычке показал лучший результат, решив в финальном раунде пять из шести задач и получив при этом 80 минут штрафного времени. Геннадий занимал первое место в чемпионате Яндекса и в 2013, и в 2014 годах.



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

                    Задачи для Яндекс.Алгоритма составляет международная команда, в которую входят как сотрудники Яндекса, так и приглашённые эксперты — в том числе победители и финалисты состязаний ACM ICPC и Topcoder Open. И мы по традиции подготовили для вас разборы всех заданий. Решить все из них никому не удалось. Больше всего участников справились с задачей B, а вот задания A и D решило всего по одному человеку.
                    Читать дальше →
                    • +44
                    • 62,1k
                    • 1
                  • Мин-плюс многочлены, циклические игры и теорема Гильберта о нулях

                      В этом докладе рассматриваются алгоритмические задачи, связанные с мин-плюс многочленами. Конкретнее — разрешимость систем линейных мин-плюс многочленов. Эта задача оказывается полиномиально эквивалентной задаче об определении победителя в так называемых циклических играх (mean payoff games), известной задаче, лежащей в пересечении сложностных классов NP и coNP. Второй результат, который обсуждается в ходе доклада, это аналог теоремы Гильберта о нулях для мин-плюс алгебры.



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

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

                      Под катом — полная расшифровка лекции.
                      Читать дальше →
                      • +29
                      • 12,9k
                      • 8
                    • Настоящее и будущее C++. Интервью с Эриком Ниблером

                        Эрик Ниблер — известный эксперт по C++, один из важных контрибьюторов Boost, человек, который добавил в стандарт библиотеку Ranges.

                        26 августа в рамках C++ Party Эрик выступит в новосибирском офисе Яндекса, где как раз расскажет о библиотеке и поговорит с гостями о новых стандартах C++.

                        image

                        Я заранее поговорил с Эриком и задал ему несколько вопросов от себя и коллег о том, каким он видит настоящее и будущее C++, что ему кажется самым важным в программировании, будет ли в C++ когда-нибудь нормальный менеджер пакетов, модули, что будет со стандартной библиотекой и о многом другом.

                        Кстати, если у вас есть ещё хорошие вопросы к Эрику, — их можно задать в комментариях, и мы попросим его на них ответить.
                        Читать дальше →
                      • 15 тривиальных фактов о правильной работе с протоколом HTTP

                          Внимание! Реклама! Пост оплачен Капитаном Очевидность!

                          Ниже под катом вы найдёте 15 пунктов, описывающих правильную организацию ресурсов, доступных по протоколу HTTP — веб-сайтов, «ручек» бэкенда, API и прочая. «Правильный» здесь означает «соответствующий рекомендациям и спецификациям». Большая часть ниженаписанного почти дословно переведена из официальных стандартов, рекомендаций и best practices от IETF и W3C.



                          Вы не найдёте здесь абсолютно ничего неочевидного. Нет, серьёзно, каждый веб-разработчик теоретически эти 15 пунктов должен освоить где-то в районе junior developer-а и/или второго-третьего курса университета.

                          Однако на практике оказывается, что великое множество веб-разработчиков эти азы таки не усвоило. Читаешь документацию к иным API и рыдаешь. Уверен, что каждый читатель таки найдёт в этом списке что-то новое для себя.
                          Читать дальше →
                        • Опасный мир вредоносных расширений и защита от них. Опыт Яндекс.Браузера

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



                            Весной 2014 года поддержка Яндекс.Браузера обратила внимание на стремительно растущее число обращений от пользователей, в которых говорилось о «заражении браузера вирусом» и агрессивной рекламе, всплывающей на посещаемых сайтах. Наиболее распространенным симптомом была подмена или добавление новых рекламных блоков на популярных в Рунете сайтах (ВКонтакте, Яндекс, ...). При этом разработчики вредоносных расширений не утруждали себя заботой о пользователях и не брезговали откровенно мошеннической или шок-рекламой. Встречались и другие проявления. Например, автоматическое открытие вкладки с определенным сайтом, подмена поиска по умолчанию или даже воровство данных.

                            В определенный момент количество таких обращений стало достигать 30% от всех сообщений в поддержку. Наблюдения поддержки также подтверждались статистикой основных причин удаления нашего браузера (при удалении пользователям предлагается описать причину). Многие люди искренне считали, что это наша команда решила таким вот способом монетизировать браузер. За короткий период времени количество удалений Яндекс.Браузера, связанных с деятельностью сторонних вредоносных разработок, удвоилось. Нужно было срочно вмешаться и начать работать над этой проблемой.
                            Читать дальше →
                          • 36 на Fronttalks. Доклад о том, о чём нигде не рассказывают

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

                              Я благодарен организаторам за то, что мне посчастливилось выступить с таким докладом.



                              В этом году состоится третья по счёту конференция для фронтенд-разработчиков FrontTalks. На этот раз я не докладчик, а один из организаторов, и теперь у меня самого есть возможность «рисковать» и составлять программу конференции так, чтобы вам было интересно. Ниже расскажу немного о том, что у нас получилось.
                              Читать дальше →
                            • История одного факапа Яндекс.Навигатора. В шести действиях с прологом и раскаянием

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



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

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

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



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

                                  Под катом — расшифровка лекции.
                                  Читать дальше →
                                  • +35
                                  • 16,4k
                                  • 2
                                • Безопасный WiFi в Яндекс.Браузере. О защите для тех, кто ещё не успел HTTPS

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



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

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

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

                                      image

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

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

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

                                        image

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

                                        Если вы хотите узнать на примерах, как мы пришли к нашим принципам разработки, добро пожаловать под кат.
                                        Читать дальше →
                                      • Курс по машинному обучению на Coursera от Яндекса и ВШЭ

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

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


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

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

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

                                          Под катом можно прочитать подробнее обо всех авторах курса и узнать его примерное содержание.
                                          Читать дальше →
                                        • Big Data от А до Я. Часть 2: Hadoop

                                          • Tutorial
                                          Привет, Хабр! В предыдущей статье мы рассмотрели парадигму параллельных вычислений MapReduce. В этой статье мы перейдём от теории к практике и рассмотрим Hadoop – мощный инструментарий для работы с большими данными от Apache foundation.

                                          В статье описано, какие инструменты и средства включает в себя Hadoop, каким образом установить Hadoop у себя, приведены инструкции и примеры разработки MapReduce-программ под Hadoop.


                                          Читать дальше →
                                          • +32
                                          • 158k
                                          • 8