Алгоритмы *

В последнее время все больше «ходят» разговоры про новомодные алгоритмы, такие как нейронные сети и генетический алгоритм. Сегодня я расскажу про генетические алгоритмы, но давайте на этот раз постараемся обойтись без заумных определений и сложных терминах.
Как сказал один из великих ученных: «Если вы не можете объяснить свою теорию своей жене, ваша теория ничего не стоит!» Так давайте попытаемся во всем разобраться по порядку.

Существует много способов вычисления числа Пи. Самым простым и понятным является численный метод Монте-Карло, суть которого сводится к простейшему перебору точек на площади. Суть расчета заключается в том, что мы берем квадрат со стороной a = 2 R, вписываем в него круг радиусом R. И начинаем наугад ставить точки внутри квадрата. Геометрически, вероятность P₁ того, чтот точка попадет в круг, равна отношению площадей круга и квадрата:
P₁=S_круг / S_{квадрата} = πR² / a ² = πR² / (2 R ) ²= πR² / (2 R) ² = π / 4 (1)
Выглядит это так:

Вступление издалека

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

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

Однако речь сейчас не об алгоритме сортировки, а о способе сравнения строк. Казалось бы, здесь всё тривиально — достаточно сравнить первые с начала различающиеся символы. А если в строках есть числа? Тогда такая сортировка (лексикографическая) преобразует последовательность [ 'file2', 'file10', 'file1' ] в [ 'file1', 'file10', 'file2' ]. Но человек при чтении текста воспринимает числа отдельно, и эта же последовательность, упорядоченная интуитивно, выглядит так: [ 'file1', 'file2', 'file10' ]. Такая сортировка и называется естественной (natural sort).

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

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

Подробности под катом.

Что такое анализ?
Анализируя алгоритм, можно получить представление о том, сколько времени займет решение данной задачи при помощи данного алгоритма. Одну и ту же задачу можно решить с помощью различных алгоритмов. Анализ алгоритмов дает нам инструмент для выбора алгоритма.
Результат анализа алгоритмов — не формула для точного количества секунд или компьютерных циклов, которые потребует конкретный алгоритм. Нужно понимать, что разница между алгоритмом, который делает N + 5 операций, и тем, который делает N + 250 операций, становится незаметной, как только N становится очень большим.

Привет, %username%.

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

Введение

Для начала рассмотрим, как устроено стереоизображение и как на него смотреть.

Тест Соловея–Штрассена

Роберт Соловей и Фолькер Штрассен разработали алгоритм вероятностного тестирования простоты числа, который использует символ Якоби. Определяет числа как составные или вероятно простые. Распознает числа Кармайкла как составные.

Коротко и на русском

О новой технологии, над которой в MR работаю уже довольно долго, было объявлено на Interspeech 2011, проходящей сейчас во Флоренции.
С помощью гибридной контекстно-зависимой глубокой нейронной сети (Hybrid Context-Dependent Deep Neural Networks for Large Vocabulary Speech Recognition — CD-DNN-HMM) и Джорджа Дала (George Dahl) из Университета Торонто команде MR удалось улучшить качество и скорость распознавания речи до «почти человеческих» показателей. За счет сходства структур этой нейронной сети с 3D команда добилась значительного прироста скорости при использовании вычислений на GPU.

[ Оригинальная новость ]

Иногда возникают такие ситуации, когда нужно прочитать QR код, а смартфона под рукой нет. Что же делать? В голову приходит лишь попробовать прочитать вручную. Если кто-нибудь сталкивался с такими ситуациями или кому просто интересно как же читается QR код машинами, то данная статья поможет вам разобраться в этой проблеме.

В статье рассмотрены базовые особенности QR кодов и методика дешифрирования информации без использования вычислительных машин.

Иллюстраций: 14, символов: 8 510.

В прошлый раз мы разобрались как устроен JPEG (Декодирование JPEG для чайников). Вполне логично, что следующим форматом стал GIF. Кстати, он гораздо проще. Его, в отличии от JPEG, можно декодировать имея только ручку с бумажкой. Сначала, продолжая традицию, я захотел закодировать в GIF favicon Гугла, но потом решил, что лучше расписать процесс декодирования всего файла на маленьком изображении. Без всяких «а дальше по аналогии...». Пришлось долго экспериментировать, и картинка получилась неказистой, зато вполне наглядной для изучения.

Итак, мы будем ковырять вот эту картинку . Видите? :) Тогда она же, увеличенная в 10 раз:


Внутренности в hex-редакторе:

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

Перевод интервью с Кевином Слэвином (Kevin Slavin), разработчиком игр из Нью-Йорка, сооснователем компании Area/Code (теперь Zynga NY). Он ведёт курс компьютинга и дизайна в Нью-Йоркском университете, а в июле прочитал лекцию на конференции TED на тему алгоритмизации жизни (видеозапись лекции). Интервью опубликовано в журнале New Scientist (выпуск 2826 от 22.08.2011).

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

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

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

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

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

Индикатор (в контексте этой статьи) – это просто какая-то функция над ценой. Например, скользящее среднее (moving average). Существуют сотни разных индикаторов.

Фигура технического анализа – это какой-то известный паттерн, например, треугольник, двойное дно, голова и плечи. Фигур этих тоже сотни.

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

Здравствуйте.

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

Странно, но статей о извлечение знаний (data mining) и кластеризации (как одном из основных инструментом, которие используются для извлечения знаний) на Хабре совсем немного. А если говорить говорить о конкретных алгоритмах, то рассматривались только hard/soft k-means.

В статье ниже описывается теория и реализация (Python + matplotlib) не очень известного, но крайне интересного иерархического метода который можно назвать алгоритмом а-квазиэквивалентности.