Недавно я решил написать программу, которая будет выдавать алгоритм решения некоторых механических головоломок, таких как кубик 2х2х2, 3х3х1, пирамидка и других. Полный список есть в интерфейсе программы, а также на её сайте, но об этом позже. Естественно, алгоритм этот должен быть самым коротким, иначе не интересно: можно было бы забить туда известные формулы, чтобы она собирала как человек. Сразу скажу две причины, почему я не стал включать в список кубик Рубика 3х3: во-первых, из за его популярности. Наверняка есть уже куча софта для этого, не хочется изобретать велосипед. Ну и во-вторых, из за его сложности: начав писать программу, я хотел «потренироваться» на чём-нибудь попроще. Итак, приступим. Читать полностью »
Рубрика «Алгоритмы» - 312
Собираем кубик Рубика 2x2x2, пирамидку и другие механические головоломки
2012-03-31 в 20:37, admin, рубрики: Алгоритмы, кубик рубика, перебор, Программирование, метки: кубик рубика, перебор, ПрограммированиеСтруктура Radix Tree для сжатия данных
2012-03-31 в 15:45, admin, рубрики: c++, radix tree, Алгоритмы, исходники, сжатие данных, структуры данных, метки: radix tree, Алгоритмы, исходники, сжатие данных, структуры данных 
Этот топик повествует об использовании Radix Tree на практическом примере. Radix Tree или дерево остатков — это структура данных, формируемая по принципу хранение значений в листовом узле. Промежуточные узлы представляют собой элемент конечного значения. Это может быть бит для чисел, символ для строк или цифра для номера, как в примере ниже. Приведенный алгоритм сжатия с использованием Radix Tree используется в реальной embeded системе, для хранения параметров телефонного файрвола.
Читать полностью »
Асинхронный конечный автомат: идеология и технология
2012-03-31 в 14:05, admin, рубрики: dos, FSM, Алгоритмы, асинхронная модель, драйвера, конечные автоматы, очередь сообщений, Проектирование и рефакторинг, сетевые протоколы, метки: dos, FSM, асинхронная модель, драйвера, конечные автоматы, очередь сообщений, сетевые протоколыВступление
Хорошо, когда твои подчиненные никогда не болеют, не умирают, всегда присутствуют на работе и выполняют твои распоряжения без предварительных приготовлений: «Вызвали — встань». Таковы, например, веб-сервисы, соблюдающие модель REST (которая, если отбросить специальную HTTP-терминологию, сводится к тому, что интерфейс сервиса фактически является интерфейсом контейнера данных).
В реальной жизни у подчиненных бывают насморк и декретный отпуск, у сетевых соединений — таймауты, у авиарейсов — погода, а у автомобильных двигателей в мороз — необходимое время холостого прогрева.
Асинхронный конечный автомат — это удобная абстракция верхнего уровня для управления сущностями с богатым и не всегда предсказуемым внутренним миром. Такой сущностью может быть аппаратное устройство, сессия сетевого протокола или просто параллельно запущенный процесс, код которого вы не контролируете.
Описываемая ниже архитектура асинхронного конечного автомата решает ряд стандартных проблем, возникающих при «лобовой» интеграции подсистем с учетом их внутреннего состояния. Самая заметная из таких проблем — это недостаточная разнесенность (я бы даже сказал — недостаточная «гальваническая развязка») сущностей сигнала и перехода между состояниями, из-за чего автомат становится неустойчивым к DoS-атакам. Есть и другие, менее очевидные — например, «недостаточно атомарная» замена узла подсистемы или используемого ей ресурса.
Анатомия (объектная декомпозиция)
Модель конечного автомата включает следующие базовые сущности:
- Состояние — это режим функционирования управляемой системы, отличный от других по предоставляемым возможностям. Таким образом, снапшоты кешей и буферов, варианты циклов «от забора и до обеда» и другие акциденции управляемой системы в понятие «состояния» не входят. В норме состояний должны быть считанные единицы; если счет пошел на второй десяток — скорее всего, управляемую систему следует раздробить или иерархизировать.
- Условие — это логическое значение (true или false) на одном из «входов» системы. Суперпозиция состояний всех входов автомата однозначно определяет целевое состояние автомата. Таким образом, любой входной сигнал, значимый для состояния автомата, в конечном счете сводится к установке значения одного или нескольких условий.
- Реакция — это отклик автомата на отличие текущего состояния от целевого. Принципиально различных видов реакции мы насчитали два с половиной: прямой переход между состояниями, маршрут и стоп-маршрут («кирпич»). Прямой переход может быть и пустой операцией (NOP) — например, в случае, если изменение входов вызвано уведомлением о завершении асинхронной операции.
История игры Триплекс, или сколько нужно квадратиков чтобы сломать голову
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). Написать игру для себя и для друзей — полдела. Захотелось довести проект до ума, сделав из игры продукт для широкого круга пользователей. Насколько получилось — судить вам.
Правила игры просты. На игровом поле разложены фигуры из квадратиков. Цель игры — уложить все фигуры в указанный прямоугольник. Вращать можно только одну фигуру, помеченную кружком, если она есть. Решение в каждой задаче существует и единственное.
Часть №6. Введение в сворачивание многоспиральных РНК
2012-03-29 в 13:23, admin, рубрики: Алгоритмы, биоинформатика, Биотехнологии, кибернетика, математика, сворачивание рнк, теория игр, Фолдинг белков, метки: кибернетика, математика, сворачивание рнк, теория игр, Фолдинг белковИтак, в прошлых частях мы разобрались как сравнительно просто сворачивать спирали РНК. Теперь нам предстоит понять, как вообще сворачивается РНК. То РНК, которые мы взяли в виде примера имеет три спирали. Две из них L1 и L2 можно свернуть независимо. А вот с третьей проблемы. Эта третья состоит из концов РНК, и при ее сворачивании начинаю двигать наши свернутые спирали L1 и L2. Во-первых, при этом они мешают друг другу, и следовательно и сворачиванию третьей спирали. Во-вторых, возможно образование около десятка разнообразных псевдосимметричных структур — спирали L1, L2 могут по разному располагаться по отношению к сворачиваемым концам РНК.
Здесь мы попробуем разобраться как эти проблемы решить.
Мел-кепстральные коэффициенты (MFCC) и распознавание речи
2012-03-28 в 5:52, admin, рубрики: dsp, dtw, mfcc, Алгоритмы, Программирование, Работа со звуком, распознавание речи, метки: dsp, dtw, mfcc, распознавание речиНедавно я наткнулся на интересную статью, опубликованную rgen3, в которой описан DTW-алгоритм распознавания речи. В общих чертах, это сравнение речевых последовательностей с применением динамического программирования.
Заинтересовавшись темой, я попробовал применить этот алгоритм на практике, но на этом пути меня поджидало некоторое количество граблей. Прежде всего, что именно нужно сравнивать? Непосредственно звуковые сигналы во временной области — долго и не очень эффективно. Спектрограммы — уже быстрее, но не намного эффективнее. Поиски наиболее рационального представления привели меня к MFCC или Мел-частотным кепстральным коэффициентам, которые часто используются в качестве характеристики речевых сигналов. Здесь я попытаюсь объяснить, что они из себя представляют.Читать полностью »
Помехоустойчивое кодирование с ипользованием различных кодов
2012-03-27 в 9:49, admin, рубрики: Алгоритмы, Восстановление данных, коды, помехоустойчивое кодирование, метки: коды, помехоустойчивое кодирование Это продолженеие статьи о помехоустойчивом кодировании, которая очень долго лежала в черновиках. В прошлой части нет ничего интересного с практической точки зрения — лишь общие сведения о том, зачем это нужно, где применяется и т.п. В данной части будут рассматриваться некоторые (самые простые) коды для обнаружения и/или исправления ошибок. Итак, поехали.
Читать полностью »
Сжате пакетов и защита С# клиента с открытым исходным кодом
2012-03-26 в 18:45, admin, рубрики: .net, Алгоритмы, защита, обратка пакетов, сжатие, метки: .net, c++, защита, обратка пакетов, сжатиеПривет, сообщество.
Мой путь в программировании: ASP VB script >> VB.Net >> C#, с С и С++ я знаком минимально.
С давних пор пишу онлайн RPG (около 9 лет) и сейчас дошел до стадии публичного онлайн тестирования.
Клиентская часть написана на С# и доступна для изучения(улучшения) всеми желающими.
У меня нет никакой паранойи (надеюсь ;-)) относительно хакеров и любителей поломать чужие сервера — я отлично понимаю, что никому нет дела до моих исходников, однако мне хочется, чтобы на сервер отсылались пакеты, обработанные только известной, проверенной и утверждённой версией клиента.
Поэтому я хочу реализовать защиту в виде подключаемой приватной нативной библиотеки, которая будет отсылать на сервер хеш код используемого клиента, плюс она-же будет шифровать/дешифровать/сжимать/разжимать все пакеты. То есть если в клиенте реализуют отсылку фиктивного хешь кода, без использования нативной DLL, то злоумышленнику также придется реализовать свою версию обработки пакетов.
Читать полностью »
Сжатие пакетов и защита С# клиента с открытым исходным кодом
2012-03-26 в 18:45, admin, рубрики: .net, Алгоритмы, защита, обратка пакетов, сжатие, метки: .net, c++, защита, обратка пакетов, сжатиеПривет, сообщество.
Мой путь в программировании: ASP VB script >> VB.Net >> C#, с С и С++ я знаком минимально.
С давних пор пишу онлайн RPG (около 9 лет) и сейчас дошел до стадии публичного онлайн тестирования.
Клиентская часть написана на С# и доступна для изучения(улучшения) всеми желающими.
У меня нет никакой паранойи (надеюсь ;-)) относительно хакеров и любителей поломать чужие сервера — я отлично понимаю, что никому нет дела до моих исходников, однако мне хочется, чтобы на сервер отсылались пакеты, обработанные только известной, проверенной и утверждённой версией клиента.
Поэтому я хочу реализовать защиту в виде подключаемой приватной нативной библиотеки, которая будет отсылать на сервер хеш код используемого клиента, плюс она-же будет шифровать/дешифровать/сжимать/разжимать все пакеты. То есть если в клиенте реализуют отсылку фиктивного хешь кода, без использования нативной DLL, то злоумышленнику также придется реализовать свою версию обработки пакетов.
Читать полностью »
Код Хэмминга. Пример работы алгоритма
2012-03-26 в 12:12, admin, рубрики: алгоритм, Алгоритмы, Восстановление данных, код, пример, хэмминг, метки: алгоритм, код, пример, хэммингВступление.
Прежде всего стоит сказать, что такое Код Хэмминга и для чего он, собственно, нужен. На Википедии даётся следующее определение:
Коды Хэмминга — наиболее известные и, вероятно, первые из самоконтролирующихся и самокорректирующихся кодов. Построены они применительно к двоичной системе счисления.
Другими словами, это алгоритм, который позволяет закодировать какое-либо информационное сообщение определённым образом и после передачи (например по сети) определить появилась ли какая-то ошибка в этом сообщении (к примеру из-за помех) и, при возможности, восстановить это сообщение. Сегодня, я опишу самый простой алгоритм Хемминга, который может исправлять лишь одну ошибку.
Читать полностью »