расширенный поиск

Книга: Алгоритмические трюки для программистов

Товар № 10751705

2-е издание Hacker's Delight, 2nd Edition, Henry S. Warren

Автор: Уоррен Г.С.
Издательство: Вильямс
Вес: 0.670 кг.
Год издания: 2020
Формат: 165х235 мм
Страниц: 512 Переплет: Мягкая обложка
Товар отсутствует
Узнать о поступлении

Перед вами сборник программных приемов, которые я собирал много лет. Большинство из них работают только на компьютерах, на которых целые числа представлены в дополнительном до 2 коде. Хотя в данной книге речь идет о 32-разрядных машинах с соответствующей длиной регистра, большую часть представленных здесь алгоритмов легко перенести на машины с регистрами других размеров. В этой книге не рассматриваются сложные вопросы наподобие методов сортировки или оптимизации компилируемого кода. Основное внимание здесь уделяется приемам работы с отдельными машинными словами или командами, например подсчету количества единичных битов в заданном слове. В подобных приемах часто используется смесь арифметических и логических команд. Предполагается, что прерывания, связанные с переполнением целых чисел, замаскированы и произойти не могут. Программы на С, Fortran и даже Java работают именно в таком окружении, но программистам на Pascal и ADA следует быть осторожными! Представление материала в книге — неформальное. Доказательства приводятся только в том случае, если алгоритм неочевиден, а иногда не приводятся вообще. Все методы используют компьютерную арифметику, функции типа "пол", комбинации арифметических и логических операций и тому подобные средства, а доказательства теорем в этой предметной области часто сложны и громоздки. Чтобы свести к минимуму количество типографских ошибок и опечаток, многие алгоритмы реализованы на языке программирования высокого уровня, в качестве которого используется С. Это обусловлено его распространенностью и тем, что он позволяет непосредственно комбинировать операции с целыми числами и битовыми строками; кроме того, компиляторы языка С генерируют объектный код высокого качества. Ряд алгоритмов написан на машинном языке. В книге применяется трехадресный формат команд, главным образом для повышения удобочитаемости. Использован язык ассемблера для некой абстрактной машины, которая является представителем современных RISC-компьютеров.

Читать далее
Посмотреть все товары по теме: algoritmus
1 отзыва о Книга: Алгоритмические трюки для программистов
Средний рейтинг:
  • - 2014-05-29 16:01:19
    Знаете ли Вы Первый закон творческого программирования? Он используется в качестве эпиграфа в книге Уоррена и звучит так: Cтоимость сопровождения программного обеспечения пропорциональна квадрату творческих способностей программиста. Роберт Д. Блисc Это, конечно, шутка, но в ней, как всегда, есть изрядная доля правды. Я эту книжку мог бы купить даже за один эпиграф! Но Вы - это не я, поэтому расскажу, о чем в книге написано. Уже по оглавлению можно судить о содержании. Множество изящнейших решений задач, которые время от времени появляются в форуме "Этюды для программистов". Уже на первой странице первой главы есть несколько простых формул. Одна из них x & (x-1) Как вы думаете, для чего она может пригодиться? Оказывается, так можно обнулить крайний справа единичный бит. И таких формул - море! Но книжка ценна не только простыми формулами. Здесь огромное количество алгоритмов. Например, в главе 11 приводится аппаратный алгоритм вычисления целочисленного квадратного корня, в котором используются только операции вычитания, сдвига вправо, и логического или (- >> | в нотации С). Считать все алгоритмы я не стал, но то, что их больше сотни - это факт! Алгоритмы написаны в одной из двух нотаций: либо на псевдо-С (очень похож на настоящий), либо в кодах гипотетической трехадресной RISC-машины, которая (ИМХО) сильно похожа на кнутовскую MMIX. В первой главе Уоррен приводит полное ее описание. В общем, понятно написано. В книжке СОВСЕМ нет никакой воды - сплошная информация. Читать ее в автобусе или в метро - трудно. Если хочешь понять, почему работает, то надо вдумчиво, за столом разбирать много примеров. Изучение (не чтение, нет) этой книги существенно повысит понимание встроенных типов данных (особенно целых) и многих нюансов работы процессора. Для большинства алгоритмов приводится математическое доказательство корректности - для некоторых это может быть интересно. Книгу можно использовать и при разработке компилятора - тут прямо приводятся оптимизационные формулы и алгоритмы. Например, на странице 206 приводится алгоритм вычисления 2^n в компиляторе IBM XL Fortran. Полезна книга окажется и для разработчиков систем реального времени, где критично время вычислений. Да и в обычных приложениях найдется, где можно применить что-нибудь из этой книжки. И напоследок. В 80-е годы в сборнике Уэзерелла "Этюды для программистов" была опубликована наверное самая знаменитая задача (по крайней мере, в России): написать программу, которая выводит свой собственный текст. Файлы использовать нельзя. Автор приводит САМУЮ КОРОТКУЮ программу на С, из известных ему, содержащую всего 64 символа. Написана Владом Таировым и Рашидом Фахреевым. main(a){printf(a,34,a="main(a){printf(a,34,a=%c%s%c,34);}",34);} Печатает саму себя - проверено в Borland C++ в режиме трансляции С-программ без отладочной информации для UNIX V. Конечно, с высоты современных стандартов это уродец, но в данном случае это неважно. Книга содержит и учит находить такие нестандартные решения. Почитайте - не пожалеете Лаптев Валерий