Сразу надо сказать, что буду излагать вопрос о биовычислениях с определенной кибернетико-геометрической точки зрения. Это мое название и это направление не распространено. Уверен, что так будет легче понять тем кто не в теме этой биологической проблематики. Те кто уже в теме — готов и с вами подискутировать и показать почему традиционные методы не пригодны с точки зрения кибернетического подхода (но в этой статье не вы моя аудитория — уж извините, но уверен и вам она будет полезна как расширение мировоззрения на проблематику).

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

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

Но введения хватит, далее с корабля на бал…

Введение, или зачем нужны синтаксические анализаторы

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

Эта часть посвящена базису, общей теории computer science. Возможно, что это даже преподаётся в школах/вузах России. Самая мякота пойдет со второй части.

Итак, зачем же кому-то может понадобиться писать парсер и что вообще это такое? Парсер — это код, который наделяет входящий набор символов семантическим смыслом. То есть, происходит анализ этих символов, и на основе этого анализа программа понимает как интерпретировать эти буквы и цифры. Простой пример — «1+2», после или во время процесса парсинга знак "+" это не просто символ плюса, но обозначение бинарноого оператора сложения, а в "+3" это унарный оператор знака числа. Большинству людей это очевидно, машине — нет.

Парсеры используются всюду — в Word'e для анализа приложений, словоформ, формул, etc; практически на любом сайте при валидации входных данных: email'а, телефонного номера, номера кредитки; конфигурационные файлы; сериализованные данные (например, в xml); во многих играх — скриптовые ролики, скрипты ИИ, консоль. В общем, это неотъемлемая часть computer science.

Недавно, 19 декабря 2011г, Австралийское бюро по безопасности на транспорте выпустило отчёт об авиационном происшествии с самолётом А-330 (б/н VH-QPA) авиакомпании Qantas, которое произошло 7 октября 2008г.


(фотография Stefan Roesh planepictures.net)

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

    В предыдущих статьях (1,2) мы познакомились с тем, как могут выглядеть данные в зависимости от проведенного биологического эксперимента. На основании этих визуализированных данных были сделаны предположения о том, что же происходит внутри клетки. Теперь остановимся на том, как математически и алгоритмически проанализировать данные для того, чтобы машины за нас могли выполнить рутинную работу. К сожалению, после прочтения множества статей по анализу данных у меня сложилось впечатление, что однозначного или наиболее универсального решения не существует. Есть алгоритмы, которые хорошо себя показывают на некотором наборе данных, а в других случаях уже не отвечают поставленным задачам.

Что удивительного в этой картинке?



На самом деле она уникальна. Матрица размером 17 х 17 раскрашена четырьмя цветами, при этом на ней нельзя построить ни единого (!) прямоугольника, чтобы все углы его были одного цвета. Имеются в виду прямоугольники любого размера с вершинами в разных точках и рёбрами, параллельными осям x и y.

Ниже перевод статьи Бо Аллена отсюда.

Простой наглядный пример

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

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

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

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

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

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

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

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

К сожалению, большинство инструментов, которые применяются для вычислений, будут прятать результат, но если вы найдете такой, который этого (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

После возни с трехмерной игрой «Жизнь» я вспомнил о том, что для обычной, конвеевской версии этой игры существует алгоритм под названием «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 – он и будет ответом.

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

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

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

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

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

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

Содержание

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

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

Здравствуйте, хабражители.
Хочу с вами поделиться своими наработками по обработке изображений. В последнее время занимаюсь написанием домашнего сервера под «умный дом» и начал с видеонаблюдения.
Задача оказалась не такой тривиальной. По поводу всего видеонаблюдения я напишу отдельно (если кому-то это интересно), а сейчас хотел бы затронуть тему «Алгоритм определения движения через сравнение двух кадров».
Этот алгоритм необходим для включения (выключения) записи видео с видеокамер.

Предисловие

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

Программа написана с помощью низкоуровневого языка C++, потому что я действительно хотел понять, как же это все работает изнутри. Если вы тоже хотите начать изучение компьютерного зрения, то для этого пригодиться библиотека OpenCV. На CodeProject вы сможете найти несколько уроков по ней. Изображение с веб-камеры получается с помощью исходного кода Вадима Горбатенко (AviCap CodeProject).

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

Он, имея сложность не более O(n log n), ускоряется в случае сортировки частично упорядоченных данных и имеет сложность O(n), если данные изначально отсортированны. Но это не единственный алгоритм с такими заявленными свойствами. Существует еще как минимум два более-менее известных метода с похожей сложностью — это Smoothsort и сортировка Шелла.

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

Новости из мира науки: матрицы размера теперь умеют умножать за . Другими словами, доказано, что , где  — экспонента умножения матриц. Доказала это совсем недавно Вирджиния Василевска-Вильямс, улучшив тем самым оценку , полученную Копперсмитом и Виноградом в 1987 году. Я напишу про важность этого алгоритма совсем немножко. Тем, кому интересно узнать побольше, предлагается почитать посты Скотта Ааронсона, Ричарда Липтона и Билла Гасарша.

Итак, многие теоретические верхние оценки на время работы алгоритмов используют экспоненту умножения матриц. В частности, много алгоритмов на графах эксплуатируют данную идею: если A — матрица смежности графа, то  — количество (не обязательно простых!) путей длины k между вершинами i и j. Эта простая идея позволяет за время проверить, есть ли в графе треугольник (3-клика): нужно возвести матрицу смежности в куб (для этого потребуется два умножения матриц) и посмотреть на диагональ. Отметим, что речь здесь именно о теоретических оценках, поскольку продвинутые алгоритмы умножения матриц хоть и обгоняют асимптотически простой кубический алгоритм, но на практике дают ускорение только на огромных размерах матриц.

Ещё несколько примеров:

Хотя метод был разработан и представлен в 2001 году Полом Виолой и Майклом Джонсом [1, 2], он до сих пор на момент написания моего поста является основополагающим для поиска объектов на изображении в реальном времени [2]. По следам топика хабраюзера Indalo о данном методе, я попытался сам написать программу, которая распознает эмоцию на моём лице, но, к сожалению, не увидел на Хабре недостающей теории и описания работы некоторых алгоритмов, кроме указания их названий. Я решил собрать всё воедино, в одном месте. Сразу скажу, что свою программу успешно написал по данным алгоритмам. Как получилось рассказать о них ниже, решать Вам, уважаемые Хабрачитатели!

Timsort, в отличии от всяких там «пузырьков» и «вставок», штука относительно новая — изобретен был в 2002 году Тимом Петерсом (в честь него и назван). С тех пор он уже стал стандартным алгоритмом сортировки в Python, OpenJDK 7 и Android JDK 1.5. А чтобы понять почему — достаточно взглянуть на вот эту табличку из Википедии.



Среди, на первый взгляд, огромного выбора в таблице есть всего 7 адекватных алгоритмов (со сложностью O(n logn) в среднем и худшем случае), среди которых только 2 могут похвастаться стабильностью и сложностью O(n) в лучшем случае. Один из этих двух — это давно и хорошо всем известная «Сортировка с помощью двоичного дерева». А вот второй как-раз таки Timsort.

Алгоритм построен на той идее, что в реальном мире сортируемый массив данных часто содержат в себе упорядоченные (не важно, по возрастанию или по убыванию) подмассивы. Это и вправду часто так. На таких данных Timsort рвёт в клочья все остальные алгоритмы.

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

На снимке — скульптура абстрактного экспрессиониста Марка Ди Суверо «Решето Эратосфена», установленная в кампусе Стэнфорского университета