• Советские мечты о будущем



      Помните очаровательного котика, которые чихал в заставке советского мультфильма? Мы помним, и нашли его — вместе с ворохом другой рисованной фантастики. В детстве она пугала и обескураживала, поскольку поднимала серьезные, взрослые темы. Настала пора пересмотреть старые мультфильмы, чтобы узнать, о каком будущем мечтали в той стране.
      Читать дальше →
    • Sir Markdown. Лекция Яндекса

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


        У меня иногда складывается впечатление, что не он служит для нас, а мы служим для этого формата. Поэтому — сэр Markdown.

        Читать дальше →
      • Чтение на выходных: 17 независимых блогов по математике, алгоритмам и языкам программирования

          Сегодня мы подготовили очередную [наш IaaS-дайджест и материалы по структурированию кода] подборку полезных источников. На этот раз мы решили изучить тематическую ветку на Hacker News и рассказали о блогах, которые могут хорошо дополнить чтение «Хабра».

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

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

          Читать дальше →
          • +17
          • 54.2k
          • 1
        • 20 лет Яндексу. Лекция Ильи Сегаловича — человека, который придумал это слово

            Ровно 20 лет назад — 23 сентября 1997 года — в интернете появился Яндекс. Аркадий Волож, Илья Сегалович, Елена Колмановская представили на выставке Softool поисковую систему Yandex.ru. Открывали её, перерезав ленточку перед компьютером — потому что не понимали, как надо открывать сайты в интернете.

            Тогда он состоял из 5 тысяч сайтов, на которых было размещено около 4 гигабайт текста. Люди подходили к демонстрационному компьютеру, пробовали задавать запросы и получали ответы. На тот момент Яндекс учитывал морфологию русского языка, расстояние между словами и умел ранжировать документы.


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

            Читать дальше →
          • Доступно о криптографии на эллиптических кривых

            • Translation
            image


            Тем, кто знаком с криптографией с открытым ключом, наверно известны аббревиатуры ECC, ECDH и ECDSA. Первая — это сокращение от Elliptic Curve Cryptography (криптография на эллиптических кривых), остальные — это названия основанных на ней алгоритмов.

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

            До того, как ECC стала популярной, почти все алгоритмы с открытым ключом основывались на RSA, DSA и DH, альтернативных криптосистемах на основе модулярной арифметики. RSA и компания по-прежнему популярны, и часто используются вместе с ECC. Однако несмотря на то, что магия, лежащая в фундаменте RSA и подобных ей алгоритмов легко объяснима и понятна многим, а грубые реализации пишутся довольно просто, основы ECC всё ещё являются для большинства людей загадкой.

            В этой серии статей я познакомлю вас с основами мира криптографии на эллиптических кривых. Моя цель — не создание полного и подробного руководства по ECC (в Интернете полно информации по этой теме), а простой обзор ECC и объяснение того, почему её считают безопасной. Я не буду тратить время на долгие математические доказательства или скучные подробности реализации. Также я представлю полезные примеры с визуальными интерактивными инструментами и скриптами.
            Читать дальше →
          • Three Futamura Projections и не только

              Привет, хабрачеловек. Сегодня я расскажу тебе про некоторые фундаментальные вещи в computer science: частичные вычисления, три проекции Футамуры и суперкомпиляцию.
               
               

              1. Сразу к коду


              -- функция, которая возводит x в степень y (неотрицательную)
              power x y =
                  case y of
                      0 → 1
                      1 → x
                      _ → x * (power x (y - 1))


              Читать дальше →
            • Коды Рида-Соломона. Часть 1 — теория простым языком

                Добрый день! Меня зовут Максим, в YADRO, кроме всего прочего, я занимаюсь разработкой подсистемы, отвечающей за надежное хранение данных. Готовлю небольшой цикл статей про коды Рида-Соломона — теоретическую основу, практическую реализацию, применяемые на практике программные и аппаратные оптимизации. На Хабре и в остальной сети есть хорошие статьи по вопросам этой области — но по ним сложно разобраться, если ты новичок в теме. В этой статье я попытаюсь дать понятное введение в коды Рида-Соломона, а в следующих выпусках напишу, как все это запрограммировать.



                Читать дальше →
              • Сколько технологий нужно Яндексу, чтобы поиск находил свежие документы почти моментально

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




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


                  1. Почему свежесть?


                  Интерес к любому событию в течение нескольких дней угасает практически до нуля, если, конечно, это событие не получает какого-либо дальнейшего развития. Мы проводили исследование, из которого и родилось это утверждение: оказывается, в среднем 73% пользователей интересуется событием непосредственно в день, когда оно произошло, и только 3% читателей приходит на ресурсы спустя трое суток и более после публикации. С момента проведения этого исследования прошло уже много лет, но в целом ситуация не изменилась. И даже статьи на habrahabr.ru получают наибольшее количество поисковых переходов в первые несколько суток своего существования.

                  Читать дальше →
                • M* — алгоритм поиска кратчайшего пути, через весь мир, на смартфоне



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

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

                    • Tutorial

                    – А видела ты Черепаху «Как бы»?
                    – Нет, – сказала Алиса. – Я даже не знаю, кто это такой.
                    – Как же, – сказала Королева. – Это то, из чего делают «Как бы черепаший суп».

                                      Льюис Кэрролл, 
                                               «Алиса в Стране чудес»

                    — Судя по твоим речам, ты хорошо знаешь Фангорн? — спросил в ответ Арагорн.
                    — Какое там! — отозвался старик. — На это ста жизней не хватит. Но я сюда иной раз захаживаю.

                                     Джон Р. Р. Толкиен, 
                                              «Властелин Колец» — к слову о моём знании Haskell ;)


                    Homines dum docent, discunt. (Объясни другим — сам поймёшь.)
                                     народная латинская поговорка


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

                    Казалось бы о каком переменном числе параметров может идти речь при таком раскладе? Однако поразмыслив, посмотрев исходники printf или просто почитав wiki.haskell становится очевидным, что как раз ФП даёт ключ к достаточно красивому, хотя и несколько «казуистическому» решению этой задачи.

                    В настоящей публикации я рассмотрю один из способов реализации такого механизма на простых примерах, а также предложу некоторое обобщённое решение на базе Template Haskell, для превращения семейства обычных функций с последним параметром типа список в функцию с «как бы с переменным числом параметром» (далее по тексту просто «с переменным числом параметром»).
                    Читать дальше →
                  • От моноидов к алгебрам де Моргана. Строим абстракции на Haskell

                    Что общего у нормального распределения, конечных автоматов, хеш-таблиц, произвольных предикатов, строк, выпуклых оболочек, афинных преобразований, файлов конфигураций и стилей CSS? А что объединяет целые числа, типы в Haskell, произвольные графы, альтернативные функторы, матрицы, регулярные выражения и статистические выборки? Наконец, можно ли как-то связать между собой булеву алгебру, электрические цепи, прямоугольные таблицы, теплоизоляцию труб или зданий и изображения на плоскости? На эти вопросы есть два важных ответа: 1) со всеми этими объектами работают программисты, 2) эти объекты имеют сходную алгебраическую структуру: первые являются моноидами, вторые — полукольцами, третьи — алгебрами де Моргана.

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

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

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


                      Под катом — расшифровка и большинство слайдов.

                      Читать дальше →
                    • Тензорные разложения и их применения. Лекция в Яндексе

                        Предыдущая лекция с Data Fest была посвящена алгоритмам, необходимым для построения нового вида поиска. Сегодняшний доклад тоже в некотором смысле про разные алгоритмы, а точнее про математику, лежащую в основе множества из них. О матричных разложениях зрителям рассказал доктор наук и руководитель группы вычислительных методов «Сколтеха» Иван Оселедец.


                        Под катом — расшифровка и большинство слайдов.

                        Читать дальше →
                        • +47
                        • 21.7k
                        • 6
                      • Как посчитать перестановки. Лекция в Яндексе

                          Некоторое время назад в московский офис Яндекса приезжал Игорь Пак — ученый с множеством научных работ, выпускник мехмата МГУ и аспирантуры Гарварда. Сейчас Игорь работает в Калифорнийском университете. Его лекция в Яндексе была посвящена различным классам последовательностей и перестановкам. В том числе прямо по ходу лекции он представил выкладки, опровергающие гипотезу Нунана и Зайлбергера — одну из ключевых в области перестановок.



                          Под катом — подробная текстовая расшифровка и большинство слайдов.
                          Читать дальше →
                        • Анатомия KD-Деревьев

                          image

                          Эта статья полностью посвящена KD-Деревьям: я описываю тонкости построения KD-Деревьев, тонкости реализации функций поиска 'ближнего' в KD-Дереве, а также возможные 'подводные камни', которые возникают в процессе решения тех или иных подзадач алгоритма. Дабы не запутывать читателя терминологией(плоскость, гипер-плоскость и т.п), да и вообще для удобства, полагается что основное действо разворачивается в трехмерном пространстве. Однако же, где нужно я отмечаю, что мы работаем в пространстве другой размерности. По моему мнению статья будет полезна как программистам, так и всем тем, кто заинтересован в изучении алгоритмов: кто-то найдет для себя что-то новое, а кто-то просто повторит материал и возможно, в комментариях дополнит статью. В любом случае, прошу всех под кат.
                          Читать дальше →
                        • Аналитическое вычисление производных на шаблонах C++

                            Тут на днях писали про аналитическое нахождение производных, что напомнило мне об одной моей маленькой библиотечке на C++, которая делает почти то же, но во время компиляции.


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

                            using Formula_t = decltype (k * (_1 - r0) / (_1 + r0) * (g0 / (alpha0 - logr0 / Num<300>) - _1));    // сама формула
                            const auto residual = Formula_t::Eval (datapoint) - knownValue;    // регрессионный остаток
                            
                            // производные по параметрам:
                            const auto dg0 = VarDerivative_t<Formula_t, decltype (g0)>::Eval (datapoint);
                            const auto dalpha0 = VarDerivative_t<Formula_t, decltype (alpha0)>::Eval (datapoint);
                            const auto dk = VarDerivative_t<Formula_t, decltype (k)>::Eval (datapoint);

                            Вместо крокодилов, которые получатся, если брать частные производные функции на картинке вначале (вернее, некоторого её упрощённого варианта, но он выглядит не так страшно).

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

                            Под катом — небольшое описание, как оно там всё работает.
                            Читать дальше →
                          • С днём рождения, Эдсгер Вибе Дейкстраǃ

                              «Пусть тахорги в страхе воют,
                              Издавая визг и писк!
                              Ведь на них идет войною
                              Структуральнейший лингвист!»


                              image

                              • Очень жесткий правдоруб.
                              • Мог бы стать физиком-теоретиком (как Ричард Фейнман, который тоже родился 11 мая), но выбрал несуществующую на тот момент профессию — программист.
                              • Носит имя алгоритма поиска кратчайшего пути. Алгоритм был создан при решении железячной задачи «О нахождении оптимального пути передачи электрического тока всем существенным элементам цепи, минимизируя при этом расход меди».
                              • Непримиримый враг goto.
                              • Инициатор мема Considered harmful. «GOTO Statement Considered Harmful», "„GOTO Considered Harmful“ Considered Harmful", «„«GOTO Considered Harmful» Considered Harmful“ Considered Harmful?»
                              • Автор концепции семафора.
                              • Разработчик операционной системы THE (Technische Hogeschool Eindhoven).
                              • Стоял у истоков структурного программирования и распределенных вычислений.
                              • Не написал ни одной статьи на компьютере.

                              В обычной жизни Э.В.Дейкстра был чудаком: предпочитал простую ручку компьютеру, в его доме не было телевизора, он не пользовался мобильным телефоном, не смотрел кино. Когда его коллеги подготовили и издали к 60-летнему юбилею специальный сборник, Дейкстра ответил каждому из них личным благодарственным письмом, написанным от руки (61 адресат). Ученому его уровня и положения полагался секретарь, но Дейкстра отказался от этой привилегии и все предпочитал делать сам. Любил музыку и был хорошим пианистом.

                              Под катом несколько цитат Дейкстры, пара сокращенных эссе и список статей на русском языке.
                              (Вместе с компанией EDISON поздравляем Дейкстру и Фейнмана с днём рождения.)
                              Читать дальше →
                            • Почему в MIT больше не изучают SICP

                                На днях широкое внимание привлекло состоявшееся в начале года на митапе NYC Lisp выступление Джеральда Джей Сассмана, — одного из авторов великого и могучего SICP, а также крестного отца Scheme. Всему виной — ответ на вопрос, почему в MIT прекратили преподавать ставший легендарным курс 6.001, построенный на основе книги Сассмана и Абельсона «Структура и интерпретация компьютерных программ» (вопрос задан на 59 минуте).



                                Сассман назвал две причины; впрочем, сразу замечу, что в первой из них нет ничего особенного. К 1997 году Абельсон и Сассман уже устали рассказывать практически одно и то же с 80-ых, поэтому решили оставить преподавание и предложили главе кафедры самостоятельно решить, как поступить с самим курсом. Здесь удивляться действительно нечему — что угодно может осточертерть, если заниматься им достаточно долго.

                                Впрочем, вторая причина гораздо серьезнее. По мнению Сассмана, они с Абельсоном осознали, что учебный план SICP больше не в силах подготовить инженеров к тому, что представляет собой «инжиниринг» сегодня. В 80-ых и 90-ых инженеры строили сложные системы, комбинируя простые и хорошо изученные «части». Целью SICP было предоставить язык абстракций для рассуждений о таких системах.
                                Читать дальше →
                              • Шрифт Яндекса — Yandex Sans

                                  image

                                  23 апреля 2016 на Я.Субботнике для дизайнеров мы анонсировали наш собственный шрифт Yandex Sans. Мы работали над ним два с половиной года и очень счастливы наконец поделиться результатом. В этом посте я расскажу о том, зачем мы всё это задумали, как происходила работа, что получилось в результате и что будет дальше. Пост написан по мотивам нашего рассказа на Субботнике.
                                  Читать дальше →
                                • Более чем 80 средств мониторинга системы Linux

                                    Ниже будет приведен список инструментов мониторинга. Есть как минимум 80 способов, с помощью которых ваша машинка будет под контролем.



                                    1. первый инструмент — top

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