• Объяснение эксперимента о ветвлениях, или философские изыскания на тему бенчмарков в вакууме и в… реальности

      Надеюсь, кто хотел, ознакомился с моим пробным экспериментом на Хабре в этой статье. Теперь я считаю, что будет правильным огласить его результаты и даже дать более детальное объяснения причин, по которым вообще подобные эксперименты проводятся. Пост будет наполовину философским, поскольку сейчас в компьютерном мире всё настолько сложно, что без философского осмысления принять какие-то осмысленные решения просто невозможно. Я постараюсь вообще выразить своё мнение о сферических измерениях в вакууме, поэтому будет много букв. В статье есть опрос, проводимый до 1-го мая 2016. Под катом целиком ИМХО.

      Читать дальше →
    • Так ли нужно избавляться от ветвлений? — На примере sign, abs, min и max

        Я бы хотел предложить сообществу поучаствовать в пробном эксперименте. Суть его состоит в том, чтобы прогнать на своём компьютере программу, написанную на C++, и поделиться результатом измерения времени, которое она выдаёт, сравнивая скорость работы функций sign(x), abs(x), min(a,b) и max(a,b) в исполнении с ветвлением и без него. В статье я объясню свою мотивацию, покажу сами функции, а в конце предложу условия участия в эксперименте и его (увы) ограничения.
        Читать дальше →
      • Обстоятельно о подсчёте единичных битов

        • Tutorial
        Я хотел бы подарить сообществу Хабра статью, в которой стараюсь дать достаточно полное описание подходов к алгоритмам подсчёта единичных битов в переменных размером от 8 до 64 битов. Эти алгоритмы относятся к разделу так называемой «битовой магии» или «битовой алхимии», которая завораживает своей красотой и неочевидностью многих программистов. Я хочу показать, что в основах этой алхимии нет ничего сложного, и вы даже сможете разработать собственные методы подсчёта единичных битов, познакомившись с фундаментальными приёмами, составляющими подобные алгоритмы.

        Читать дальше →
      • Новогодний zip-квест 2012 – прохождение

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

          Читать дальше →
          • +21
          • 2.2k
          • 9
        • Новогодний zip-квест 2012

            Здравствуй, Хабрадруг!

            Мне понравилась идея создания квестов с помощью zip-архива, как это было сделано в этом посте. По указанной ссылке Мария (Nicolette) предложила квест, для прохождения которого требуется немного знать про эзотерические языки программирования. Я постарался сделать квест с таким же принципом, но в нём требуется немного уметь программировать и владеть некоторыми инструментами работы с файлами. Также пригодятся навыки нестандартного мышления и поиска информации в поисковиках. Обычно этими способностями вместе умеют пользоваться программисты, поэтому пост я решил положить в «спортивное программирование», так как больше никуда не подходит по смыслу.

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

            Читать дальше →
          • Конкурс на решение целочисленной системы линейных уравнений

              Здравствуй, Хабрадруг.

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

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

                Здравствуй, хабрачитатель.

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

                Читать дальше →
              • Метод динамического программирования для подсчёта числа циклов на прямоугольной решетке

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

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

                  Предупреждаю, что статья содержит около 2000 слов (8 страниц А4), но дорогу осилит идущий.

                  Читать дальше →
                • Математик vs. Ферзь

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

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

                    Читать дальше →