Алгоритмы *

Задача о назначениях известна достаточно давно, основные алгоритмы ее решения уже описаны на Хабарахабре (см. например Задача о назначениях). Тем не менее задача до сих пор актуальна при распределении сотрудников по должностям, в случае когда сотрудников и должностей и критериев очень много, обычные методы окажутся очень трудоемкими
для лица, принимающего решение (ЛПР). Более того, на данный момент для решения такой задачи возможно использование генетического алгоритма и его модификации (интерактивный генетический алгоритм). То есть возникает достаточно сложная многокритериальная задача поиска оптимальной альтернативы, которю можно разбить на две задачи. Если вакансия одна, а претендентов много, то для ЛПР для выбора эффективным будет использование метода многокритериальный выбора альтернатив с использованием правил нечеткого вывода (Многокритериальный выбор альтернатив с использованием правил нечеткого вывода.).

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

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

К сожалению, большинство инструментов, которые применяются для вычислений, будут прятать результат, но если вы найдете такой, который этого (1/998001=1.002003004005006e-06) не делает, то, может, не сразу заметно, но деление 1 на 998001 дает в результате все числа от 001 до 999.

Если вам интересна такого рода математика, то 1/9801 выдаст похожий результат, последовательность чисел от 01 до 99

Можно посмотреть в WolframAlpha. Нажимайте «More digits» в блоке «Decimal approximation»:
www.wolframalpha.com/input/?i=1%2F998001
www.wolframalpha.com/input/?i=1%2F9801

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

На симпозиуме по дискретным алгоритмам ACM на этой неделе группа исследователей из MIT представила новый алгоритм быстрого преобразования Фурье sFFT (Sparse Fast Fourier Transform), который на некоторых задачах может быть в десятки или сотни раз быстрее классического БПФ.

После возни с трехмерной игрой «Жизнь» я вспомнил о том, что для обычной, конвеевской версии этой игры существует алгоритм под названием «Hashlife». Он несколькими фразами описан в Википедии, и приведенной там картинки с комментарием («конфигурация через 6 октиллионов поколений») для меня было достаточно, чтобы держаться от этой идеи подальше: сколько же ресурсов нужно этому алгоритму? Стоит ли за него браться вообще?

Общая идея алгоритма такая.

Допустим, что у нас есть квадрат поля размером N*N (N>=4 – степень двойки). Тогда мы можем однозначно определить состояние его центральной области размером (N/2)*(N/2) через T=N/4 шага. Если мы запомним состояние исходного квадрата и результат его эволюции в словаре, то сможем в следующий раз, встретив такой квадрат, сразу определить, что с ним станет.

Предположим, что для квадратов N*N эволюцию на N/4 шага мы считать умеем. Пусть у нас есть квадрат 2N*2N. Чтобы просчитать его развитие на N/2 шагов, можно сделать следующее.

Разобьем квадрат на 16 квадратиков со стороной N/2. Составим из них 9 квадратов со стороной N, для каждого из них найдем результат эволюции на N/4 шага. Получится 9 квадратов со стороной N/2. В свою очередь, из них составим уже 4 квадрата со стороной N, и для каждого из них найдем результат эволюции на N/4 шага. Полученные 4 квадрата со стороной N/2 объединим в квадрат со стороной N – он и будет ответом.

Предыстория

Очень давно, когда мои познания в PHP были на уровне мат операций и вывода результатов, а нашел очень полезный класс, написанный Kalpeh Gamit, его сайт уже давно недоступен, поэтому, к сожалению контакты оставить не могу. Класс распространяется под именем GetImageColor и лицензией GPL 2.0.

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

Предыдущие части:

1. Многокритериальный выбор альтернатив с использованием правил нечеткого вывода. Часть 1/3: Теория
2. Многокритериальный выбор альтернатив с использованием правил нечеткого вывода. Реализация на Java. Часть 2/3: Основной алгоритм

Пример взят из книги: Борисов, Крумберг, Федоров — «Принятие решений на основе нечетких моделей. Примеры использования», 1990. Стр. 94-102

Условие. Руководство института рассматривает кандидатов на замещение вакантной должности на факультете. Задача заключается в том, чтобы, используя описанный выше метод, выявить наилучшеrо из них. Обсуждение среди членов факультета дало следующий результат:
d1: «Если кандидат опытный исследователь, имеет некоторый производственныи стаж и опыт преподавания технических дисциплин, то он удовлетворяющий (отвечающий требованиям)»;

d2: «Если он вдобавок к вышеописанным требованиям может преподавать теорию информационных систем, то он более чем удовлетворяющий»;
d3: «Если он вдобавок к условиям d2 имеет способпость найти заказчика наукоемкой продукции, то он безупречный»;

d4: «Если оп имеет все, oгoвopeннoe в d3, кроме способности преподавать теорию информационных систем, то он очень удовлетворяющий»;
d5: «Если кандидат очень опытный исследователь, имеет способность найти заказчика и хороший преподаватель, но не имеет производственноrо стажа, он все же будет удовлетворяющим»;
d6: «Если он не имеет квалификации исследователя или не имеет проверенной способности к преподаванию, он — неудовлетворяющий».

Не так давно прошёл конкурс параллельного программирования Acceler8 2011. Суть задачи заключалась в поиске максимальной подматрицы в данной матрице (сумма элементов найденной подматрицы должна быть максимальной). После недолгого «гугления» было найдено, что некий алгоритм Тадао Такаока решает эту задачу быстрее других.

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

Однако всё, что удалось найти, — статьи на английском этого самого Тадао Такаоки (вот одна из этих статей). Пришлось переводить.

Сама идея алгоритма сначала казалась до безобразия простой:

Перед прочтением крайне рекомендую ознакомиться с первой частью статьи:
Многокритериальный выбор альтернатив с использованием правил нечеткого вывода. Часть 1/3: Теория

Для осуществления выбора необходим набор правил (интерфейс Rule), которе включают в себя набор соответствующих им нечетких логических функций (реализующих интерфейс Function) и определенные входные формализованные данные (изначально представляющие собой двухмерный массив элементов типа double).

Для бОльшего удобства данные (одномерные массивы элементов типа double) внутри класса Rule хранятся в классе-обертке Skill.

Далее правила передаются классу Facade, создающего из них нечеткие подмножества, размеры которых зависят от количества исследуемых объектов и требуемой точности (задаваемой в статическом классе Variables).

После нахождения общего функционального решения этой системы подмножеств (метод calcD) применяется процедура сравнения полученных нечетких подмножеств в единичном интервале для получения наилучшего решения (метод calcC); для этого вычисляются мощности данных уровневых множеств и их точечные оценки (метод calcS); в данном алгоритме для облегчения требуемой сортировки элементов применяется класс-структура Num.

Нечеткая логика — математические основы
Нечёткое множество

Описание метода
Пусть имеется множество элементов U, а A – его нечеткое подмножество, степень принадлежности его элементов определяется значением X, принимающим значение из интервала [0;1].
Таким образом, объект можно описать набором критериев(параметров) X(1), X(2) … X(n), принадлежащих соответствующим базовым множествам U(1), U(2) … U(n). Совокупность критериев с соответствующими значениями характеризует приемлимость S данного объекта относительно поставленной задачи.

Рассмотрим ситуацию, когда необходимо обрабатывать столкновения между объектами. Как вы в этом случае поступите? Вероятно, самым простым решением будет проверить каждый объект с каждым другим объектом. И это правильное решение, и все будет замечательно до тех пор пока объектов не много. Как только их станет порядка нескольких тысяч, вы заметите, что все стало как-то медленно работать. А если частиц несколько десятков тысяч или сотен? Тогда все замрет. Вот здесь уже интересно, на какие хитрости и оптимизации вы пойдете, чтобы решить такую проблему.

Для простоты, будем рассматривать 2D случай, частицы круглые, радиус частиц у всех одинаковый.

Содержание

1. Обзор алгоритмов
1.1. Полный перебор
1.2. Sweep & Prune
1.3. Регулярная сеть
2. Некоторые оптимизации
2.1. Sweep & Prune
2.2. Регулярная сеть
3. Сравнение скорости выполнения
4. Приложение (программа и исходный код)
5. Заключение

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

Немного теории

Компьютерный век породил теорию R-функций — функций с «логическим зарядом», возникшую на стыке дискретного и непрерывного анализов, использующую аппарат булевой алгебры, который органически присущ и ЭВМ. На основе теории R-функций была решена обратная задача аналитической геометрии, появилась возможность строить в виде элементарной функции уравнение границы сложного объекта, и притом такое уравнение, которое обладало бы необходимыми дифференциальными свойствами. В. Л. Рвачев с помощью конструктивного аппарата теории R-функций разработал единый подход к проблеме построения координатных последовательностей для основных вариационных и проекционных методов. К настоящему времени метод R-функций был применен для решения большого числа задач электродинамики, механики деформируемого твердого тела, теории пластин и оболочек, гидродинамики и магнитной гидродинамики, теплофизики и др.

Введение

Многие сталкивались с проблемой того, что нужно быстро записать данные на flash-ку, но подлая железяка маленькое устройство ограничивало нас в скорости. Производители конечно не стоят на месте, но, для увеличения скорости, обязательно нужно покупать N-ю, модельку, а старая просто начинает пылиться на полке.
Задумавшись об этом, я начал размышлять: каким же образом можно ускорить запись, не покупая новый девайс. О том что я придумал, и почему у меня ничего не получилось и будет этот пост.

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

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

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

Здравствуйте, Хабросообщество!

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

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

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

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

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

Как видно по дискуссиям на хабре, несколько десятков хабровчан прослушали курс ml-class.org Стэнфордского университета, который провел обаятельнейший профессор Andrew Ng. Я тоже с удовольствием прослушал этот курс. К сожалению, из лекций выпала очень интересная тема, заявленная в плане: комбинирование обучения с учителем и обучения без учителя. Как оказалось, профессор Ng опубликовал отличный курс по этой теме — Unsupervised Feature Learning and Deep Learning (спонтанное выделение признаков и глубокое обучение). Предлагаю краткий конспект этого курса, без строгого изложения и обилия формул. В оригинале все это есть.