Деревья в базах данных можно хранить тремя основными методами: Adjacency List, Matherialized Path & Nested Set. Когда мы хотим переехать с AL на NS, это можно сделать с помощью рекурсии (если БД расово верная). Но что делать в случае MySQL?Читать полностью »
Рубрика «Алгоритмы» - 286
Строим Nested Set дерево без рекурсии
2012-11-25 в 17:47, admin, рубрики: mysql, nested set, sql, Алгоритмы, рекурсия, функции, метки: mysql, nested set, Алгоритмы, рекурсия, функцииПрогресс в разработке нейросетей для машинного обучения
2012-11-25 в 0:16, admin, рубрики: data mining, deep learning, Алгоритмы, искусственный интеллект, машинное обучение, нейросети, обратное распространение ошибки, метки: deep learning, искусственный интеллект, машинное обучение, нейросети, обратное распространение ошибки 
В пятничном номере NY Times опубликована статья о значительных успехах, который демонстрируют в последние годы разработчики алгоритмов для самообучаемых нейросетей. В глубоких структурах есть несколько скрытых слоёв, которые традиционно тяжело было обучать. Но всё изменилось с использованием стека из машин Больцмана (RBM) для предварительной тренировки. После этого можно удобно перенастраивать веса, применяя метод обратного распространения ошибки (backpropagation). Плюс появление быстрых GPU — всё это привело к существенному прогрессу, который мы наблюдаем в последние годы.
Сами разработчики не делают громких заявлений, чтобы не поднимать ажотаж вокруг нейросетей — такой, как в 1960-е годы поднялся вокруг кибернетики. Тем не менее, можно говорить о возрождении интереса к исследованиям в этой области.
Читать полностью »
Про двумерную упаковку: offline алгоритмы
2012-11-22 в 14:55, admin, рубрики: 2DSP, bin packing, Алгоритмы, двумерная упаковка, задача о рюкзаке, метки: 2DSP, bin packing, двумерная упаковка, задача о рюкзаке Сегодня, дорогой Хабр, я расскажу тебе историю о комбинаторной оптимизации.
Издревле (как минимум, с начала прошлого века) математики задавались вопросом, как оптимально разместить некоторое количество пива нужных и полезных предметов в рюкзаке. Была сформулирована задача о ранце и ее подзадачи — тысячи их! — которые заинтересовали информатиков, криптографов и даже лингвистов.
От задачи о ранце отпочковалась задача об упаковке в контейнеры (Bin Packing Problem), одной из разновидностей которых является задача двумерной упаковки (2-Dimensional Bin Packing). Снова отбросив несколько вариаций, мы наконец придем к двумерной упаковке в полуограниченную полосу (2-Dimensional Strip Packing, 2DSP). Чувствуете, сколько интересного уже осталось за кадром? Но мы еще не закончили продираться сквозь классификацию. У 2DSP есть два варианта входных данных: когда набор упаковываемых объектов известен заранее (offline-проблема) и когда данные поступают порциями (online-проблема).
В этой статье рассматриваются алгоритмы решения offline-варианта 2DSP. Под катом немного матчасти и много картинок с цветными квадратиками.
В чем, собственно, проблема?
Конкурс «Интернет-математика: Яндекс.Карты» — опыт нашего участия и описание победившего алгоритма
2012-11-19 в 6:33, admin, рубрики: computer vision, itseez, opencv, Алгоритмы, Блог компании «Itseez», интернет-математика, Компьютерное зрение, обработка изображений, яндекс, метки: computer vision, itseez, opencv, интернет-математика, Компьютерное зрение, обработка изображений, яндексПрошло уже больше года после завершения конкурса "Интернет-математика: Яндекс.Карты", но нас до сих пор спрашивают об алгоритме, который принёс нам победу в этом конкурсе. Узнав о том, что недавно Яндекс объявил о старте очередной "Интернет-математики", мы решили поделиться опытом нашего прошлогоднего участия и описать наш подход. Разработанный алгоритм смог с точностью 99.44% правильно определить лишние изображения в сериях панорамных снимков, например, как здесь:
В этой статье мы описываем основные идеи алгоритма и приводим его детали для интересующихся, рассказываем об извлечённых уроках и о том, как это всё вообще было.
Исходный код нашего решения доступен на github (C++ с использованием OpenCV).
Читать полностью »
Keccak, новый стандарт хеширования данных
2012-11-17 в 18:43, admin, рубрики: Keccak, SHA-3, Алгоритмы, информационная безопасность, криптография, метки: Keccak, SHA-3 
Доброго времени суток, уважаемые читатели.
Многие из вас наверняка знают о том, что на протяжении нескольких лет NIST проводил конкурс среди хеш-функций с целью принятия нового стандарта SHA-3. И в этом году награда нашла своего героя. Новый стандарт был благополучно принят.
Ну а раз стандарт уже принят, самое время посмотреть что же он из себя представляет.
И тихим, субботним вечером, я обложившись мануалами открыв в браузере google.com начал свое небольшое исследование.
Читать полностью »
Разбор картинки в текст: простой алгоритм
2012-11-13 в 9:06, admin, рубрики: captcha, ocr, php, Алгоритмы, капча, метки: captcha, ocr, капчаКорни истории уходят в те годы, когда один из кланов древней текстовой игры «Бойцовский клуб» заказал у меня, молодого программиста на Perl, капчу для игры. Пара бессонных ночей — и четыре ровных цифры готовы вместе с проверкой ввода.
Через несколько дней пришёл другой, не менее уважаемый клан, и заказал парсер той самой капчи. Для её разбора пришлось потратить гораздо больше времени, никакого Ocrad тогда ещё не было, но был найден очень простой и рабочий способ.
Через неделю пришёл третий, и самый заслуженный в игре клан, и заказал новую капчу. Через пару месяцев перетягивания одеяла почти все топовые кланы обогатились на новые картинки-артефакты, их программисты на ворох разноцветных бумажек, проект — на кучу генераторов чепухи, а лично я на бесценный опыт.
Совсем недавно этот опыт пригодился для разбора тысяч телефонных номеров с одного из сайтов из изображения обратно в текст. Алгоритм использовался тот же самый, и я хочу им поделиться. Вот отвёртка и молоток, а что вы ими соберёте — синхрофазотрон или гравипушку — уже ваше личное дело.
Читать полностью »
Талмуд по формулам в Google SpreadSheet
2012-11-09 в 4:27, admin, рубрики: Excel, Google, Google Docs, microsoft, microsoft office, ms excel, OpenOffice, Алгоритмы, формулы, метки: Excel, Google Docs, microsoft office, ms excel, OpenOffice, формулы«Талмуд» по формулам в Google SpreadSheet
За несколько месяцев работы с таблицами Google пришлось много раз анализировать посредством формул разного рода данные. Как и ожидалось — то, что можно было решить в MS Excel, можно реализовать и в Google таблицах. Но многочисленные попытки решить проблемы с помощью любимого поисковика приводили только к новым вопросам и почти к нулевым ответам.
Посему, было решено облегчить жизни другим и прославить себя.
Кратко о главном
Для того чтоб Excel, либо spreadsheet (таблица Google) поняли что написанное — это формула, необходимо поставить знак "=" в строку формул (Рисунок 1).
Рисунок 1
Далее, начинаем писать формулу с клавиатуры либо выделяем мышкой те ячейки, с которыми мы собираемся работать.
Читать полностью »
Многозначное шифрование с использованием хеш-функций: продолжение
2012-11-07 в 17:25, admin, рубрики: c++, Алгоритмы, анонимность, информационная безопасность, коллизии, недоказуемость, хеш-функции, шифрование, метки: c++, анонимность, коллизии, недоказуемость, хеш-функции, шифрование 
В прошлой заметке я рассказывал о возможности создать алгоритм шифрования, основывающийся на использовании хеш-функций, позволяющий шифровать несколько текстов с различными ключами в один неразделимый информационный поток, без возможности определить сколько и каких сущностей было зашифровано. Теперь детали алгоритма стали ясны, что позволило создать утилиту, реализующую описанный метод. В этой заметке я поделюсь утилитой, проведу анализ алгоритма и предложу (довольно поверхностные) обоснования криптостойкости метода.
Читать полностью »
Бесконечные генераторы значений на Delphi + Ассемблер
2012-11-07 в 17:20, admin, рубрики: Delphi, x64, Алгоритмы, ассемблер, генераторы, Программирование, функциональное программирование, метки: Delphi, x64, Алгоритмы, ассемблер, генераторы, функциональное программирование В функциональных языках программирования есть возможность генерировать бесконечные последовательности значений (как правило чисел) и оперировать этими последовательностями. Реализуется это функцией, которая, не прерывая свою работу, генерирует значения одно за другим на основе своего внутреннего состояния.
Но, к сожалению, в обычных языках нет возможности «вернуть» значения в место вызова не выходя из функции. Один вызов — один результат.
Генераторы удобно было бы использовать совместно с возможностью Delphi по перечислению значений (GetEnumerator/MoveNext/GetCurrent). В этой статье мы создадим функцию-генератор (может даже бесконечную) и будем использовать ее с таким объектом для перечисления, чтобы всё работало прозрачно без необходимости вникать в реализацию.
Читать полностью »
Конкурс Ivideon. Продолжение
2012-11-07 в 13:39, admin, рубрики: ivideon, Алгоритмы, Блог компании Ivideon, Компьютерное зрение, конкурс, обработка изображений, ответы, метки: ivideon, Компьютерное зрение, конкурс, ответы 
Вчера мы рассказали о том, что объявляем конкурс на создание демонстрационного приложения на основе OpenCV для слежения за несколькими объектами, где в качестве приза будет поездка вместе с нашей командой на Шри-ланку, а также предложение о работе в нашей компании.
Очень здорово, что конкурс был воспринят позитивно и нам активно стали писать всеми различными способами, чтобы уточнить те или иные вопросы. Многие из них были достаточно однотипными, поэтому нам бы хотелось ответить на них в виде отдельного небольшого топика.Читать полностью »