Бизенц Торра - Том 15. От абака к цифровой революции. Алгоритмы и вычисления

* * *

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

Число π в XIX веке

В середине XVIII века, точнее в 1761 году, немецкий математик, физик, астроном и философ французского происхождения Иоганн Ламберт (1728–1777) показал, что число π и его квадрат π2 являются иррациональными числами. Тем самым была доказана невозможность вычислить их «точное» значение. Лишь 120 лет спустя работы по вычислению значения π снова обрели важность. В 1882 году математик Фердинанд Линдеман (1852–1939) доказал, что число π является трансцендентным. Это означало, что задача о квадратуре круга нерешаема с помощью циркуля и линейки.

Некоторые задачи, касающиеся числа π, до сих пор остаются открытыми, в частности задача о нормальности π. Иррациональное число является нормальным, если вероятность появления числовых последовательностей равной длины в его записи одинакова. Например, все цифры от 0 до 9 фигурируют в записи нормального с одинаковой вероятностью, равной 1/10, все последовательности из двух цифр — с вероятностью 1/100 и так далее. Нормальность числа π все еще не доказана, однако считается, что π действительно является нормальным. Были подсчитаны частоты, с которыми в его записи появляются различные цифры. В конце XX века американский математик Дэвид Бэйли проанализировал первые 29360000 знаков π. Рассмотрев последовательности длиной до 6 цифр включительно, он не обнаружил никаких признаков неравномерности. Различия в частотах оказались минимальными и не имели статистической значимости. Приведем в качестве примера частоты, с которыми в записи π появляются цифры от 0 до 9.

* * *

АЛГЕБРАИЧЕСКИЕ И ТРАНСЦЕНДЕНТНЫЕ ЧИСЛА

Число называется алгебраическим, если оно является корнем многочлена одной переменной с целыми коэффициентами. Все целые и рациональные числа, а также некоторые иррациональные, являются алгебраическими. Наиболее известное из алгебраических иррациональных чисел — √2. Это число является корнем многочлена х2 — 2 = 0. Множество алгебраических чисел является счетным. Трансцендентное же число не является корнем многочлена с целыми коэффициентами. Самыми известными трансцендентными числами являются π и е.

Глава 4

Компьютеры в XX веке

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

Главными героями в истории информатики и вычислительной техники в XX веке были исключительные личности, которые много лет были никому не известны. Среди них — немецкий инженер Конрад Цузе и его вычислительные машины серии Z. Большинство изобретений Цузе долгое время оставались незамеченными, так как были сделаны незадолго до начала Второй мировой войны, а работа над ними продолжалась в последующие несколько лет. Цузе, сам того не осознавая, следовал идеям Бэббиджа, с работами которого он был совершенно не знаком. Когда Джон фон Нейман позднее описал архитектуру компьютера, он не руководствовался работами Цузе. Несомненно, созданная ими архитектура вычислительных машин была оптимальной: это подтвердили специалисты в области логики. Она содержала устройство управления, память и арифметико-логическое устройство для выполнения вычислений.

Цузе создал две первые машины в период с 1935 по 1939 год, перед самым началом Второй мировой войны. Его первая патентная заявка датирована 11 апреля 1936 года. В 1938 году он подал патентную заявку в США. Она была отклонена, так как Цузе изложил свое открытие недостаточно подробно. Его вычислительные машины назывались Z1 и Z2. Сначала Цузе назвал первую машину VI (от слова Versuchsmodell, что означало «экспериментальная модель»), но затем сменил название, чтобы избежать путаницы с названиями ракет VI и V2 Вернера фон Брауна.

Первая машина Z1 имела размеры 2 х 1,5 метра. Сделанная из стали, она была достаточно ненадежной: поправки требовалось вносить каждые несколько минут. Это был всего лишь двоичный механический калькулятор с ограниченными возможностями программирования, работавший от электричества. Цузе сконструировал Z2, чтобы исправить недостатки первой машины. Для сохранения чисел и представления чисел с фиксированной запятой в ней использовались реле. Позднее, по совету Хельмута Шрайера, Цузе спроектировал машину Z3, в которой использовались электронные лампы. Эта машина работала без сбоев.

Она была представлена в Институте аэродинамических исследований 5 декабря 1941 года. В машине Z3 ввод данных выполнялся с клавиатуры, а управляющая программа записывалась на целлулоидной ленте. В памяти машины можно было сохранять до 64 чисел, представляемых в двоичной системе счисления с плавающей запятой. Для хранения каждого числа использовалось 22 бита: 1 бит для знака, 7 для показателя степени, 14 для мантиссы. Цузе обнаружил, что в представлении числа с плавающей запятой первый бит может быть всегда равным единице — достаточно подобрать соответствующий показатель степени. Эта форма представления чисел используется и сейчас. С ее помощью можно «сэкономить» один бит, который всегда равен единице. Благодаря открытию Цузе машина Z3 могла работать с числами, мантисса которых представлялась 13 битами. Тем не менее эта машина имела одно важное ограничение: в ней не были реализованы условные переходы. Скорость вычислений составляла три-четыре операции сложения в секунду, умножение выполнялось за четыре-пять секунд.

По заказу Института аэродинамических исследований Цузе немедленно приступил к работе над Z4. Окончательный вариант машины был представлен 28 апреля 1945 года. В памяти машины можно было сохранять 1024 32-битных числа. В ней также были реализованы подпрограммы и условные переходы. Кроме того, был реализован механизм чтения двух инструкций, следующих за данной. Таким образом, операции можно было менять местами, если это не влияло на результат, что обеспечивало экономию времени. Эта процедура была реализована в более поздних компьютерах и получила название lookahead («просмотр вперед»).

Перед самым окончанием войны Цузе переехал на ферму в Альпах и начал работу над докторской диссертацией, озаглавленной «Общая теория вычислений». В этой диссертации, завершенной в 1946 году, описывался язык Планкалкюль (от нем. Plankalkül — «исчисление планов») — протоязык программирования, который тем не менее не был реализован. Планкалкюль был создан для решения числовых и других задач. Для него был характерен высокий уровень абстракции, значительно превосходящий другие языки программирования того времени. Первым языком, который действительно мог с ним сравниться, был Алгол, созданный много лет спустя.

* * *

КОНРАД ЦУЗЕ (1910–1995)

В университетские годы немецкому инженеру Конраду Цузе приходилось выполнять множество расчетов вручную. Он изнывал от скуки и задумался о создании машины, способной помочь ему в расчетах. По окончании университета он начал работать на авиационном заводе, но вскоре оставил работу и занялся постройкой своей машины в доме родителей. Вскоре он создал первый в мире работающий программируемый компьютер. Он создал машины общего назначения серии Z, машины S1 и S2 для выполнения расчетов, связанных с бомбардировками, а также машину L1 для вычисления значений логических функций. Он также разработал язык программирования Планкалкюль, который не вышел за рамки теории. Цузе основал несколько компаний для постройки своих машин. Важнейшей из них стала Zuse KG, силами которой были частично изготовлены машины серии Z. Zuse KG считается первой в истории компьютерной компанией.

* * *

В 1947 году в разрушенной послевоенной Германии Цузе возвращается к работе над своими машинами. Он наладил контакты с IBM, а позднее с Remington-Rand, с которой заключил соглашение. Он создал машины на электронных лампах, в частности Z22, и на транзисторах, в частности Z23 и Z3. Позднее ученый разработал Z64 — графопостроитель, управляемый машиной.