Привет, %username%!

В сегодняшнем посте речь пойдет о криптостойкости генераторов псевдослучайных чисел (ГПСЧ).
Для начала определимся, что же такое криптостойкий ГПСЧ (КСГПСЧ).

КСГПСЧ должен удовлетворять «тесту на следующий бит». Смысл теста в следующем: не должно существовать полиномиального алгоритма, который, зная первые k битов случайной последовательности, сможет предсказать k+1 битов с вероятностью более 50 %.

Wikipedia

Возможно, кое-кто из читателей использовал такие ГПСЧ, как регистры сдвига с линейной обратной связью (РСЛОС) или любимый многими программистами Вихрь Мерсенна. Я постараюсь показать, что оба этих способа, несмотря на весьма хорошие статистические свойства и большие периоды, не соответствуют приведенному выше определению и их нельзя считать криптографически стойкими, а также предложу, в качестве альтернативы, два очень надежных ГПСЧ.

От переводчика: данный текст даётся с незначительными сокращениями по причине местами излишней «разжёванности» материала. Автор абсолютно справедливо предупреждает, что отдельные темы могут показаться читателю чересчур простыми или общеизвестными. Тем не менее, лично мне этот текст помог упорядочить имеющиеся знания по анализу сложности алгоритмов. Надеюсь, что он окажется полезен и кому-то ещё.
Из-за большого объёма оригинальной статьи я разбила её на части, которых в общей сложности будет четыре.
Я (как всегда) буду крайне признательна за любые замечания в личку по улучшению качества перевода.

Опубликовано ранее:
Часть 1

Сложность

Из предыдущей части можно сделать вывод, что если мы сможем отбросить все эти декоративные константы, то говорить об асимптотике функции подсчёта инструкций программы будет очень просто. Фактически, любая программа, не содержащая циклы, имеет f( n ) = 1, потому что в этом случае требуется константное число инструкций (конечно, при отсутствии рекурсии — см. далее). Одиночный цикл от 1 до n, даёт асимптотику f( n ) = n, поскольку до и после цикла выполняет неизменное число команд, а постоянное же количество инструкций внутри цикла выполняется n раз.

От переводчика: данный текст даётся с незначительными сокращениями по причине местами излишней «разжёванности» материала. Автор абсолютно справедливо предупреждает, что отдельные темы покажутся чересчур простыми или общеизвестными. Тем не менее, лично мне этот текст помог упорядочить имеющиеся знания по анализу сложности алгоритмов. Надеюсь, что он будет полезен и кому-то ещё.
Из-за большого объёма оригинальной статьи я разбила её на части, которых в общей сложности будет четыре.
Я (как всегда) буду крайне признательна за любые замечания в личку по улучшению качества перевода.

Введение

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

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

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

Количество ложно-положительных срабатываний фильтра Блума.

Описание

Фильтр Блума — это рандомизированная структура данных для запросов, разработанная Бёртоном Блумом в 1970 году. Фильтр Блума даёт ошибочный ответ на запрос, т.н. ложно-положитеное срабатывание. Т.е. если мы добавляем некоторый элемент, то существует отличная от нуля вероятность, что фильтр Блума вернет ответ что элемент находится в векторе, хотя его там нет.

Грубо говоря, фильтр Блума возвращает 2 возможных ответа:

1. элемента нет в векторе
2. элемент возможно есть в векторе

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

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

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

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

Собственно речь пойдет о двоичной куче и ее построении с помощью Sift-Down(или Heapify). Многим наверное известно, что построение кучи таким образом осуществляется за . Здесь я приведу доказательство этого факта.

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

В одном из вчерашних комментариев был вопрос о том, что если всё плохо, то
— Как же будет хорошо?
— Сделать лучше.

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

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

Ниже дан вольный перевод записи с сайта Sakshat Virtual Labs
Need for Short Term Processing of Speech
В статье содержится информация об одном из методов сбора характеристик речевого сигнала и о трех основных характеристиках, которые лежат в основе многих алгоритмов обработки звуковых сигналов и речи.

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

Было предложено решение для обработки речи, которое заключалось в использовании уже известных методов из области обработки сигналов с их небольшой модификацией. То-есть используемые средства обработки все так же предполагали стационарный сигнал. Стационарным речевой сигнал получается, когда рассматривается небольшими блоками по 10-30мс. Следовательно, для обработки речи разными средствами обработки сигналов, она рассматривается в блоках по 10-30мс (дальше такой участок будем называть речевым сигналом). Такая обработка называется Краткосрочной Обработкой (Short Term Processing (STP)).

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

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

На примере движка Unity и C# я покажу как можно работать с моделями и превращать текст в графику. Большинство приводимого кода легко портируется на другие фреймфорки и языки.

Треугольник

Начнём с простейшей формы — треугольника. В Unity и во многих других движках используется популярный способ описания моделей: с помощью массивов вершин, треугольников и нормалей. Дополнительно для текстурирования используются uv-координаты вершин. Для работы с моделями есть класс Mesh, в котором для каждого набора данных имеется отдельный массив. В Mesh.vertices хранятся координаты вершин, в Mesh.triangles — индексы вершин группами по три. А в Mesh.normals и Mesh.uv лежат векторы нормалей и координаты uv-карт, индексы которых должны совпадать с индексами соответствующих вершин, т. е. порядок в массивах должен быть одинаковым. Покажу на примере, чтобы было понятнее.

Привет, Хабр!
Становится традицией публиковать отчёты команд после выступления на соревнованиях “Робокросс”.
В прошлом сезоне были отчёты команд НАМТ и MobRob, а сейчас, мне хотелось бы рассказать о работе нашей команды.

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

Мы разрабатываем проект CRIU (Checkpoint/Restore in Userspace) и у нас возникла достаточно интересная задача о том, как восстановить оригинальное дерево процессов. Я предлагаю вам попытаться решить ее.

Задача

CRIU — это утилита, которая позволяет сохранить состояние процессов на диск и постановить их позднее на этой или на любой другой машине. Одной из подзадач восстановления является нахождение последовательности действий для того, чтобы восстановить дерево процессов. Входные данные содержат набор параметров для каждого процесса: уникальный идентификатор (PID), ссылку на родителя (PPID), идентификатор сессии (SID).

Всю сознательную программистскую деятельность я увлекался созданием игр и не любил делать редакторы и прочие утилиты. Главным моим редактором почти всегда был Paint. Но для игр, в которых уровень статичен и состоит из тайлов (Марио подобные и прочие танчики), это более-менее оправдано, т.к. одному пикселю из файла уровня, созданного в Paint, соответствует тайл в игре. А что если требуется создать игру, где нет тайлов, а игровая локация состоит из неровных скалистых пещер. Или игру, в которой много движущихся элементов (летающие платформы, лифты, циркулярные пилы, вращающиеся по окружности).

Создавать редактор для таких целей мне по-прежнему не хотелось. О том, как я это решил с помощью Paint опишу в этой статье.

UPD: схема заменена на вариант с контейнерами из С++11, соавторы — в комментариях ниже

Предисловие

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

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

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

Предисловие

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

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

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

Предпредисловие

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

Предисловие

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