Под катом:

• Шифр Цезаря
• Шифр пар
• Шифр четырех квадратов
• Матричный шифр
• Шифр ADFGX
• Шифр Виженера

Прочитав статью об алгоритмах поиска подстроки в строке, я обнаружил, что там не рассказывается об алгоритме Бойера-Мура. Пара слов о нём всё-таки там есть, а именно, говорится, что алгоритм Бойера-Мура заслужил себе звание «алгоритма по умолчанию», потому что он в среднем дает лучшее время поиска (с чем я полностью согласен). Под катом рассказано об упрощенной версии этого алгоритма. В принципе, большинство скорее всего изучало этот алгоритм на 1-м или 2-м курсе ВУЗа (как и я), поэтому они могут пропустить эту статью, ничего нового тут нет.

В первой части нашей темы мы рассмотрели решение задачи static RMQ за (O(nlogn), O(1)). Теперь мы разберёмся со структурой данных, называемой дерево отрезков, или интервалов (в англоязычной литературе – segment tree или interval tree). С помощью неё можно решать dynamic RMQ за (O(n), O(logn)).

Определение

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

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

Представляю вашему вниманию перевод статьи "Mobile Form Design Strategies" от Chui Chui Tan. Перевели в компании UXDepot. Специально для пользователей Хабрахабра с одобрением издания UX Booth.

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

Интернет на экране мобильного телефона находится под влиянием нескольких важных факторов:

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

В данном топике речь пойдет о причинах, вызывающих длинные паузы сборщика мусора и о способах борьбы с ними. Рассказывать я буду о CMS (low pause), так как на данный момент это наиболее часто используемый алгоритм для приложений с большой памятью и требованием малой задержки (low latency). Описание дается в предположении, что у вас приложение крутится на боксе с большим объемом памяти и большим количеством процессоров.

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

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

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

Пусть дан массив A длины N, и дано число K ≤ N. Требуется найти максимум (минимум, сумма ...) в подотрезках длины K данного массива. Это частный случай задачи RMQ (Range Minimum Query — минимум на отрезке), но с дополнительными ограничениями — постоянная длина отрезка поиска. В данном решении задача не предполагает возможность изменения элементов массива.

Договоры, отчеты, акты — кому охота заниматься этой скукотой, когда вокруг бьет ключом и фонтанирует идеями креативная жизнь? Особенно, если заказчик снисходительно хлопает творческого подрядчика по плечу: «Да ладно, зачем какие-то договоры. Мое слово — закон!» Остается только радостно согласиться и приступить к работе.

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

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

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

Устанавливал я Ubuntu 10.10 на ноутбук Acer Aspire Timeline 5810TG. Эта машина обладает экраном в почти 16 дюймов и относительно производительным железом, зато батарея достаточно емкая, чтобы ставить с ней личные рекорды.

Дорогие коллеги!

Рад сообщить о выходе новой версии программы для установки драйверов DriverPack Solution 11!

В новой версии используются свежие базы драйверов, новый движок и реализована возможность установки дополнительных программ.
Ссылка для скачивания (объём 2,8Гб): http://drp.su/ru/download.htm


Наша цель – собрать все драйвера в одном месте.
Кстати, у нас уже 9млн. пользователей!

Добрый день, Хабрахабр. Это еще один пост в рамках моей программы по обогащению базы данных крупнейшего IT-ресурса информацией по алгоритмам и структурам данных. Как показывает практика, этой информации многим не хватает, а необходимость встречается в самых разнообразных сферах программистской жизни.
Я продолжаю преимущественно выбирать те алгоритмы/структуры, которые легко понимаются и для которых не требуется много кода — а вот практическое значение сложно недооценить. В прошлый раз это было декартово дерево. В этот раз — система непересекающихся множеств. Она же известна под названиями disjoint set union (DSU) или Union-Find.

Условие

Поставим перед собой следующую задачу. Пускай мы оперируем элементами N видов (для простоты, здесь и далее — числами от 0 до N-1). Некоторые группы чисел объединены в множества. Также мы можем добавить в структуру новый элемент, он тем самым образует множество размера 1 из самого себя. И наконец, периодически некоторые два множества нам потребуется сливать в одно.

Формализируем задачу: создать быструю структуру, которая поддерживает следующие операции:

MakeSet(X) — внести в структуру новый элемент X, создать для него множество размера 1 из самого себя.
Find(X) — возвратить идентификатор множества, которому принадлежит элемент X. В качестве идентификатора мы будем выбирать один элемент из этого множества — представителя множества. Гарантируется, что для одного и того же множества представитель будет возвращаться один и тот же, иначе невозможно будет работать со структурой: не будет корректной даже проверка принадлежности двух элементов одному множеству if (Find(X) == Find(Y)).
Unite(X, Y) — объединить два множества, в которых лежат элементы X и Y, в одно новое.

На рисунке я продемонстрирую работу такой гипотетической структуры.

Про взлом паролей windows было написано немало статей, но все они сводились к использованию какого-либо софта, либо поверхностно описывали способы шифрования LM и NT, и совсем поверхностно описывали syskey. Я попытаюсь исправить этот неодостаток, описав все подробности о том где находятся пароли, в каком виде, и как их преобразует утилита syskey.

Натолкнулся в разделе QA на интересный вопрос. Ответ на него заставил написать эту статью как бОлее полный ответ на вопрос «как организовать поиск по множеству параметров, как в Яндекс-маркете, например».

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

Итак, что имеем в «ДАНО»

• Имеем 120 чекбоксов — вариант 1/0
• Имеем 30 «радио» с выбором «да/нет/не важно»
• Имеем 2-3 слайдера для указания диапазона цен/размера чего нить
• Имеем самое главное: 12 млн записей в БД.
• Имеем Select * From tovar Where (wifi=true) and (led=false) and (type=3) and ….остальные параметры …; со временем выполнения близкому к истерике клиента.

Здравствуйте, уважаемое сообщество! Недавно на Хабре проскакивала неплохая обзорная статья о разных алгоритмах поиска подстроки в строке. К сожалению, там отсутствовали подробные описания каких либо из упомянутых алгоритмов. Я решил восполнить данный пробел и описать хотя бы парочку тех, которые потенциально можно запомнить. Те, кто еще помнит курс алгоритмов из института, не найдут, видимо, ничего нового для себя.

Введение

Задача RMQ весьма часто встречается в спортивном и прикладном программировании. Удивительно, что на Хабре ещё никто не упомянул эту интересную тему. Попробую восполнить пробел.

Аббревиатура RMQ расшифровывается как Range Minimum (Maximum) Query – запрос минимума (максимума) на отрезке в массиве. Для определённости мы будем рассматривать операцию взятия минимума.

Пусть дан массив A[1..n]. Нам необходимо уметь отвечать на запрос вида «найти минимум на отрезке с i-ого элемента по j-ый».



Рассмотрим в качестве примера массив A = {3, 8, 6, 4, 2, 5, 9, 0, 7, 1}.
Например, минимум на отрезке со второго элемента по седьмой равен двум, то есть RMQ(2, 7) = 2.

В голову приходит очевидное решение: ответ на каждый запрос будем находить, просто пробегаясь по всем элементам массива, лежащим на нужном нам отрезке. Такое решение, однако, не является самым эффективным. Ведь в худшем случае нам придётся пробежаться по O(n) элементам, т.е. временная сложность этого алгоритма – O(n) на один запрос. Однако, задачу можно решить эффективнее.

Введение

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

Основные операции в деревьях выполняются за время пропорциональное его высоте. Сбалансированные деревья минимизируют свою высоту (к примеру, высота бинарного сбалансированного дерева с n узлами равна log n). Большинство знакомо с такими сбалансированными деревьями, как «красно-черное дерево», «AVL-дерево», «Декартово дерево», поэтому не будем углубляться.

В чем же проблема этих стандартных деревьев поиска? Рассмотрим огромную базу данных, представленную в виде одного из упомянутых деревьев. Очевидно, что мы не можем хранить всё это дерево в оперативной памяти => в ней храним лишь часть информации, остальное же хранится на стороннем носителе (допустим, на жестком диске, скорость доступа к которому гораздо медленнее). Такие деревья как красно-черное или Декартово будут требовать от нас log n обращений к стороннему носителю. При больших n это очень много. Как раз эту проблему и призваны решить B-деревья!

B-деревья также представляют собой сбалансированные деревья, поэтому время выполнения стандартных операций в них пропорционально высоте. Но, в отличие от остальных деревьев, они созданы специально для эффективной работы с дисковой памятью (в предыдущем примере – сторонним носителем), а точнее — они минимизируют обращения типа ввода-вывода.

Введение

Алгоритмы нечеткого поиска (также известного как поиск по сходству или fuzzy string search) являются основой систем проверки орфографии и полноценных поисковых систем вроде Google или Yandex. Например, такие алгоритмы используются для функций наподобие «Возможно вы имели в виду …» в тех же поисковых системах.

В этой обзорной статье я рассмотрю следующие понятия, методы и алгоритмы:

• Расстояние Левенштейна
• Расстояние Дамерау-Левенштейна
• Алгоритм Bitap с модификациями от Wu и Manber
• Алгоритм расширения выборки
• Метод N-грамм
• Хеширование по сигнатуре
• BK-деревья

А также проведу сравнительное тестирование качества и производительности алгоритмов.

Тема бинарных деревьев уже обсуждалась на хабре (здесь и здесь).

Про AA-дерево было сказано, что «из-за дополнительного ограничения операции реализуются проще чем у красно-черного дерева (за счет уменьшения количества разбираемых случаев)».

Мне, однако, кажется, что AA-дерево заслуживает отдельной статьи.

Интро

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

В своих статьях я буду приводить примеры кода сразу на двух языках: на Java и на Haskell. Благодаря этому можно будет сравнить императивный и функциональный стили программирования и увидить плюсы и минусы того и другого.

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

Хочу поділитися досвідом по темі звуку в Windows 7.
Насправді все не так погано, як спочатку здається, і я вам зараз це продемонструю.