Предисловие

Доброго времени суток, дорогие Хабровчане.

Сравнительно долгий период времени я изучаю такую область математики, как оптимизация. Если быть более конкретным, то оптимизация функций и динамических систем (синтез оптимального программного управления и управления с полной обратной связью). Особое внимание с моей стороны было уделено эвристическим методам оптимизации в связи с тем, что решение прикладных задач, с которыми я сталкиваюсь, связано с некоторыми трудностями:

• большие размерности,
• нелинейность,
• мультимодальность.

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

Несколько дней назад, на форуме KolibriOS зарегистрировался англоязычный пользователь с ником mdickie, и пожаловался, что в его ноутбуке Dell Latitude C640 не работает мышь: board.kolibrios.org/viewtopic.php?f=4&t=2389. Так как недавно у нас появилась поддержка USB (в частности, USB-мышей), то наш основатель Mario_Z логично предположил, что mdickie использует какую-то старую версию, и посоветовал ему скачать последнюю ночную сборку и проверить на ней.

Предположение Mario_Z оказалось верным — в ночной сборке мышь заработала, но сломалось что-то другое:

It works with the latest build,
Thanks
EDIT: It freezes slower.

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

I mean it needs a little more time to freeze the mouse.
Oh yes, the whole system freezes. The Keyboard and the clock aren't working.

Здесь уже я догадался, что причиной зависания, скорее всего, является драйвер SATA IDE, который в настоящий момент разрабатывает Mario_Z. На данный момент, в KolibriOS есть родной драйвер только для контроллера PATA, а поддержка контроллера SATA в режиме IDE осуществляется только через BIOS, что вносит 2 ограничения:

1. Доступ к дискам через «костыль» BIOS очень медленный, поэтому фильм с такого диска в KolibriOS не посмотришь — будет идти рывками. Скорость копирования файлов тоже неприемлемая — можно пообедать, пока копируется большой файл.
2. Некоторые диски без драйвера вообще никак не видны в системе.

Ввиду этого, на сегодняшний момент у нас пишутся 2 драйвера SATA (параллельно):

• Драйвер для контроллера SATA в режиме IDE от Mario_Z: board.kolibrios.org/viewtopic.php?f=1&t=2343
• Драйвер для контроллера SATA в режиме AHCI от Serge: board.kolibrios.org/viewtopic.php?f=31&t=2152

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

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

По процедурной генерации планов помещений есть много, очень много статей. Вот ещё пяток ссылок на статьи. Только исходников ни к одной из них нет.

В этой статье я расскажу о том, как я реализовал на Unity3d один простой метод генерации, который приводит к хорошим результатам и легко модифицируется. С картинками и исходниками.

Введение

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

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

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

Ниже дан перевод статьи
A SIMPLE BUT EFFICIENT REAL-TIME VOICE ACTIVITY DETECTION ALGORITHM
М.H. Moattar and M.M. Homayonpour
Laboratory for Intelligent Sound and Speech Processing (LISSP), Computer Engineering and Information Technology Dept., Amirkabir University of Technology, Tehran, Iran
Оригинал по ссылке

РЕЗЮМЕ

Алгоритм обнаружения активности голоса (Voice Activity Detection, далее VAD) очень важный метод в приложениях обработки речи и аудио. Эффективность большинства, если не всех методов обработки речи/аудио сильно зависит от эффективности применяемого алгоритма VAD. Идеальный детектор активности голоса должен быть независимым от области применения приложения, от уровня шума и быть наименее зависимым от максимума параметров приложения, в котором его используют. В этой статье предлагается близкий к идеальному алгоритм VAD, который одновременно легок в реализации и устойчив к шуму. Предложенный метод использует такие кратковременные характеристики как Spectral Flatness (SF) (спектральная плоскостность, ровность) и Short-term Energy, что делает метод целесообразным для применения в реальном времени. Этот метод был проверен на нескольких записях с разным уровнем шума и сравнивался с недавно преложенными методами. Эксперименты показали удовлетворительные результаты при разных уровнях шума.

Добрый день, хабр!
Наверное, у всех системных администраторов была проблема определения имени компьютера пользователя. То есть мы знаем имя сотрудника, но какой у него компьютер, без понятия. И, зачастую, попытка заставить пользователя определить имя компьютера вызывает мучение. Они вместо этого называют имя пользователя, mail, номер телефона, все что угодно, только не имя компьютера. А попытка объяснить пользователю где находится информация о системе вызывает баттхерт сотрудника и лютую ненависть. Можно, конечно, было бы написать какую-нибудь утилитку, позволяющая отображать имя компьютера на рабочем столе или где-нибудь еще на видном месте, но для этого надо каждый раз объяснять где находится эта информация. Немного упрощает задачу, но не решает ее полностью. Тем более что я склоняюсь к тому, что пользователю и во все положено не знать имя компьютера, на котором он сидит. В результате было решено сделать определение имени компьютера современным, удобным, правильным и, главное, автоматическим.


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

Спасибо Хабру, много полезного тут для себя нашел. Думаю, пора «отдавать долги».
Хочу описать алгоритм, который работает больше года на моем шлюзе для балансировки каналов (Гбит трафика, 8k клиентов, 2 провайдера, AS на 1k адресов, большинство клиентов за NAT). Возможно, кому-то пригодится. Во всяком случае, ничего похожего не встречал и когда специально искал — не нашел. Так что полностью мое детище.
Все, что попадалось на просторах Интернета, позволяло резервировать один из каналов. И исходящий регулировать — описаний много. А вот регулировать входящий трафик (т.е. обеспечить равномерную загрузку нескольких каналов) — не попадалось.
Конечно, указанный алгоритм нельзя считать универсальным, подойдет только в подходящих условиях.

Итак, исходные:
— Шлюз на Linux (Debian 6). Используется пакет quagga (бывший zebra).
— Два провайдера (пусть будут ТТК и РТК). Каждый дает канал определенной толщины, «лишнее» режет.
— AS на 1k адресов (пусть будет 1.1.144.0/22). AS0000.
— Большинство клиентов имеют серые адреса (пусть будет 192.168.0.0/16), «клиентские» сети 192.168.1-99.0/24, на шлюзе натятся.
— Небольшая часть клиентов имеют белые адреса в пространстве моей AS.

Задача:
Обеспечить равномерную загрузку каналов ТТК и РТК входящим трафиком для исключения перегрузки каналов.

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

# Весь код в статье написан на языке Python

Основы

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

Динамическое программирование — это когда у нас есть задача, которую непонятно как решать, и мы разбиваем ее на меньшие задачи, которые тоже непонятно как решать. (с) А. Кумок.

Привет, Хабр!

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

В названии этой статьи присутствуют слова «скобочная последовательность». За этими словами скрывается нечто большее, поскольку с помощью скобок можно описать очень разнообразные объекты, в том числе и бинарные деревья. На Хабре этому факту был посвящен отдельный пост.

В этой статье я расскажу несколько способов генерирования случайной скобочной последовательности, в том числе за линейное время, а потом приведу пример преобразования последовательности в бинарное дерево. Интересно?

Эта статья родилась как логическое продолжение пятничного поста о методе Бутстрапа, а особенно, комментариев к нему. Не защищая метод Бутстрапа, стоит уделить внимание методам Монте-Карло. Здесь я хочу поделиться своим опытом применения Монте-Карло в одной из своих практических задач, а также обоснованием законности этого применения.

Итак, моя задача заключалась в необходимости вычисления площади фигуры, являющейся пересечением окружностей, с последующей реализацией на языке JavaScript. Площадь под графиком – это интеграл. Интегрирование методом Монте-Карло достаточно широко известно, но, как многие верно заметят, его применение требует некоторого обоснования. За подробностями прошу под кат.

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

На данный момент сделаны хеш-таблицы 6 типов: множества примитивов, объектов и все 4 варианта мапов: примитив — примитив, примитив — объект, объект — примитив и объект — объект, над которыми нависает туча обобщающих интерфейсов.

Меня всегда удивляло, почему все подобные библиотеки создают еще одну иерархию типов, а не встраиваются в давно уже зарекомендовавший себя стандартный каркас коллекций Явы. Никаких принципиальных проблем с этим я не видел и не вижу. Поэтому над моей тучей интерфейсов, как на пантеоне, возвышаются java.lang.Iterable, java.util.Collection и java.util.Map. Я не зря дал ссылки на документацию по Java 8. Реализованы почти все методы из будущих интерфейсов, кроме spliterator(). Можно начинать привыкать.

Доброго времени суток!

Думаю, головоломка Судоку не нуждается в представлении. Многие из нас проводят за её решением достаточно много времени. Например, когда нужно убить время в дороге или просто поворочать мозги, чтобы не сохли. На хабре есть довольно много постов о решении головоломки. Но когда человек решает с десяток, а может и сотню головоломок, то найдётся пытливый ум, который задаст себе вопрос «А как же получается таблица Судоку, имеющая единственное решение? И как можно описать алгоритм для сетки 9x9?».

Приведённый алгоритм является вполне логичным. Но моей задачей было описание и реализация. Обо всём этом написано под катом.

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

В статистике тоже есть нечестный метод, который позволяет получить примерный ответ на многие практические вопросы без анализа, грубой компьютерной силой: бутстрап (англ. bootstrap). Придумал и опубликовал его в 1979 году Брэдли Эфрон.

Решение транспортной задачи при помощи генетического алгоритма как часть SOA

Приветствую уважаемое Хабрасообщество!

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

Формулировка задачи

Википедия формулирует задачу следующим образом — задача об оптимальном плане перевозок однородного продукта из однородных пунктов наличия в однородные пункты потребления на однородных транспортных средствах (предопределённом количестве) со статичными данными и линеарном подходе.

Например – необходимо спланировать доставку бутылей воды по городу, известны потребности каждого заказчика, грузоподъёмность транспортных средств и расстояния между точками.

В прошлой статье я писал про эвристические методы оптимизации перебора. В этой статье я расскажу вам о ещё одной, но уже асимптотической оптимизации — meet-in-the-middle.

Типичные для этого метода снижения асимптотики: и .

Вступление

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

Meet-in-the-middle имеет смысл применять, если для конкретной задачи выполняются два условия:
1) Время обработки половины данных асимптотически меньше времени получения итогового ответа.
2) Известен асимптотически более быстрый способ получения ответа для всей задачи с использованием информации об обработки её половинок.

Доброго времени суток, хабр!

В этой статье я расскажу о том, как я создавал искусственный интеллект для игры Эрудит. Подробности под катом.

В задачах поиска информации одной из важнейших задач является поиск точно заданной подстроки в строке. Примитивный алгоритм поиска подстроки в строке основан на переборе всех подстрок, длина которых равна длине шаблона поиска, и посимвольном сравнении таких подстрок с шаблоном поиска. По традиции шаблон поиска или образец принято обозначать как needle (англ. «иголка»), а строку, в которой ведётся поиск — как haystack (англ. «стог сена»). На языке Python примитивный алгоритм выглядит так:

index = -1
for i in xrange(len(haystack)-len(needle)+1):
    success = True
    for j in xrange(len(needle)):
        if needle[j]<>haystack[i+j]:
            success = False
            break
    if success:
        index = i
        break
print index

Обозначим n=|haystack|, m=|needle|. Простейший алгоритм поиска даже в лучшем случае проводит n–m+1 сравнений; если же есть много частичных совпадений, скорость снижается до O(n*m).

Рассматриваемый далее алгоритм хотя и имеет невысокую скорость на «хороших» данных, но это компенсируется отсутствием регрессии на «плохих». Алгоритм Кнута-Морриса-Пратта является одним из первых алгоритмов с линейной оценкой в худшем случае.

Нормальное распределение (распределение Гаусса) всегда играло центральную роль в теории вероятностей, так как возникает очень часто как результат воздействия множества факторов, вклад любого одного из которых ничтожен. Центральная предельная теорема (ЦПТ), находит применение фактически во всех прикладных науках, делая аппарат статистики универсальным. Однако, весьма часты случаи, когда ее применение невозможно, а исследователи пытаются всячески организовать подгонку результатов под гауссиану. Вот про альтернативный подход в случае влияния на распределение множества факторов я сейчас и расскажу.

Благодаря кодам Рида-Соломона можно прочитать компакт-диск с множеством царапин, либо передать информацию в условиях связи с большим количеством помех. В среднем для компакт-диска избыточность кода (т.е. количество дополнительных символов, благодаря которым информацию можно восстанавливать) составляет примерно 25%. Восстановить при этом можно количество данных, равное половине избыточных. Если емкость диска 700 Мб, то, получается, теоретически можно восстановить до 87,5 Мб из 700. При этом нам не обязательно знать, какой именно символ передан с ошибкой. Также стоит отметить, что вместе с кодированием используется перемежевание, когда байты разных блоков перемешиваются в определенном порядке, что в результате позволяет читать диски с обширными повреждениями, локализированными близко друг к другу (например, глубокие царапины), так как после операции, обратной перемежеванию, обширное повреждение оборачивается единичными ошибками во множестве блоков кода, которые поддаются восстановлению.

Давайте возьмем простой пример и попробуем пройти весь путь – от кодирования до получения исходных данных на приемнике. Пусть нам нужно передать кодовое слово С, состоящее из двух чисел – 3 и 1 именно в такой последовательности, т.е. нам нужно передать вектор С=(3,1). Допустим, мы хотим исправить максимум две ошибки, не зная точно, где они могут появиться. Для этого нужно взять 2*2=4 избыточных символа. Запишем их нулями в нашем слове, т.е. С теперь равно (3,1,0,0,0,0). Далее необходимо немного разобраться с математическими особенностями.

Поля Галуа

Многие знают романтическую историю о молодом человеке, который прожил всего 20 лет и однажды ночью написал свою математическую теорию, а утром был убит на дуэли. Это Эварист Галуа. Также он несколько раз пытался поступить в университеты, однако экзаменаторы не понимали его решений, и он проваливал экзамены. Приходилось ему учиться самостоятельно. Ни Гаусс, ни Пуассон, которым он послал свои работы, также не поняли их, однако его теория отлично пригодилась в 60-х годах ХХ-го века, и активно используется в наше время как для теоретических вычислений в новых разделах математики, так и на практике.

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

В общем виде словарь — множество записей вида {строка, данные ассоциированные с этой строкой}.

Например, для морфологического анализа словарь состоит из троек {словоформа, нормальная форма, морфологические характеристики}. При анализе слова «мыла» из предложения «мама мыла раму» надо уметь получать следующие варианты анализа:

Нормальная форма	Характеристики
МЫЛО	S (существительное), РОД (родительный падеж), ЕД (единственное число), СРЕД (средний род), НЕОД (неодушевленность)
МЫЛО	S (существительное), ИМ (именительный падеж), МН (множественное число), СРЕД (средний род), НЕОД (неодушевленность)
МЫЛО	S (существительное), ВИН (винительный падеж), МН (множественное число), СРЕД (средний род), НЕОД (неодушевленность)
МЫТЬ	V (глагол), ПРОШ (прошедшее время), ЕД (единственное число), ИЗЪЯВ (изъявительное наклонение), ЖЕН (женский род), НЕСОВ (несовершенный вид)