Алгоритмы *

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

Отличие от JPEG

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

Пример

Для примера сильно сожмем одно и тоже изображение приблизительно до одного размера:

В начале с использованием JPEG:

(7959 байт)

затем алгоритмом вейвлетного сжатия JPEG 2000:

(7813 байт)

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

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

Итак, алкотестер. Он же breathalyzer. Это задачка snack-сложности по классификации facebook, т.е. по их меркам она совсем не сложная. Что не помешало мне потратить на её решение добрых пару недель(отчасти из-за принципиального желания решить её на Ruby). Эту задачу я делал второй по-очереди, и именно она натолкнула меня на основную идею, побудившую меня прикладывать кучу усилий для поиска решения. А идея была в следующем — я не умею программировать…

Я расскажу о структуре под названием дерево отрезков и приведу его простую реализацию на языке С++. Эта структура весьма полезна в случаях, когда необходимо часто искать значение какой-то функции на отрезках линейного массива и иметь возможность быстро изменять значения группы подряд идущих элементов.
Типичный пример задачи на дерево отрезков:
Есть линейный массив, изначально заполненный некоторыми данными. Далее приходят 2 типа запросов:
1й тип — найти значение максимального элемента на отрезке массива [a..b].
2й тип — заменить iй элемент массива на x.
Возможен запрос «добавить х ко всем элементам на отрезке [a..b]», но в данной статье я его не рассматриваю.
С помощью дерева отрезков можно искать не только максимум чисел, но и любую функцию, удовлетворяющую свойству ассоциативности.

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

Те, кто занимался графикой на Windows Mobile, наверняка слышали о графической библиотеке GapiDraw. Если заглянуть в их Feature List, то в разделе High Performance можно обнаружить следующие слова: «drawing surfaces with opacity will only require one multiplication per pixel». То есть, они утверждают, что для рисования полупрозрачных картинок требуется всего по одному умножению на каждый пиксель.

В данной статье я попытаюсь объяснить, как это возможно.

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

Существует много способов вычисления числа Пи. Самым простым и понятным является численный метод Монте-Карло, суть которого сводится к простейшему перебору точек на площади. Суть расчета заключается в том, что мы берем квадрат со стороной 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 приемлемую альтернативу, либо наилучшую.