Люди, использующие системы контроля версий исходного кода (SVN, Mercurial, Git и т.п.), наверняка часто пользуются возможностью сравнения версий файлов для просмотра внесенных пользователями изменений. Существует множество независимых программ сравнения версий (WinMerge, BeyondCompare и др.). При сравнении версий, как правило, две версии файла показываются рядом друг с другом таким образом, чтобы одинаковые (неизменившиеся) части документов были расположены напротив друг друга, а изменившиеся (добавленные и удаленные) выделяются соответствующим цветом.
Уверен, многим было бы интересно узнать, какие алгоритмы могут использоваться для реализации такого сравнения.
Читать полностью »
Метка «Алгоритмы» - 15
О подходах к сравнению версий файлов
2012-04-24 в 4:45, admin, рубрики: алгоритм, Алгоритмы, контроль версий, оптимизация, Программирование, разработка, расстояние Левенштейна, сравнение, сравнение файлов, хэширование, метки: алгоритм, Алгоритмы, контроль версий, оптимизация, расстояние Левенштейна, сравнение, сравнение файлов, хэшированиеПолиномиальные хеши и их применение
2012-04-23 в 19:37, admin, рубрики: Алгоритмы, олимпиадные задачи, поиск подстроки в строке, сравнение строк, строки, хеширование, метки: Алгоритмы, олимпиадные задачи, поиск подстроки в строке, сравнение строк, строки, хешированиеЗдравствуй. Сегодня я напишу, как можно использовать полиномиальные хеши (далее просто хеши) при решении различных алгоритмических задач.
Введение
Начнем с определения. Пусть у нас есть строка s0..n-1. Полиномиальным хешем этой строки называется число h = hash(s0..n-1) = s0 + ps1 + p2s2 +… + pn-1sn-1, где p — некоторое натуральное число (позже будет сказано, какое именно), а si — код i-ого символа строки s (почти во всех современных языках он записывается s[i]).
Хеши обладают тем свойством, что у одинаковых строк хеши обязательно равны. Поэтому основная операция, которую позволяют выполнять хеши — быстрое сравнение двух подстрок на равенство. Читать полностью »
Шум Перлина (Perlin Noise)
2012-04-23 в 7:41, admin, рубрики: game development, Gamedev, gamedevelopment, Алгоритмы, переводы, метки: Gamedev, gamedevelopment, АлгоритмыДоброго времени суток. Предлагаю Вашему вниманию перевод статьи про шум Перлина (вот этой). Ссылки на эту статью уже мелькали на хабре (тут), но перевод статьи мне не попался. Так что надеюсь кому либо он может оказаться полезен.
Многим людям приходилось использовать генератор случайных чисел в программах для создания непредсказуемости, чтобы сделать движение и поведение объектов более натуральными или генерировать текстуры. Генераторы случайных чисел, конечно, имеют свои области применения, но иногда их выход может быть слишком «жесткий», чтобы казаться естественным. В этой статье мы представляем функцию, которая имеет очень широкий спектр применения, больше, чем я мог бы думать, но в основном везде, где вам нужно чтобы что-то выглядело естественного происхождения. К тому же вывод может быть легко настроен под ваши нужды.
Если посмотреть на многие вещи в природе, вы заметите, что они являются фрактальными. Они имеют различные уровни детализации. Типичным примером является очертание горного хребта. Оно содержит значительные различия в высоте (горы), средние изменения (холмы), небольшие вариации (валуны), крошечные изменения (камни) и так далее. Посмотрите на что угодно: распространение пятен травы на поле, волн в море, движение муравьев, движение ветвей дерева, узоры из мрамора, ветра. Все эти явления поддаются той же схеме, в больших и малых вариациях. Функция шума Перлина воссоздает это, просто складывая функции шума в различных масштабах.
Для создания функции шума Перлина, вам нужны две вещи, функции шума и функция интерполяции.
Читать полностью »
Unbiased rendering (рендеринг без допущений)
2012-04-16 в 14:47, admin, рубрики: 3d графика, path tracing, ray tracing, unbiased rendering, Алгоритмы, Анимация и 3D графика, рендеринг, рендеринг без допущений, трассировка лучей, трассировка пути, метки: 3d графика, path tracing, ray tracing, unbiased rendering, Алгоритмы, рендеринг, рендеринг без допущений, трассировка лучей, трассировка путиВ компьютерной графике, рендеринг без допущений относится к технике рендеринга, которая не вносит в расчет систематических ошибок, предположений или погрешностей. Изображение получается таким, каким должно быть в природе, а рендер не имеет настроек качества поверхностей либо источников света.
.png "Unbiased rendering (рендеринг без допущений)")
Изображение отрендерено с помощью Maxwell Render.
GraphiCon’2012 — 22 международная конференция по компьютерной графике и машинному зрению
2012-04-06 в 15:29, admin, рубрики: Алгоритмы, Компьютерное зрение, конференция, обработка изображений, Работа с видео, метки: Алгоритмы, Компьютерное зрение, конференция, обработка изображений 
Друзья! С 1 по 5 октября в Москве пройдет международная конференция по компьютерной графике и машинному зрению GraphiCon’2012. Партнерами конференции уже выступали такие компании, как Intel, NVidia, Microsoft, Autodesk и другие. Если вы работаете или интересуетесь этими направлениям, вы можете стать участником конференции или выступить на ней с докладом.
По итогам конференции лучшие доклады участников будут опубликованы в журнале списка ВАК. Крайний срок подачи статей на публикацию — 28 мая.
Читать полностью »
Структура Radix Tree для сжатия данных
2012-03-31 в 15:45, admin, рубрики: c++, radix tree, Алгоритмы, исходники, сжатие данных, структуры данных, метки: radix tree, Алгоритмы, исходники, сжатие данных, структуры данных 
Этот топик повествует об использовании Radix Tree на практическом примере. Radix Tree или дерево остатков — это структура данных, формируемая по принципу хранение значений в листовом узле. Промежуточные узлы представляют собой элемент конечного значения. Это может быть бит для чисел, символ для строк или цифра для номера, как в примере ниже. Приведенный алгоритм сжатия с использованием Radix Tree используется в реальной embeded системе, для хранения параметров телефонного файрвола.
Читать полностью »
История игры Триплекс, или сколько нужно квадратиков чтобы сломать голову
2012-03-30 в 14:13, admin, рубрики: android, game, game development, Gamedev, Google Chrome, html 5, html5, java, javascript, puzzle, Алгоритмы, Веб-разработка, головоломка, Программирование, метки: android, game, Gamedev, Google Chrome, html 5, html5, java, javascript, puzzle, Алгоритмы, головоломка 
Чтобы освоить азы Web программирования, я решил написать HTML5 игру — головоломку под названием Triplex (www.quadpuzzle.ru). Написать игру для себя и для друзей — полдела. Захотелось довести проект до ума, сделав из игры продукт для широкого круга пользователей. Насколько получилось — судить вам.
Правила игры просты. На игровом поле разложены фигуры из квадратиков. Цель игры — уложить все фигуры в указанный прямоугольник. Вращать можно только одну фигуру, помеченную кружком, если она есть. Решение в каждой задаче существует и единственное.
Создаем движущиеся картинки с помощью Processing
2012-03-21 в 14:15, admin, рубрики: processing, Алгоритмы, обработка изображений, метки: Processing, Алгоритмы, обработка изображений 
На Хабре есть статья, как получить синемаграфы с помощью бесплатной программы от Microsoft. Меня заинтересовала эта тема и я решил написать короткий скетч для скриптового языка Processing. Что это за язык программирования можно почитать здесь. Подобные движущиеся картинки представляют собой набор нескольких десятков кадров, у которых большая часть пикселей прозрачна.Читать полностью »
… или как я получил «Аленку» за консольное приложение
Существует довольно распространённое мнение, что выполнение различных тестовых заданий помогает очень быстро поднять свой профессиональный уровень. Я и сам люблю иногда откопать какое-нить мудреное тестовое и порешать его, чтобы быть постоянно в тонусе, как говорится. Как-то я выполнял конкурсное задание на стажировку в одну компанию, задачка показалась мне забавной и интересной, вот её краткий текст:
Представьте, что ваш коллега-нытик пришел рассказать о своей непростой задаче — ему нужно не просто упорядочить по возрастанию набор целых чисел, а выдать все элементы упорядоченного набора с L-го по R-й включительно!
Вы заявили, что это элементарная задача и, чтобы написать решение на языке C#, вам нужно десять минут. Ну, или час. Или два. Или шоколадка «Алёнка»
Предполагается, что в наборе допускаются дубликаты, и количество элементов будет не больше, чем 10^6.
К оценке решения есть несколько комментариев:
Ваш код будут оценивать и тестировать три программиста:
- Билл будет запускать ваше решение на тестах размером не больше 10Кб.
- В тестах Стивена количество запросов будет не больше 10^5, при этом количество запросов на добавление будет не больше 100.
- В тестах Марка количество запросов будет не больше 10^5.
Решение может быть очень интересным, поэтому я посчитал нужным его описать.
Читать полностью »
Учебный процесс в IT / Обновление по онлайн-курсам Stanford University
2012-03-06 в 19:38, admin, рубрики: nlp, Алгоритмы, дистанционное образование, статистический анализ, метки: nlp, Алгоритмы, дистанционное образование, статистический анализПонимаю, что все заинтересованные уже получили оповещение по почте, но для тех кто не в танке — объявление: онлайн курсы от Stanford University наконец-то начинаются.
Probabilistic Graphical Models — начинается 19 марта, лекции пока не доступны.
По данным курсам доступны первые лекции и задания
Natural Language Processing — начало с 12 марта, первое задание Spamlord должно быть уже выполнено к 19 марта, так что регистрируемся.
Design and Analysis of Algorithms I — курс по дизайну и анализу алгоритмов.