Алгоритмы *

Число подписчиков блога. Число опубликованных постов пользователя. Число положительных и отрицательных голосов за комментарий. Число оплаченных заказов товара. Вам приходилось считать что-то подобное? Тогда, готов поспорить, что оно у вас периодически сбивалось. Да ладно, даже у вконтакта сбивалось:

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

Привет, %username%! Сегодня у нас немного пятничная криптотема. В марте 2016 года вышла интересная публикация от NIST под номером 800-38G (pdf) и с очень интересным называнием Recommendation for Block Cipher Modes of Operation:Methods for Format-Preserving Encryption, в которой отписываются два алгоритма, позволяющие не менять формат данных при шифровании. То есть, если это будет номер кредитки 1234-3456-4567-6678, то после шифрования он тоже останется номером, просто другим. Например 6243-1132-0738-9906. И это не простой xor, там AES и вообще всё серьезно. Давайте немного поговорим о FPE вообще, и об одной из реализаций в частности.

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

Я занимаюсь разработкой своего скромного бота для игры в Го. И меня искренне удивляет отсутствие информации эту тему на русском языке. Поэтому я решил поделиться накопленными знаниями в этой статье.

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

Педагог-новатор Виктор Федорович Шаталов в 70-х годах прошлого века разработал систему обучения с использованием опорных сигналов — взаимосвязанных ключевых слов, условных знаков, рисунков и формул с кратким выводом [1].

Опорным алгоритмом в Excel будем называть набор изображений и алгоритмов (формул), особым образом расположенных на Excel-листе, который помогает активизировать мышление обучающихся.

Занимаясь музыкальным творчеством, я часто делаю аранжировки и записи на компьютере — используя кучу всяких VST плагинов и инструментов. Стыдно признаться — я никогда не понимал, как "накручивают" звуки в синтезаторах. Программирование позволило мне написать свой синтезатор, "пропустить через себя" процесс создания звука.

Я планирую несколько статей, в которых будет пошагово рассказано, как написать свой VST плагин/инструмент: программирование осциллятора, частотного фильтра, различных эффектов и модуляции параметров. Упор будет сделан на практику, объяснение программисту простым языком, как же все это работает. Теорию (суровые выводы и доказательства) обойдем стороной (естественно, будут ссылки на статьи и книги).

Обычно плагины пишутся на C++ (кроссплатформенность, возможность эффективно реализовать алгоритмы), но я решил выбрать более подходящий для меня язык — C#; сфокусироваться на изучении самого синтезатора, алгоритмов, а не технических деталей программирования. Для создания красивого интерфейса я использовал WPF. Возможность использования архитектуры .NET дала возможность библиотека-обертка VST. NET.

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

Предстоит нелегкий путь, если вы готовы — добро пожаловать под кат.

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

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

Алгоритмы сортировки

В этой статье речь пойдет о сравнении некоторых алгоритмов сортировки, реализованных на C++ для последовательности не упакованных BCD чисел большого размера.



Данный анализ я проводил в качестве летней практики в компании «Программные технологии».
Сортируемая последовательность не имеет заголовка, числа в ней имеют различную разрядность и хранятся без выравнивания. Между числами стоят разделители (0xFF).

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

1. Сортировка слиянием;
2. Сортировка слиянием без использования буфера;
3. Естественная сортировка слиянием;
4. Естественная сортировка слиянием без использования буфера;
5. Модифицированная естественная сортировка слиянием;
6. Модифицированная естественная сортировка слиянием без использования буфера;
7. std::sort.

В течение последних шести лет в Яндексе идет работа над системой под кодовым называнием YT (по-русски мы называем её «Ыть»). Это основная платформа для хранения и обработки больших объемов данных — мы уже о ней рассказывали на YaC 2013. С тех пор она продолжала развиваться. Сегодня я расскажу о том, с чего началась разработка YT, что нового в ней появилось и что ещё мы планируем сделать в ближайшее время.



Кстати, 15 октября в офисе Яндекса мы расскажем не только о YT, но и о других наших инфраструктурных технологиях: Media Storage, Yandex Query Language и ClickHouse. На встрече мы раскроем тайну — расскажем, сколько же в Яндексе MapReduce-систем.

Какую задачу мы решаем?

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

Если Вы последние 10 лет провели на удаленном острове, без интернета и в отрыве от цивилизации, то специально для Вас мы попытаемся еще раз рассказать про концепцию MapReduce. Введение будет небольшим, в объеме достаточном, для реализации концепции MapReduce в среде InterSystems Caché. Если же Вы не сильно далеко удалялись последние 10 лет, то сразу переходите ко 2ой части, где мы создаем основы инфраструктуры.

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

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

Правила трактовки зависят от тех сопутствующих обстоятельств, в которых мы пытаемся дать интерпретацию информации. Эти обстоятельства принято называть контекстом, в котором трактуется информация.

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

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

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

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

James Kyle как-то раз взял и написал пост про структуры данных, добавив их реализацию на JavaScript. А я взял и перевёл.

Дисклеймер: в посте много ascii-графики. Не стоит его читать с мобильного устройства — вас разочарует форматирование текста.

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



Не идеально, но по мне — очень классно. 3D шутер, который играется в реальном времени — это впервые.

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

При развитии free-to-play мобильной игры вместе с новыми фичами регулярно добавляется и новая графика. Часть ее включается в дистрибутив, часть скачивается в ходе игры. Для возможности запуска приложения на устройствах с небольшим размером оперативной памяти разработчики применяют аппаратно сжатые текстуры.



Формат ETC1 обязателен к поддержке на всех Android-устройствах с OpenGL ES 2.0 и является хорошей отправной точкой оптимизации потребляемой оперативной памяти. По сравнению с форматами PNG, JPEG, WebP загрузка текстур ETC1 осуществляется без интенсивных расчетов обычным копированием памяти. Также улучшается производительность игры по причине меньших размеров данных текстур пересылаемых из медленной памяти в быструю.

18-го сентября был проведен последний, финальный этап чемпионата по спортивному программированию Russian Code Cup 2016 года. Первое место в упорной борьбе занял Геннадий Короткевич, второе и третье места — Владислав Епифанов и Николай Калинин соответственно.

Турнирную таблицу финала можно найти здесь, призовой фонд в этом году впервые распределен на первые 25 мест рейтинга. Это не единственное нововведение — впервые в RCC имели возможность поучаствовать англоговорящие программисты, коих набралось более тысячи из 4.5 тысяч участников. Помимо традиционных для соревнования стран СНГ, в финальном раунде боролись представители Германии, Финляндии, Японии, Швейцарии, Китая и Южной Кореи. Кроме того, в этот раз был проведен зеркальный раунд на Codeforces — сразу после финала основного состязания, у всех желающих была возможность решить задачи финала в специально организованном соревновании для первого дивизиона, поучаствовало чуть больше 200 программистов.

Традиционно предлагаем вам разбор задач финала (тесты можно скачать здесь):

A. Церемония закрытия
B. Кактусофобия
C. Домашнее задание
D. Слалом
E. Шифр
F. Покрытие массива

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

Информация, чтобы быть использованной, должна получить интерпретацию. Например, красный сигнал светофора можно интерпретировать как запрет ехать, улыбку как сигнал хорошего расположения и тому подобное. Конкретная интерпретация называется смыслом информации. По крайней мере, такой трактовки придерживается международная организация по стандартизации: «knowledge concerning objects, such as facts, events, things, processes, or ideas, including concepts, that within a certain context has a particular meaning».

Этот документ поможет вам изучить контейнер для языка программирования Rust — futures, который обеспечивает реализацию futures и потоков с нулевой стоимостью. Futures доступны во многих других языках программирования, таких как C++, Java, и Scala, и контейнер futures черпает вдохновение из библиотек этих языков. Однако он отличается эргономичностью, а также придерживается философии абстракций с нулевой стоимостью, присущей Rust, а именно: для создания и композиции futures не требуется выделений памяти, а для Task, управляющего ими, нужна только одна аллокация. Futures должны стать основой асинхронного компонуемого высокопроизводительного ввода/вывода в Rust, и ранние замеры производительности показывают, что простой HTTP сервер, построенный на futures, действительно быстр.

Что является основным инструментом, который использует руководитель при управлении проектом? Принято считать, что основным инструментом руководителя проекта является календарный план, в основе которого лежит сетевая модель работ по проекту. Однажды мне довелось реализовать сетевую модель работ на языке Python (код и описание здесь). Ниже приведены уроки, извлеченные по результатам проделанной работы.