Прочитал недавно книгу Уоррена «Алгоритмические трюки для программистов» (в оригинале она называется «Hacker’s Delight»), любопытная оказалась книжка, хотя алгоритмы, рассмотренные в ней, довольно специфические.

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

Многие алгоритмы явно предназначены для того, чтобы их реализовали на ассемблере, причем иногда для процессоров, более редких, чем x86 (например, часто упоминаются процессоры IBM, а иногда опоминаются и древние компьютеры еще 60-ых годов прошлого века). Автор пишет, что многие примеры из книги могут пригодиться тем, кто создает компиляторы. Для примера приведу описание некоторых задач, разбираемых автором: как обнулить крайний справа единичный бит (01011000 -> 01010000), округление к кратному степени двойки, подсчет единичных битов в слове, поиск строки битов и тому подобные. Почти для каждого алгоритма автор пытается оценить количество необходимых тактов процессора, иногда с учетом распараллеливания.

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

Ближе к концу книги есть глава, посвященная системам счисления с необычными основаниями, такие как -2, -1+i, -1-i. Такие системы счисления никто в здравом уме применять не будет, но почитать про них все-равно интересно.

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

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

Книгу можно рассматривать как небольшой сборник рецептов про битовые операции. Книга издавалась несколько раз, последнее издание 2007 года.

В электронном виде найти ее можно без проблем.

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

И вот неожиданно попалась книга Л.Г. Комарцовой и А.В. Максимова «Нейрокомпьютеры», изданная в МГТУ им. Баумана. Сначала, когда я взял в руки эту книжку в магазине, то не думал, что она меня заинтересует, предполагая по названию, что это будет что-то про реализацию персептронов в железе. Да и то, что книга предназначена для студентов сначала смутило, есть у меня одно предубеждение на счет институтских книжек, очень уж часто они оказываются слишком обобщенными и слишком теоретическими. После них остается какое-то странное ощущение, что вроде бы прочитал про описываемый предмет целую книгу, но как применить то, что там написано, непонятно.

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

Читать далее ‘Нейрокомпьютеры’ »

Прочитал книгу М. Тима Джонса «Программирование искусственного интеллекта в приложениях», которая в оригинале называется «AI Application Programming». Оказалось, что это очень даже интересная книжка, посвященная так называемому «слабому искусственному интеллекту», то есть алгоритмам и технологиям, которые уже сейчас используют в приложениях.

Все описываемые алгоритмы очень хорошо объясняются. Сначала алгоритм описывается буквально на пальцах, затем строится блок-схема последовательности действий, после чего приводится пример одной или нескольких итераций алгоритма на конкретных данных. После этого идет пример законченной программы, использующей описываемый алгоритм. Причем кроме подробных комментариев в тексте программы, работа каждой функции объясняется словами. Программы написаны на языке C (не C++) и изначально рассчитаны на Unix, поэтому для компиляции под Windows придется использовать CygWin, или подправлять исходники, чтобы программа компилировалась без CygWin. После описания программы в конце каждой главы кратко описываются пути улучшения алгоритма и ссылки по данной теме на литературу и сайты в интернете.

Кратко опишу про какие технологии и алгоритмы рассказывается в этой книге и на каких примерах.

Читать далее ‘Программирование искусственного интеллекта в приложениях’ »