• Разбор задач финала чемпионата мира про программированию ACM ICPC 2013

      На прошедшем неделю назад чемпионате мира по командному программированию ACM ICPC 2013 было 11 задач, одну из которых за отведённое время не смогла решить правильно ни одна из команд.

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

      В этом году на ACM ICPC был 21 аналитик из Швеции, Нидерландов, США, Словакии, Беларуси и России. И 10 из них были из Яндекса. Все они в разные годы были призёрами ICPC. Специально для Хабра они разобрали все задания чемпионата.

      Разбор задачи «Матрёшка» во время трансляции ACM ICPC 2013
      Читать дальше →
    • Нейронные сети в картинках: от одного нейрона до глубоких архитектур

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

        В статье мы пойдём по другому пути. Начнём с самой простой конфигурации — одного нейрона с одним входом и одним выходом, без активации. Далее будем маленькими итерациями усложнять конфигурацию сети и попробуем выжать из каждой из них разумный максимум. Это позволит подёргать сети за ниточки и наработать практическую интуицию в построении архитектур нейросетей, которая на практике оказывается очень ценным активом.
        Читать дальше →
      • Сверточная нейронная сеть, часть 1: структура, топология, функции активации и обучающее множество

        Предисловие


        Данные статьи (часть 2) являются частью моей научной работы в ВУЗе, которая звучала так: «Программный комплекс детектирования лиц в видеопотоке с использованием сверточной нейронной сети». Цель работы была — улучшение скоростных характеристик в процессе детектирования лиц в видеопотоке. В качестве видеопотока использовалась камера смартфона, писалось десктопное ПС (язык Kotlin) для создания и обучения сверточной нейросети, а также мобильное приложение под Android (язык Kotlin), которая использовала обученную сеть и «пыталась» распознать лица из видеопотока камеры. Результаты скажу получились так себе, использовать точную копию предложенной мной топологии на свой страх и риск (я бы не рекомендовал).
        Читать дальше →
        • +23
        • 122k
        • 7
      • Алгоритм обучения многослойной нейронной сети методом обратного распространения ошибки (Backpropagation)

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



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

          Итак, представим себе, что есть два программиста. Один из них умный, прочёл кучу статей на Хабре, знает каталог GoF наизусть, а Фаулера — в лицо. Другой же делает всё просто. Первого будут звать, например, Борис Н., а второго — Маркус П. Само собой, имена вымышленные, и все совпадения с реальными людьми и программистами случайны.

          Итак, к ним обоим приходит проектный менеджер (если в вашей вселенной PM не ходит сам к программистам, назовите его как-то иначе, например BA или lead, сути это не изменит) и говорит:
          — Ребята, нам нужно, чтобы делался хлеб.

          Именно так, «делался», без уточнения способа производства.

          Как же поступят наши программисты?
          Читать дальше →
        • Как замкнуть переменную в C# и не выстрелить себе в ногу

            Еще в далеком 2005 с выходом стандарта C# 2.0 появилась возможность передачи переменной в тело анонимного делегата посредством ее захвата (или замыкания, кому как угодно) из текущего контекста. В 2008 вышел в свет новый стандарт C# 3.0, принеся нам лямбды, пользовательские анонимные классы, LINQ запросы и многое другое. Сейчас на дворе январь 2017 и большинство C# разработчиков с нетерпением ждут релиз стандарта C# 7.0, который должен привнести много новых полезных «фич». А вот фиксить старые «фичи», никто особо не торопится. Поэтому способов случайно выстрелить себе в ногу по-прежнему хватает. Сегодня мы поговорим об одном из их, и связан он с не совсем очевидным механизмом захвата переменных в тело анонимных функций в языке C#.

            Picture 1

            Читать дальше →
          • Обманываем нейросети при помощи шума

            • Перевод


            Меня всегда занимали отказы систем и странности их поведения, в особенности когда те работают в нормальных для себя условиях. Недавно я видел один из слайдов презентации Йена Гудфелло, показавшийся мне очень смешным. Случайный визуальный шум скормили обученной нейросети, и она распознала его как один из известных ей объектов. Тут сразу появляется много вопросов. Будут ли видеть один и тот же объект разные обученные нейросети? Каков максимальный уровень уверенности нейросети в том, что этот случайный шум действительно является распознанным ею объектом? И что на самом деле «видит» там нейросеть?

            Из моего любопытства по этому поводу и родилась данная запись. К счастью, подобные эксперименты очень легко проводить при помощи PyTorch. Для визуализации того, почему нейросеть классифицирует объекты определённым образом, я использую платформу интерпретируемости модели Captum. Код можно скачать с Github.
            Читать дальше →
          • «Выглядит похоже». Как работает перцептивный хэш

            • Перевод
            За последние несколько месяцев несколько человек спросили меня, как работает TinEye и как в принципе работает поиск похожих картинок.

            По правде говоря, я не знаю, как работает поисковик TinEye. Он не раскрывает деталей используемого алгоритма(-ов). Но глядя на поисковую выдачу, я могу сделать вывод о работе какой-то формы перцептивного хэш-алгоритма.
            Читать дальше →
          • Как я искал пацанский движок для блога



              Я много пишу в интернетах и мне захотелось завести свой личный стэндалон блог, куда можно писать мелкие заметки и статьи, не подходящие для других площадок. Главная проблема личного блога — мне лень оформлять посты. Чтобы черкануть пару строк в каком-нибудь Wordpress, нужно слишком много телодвижений. Я попробовал несколько разных движков и каждый раз ловил себя на ощущении, что мне не хочется ими пользоваться, намного быстрее и проще писать в записную книжку вроде Evernote или Notion. Так я стал искать идеальный движок для блога, отвечающий всем моим потребностям.

              Мои требования к идеальному движку:


              • Желательно self-hosted — я пережил много закрытий сервисов, от narod.ru до google+ и точно знаю, что рано или поздно все протухает, поэтому надежнее всего держать контент у себя. Также посты могут удалять по каким-то фейковым жалобам или по DMCA, как это происходит на Medium и LiveJournal.
              • Возможность подключения своего домена — мне нужен сайт-визитка со всеми проектами и ссылками в одном месте, где можно разместить портфолио, резюме, контакты.
              • Минимум телодвижений и интерфейса — в идеале интерфейса CMS вообще не должно быть видно, админская панель не нужна, посты должны редактироваться, создаваться и просматриваться в одном месте.
              • Полноценный WYSIWYG редактор — поддержка разметки Markdown и обработка её в реальном времени, подсветка кода, вставка картинок из буфера обмена.
              • Нормальные комментарии — возможность оставлять анонимные комментарии и авторизовываться через максимум соц. сетей для персонифицированных комментариев.
              • Минималистичный внешний вид — я не хочу заниматься версткой и темами, подходящее оформление должно быть из коробки.


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

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

                TL;DR: базовая логика redux помещается в 7 строк JS кода.

                О redux вкратце (вольный перевод заголовка на гитхабе):
                Redux — библиотека управления состоянием для приложений, написанных на JavaScript.

                Она помогает писать приложения, которые ведут себя стабильно/предсказуемо, работают на разных окружениях (клиент/сервер/нативный код) и легко тестируемы.
                Я склонировал репозиторий redux, открыл в редакторе папку с исходниками (игнорируя docs, examples и прочее) и взялся за ножницы клавишу Delete:

                • Удалил все комментарии из кода
                  Каждый метод библиотеки задокументирован с помощью JSDoc весьма подробно
                • Убрал валидацию и логирование ошибок
                  В каждом методе жёстко контролируются входные параметры с выведением очень приятных глазу подробных комментариев в консоль
                • Убрал методы bindActionCreators, subscribe, replaceReducer и observable.

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

                А теперь давайте разберём то, что осталось
                Читать дальше →
              • Как я забросил игру спустя четыре года разработки

                • Перевод


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

                Под катом ожидания, реальность и выгорание инди-разработки. А в конце — ссылка на демо, можно прочувствовать, как близко автор был к успеху.
                Читать дальше →
              • Как развивается умение общаться (с самого-самого начала) и что с ним делают игры на сторителлинг

                  Одна из самых распространенных тем запросов, с которыми приходят к детским специалистам, это речь. Самая очевидная проблема — это когда ребенок не говорит. Вот ему год, а он молчит. Вот ему уже три, а он все равно молчит. А вот уже пять… Тут понятно, что что-то пошло не так. Есть менее очевидные проблемы, которые на самом деле тоже про речь. Например, ребенок плохо учится. Почему плохо учится? Оказывается, когда ему учительница задает вопрос, он в ответ двух слов связать не может. Или у ребенка почему-то нет друзей. И оказывается, что он просто не представляет, как со сверстниками вообще разговаривать. Ну и не разговаривает. И так далее.

                  Самый нужный человек здесь, как понятно, логопед (и очень важно дойти до логопеда, если есть подозрение, что развитие речи пошло как-то не так). Игротерапевты с этим тоже работают, потому что умение разговаривать и договариваться развивается вместе с развитием игры. Чтобы понять, как это происходит, начнем с самого начала.
                  Читать дальше →
                • Описание алгоритмов сортировки и сравнение их производительности

                  Вступление


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

                  Во многом статья посвящена тому, как написать все алгоритмы и протестировать их. Если говорить о самом программировании, то иногда могут возникнуть совершенно неожиданные трудности (во многом благодаря оптимизатору C++). Однако не менее трудно решить, какие именно тесты и в каких количествах нужно сделать. Коды всех алгоритмов, которые выложены в данной статье, написаны мной. Доступны и результаты запусков на всех тестах. Единственное, что я не могу показать — это сами тесты, поскольку они весят почти 140 ГБ. При малейшем подозрении я проверял и код, соответствующий тесту, и сам тест. Надеюсь, что статья Вам понравится.
                  Читать дальше →
                • DisplayPort-LVDS

                    Доброго времени суток, Хабр!



                    И снова хочу предложить Вашему вниманию проект аппаратного конвертера, но теперь уже DisplayPort-LVDS построенный на одной (!) микросхеме NXP.
                    Читать дальше →
                  • Проекции карт: о чём на самом деле шутит xkcd

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

                      Иногда выпуск комикса xkcd — это поверхностная шутка в узкой области знаний. Понять такой юмор сможет специалист или хотя бы слабо знакомый с затрагиваемой областью, а остальные будут лишь недоумевать. Пример такого выпуска — xkcd.com/977 Map Projections 2011 года. Для полного понимания выпуска нужно лишь примерно представлять историю и функцию различных проекций карт мира, иначе комикс останется чёрно-белым рисунком.



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

                      Не все мы смотрим на карту для навигации в открытом море. Часто выбор метода преобразования формы Земли — это не вопрос жизни и смерти, это художественная иллюстрация. В этих случаях проекцию выбирают из устоявшихся вкусов и предпочтений — точно так же, как выбирают одежду или автомобиль. Можно смешно шутить про моду на дорогие кроссовки среди директоров крупных компаний Кремниевой долины или про популярность заниженных автомобилей. Точно так же шуткам поддаются предпочтения картографической проекции, как это и было сделано в Map Projections.
                      Читать дальше →
                    • Импортозамещение на практике. Часть 3.1. «QP ОС». Первый в своем роде обзор операционной системы

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

                        Всех интересующихся отечественными разработками ПО — прошу под кат.
                        Читать дальше →
                      • Разбор квалификации чемпионата по программированию среди бэкенд-разработчиков

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


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



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


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

                          Читать дальше →
                          • +33
                          • 26,3k
                          • 7
                        • Шейдеры 3D-игр для начинающих: эффекты

                          • Перевод
                          [Первая часть]

                          Разобравшись с основами, в этой части статьи мы реализуем такие эффекты, как контуры объектов, bloom, SSAO, размытие, глубина резкости, пикселизация и другие.

                          Контуры



                          Создание контуров вокруг геометрии сцены придаёт игре уникальный внешний вид, напоминающий комиксы или мультфильмы.

                          Diffuse материала


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

                          uniform struct
                            { vec4 diffuse
                            ;
                            } p3d_Material;
                          
                          out vec4 fragColor;
                          
                          void main() {
                            vec3 diffuseColor = p3d_Material.diffuse.rgb;
                            fragColor = vec4(diffuseColor, 1);
                          }

                          Здесь показан небольшой фрагментный шейдер, который рендерит диффузный цвет материала геометрии в текстуру буфера кадров. Эта текстура диффузного цвета из буфера кадров будет входящей текстурой для шейдера контуров.
                          Читать дальше →
                          • +39
                          • 10,3k
                          • 4
                        • Опусы про Его Величество Клей. Часть четвертая — силиконы

                          • Tutorial
                          Посвящается Андрею А., котрому я так и не принес до сих пор извинения за испорченную силиконом вещь...

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

                          Читать дальше →
                        • Призоловство — мой «бывший бизнес»

                          Здравствуйте уважаемые!
                          Расскажу о «бизнесе» — призоловство. И сколько денег на нём можно поднять. Сразу скажу – если ты не ленишься и живешь в городе милионнике – в летний месяц легко делать порядка 100-150 тыс руб., причем даже не бросая основного места работы.
                          Моя специализация была: «пластик» — это крышки различных акций напитков и пива: спрайт, гринбир, колы всякие, медведь, три толстяка… можно перечислить все представленные на нашем рынке продукты.

                          image
                          Но, так же я не брезговал и другими акциями: сигаретные, продуктовые и т.д – благо, если ты «барыжишь» хотя бы одним видом кодов, то их всегда с удовольствием готовы обменять на любом призоловском форуме.
                          Читать дальше →