• Для доказательства 30-летней гипотезы из области информатики хватило двух страничек

    • Перевод

    Гипотеза «чувствительности» ставила в тупик многих выдающихся специалистов по информатике, но её новое доказательство оказалось настолько простым, что один исследователь смог свести его к единственному твиту



    Опубликованная этим летом работа ставит точку в почти 30-летней истории гипотезы, касающейся структуры фундаментальных строительных блоков компьютерных схем. Эта гипотеза «чувствительности» годами ставила в тупик многих выдающихся специалистов по информатике, но её новое доказательство оказалось настолько простым, что один исследователь смог свести его к единственному твиту.

    «Эта гипотеза была одной из самых раздражающих и позорных открытых задач во всей комбинаторике и теоретической информатике», — писал в своём блоге Скот Ааронсон из Техасского университета в Остине. «Список людей, пытавшихся доказать её, и не сумевших сделать это, представляет собой список самых выдающихся людей в дискретной математике и теоретической информатике», — добавил он в емейле.
    Читать дальше →
  • Как рисует браузер. Доклад Яндекса

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



      — Всем привет, меня зовут Костя. Удивительно — сейчас я работаю в команде виртуальной сети Яндекс.Облака. До этого я пять с лишним лет проработал в команде Браузера, так что сегодня буду говорить о вещах, общих для нас с вами.

      Читать дальше →
      • +31
      • 17,1k
      • 9
    • Собственный DHCP-сервер силами bash

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

        В данной статье я расскажу немного про протокол DHCP и некоторые тонкости из bash'а.
        Поднять паруса!
      • Как работает Git

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

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

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

        После прочтения для ещё более глубокого погружения можно обратиться к обильно комментируемому исходному коду моей реализации Git на JavaScript.
        Читать дальше →
      • Криптомайнер заразил тысячи NAS во всём мире, майнит около 428 евро в день

          С появлением Bitcoin скрытая установка криптомайнеров на чужих ПК стала отличным бизнесом. Но он быстро пошёл на спад с увеличением сложности майнинга. Примерно с 2013 года майнинг на CPU и даже на GPU стал практически бесполезным занятием, все перешли на ASIC.


          Рост сложности майнинга Bitcoin с июня 2013 года по сентябрь 2016 года, график CoinDesk

          Казалось бы, злоумышленникам пора отказаться от зловредов с криптомайнерами и перейти на вымогатели (ransomware). Многие так и сделали. Но тут на сцену вышли новые криптовалюты — и старая бизнес-модель снова стала эффективной.
          Читать дальше →
        • Palantir: Объектная модель

            Шрияс Виджайкумар, ведущий инженер по внедрению, расскажет про еще один элемент внутренней кухни системы Palantir.



            Как организации управляются с данными, на текущий момент?
            В существующих системах встречаются довольно распространенные артефакты, и многие из них, если не все, вам знакомы:
            • пользователи часто оставляют заметки для себя в имени файла, так что мы можем встретить конструкции вида отправить_по_почте.пятница.10_утра.не_стирать!!;
            • каждое изменение онтологии требует модификации всей схемы;
            • данные из разных источников невозможно исследовать вместе, в одной среде, так что у вас может быть база данных людей и трафика сообщений, которые приходится исследовать по отдельности;
            • пересинхронизация данных нецелесообразна или невозможна, — а это часто бывает нужно;
            • информация не может быть прослежена до её источника.

            Что мы принципиально иначе делаем в Palantir?
            Когда мы разрабатывали систему, мы много работали с обратной связью от сообщества. Первое, что мы постарались запроектировать — это максимальная гибкость системы, дающая возможность моделировать все что угодно.

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

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

            Читать дальше →
          • Работа с MySQL: как масштабировать хранилище данных в 20 раз за три недели

            • Перевод


            Ранее в блоге на Хабре мы рассказывали о развитии нашего продукта — биллинга для операторов связи «Гидра», а также рассматривали вопросы работы с инфраструктурой и использования новых технологий. К примеру, мы рассмотрели плюсы Clojure, ситуации, когда стоит и не стоит использовать MongoDB и ограничения в PostgreSQL.

            Сегодня речь пойдет о масштабировании. Разработчики open-source почтового приложения Nylas опубликовали в своем блоге материал о том, как им удалось масштабировать систему в 20 раз за три недели с помощью инструмента ProxySQL. Для этого им пришлось переехать с Amazon RDS на MySQL на EC2. Мы представляем вашему вниманию основные моменты этой интересной заметки.
            Читать дальше →
            • +11
            • 29,9k
            • 6
          • От шедулера к планировщику

              См. две другие статьи этой группы — Делаем многозадачность и Преемптивность: как отнять процессор.

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

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

              Как я уже говорил, шедулер — это просто функция, которая отвечает на вопрос: какую нить и на сколько времени поставить на процессор.

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

              Говоря о шедулере нельзя не сказать о приоритетах.

              Приоритет — свойство нити (или процесса) влияющее на конкуренцию этой нити с другими нитями за процессор.

              Приоритет обычно описывается парой <класс приоритета, значение приоритета внутри класса>.
              Читать дальше →
            • Математическая модель восприятия (Часть 1)

                Часть 2
                Часть 3

                Введение (Языковая природа абстрактных понятий)


                Цель этой работы показать, как языки наподобие английского, в качестве естественного и эффективного метода могут возникнуть на различных уровнях процесса восприятия. Попутно затронуты вопросы механизмов, позволяющих нам и животным видеть, классифицировать по форме цветовые пятна, составлять представление о местах, предметах и их геометрических свойствах. Несколько слов посвящено чисто языковым проблемам: тому, какие понятия и методы должны присутствовать в любом достаточно выразительном описательном языке среди первоначальных, а какие, в качестве производных, из первоначальных могут быть получены.
                Каким же образом мог бы участвовать язык, например, в процессе зрительного восприятия? Каждый из нас привык говорить о своей способности видеть дерево, слышать пение птиц и чувствовать тепло, держа руку над свечой. Тем не менее нашему
                Читать дальше →
              • Flume — управляем потоками данных. Часть 2

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

                  Читать дальше →
                • Houdini: один из самых впечатляющих проектов в CSS, о котором вы никогда не слышали

                  • Перевод


                  Бывало ли у вас так, что хотелось использовать какую-нибудь фичу из стандарта CSS, но вы этого не делали, потому что она поддерживается не всеми браузерами? Или ещё хуже: её поддерживают все браузеры, но поддержка глючная, противоречивая или вообще несовместимая? Наверняка вы с таким сталкивались, и поэтому рекомендую вам присмотреться к Houdini.

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

                  Но что конкретно кроется за этими обещаниями? Это хотя бы хорошая затея? И как всё вышесказанное поможет нам, разработчикам, создавать сайты сегодня и завтра?

                  На все эти вопросы я постараюсь дать ответы. Но сначала внесу ясность относительно актуальных сегодняшних проблем и необходимости их решения. А затем уже мы поговорим о том, как Houdini может нам с ними помочь, и рассмотрим ряд его наиболее впечатляющих возможностей, находящихся в процессе разработки. И в завершение я внесу ряд предложений, как сообщество разработчиков может помочь реализоваться проекту Houdini.
                  Читать дальше →
                • Шпаргалка Java-программиста 6. Список полезных ссылок для Java программиста

                    Добрый день, данная статья о моем opensource pet проекте на github'e useful-java-links, в котором я собрал большое количество ссылок на полезные открытые (и некоторые закрытые) проекты. Этот проект существует на двух языках сразу русском и английском, которые являются полными дубликатами друг друга (кроме отсутствия ссылок на русскоязычные ресурсы в английской версии).


                    image


                    Данный проект — форк такого проекта как awesome-java, плюс добавлены все не мобильные проекты github'a c количеством звезд более 390 (то что описано в этой статье), все проект Apache верхнего уровня, ряд других ссылок, плюс ссылки на русскоязычное видео из этой статьи. В целом, количество полезных ссылок примерно в два раза больше чем в awesome-java. Есть строгая структура разделов, сразу дана информация об лицензиях и возможности использования данной лицензии в закрытом продукте (то есть строгость копилефта и возможность линкования с закрытыми проектами) и количество звезд набранным каждым проектом.


                    Буду очень благодарен за любые исправления и дополнения в данный сборник (добавить можно как в комментариях к статье, так и просто на github'e ). И за помощь в распространении ссылок на данный проект как среди русскоязычных, так и среди англоязычных (так как версия на английском полностью аналогична русской). В этой статье даны все ссылки, однако обновляемая версия все-таки будет на github'e.


                    Читать дальше →
                  • Микросервисная архитектура, Spring Cloud и Docker

                    • Tutorial

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



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

                    Читать дальше →
                  • Сборка мусора в персистентной модели: от терабайта и дальше

                      Привет всем. Продолжу о Фантоме. Для понимания полезно прочесть статью про персистентную оперативку, а так же общую статью про Фантом на Открытых Системах. Но можно и так.

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

                      Очевидно, что такой среде нужна сборка мусора. Но — какая?

                      Есть несколько проблем, навязанных спецификой.

                      Во-первых, теоретически, объём виртуальной памяти в такой среде огромен — терабайты, всё содержимое диска. Ведь мы отображаем в память всё и всегда.

                      Во-вторых, нас категорически не устраивают stop the world алгоритмы. Если для обычного процесса остановка в полсекундны может быть приемлема, то для виртуальной памяти, которая, большей частью, на диске, это будут уже полчаса, а то как бы не полсуток!

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

                      Тут нужна оговорка. Вообще говоря, в системе, которая располагает парой терабайт виртуальной памяти, это не так уж критично — даже если не делать освобождение памяти полсуток, возможно, не так много и набежит — ну, например, истратится 2-3, ну 5 гигабайт, ну даже и 50 гигабайт — не жалко, диск большой.

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

                      Ок, итого у нас две задачи.
                      Читать дальше →
                    • GSM-ловушки: ещё один привет от Большого Брата



                        Предлагаю сегодня поговорить о скрытой и неизведанной области — GSM-связи. Почему же неизведанной, спросите вы? Ведь все носят в кармане сотовый телефон, чуть ли не дошкольники ходят с ними, а базовые станции висят на каждом столбе? Увы, обыватель считает, что всё просто и прозрачно: совершает звонки, посылает СМС. И редко задумывается над процессами, которые обеспечивают все эти действия. В этом статье я попробую показать, что GSM-связь — с одной стороны весьма непрозрачная тема, а с другой — прорва уязвимостей. Если конкретнее – то поговорим о так называемых IMSI-ловушках (или IMSI-catchers).

                        Подробности
                      • Метрика рекомендательной системы imhonet.ru

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


                          Читать дальше →
                          • +32
                          • 13,9k
                          • 8
                        • Лямбда-выражения Java 8 — это замыкания?

                          • Перевод
                          Развернутый ответ на вопрос, вынесенный в заглавие поста, приводится в статье Брюса Эккеля в редакции от 25 ноября 2015 года. Мы решили разместить здесь перевод этой статьи и поинтересоваться, что вы думаете о функциональном программировании в Java, а также об актуальности такой книги:



                          Приятного чтения!

                          Читать дальше →
                        • Chrome дополнение PushAll возвращает возможности центра оповещений и дополняет его

                            Многие наверное видели область уведомлений в Chrome? Мы ранее писали, что Chrome её убрал.



                            При этом все сервисы, использующие push-уведомления, получили ряд проблем.
                            • Если вы используете Web Push, то у вас есть возможность закрепить оповещение на экране. И пользователь может либо закрыть оповещение, либо нажать на него. То есть если он занят, то он скорее всего закроет, даже если бы он хотел прочесть материал
                            • Если вы используете дополнение для Chrome, тогда Rich Notification исчезает через несколько секунд в небытие.


                            Мы сделали раздел пропущенных оповещений, в котором собираются те оповещения, которые исчезли, и те которые не были доставлены (например если у вас были заблокированы порты)



                            Ссылка на обновленное расширение
                            Читать дальше →
                            • –4
                            • 4,6k
                            • 3
                          • Эксперимент: Что гипотеза случайного блуждания говорит о прогнозировании финансовых рынков



                              В блоге на Хабре и аналитическом разделе нашего сайта мы много пишем об алгоритмах и инструментах прогнозирования движения на финансовы рынках. При этом многие наблюдатели считают, что подобные занятия сродни игре в казино — на бирже все случайно, а значит ничего нельзя спрогнозировать. Количественный аналитик хедж-фонда NMRQL Стюарт Рид опубликовал на сайте Turing Finance результаты исследования, в ходе которого использовал гипотезу случайного блуждания, пытаясь подтвердить или опровергнуть тезис о случайности финансовых рынков. Мы представляем вашему вниманию основные мысли этого материала.
                              Читать дальше →
                            • Разрушители мифов: Автоматическое решение Google Recaptcha

                                Привет! Я воплощаю интересные идеи на python и рассказываю о том, что из этого вышло. В прошлый раз я пробовал найти аномалии на карте цен недвижимости. Просто так. На этот раз идея была построить систему, которая смогла бы сама решать очень популярную ныне Google Recaptcha 2.0, основываясь на некоторых алгоритмах и большой базе обучающих примеров.
                                Google Recaptcha 2.0 представляет собой набор изображений (9 или 16 квадратных картинок под одной инструкцией), среди которых пользователю, для подтверждения своей разумности, нужно выбрать все изображения одной категории. Речь пойдет НЕ о построении системы машинного обучения — распознавать мы будем именно капчи!
                                Читать дальше →
                                • +45
                                • 30,6k
                                • 6