После публикации прошлой статьи, я полностью забил на попытку выполнить алгоритм при помощи HSV или Lab координат. Забил на использовании библиотек цветов и вообще на сам скрипт забил.

Но что-то стало скучно и опять зачесались руки поработать с изображениями и одновременно захотелось исправить уже имеющийся алгоритм.
Скрипт: link

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

Алгоритм метода Шеннона-Фано — один из первых алгоритмов сжатия, который впервые сформулировали американские учёные Шеннон и Фано, и он имеет большое сходство с алгоритмом Хаффмана. Алгоритм основан на частоте повторения. Так, часто встречающийся символ кодируется кодом меньшей длины, а редко встречающийся — кодом большей длины.
В свою очередь, коды, полученные при кодировании, префиксные. Это и позволяет однозначно декодировать любую последовательность кодовых слов. Но все это вступление.

Давным-давно в 1637 году Пьер Ферма имел глупость написать на полях «Арифметики» Диофанта следующее: «… невозможно разложить куб на два куба, биквадрат на два биквадрата и вообще никакую степень, большую квадрата, на две степени с тем же показателем. Я нашел этому поистине чудесное доказательство, но поля книги слишком узки для него».

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

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

Недавно сразу несколько достаточно авторитетных по местным меркам новостных порталов взорвала новость: Узбекский математик разгадал теорему Ферма — Математик из Ташкента Борис Пономарев утверждает, что отыскал «простое оригинальное доказательство» Великой теоремы Ферма — загадки, над которой ученые всего мира бьются вот уже 350 лет (например, здесь, здесь и здесь). В одной из них даже было приведено доказательство.

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

• есть некоторое количество (можно считать, что не более 16 миллионов) измерений набора параметров. Число параметров в наборе – от 2 до 5.
• измерение параметров может быть относительно успешным – тогда их результат будет неподалеку от истинного (параметры и тип распределения неизвестны), либо не успешным – тогда результат будет случайным (опять-таки с неизвестными параметрами распределения). Определить по одиночному измерению, было ли оно успешным, нельзя.
• Можно считать, что точка сгущения существует. Если их несколько с близким качеством (которое формально так и не определяется), можно выдать любую.
• ответ нужно дать за один проход по исходным данным: перевычислять их или сохранять целиком – дорого.
• И, как обычно, хочется, чтобы алгоритм выглядел попроще, а работал побыстрее.

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

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

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

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