Показать ещё...
Предлагаемая вниманию читателя книга является продолжением моей книги "Занимательная компьютерная арифметика: Математика и искусство счета на компьютерах и без них". Название "Быстрые алгоритмы" допускает неоднозначное толкование. Например, естественно подумать, что будут обсуждаться методы быстрого выполнения различных видов вычислений (фактически, подобные вопросы уже рассматривались в предыдущей части книги). Но можно также решить, что будут рассматриваться вопросы о том, как измерить сложность того или иного вычислительного алгоритма и оценить время его работы на компьютере (или объем вычислений, который предстоит выполнить собственными руками). Речь пойдет и о том, и о другом. Настоящий материал можно изучать независимо от первой части, хотя в нем и содержится небольшое количество ссылок на книгу "Математика и искусство счета на компьютерах и без них". Следующее далее введение в основном повторяет введение к предыдущей книге. Развитие быстрых алгоритмов происходит медленно.
Арнольд Шёнхаге Здесь уместно разъяснить, что означает термин "компьютерная арифметика" или, по крайней мере, как он понимается в книге. Как и любая область науки, компьютерная арифметика состоит из нескольких связанных между собой направлений и по-разному выглядит с разных точек зрения. В ней есть и многочисленные технические детали, и фундаментальные понятия. Естественно, вторым будет уделяться больше внимания, чем первым, поэтому в технической области изложение не всегда будет исчерпывающим. С одной стороны, компьютерная арифметика, как и следует ожидать, должна объяснять, как выполняются на компьютере различные операции с числами и/или машинными словами. Компьютеры имеют многочисленные команды для выполнения таких операций, среди которых есть и арифметические, и логические. Разные компьютеры (а к их числу без большой ошибки можно причислить и калькуляторы, да и почти любую цифровую технику) делают это по-разному и имеют различные наборы команд. Знание особенностей системы команд компьютера, конечно, нужно каждому программисту, хотя оно выходит за пределы собственно программирования – чтобы писать программы, в общем-то не обязательно знать, каким образом компьютер выполняет команду сравнения чисел или их деления с остатком. Кроме того, полное понимание процессов, реально происходящих в компьютере во время выполнения программы, требует знания массы технических деталей, связанных с устройством процессора и других микросхем, составляющих компьютер, и выходит за рамки собственно компьютерной арифметики, относясь к области, которую можно назвать архитектурой вычислительных систем. Тем не менее компьютерные процессоры и другие большие цифровые микросхемы ("чипы") содержат в себе сравнительно небольшие микросхемы для выполнения отдельных арифметических или логических операций. Разобраться в их устройстве, по крайней мере в общих принципах функционирования, не так уж и сложно, потому что электронные микросхемы, как старые, так и самые современные, имеют очень простую математическую модель – схему из функциональных логических элементов, часто называемую в инженерной практике комбинационной схемой, а в теории – булевой логической схемой, или просто схемой (реализующей булевы функции, называемые также функциями алгебры логики). Построение булевых схем, реализующих арифметические и логические операции, относится к сфере первоочередных интересов компьютерной арифметики, и в тоже время составляет существенный раздел теории сложности булевых функций. Впрочем, вопросы связанные с поиском эффективных алгоритмов построения булевых схем и с автоматизацией проектирования реальных электронных микросхем содержат множество технических деталей и выходят за рамки как компьютерной арифметики, так и теории сложности булевых функций, относясь к специальной области компьютерных наук – автоматизации проектирования микросхем. Разумеется, касаться этой области в популярной книге неуместно. В программировании иногда возникает необходимость выполнять арифметические действия с "длинными" числами, не умещающимися в разрядную сетку компьютера, например в научных расчетах для достижения требуемой точности, в криптографии для выполнения действий с числами, состоящими из сотен цифр, в рекордных вычислениях, например, с целью найти миллиард знаков числа pi и т.д. Для выполнения этих действий нельзя непосредственно использовать команды машинной арифметики, а необходимо писать программы для так называемой длинной арифметики. Такие программы давно написаны и входят в пакеты многих систем компьютерной алгебры. Чтобы самому написать подобные программы и разобраться в работе известных программ нужна компьютерная арифметика. На самом деле используемые в этих программах арифметические алгоритмы весьма близки к алгоритмам, "зашитым в железе" электронных микросхем для выполнения арифметических операций. Но вместо двоичной системы счисления, которая используется в микросхемах (хотя используются и микросхемы, реализующие с помощью двоичных элементов десятичную арифметику), в компьютерных программах "длинной арифметики" обычно применяется система счисления с основанием 2w где w – длина машинного слова применяемого компьютера, а для записи самих программ вместо двоичной удобно использовать шестнадцатеричную систему (так как это в четыре раза сокращает длину записи чисел). Использование подходящей (как правило, того или иного варианта позиционной) системы счисления является простейшей, старейшей, и в то же время важнейшей и фундаментальной идеей, используемой в компьютерной арифметике. Поэтому знакомство с ней естественно начинать с рассмотрения различных систем счисления. Книга "Занимательная компьютерная арифметика: Математика и искусство счета на компьютерах и без них" с этого и начинается, причем содержит почти целиком (и в несколько дополненном виде) материал из брошюры автора "Системы счисления и их применения". На самом деле упомянутая брошюра и задумывалась как первая часть популярной книги по компьютерной арифметике, но ее написание несколько затянулось, и первую часть пришлось опубликовать отдельно. Арифметические алгоритмы в нашей книге обычно излагаются для произвольной позиционной системы, но иногда они даются только для десятичной системы (чтобы подчеркнуть удобство их применения в ручных вычислениях, и даже в устном счете), а иногда – только для двоичной (потому что в двоичной системе они имеют наиболее простой вид и наиболее широкую область применения). Кроме чисто арифметических алгоритмов уместно показалось рассмотреть в книге некоторые вопросы, связанные с вычислениями с обыкновенными дробями, многочленами и дробно-рациональными функциями. Эти вопросы являются пограничными между компьютерной алгеброй и компьютерной арифметикой и весьма близки к последней. Их включение в книгу оправдано также тем, что, например, алгоритмы арифметических действий с многочленами на самом деле проще аналогичных алгоритмов для чисел. Особенностью книги является также то, что, помимо описания различных алгоритмов, часто дается обоснованная оценка их сложности (т.е. числа выполняемых ими операций). В случае логических схем оценка их сложности позволяет объективно судить о размерах, которые может иметь реальная электронная микросхема, моделируемая рассматриваемой логической схемой. В случае же программных алгоритмов оценка их сложности позволяет судить о времени их работы. Умение оценивать сложность алгоритма, таким образом, полезно и в программировании и в проектировании (и производстве) электронной техники. Разделы, связанные с оценками сложности, находятся в конце книги и составляют, по-видимому, наиболее сложную ее часть (извините за каламбур). Это не удивительно, поскольку они находятся на границе между собственно компьютерной арифметикой и теорией сложности вычислений. Чтобы компенсировать неизбежную сложность некоторых разделов книги, в нее показалось разумным вставить различный развлекательный материал, вроде приемов устных вычислений, интересных даже младшеклассникам, алгоритмам вычислений на калькуляторах, применений систем счисления за пределами компьютерной арифметики, исторических сведений о первооткрывателях тех или иных идей, затрагиваемых в книге и т.д. (однако точные ссылки на используемые результаты, как правило, не даются). Рассмотрены также вопросы эффективного выполнения некоторых манипуляций с числами и машинными словами на компьютере в условиях, когда отсутствуют команды, непосредственно их выполняющие. Подобные вопросы несомненно также относятся к компьютерной арифметике. Книга, претендующая на популярность, не может освещать рассматриваемые вопросы в достаточной полноте. Поэтому некоторые вопросы, связанные с компьютерной арифметикой, затронуты лишь мимоходом или не затронуты вовсе. Это и вопросы оценки точности машинных вычислений, арифметика с плавающей запятой, логические схемы с памятью (автоматные схемы), алгоритмы вычисления элементарных функций, принципы работы компьютерного процессора, физические принципы работы электронных микросхем и их математического моделирования, вопросы проектирования, тестирования и производства чипов и т.д. Многим из подобных вопросов уже посвящаются целые книги (разумеется, не научно-популярные). Из великого множества алгоритмов компьютерной арифметики в книге упоминается лишь небольшая часть. Предполагается, что читатель немного знает школьную математику (сейчас изучает ее или еще не успел забыть), поэтому иногда в книге используются без пояснений некоторые понятия и обозначения. Но во многих случаях необходимые пояснения даются. В отличие от учебников изложение не всегда систематичное, одним вопросам уделяется больше внимания, другим – меньше, некоторые темы даже не упоминаются, в книге встречаются ссылки как назад, так и вперед и т.д. Все это неизбежные особенности вольного стиля изложения (вообще свойственного, как нам кажется, научно-популярной литературе). Но изНза почти полного отсутствия на русском языке литературы по компьютерной арифметике автор надеется, что ее можно будет использовать и с учебной целью как в школах, так и в вузах. В заключение автор благодарит своих бывших учеников (и нынешних коллег) А.А.Бурцева и И.С.Сергеева за помощь в работе. Гашков Сергей Борисович Доктор физико-математических наук, профессор. Профессор кафедры дискретной математики механико-математического факультета МГУ имени М. В. Ломоносова. Автор и соавтор книг «Примени математику», «Арифметика. Алгоритмы. Сложность вычислений», «Системы счисления и их применения», «Современная элементарная алгебра», «Элементарное введение в эллиптическую криптографию» (URSS; в 2 кн.), «Криптографические методы защиты информации», «Занимательная компьютерная арифметика» (URSS; в 2 кн.), «Геометрические неравенства: Путеводитель в задачах и теоремах» (URSS), «Алгоритмические основы эллиптической криптографии», «Дискретная математика: Учебник и практикум для академического бакалавриата», «Обыкновенные дроби: От Древнего Египта до наших дней» (URSS), «Булев куб, или Булеан: Уникальная комбинаторная конструкция и ее приложения» (URSS), «Введение в конструктивную комбинаторику» (URSS), «Элементарная комбинаторика» (URSS).
|
2023. 720 с. Твердый переплет. 16.9 EUR
Книга «Зияющие высоты» – первый, главный, социологический роман, созданный интеллектуальной легендой нашего времени – Александром Александровичем Зиновьевым (1922-2006), единственным российским лауреатом Премии Алексиса де Токвиля, членом многочисленных международных академий, автором десятков логических... (Подробнее) URSS. 2024. 800 с. Мягкая обложка. 37.9 EUR
ВЕРСАЛЬ: ЖЕЛАННЫЙ МИР ИЛИ ПЛАН БУДУЩЕЙ ВОЙНЫ?. 224 стр. (ТВЁРДЫЙ ПЕРЕПЛЁТ) 11 ноября 1918 года в старом вагоне неподалеку от Компьеня было подписано перемирие, которое означало окончание Первой мировой войны. Через полгода, 28 июня 1919 года, был подписан Версальский договор — вердикт, возлагавший... (Подробнее) 2023. 696 с. Твердый переплет в суперобложке. 119.9 EUR
Опираясь на новейшие исследования, историк Кристофер Кларк предлагает свежий взгляд на Первую мировую войну, сосредотачивая внимание не на полях сражений и кровопролитии, а на сложных событиях и отношениях, которые привели группу благонамеренных лидеров к жестокому конфликту. Кларк прослеживает... (Подробнее) URSS. 2024. 704 с. Твердый переплет. 26.9 EUR
В новой книге профессора В.Н.Лексина подведены итоги многолетних исследований одной из фундаментальных проблем бытия — дихотомии естественной неминуемости и широчайшего присутствия смерти в пространстве жизни и инстинктивного неприятия всего связанного со смертью в обыденном сознании. Впервые... (Подробнее) URSS. 2024. 344 с. Мягкая обложка. 18.9 EUR
Мы очень часто сталкиваемся с чудом самоорганизации. Оно воспринимается как само собой разумеющееся, не требующее внимания, радости и удивления. Из случайно брошенного замечания на семинаре странным образом возникает новая задача. Размышления над ней вовлекают коллег, появляются новые идеи, надежды,... (Подробнее) URSS. 2023. 272 с. Мягкая обложка. 15.9 EUR
Настоящая книга посвящена рассмотрению базовых понятий и техник психологического консультирования. В ней детально представлены структура процесса консультирования, описаны основные его этапы, содержание деятельности психолога и приемы, которые могут быть использованы на каждом из них. В книге... (Подробнее) URSS. 2024. 576 с. Мягкая обложка. 23.9 EUR
Эта книга — самоучитель по военной стратегии. Прочитав её, вы получите представление о принципах военной стратегии и сможете применять их на практике — в стратегических компьютерных играх и реальном мире. Книга состоит из пяти частей. Первая вводит читателя в мир игр: что в играх... (Подробнее) URSS. 2024. 248 с. Мягкая обложка. 14.9 EUR
В книге изложены вопросы новой области современной медицины — «Anti-Ageing Medicine» (Медицина антистарения, или Антивозрастная медицина), которая совмещает глубокие фундаментальные исследования в биомедицине и широкие профилактические возможности практической медицины, а также современные общеоздоровительные... (Подробнее) URSS. 2024. 240 с. Твердый переплет. 23.9 EUR
Предлагаемая вниманию читателей книга, написанная крупным биологом и государственным деятелем Н.Н.Воронцовым, посвящена жизни и творчеству выдающегося ученого-математика, обогатившего советскую науку в области теории множеств, кибернетики и программирования — Алексея Андреевича Ляпунова. Книга написана... (Подробнее) 2023. 416 с. Твердый переплет. 19.9 EUR
Вам кажется, что экономика — это очень скучно? Тогда мы идем к вам! Вам даже не понадобится «стоп-слово», чтобы разобраться в заумных формулах — их в книге нет! Все проще, чем кажется. Автор подаст вам экономику под таким дерзким соусом, что вы проглотите ее не жуя! Вы получите необходимые... (Подробнее) |