Алгоритмы *

Алгоритмы сортировки. Их не много, но и не мало. Есть часто используемые, есть никому не нужные. Я решил произвести обзор этих алгоритмов, чтоб освежить и свою память, и память хабрапользователей. И начнём с редкоиспользуемого алгоритма Gnome Sort(гномья сортировка).

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

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

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

Всем привет.

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

В этот раз мне на глаза попались статьи по cache oblivious алгоритмам. Это такие алгоритмы, которые изначально более оптимизированы для работы с подсистемой кэширования современных процессоров.

Одним из представителей этой группы является Unrolled linked list.

Что же это такое?

Когда-то давно я уже писал довольно большую статью об использовании эвристик в программировании, но сегодня я хочу привести небольшой практический пример. Этим летом я плавал на теплоходе по маршруту Москва — Ростов-на-Дону — Москва, и заметил, что каждый вечер директор круиза пытается найти оптимальную рассадку туристических групп по автобусам. Задача не такая сложная, но минимум 15 минут в день на её решение тратится. Разумеется, я попробовал автоматизировать этот процесс.

kNN расшифровывается как k Nearest Neighbor или k Ближайших Соседей — это один из самых простых алгоритмов классификации, также иногда используемый в задачах регрессии. Благодаря своей простоте, он является хорошим примером, с которого можно начать знакомство с областью Machine Learning. В данной статье рассмотрен пример написания кода такого классификатора на python, а также визуализация полученных результатов.

Sentiment analysis (по-русски, анализ тональности) — это область компьютерной лингвистики, которая занимается изучением мнений и эмоций в текстовых документах. Недавно на хабре появилась статья про использование машинного обучения для анализа тональности, однако, она была настолько плохо составлена, что я решил написать свою версию. Итак, в этой статье я постараюсь доступно объяснить, что такое анализ тональности, и как реализовать подобную систему для русского языка.

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

Именно о лесенках хотелось бы немного поговорить. Есть такая относительно распространенная задача с программистских собеседований:

Вы поднимаетесь по лестнице. На каждом шаге вы можете подняться либо на 1 ступеньку, либо на 2. Всего лестница имеет n ступенек. Сколькими разными способами вы можете дойти до конца лестницы?

Задача не сильно сложная, но имеющая пару интересных моментов относительно минимально возможной сложности решения и демонстрирующая «штуки, которые интересно знать».

Пару месяцев назад я рассказывал о приближенных результатах в задаче о сворачивании РНК. Напомню требуется свернуть вироидный рибозим NC_003540 организма Chrysanthemum chlorotic mottle viroid, третичная структура которого неизвестна.

И вот оно свершилось — рибозим свернулся ! (В нем образованы все имеющиеся водородные связи)

Смотрим его конечное состояние, а под катом еще его траекторию сворачивания, а также подводим итоги.

Вместо вступления

Лень — двигатель прогресса. Не хочешь сам молоть зерно — сделай мельницу, не хочешь сам кидать во врагов камни — сооруди катапульту, надоело гореть на кострах инквизиции и гнуть спину под феодалом — замути с ребятами ренессанс… впрочем, о чем это я.
Автоматизация, господа. Берешь какой-нибудь полезный процесс, в котором участвует человек, заменяешь человека на сложный механизм, получаешь профит. Относительно недавно также стало модно заменять человека куском кода. О, сколько благородных профессий может пасть под натиском информатизации. Особенно если учесть, что кусок кода в наше время способен не только на заранее определенное поведение, но и на «обучение» какому-то поведению.

Введение

Обычно данный материал приводится с обилием формул и рассчитан больше на математиков. Я постараюсь расписать его наиболее доступно на простых численных примерах с точки зрения применения этого метода в микроэлектронике на аппаратном уровне. В численных примерах для наглядности будет использоваться значение p = 11.

Постановка задачи

Положим, что нам требуется выполнить умножение следующего вида: res = (a*b) mod p, где
0 <= a < p
0 <= b < p
p – простое число.
mod p – операция нахождения остатка по модулю.
И выполнить его надо на низком уровне, где нет как таковой операции умножения и операции взятия остатка от деления или же они реализуются достаточно сложно (например, в электронном устройстве).

Уже много лет учёные экспериментируют с алгоритмами, способными предсказывать преступность. Предполагается, что преступники склонны повторять успешные действия — по крайней мере, они не используют ГСЧ для выбора места и времени преступлений, так что их действия предсказуемы по определению.

Например, год назад калифорнийский город Санта-Крус первым в мире внедрил математическую модель расчёта вероятности преступлений, которая каждый день составляет новый маршрут для патрульных машин, основываясь на статистике преступлений по улицам. Учитываются день недели, время суток, наличие/отсутствие футбольных матчей по ТВ и другие факторы.

Исследователь из Бирмингемского университета Мирко Мусолези (Mirco Musolesi) применил совершенно другой подход. Его метод основан не на статистике, а на оперативных данных из сетей сотовой связи. Мусолези начал с того, что научил алгоритм с высокой степенью вероятности прогнозировать перемещения каждого абонента: он даже выиграл конкурс Nokia Mobile Data, наиболее точно предсказав перемещения 25-ти добровольцев по сигналам их телефонов, истории звонков и текстовым сообщениям. Иногда алгоритм прогнозирует координаты пользователя с точностью до 20 м².

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

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

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

Это перевод и форма повествования от первого лица сохранена. Автор — Бен Бойтер, бакалавр информационных технологий в Университете Чарльза Стерта (CSU).


Большинство людей не в курсе, но моей диссертацией была программа для чтения текста с изображения. Я думал, что, если смогу получить высокий уровень распознавания, то это можно будет использовать для улучшения результатов поиска. Мой отличный советник доктор Гао Джунбин предложил мне написать диссертацию на эту тему. Наконец-то я нашел время написать эту статью и здесь я постараюсь рассказать о всем том, что узнал. Если бы только было что-то подобное, когда я только начинал…

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

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

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

Пока я тут излагал мысль она несколько растеклась по статьям

1. Модель функционального разделения сознания и бессознательного. Введение
2. Модель проявления сознания или ИНС без эффекта забывания
3. Проблема «двух и более учителей». Первые штрихи
4. Обучение с подкреплением на нейронных сетях. Теория

казалось аудитория имеет нужные знания, все таки у нас цвет общества — программисты :) Но увы… последний опрос показал, что далеко не все программисты в курсе ИИ-проблематики. А хамоватые студенты набежавшие на эти статьи в комментариях — еще не доучились.

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

Недавно на хабре появилась неплохая статья про вычисление N-ного числа фибоначи за O(log N) арифметических операций. Разумный вопрос, всплывший в комментариях, был: «зачем это может пригодиться на практике». Само по себе вычисление N-ого числа фибоначи может и не очень интересно, однако подход с матрицами, использованный в статье, на практике может применяться для гораздо более широкого круга задач.

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

loop 1000000000
  loop 1000000000
    loop 1000000000
      a += 1
      b += a
    end
  end
end
end

Незамедлительно выведет a = 1000000000000000000000000000, b = 500000000000000000000000000500000000000000000000000000, несмотря на то, что если бы программа выполнялась наивно, интерпретатору необходимо было бы выполнить октиллион операций.

Я тут написал статью Проблема «двух и более учителей». Первые штрихи, пытаясь показать одну сложную нерешенную проблему. Но первые штрихи оказались немного за сложными. Поэтому я решил для читателей немного разжевать теорию. Увы, сейчас видимо учат/(учатся ?) несколько шаблонно — типа как для каждой задачи свои методы.

Так мне указали, что для задачи классификации — нейронные сети (обучение с учителем), генетические алгоритмы (обучение без учителя) — задача кластеризации, а еще есть обучение с подкреплением (Q-обучение) — как задача агента, который бродит и что-то делает. И вот такими шаблонами многие и судят.

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

И заодно проанализируем диссертацию Бурцев М.С., «Исследование новых типов самоорганизации и возникновения поведенческих стратегий», в которой не больше не меньше красиво сделано именно применение простеньких нейронных сетей в задаче обучения с подкреплением.

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

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

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

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