Демонстрируем некоторые особенности написания TeX-макросов, встраивая в TeX калькулятор теоретико-числовых функций.

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

Время от времени мне приходится набирать очередной текст, сопровождаемый примерами вычисления теоретико-числовых функций: функция Эйлера φ, функция делителей τ, функция Кармайкла λ. Раньше это делалось так: запускаем любимый калькулятор (мой выбор — PARI/GP), в нем все считаем и копируем выкладки в ТеХ. Изменились исходные данные — снова в калькулятор и обратно. Много возни, много шансов забыть заменить какой-то промежуточный результат. Да и просто мышкой махать надоедает. Хочется автоматизировать этот процесс хотя бы для самых распространенных функций, чтобы можно было написать

$\phi(1001)=\Phi(1001)$

и получить на печати

Бэкапил историю сообщений из Skype самописной утилиткой, год назад она работала отлично, а теперь стала люто тормозить. Это неприемлемо, тк. в том числе ради скорости экспорта она и была написана, поэтому полез в профайлер. По итогам узнал всякое и получил множественные просветления. Оказывается, breakpoint на функцию в подгруженной системной DLL ставить приходится с подвывертом, а не просто по имени, но таки можно и нетяжело. Оказывается, Skype API написан местами зверски криво, отчего и тормозища. Оказывается, чужие бинарники иногда можно очень легко подхачить и подоптимизить (слава MS Research!). Оказывается, профайлер может сильно врать, а не просто слегка подбрехивать. Ключевые слова для нетерпеливых: C++, VS, CodeAnalyst, Skype COM API, MS Research, Detours, SQLite; а для всех остальных подробности под катом.

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

Привет, Хабр!
Сегодня я расскажу и покажу вам, как можно использовать всю мощность ваших видеокарт для игр перебора паролей к Wi-Fi. Как-то не комильфо в наше время использовать только процессорные мощности под эти задачи (в частности aircrack-ng), когда в 80% компьютеров есть видеокарта. Поэтому разумно использовать всю потенциальную мощность ваших систем. А именно, речь пойдет о замечательной программе pyrit.

Так уж случилось, что пару лет назад по долгу службы на команду разработчиков, к которой я отношусь, свалилась неожиданная задача — разработка системы управления оборудованием (в этом-то как-раз неожиданности нет, ибо направление разработок такое) с управляющим PC под Linux.
Разработки линуксовой части велись (да и ведутся) под Ubuntu, в среде Code::Blocks. Но, как показала практика, для качественной работы нужно что-то гораздо более легкое с гарантированным временем отклика. Для работы было достаточно консоли, так как задачи организации пользовательского интерфейса решались на подключаемом по TCP/IP удаленном компьютере.
Тогда и пришла идея использовать дистрибутив Linux собственной сборки, чем (сборкой дистрибутива), собственно, в свободное время я и занялся. Выбор пал на LFS. Про то что такое LFS уже неоднократно писали даже на Хабре, я же опишу решение нескольких дополнительных (кроме простенького Linux'а) задач, вставших передо мной в нашем конкретном случае.
Поначалу такая задача была одна — использовать real-time ядро.
Однако дальше, когда идея USB-флешки с дистрибутивом, пришлась всем по душе, то появились задачи размножения флешек и запуска системы на различных компьютерах (тестовых стендов много, имея свою флешку суешь в карман и иди к любому). Вот тут и появились проблемы — LFS не обладает 100% переносимостью с одного компьютера на другой. Для ее адаптации к конкретному компьютеру нужно править некоторые скрипты, что в условиях команды вчерашних Windows-кодеров проблематично (на виртуалку с Ubuntu некоторые пересели, но консоль и скрипты — это беда). Размножение системы также требует повторения некоторых манипуляций, проделываемых в процессе сборки (тот же GRUB установить).

Межпроцессное взаимодействие (Inter-process communication (IPC)) — это набор методов для обмена данными между потоками процессов. Процессы могут быть запущены как на одном и том же компьютере, так и на разных, соединенных сетью. IPC бывают нескольких типов: «сигнал», «сокет», «семафор», «файл», «сообщение»…

В данной статье я хочу рассмотреть всего 3 типа IPC:

1. именованный канал
2. разделенная память
3. семафор

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

После покупки своего первого смартфона люди обычно замечают, что расходы на мобильную связь немного увеличиваются. Обычно это происходит за-за того, что «умный» телефон «ходит в Сеть» без ведома хозяина. Конечно, решить эту проблему просто — установить специальные утилиты для блокирования подключений к точкам доступа GPRS/HSDPA либо купить безлимитный тариф на доступ в Интернет и забыть. Столкнувшись с описанной ситуацией, я в первую очередь заинтересовался и тем, что телефон ищет в Сети и, самое главное, что передает в Сеть. Последнее особенно актуально в связи с недавними новостями.

Довольно оживленное обсуждение предыдущей стати (http://habrahabr.ru/blogs/programming/47416/) показало, что тема пролога оказалась интересна сообществу.
Чтобы заинтересовать еще более читателя и вместе с тем облегчить ему начало работы с этим языком, я решил написать немного начальных данных о прологе.

Кратко основные особенности.

Добрый вечер.
Этот пост посвящён быстрому преобразованию Фурье. Будут рассмотрены прямое и обратное преобразования (в комплексных числах). В следующей части я планирую рассмотреть их применения в некоторых задачах олимпиадного программирования (в частности, одна задача про «похожесть» строк), а также рассказать про реализацию преобразования в целых числах.
БПФ — это алгоритм, вычисляющий значения многочлена степени n=2^k в некоторых n точках за время O(n⋅logn) («наивный» метод выполняет ту же задачу за время O(n²)). За то же время можно выполнить и обратное преобразование. Так как складывать, вычитать и умножать массивы чисел гораздо легче, чем многочлены (особенно умножать), БПФ часто применяется для ускорения вычислений с многочленами и длинными числами.

Здравствуйте!

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

О том, что спрашивают на собеседовании у C++ программистов, а также об ответах на эти вопросы и пойдет речь в данном посте.

Редакционное расстояние, или расстояние Левенштейна — метрика, позволяющая определить «схожесть» двух строк — минимальное количество операций вставки одного символа, удаления одного символа и замены одного символа на другой, необходимых для превращения одной строки в другую. В статье излагается метод вычисления редакционного расстояния при использовании небольшого объема памяти, без существенной потери скорости. Данный подход может быть применен для больших строк (порядка 10⁵ символов, т.е. фактически для текстов) при получении не только оценки «схожести», но и последовательности изменений для перевода одной строки в другую.

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



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

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

Потребовалось мне как-то запустить игру, которая запускается под wine, через прокси. Поднял ssh-туннель, запустил игру через proxychains, и… игра не смогла соединиться с сервером, хотя chromium без проблем работал и показывал ip прокси. Попробовал tsocks — игра вообще не запустилась. Можно, конечно, было настроить VPN-туннель с помощью того же ssh, но сервер — VPS, под OpenVZ, у которого по умолчанию выключен TUN, что привело бы к письму в техподдержку и ожиданию.
Итак, пятиминутное гугление привело меня к заброшенному проекту Transocks, который, в отличие от proxychains и tsocks, которые подгружают свои библиотеки и перехватывают сетевые вызовы, слушает определенный порт и перенаправляет все, что в него пришло, через socks4 прокси. К сожалению, transocks у меня не собрался, и я начал гуглить дальше.

Пользователь yruslan опубликовал хорошую статью про арифметику с плавающей запятой: «Что нужно знать про арифметику с плавающей запятой».

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

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

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

Арифметика с плавающей запятой почему-то считается экзотической областью компьютерных наук, учитывая, что соответствующие типы данных присутствуют в каждом языке программирования. Я сам, если честно, никогда не придавал особого значения компьютерной арифметике, пока решая одну и ту же задачу на CPU и GPU получил разный результат. Оказалось, что в потайных углах этой области скрываются очень любопытные и странные явления: некоммутативность и неассоциативность арифметических операций, ноль со знаком, разность неравных чисел дает ноль, и прочее. Корни этого айсберга уходят глубоко в математику, а я под катом постараюсь обрисовать лишь то, что лежит на поверхности.

Введение

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

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

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

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

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

Сразу скажу — топик — для тех, кто не разобрался что такое MapReduce. Для тех, кто разобрался — полезного тут ничего не будет.

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

Сначала опишу как она рождалась (подход был неправильный), а потом как надо правильно делать.

Как посчитать все слова в Википедии (неправильный подход)

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

В самом простом случае мы можем завести хеш (dict, map, hash, ассоциативный массив, array() в PHP) и считать в нем слова.

$dict['word1'] += 1

Но что делать когда память под хеш кончится, а мы посчитали только одну сотую всех слов?

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

Ранее была получена возможность перехватывать весь трафик исследуемого субъекта. Однако банальный анализ логов tcpdump не даёт значимого результата, так как большинство сервисов использует шифрование с помощью SSL для передачи важных данных, в том числе паролей.