Здравствуйте, уважаемое сообщество! Думаю, многим знакома такая структура данных как суффиксное дерево. На Хабре уже было описание как его построить и зачем. Если вкратце, то оно нужно тогда, когда надо много раз искать какие-то произвольные образцы X_i в заранее заданном тексте A, а строится такое дерево мучительно с помощью алгоритма Укконена (есть и другие варианты, но они предполагают еще большее количество страданий). Общее наблюдение при работе с алгоритмами таково, что деревья — это, конечно, хорошо, но на практике их лучше избегать из за серьезных оверхэдов по памяти и не очень оптимального (с точки зрения эффективности оперирования данными компьютером) расположения. Кроме того, именно в таком дереве есть еще более существенная неприятность, а именно алфавитнозависимость структуры. Для решения этих проблем был придуман суффиксный массив. О том как его строить и как использовать и пойдет в этой статье.

Материал статьи предполагает знание понятий суффикса и префикса строки, а также знание того, как работает бинарный поиск. Надо также представлять, что такое стабильная сортировка и поразрядная сортировка, а также понимание, что имеется ввиду под стабильной сортировкой подсчетом. Для некоторых частей нам понадобится знание задачи о минимуме на отрезке — Range Minimum Query (RMQ). Ну, в общем, вас предупредили: никто не говорил, что будет просто.

Введение

Как настроить nginx в качестве frontend к apache и зачем это нужно — написано неоднократно, в том числе и на Хабре. Мой случай немного отличается от классического. Начиналось все как обычно, проект на apache, увеличение количества посетителей и, связанная с ним, недостаточность ресурсов сервера. Но проект использовал SSL для защиты обмена данными с клиентами. С чем я столкнулся и как решил проблемы я расскажу под катом.

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


Изображение отрендерено с помощью Maxwell Render.

Все знакомы с css параметром border, но есть ли вещи, которые мы не знаем о нем?

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

Пример такого поста: habrahabr.ru/post/139542

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

Уверен, что курсов по данным дисциплинам, информативнее и понятнее выложенных, в природе не существует.

Под катом ссылки и список того, что было выложено, что ещё предстоит выложить…

Агентство национальной безопасности США рассекретило изумительные письма, которые знаменитый математик Джон Нэш отправил им в 1955 году.

Джон Нэш предложил для тех времён совершенно революционную идею: использовать в криптографии теорию сложности вычислений. Если прочитать письмо от 18 января 1955 года, то вызывает восхищение, насколько пророческим оказался анализ Нэша о вычислительной сложности и криптостойкости. Именно на этих принципах основана современная криптография. Первая работа в этой области была опубликована только в 1975 году.

Отсканированные копии рукописных писем Джона Нэша

В своё время власти так и не проявили интереса к работе чудаковатого профессора математики. Или, что тоже возможно, использовали идеи Нэша втайне от него.

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

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

Содержание

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

Сегодня попробую осветить денежные вопросы.
Банковский счет, карты, платежи, PayPal и все такое.
Это продолжение топика HOWTO: свой бизнес в США из России, если кто пропустил.

    Наверняка многие из нас хоть раз думали про себя: «Черт побери, и везет же этим американцам!». Это касается многого, от магазинов с доставкой «только в пределах 48 континентальных штатов» до вполне серьезных контрактов, которые срываются только потому, что потенциальный заказчик в США категорически не желает иметь дело с иностранцами.

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

Сколько я себя помню, всегда мечтала сделать процессор. Наконец, вчера я его сделала. Не бог весть что: 8 бит, RISC, текущая рабочая частота — 4 кГц, но он работает. Пока что в программе моделирования логических цепей, но все мы знаем: «сегодня — на модели, завтра — на деле!».

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

Введение

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

Эта статья — не набор “волшебных команд” и рецептов (cookbook, как называют такие наборы по-английски), хотя они тут тоже присутствуют, а, скорее, попытка описать, как общие принципы построения эргономичных интерфейсов можно применить в практике использования Vim, чтобы сделать из него удобную и эффективную среду работы с текстами.

Эта статья также не является tutorial’ом для начинающих пользователей Vim, хотя и им (а также пользователям Emacs) может быть интересна, поскольку некоторые упоминаемые принципы являются достаточно общими и действуют не только в системах редактирования текстов, а вообще везде, где идет речь об использовании компьютера для редактирования чего-либо. Тем не менее, я предполагаю, что читатель знаком с основными концепциями, применяемыми в Vim (режимы, регистры, буфера, команды) и не останавливаюсь на их подробном описании.

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

Эта статья является переводом цикла из четырёх статей «Linear algebra for game developers», написанных David Rosen и посвящённых линейной алгебре и её применению в разработке игр. С оригинальными статьями можно ознакомиться тут: часть 1, часть 2, часть 3 и часть 4. Я не стал публиковать переводы отдельными топиками, а объединил все статьи в одну. Думаю, что так будет удобнее воспринимать материал и работать с ним. Итак приступим.

Думаю каждый кто работал с под-доменами в Rails 3 видел данный скринкаст.

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

• возможность указания фиксированного поддомена, либо группы поддоменов;
• возможность привязки к полю из модели ActiveRecord;
• удобный синтаксис для записи всего этого в routes.rb.

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

Зачем нам консоль в МК?

Текстовый консольный интерфейс обладает рядом преимуществ для встраиваемых систем, при всей своей мощи и простоте (ведь текст, в отличие от светодиода, говорит сам за себя!):

• Требует относительно мало ресурсов МК, и минимум аппаратных затрат — последовательный интерфейс типа UART или любой другой имеющийся в МК, это может быть встроенный USB или внешний USB-Com адаптер или даже TCP если ваше микроконтроллер достаточно серьезный.
• Удобно подключаться — достаточно терминала поддерживающего Com-port (putty для Windows или minicom для linux).
• Удобно использовать — цветной вывод в терминал, поддержка авто-дополнений, горячих клавиш и истории ввода.

Под катом — список из 15 лучших ресурсов, посвящённых Спортивному Программированию.

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

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

Если поискать, то на русском языке нет ничего толкового по разработке расширений для chrome, только лишь эта статья доступно описывает самые основы.

Данный пост будет более продвинутой версией.

Почти каждый владелец arduino сталкивается с задачей управления ее пинами по сигналу с компьютера, и почти каждый пишет свою программку в которой чтение Serial, и switch с действиями.
Однажды мне надоело на каждый чих что-то компилировать и получился еще один маленький, простой, человеко-и скрипто- ориентированный протокол.

Решая упражнения к книге «Программируем коллективный разум», я решил поделиться реализацией одного из алгоритмов упомянутого в этой книге (Глава 2 — Упражнение 1).

Исходные условия следующие: пусть мы имеем словарь с оценками критиков:

critics={'Lisa Rose': {'Superman Returns': 3.5, 'You, Me and Dupree': 2.5, 'The Night Listener': 3.0}, 
           'Gene Seymour': {'Superman Returns': 5.0, 'The Night Listener': 3.5, 'You, Me and Dupree': 3.5}}

Чем выше оценка, тем больше нравится фильм.
Надо вычислить: насколько схожи интересы критиков для того, например, чтобы можно было на основе оценок одного рекомендовать фильмы другому?

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

Дисклаймер: описываю только свой личный опыт и мнения автора могут не совпадать с мнением автора. Статья огромная, читать много.

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

Эта статья адресована тем, кто уже «на грани». Она почти лишена философии и туманных ссылок, просто тупо туду-лист. Бери и делай. Намеренно избавляю тебя от объяснений, зачем молодому проекту нужна госрегистрация, такая ли уж это свобода – быть собственником и от куда взять деньги на госпошлину. Статья адресована московским стартаперам, гео-патчи от других городов приветствуются в комментариях.
Будем считать, что с формой собственности определились — это ООО и упрощенка 6%. Если кому нужно ИП – там проще, справишься и без этой статьи.

Для создания фирмы необходимо: