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

Большая заслуга в этом принадлежит американскому математику и инженеру Клоду Шеннону(1916–2001), который считается создателем теории информации. Шеннон познакомился с работой Буля на занятиях по философии в Мичиганском университете, и в 1937 году защитил магистерскую диссертацию в Массачусетском технологическом институте (MIT), показав, что булеву алгебру можно использовать для оптимизации электрических цепей. В 1935 году независимо от Шеннона логик Виктор Шестаков(1907–1987) из Московского государственного университета также использовал булеву алгебру в этих же целях.

Булева алгебра оказалась столь полезной в информатике потому, что она описывает идеальный сценарий с точки зрения двоичной логики. В ней используются только нули и единицы, основными операциями являются И, ИЛИ и НЕ, то есть конъюнкция (бинарная операция, обозначаемая ), дизъюнкция (бинарная операция, обозначаемая ) и отрицание (унарная операция, обозначаемая ¬). Эти логические операции определяются с помощью следующих таблиц истинности.

Другие привычные операции, например импликация (операция, схожая с конструкцией «если… то»), выражаются через три основные операции, представленные выше: ( х — > у ) = ¬ х y , Кроме того, в виде комбинации этих операций можно представить любую другую логическую функцию. Так называемый закон де Моргана гласит, что существует всего две основные логические операции. Например, это могут быть дизъюнкция и отрицание, с помощью которых также можно выразить операцию конъюнкции.

* * *

ДЖОРДЖ БУЛЬ (1815–1864)

Британский математик и философ Джордж Буль создал алгебру, которая стала основой современной вычислительной техники. Именно поэтому он считается одним из основателей информатики. Его важнейшими математическими трудами являются Treatise on Differential Equations («Трактат о дифференциальных уравнениях»), опубликованный в 1859 году, и его продолжение Treatise on the Calculus of Finite Differences («Трактат о конечных разностях»), вышедший в 1860 году. Свою систему правил для математической записи и упрощения логических и философских задач, аргументы которых могут принимать только два значения (истина или ложь), он изложил в труде «Исследование законов мышления, на которых основываются математические теории логики и вероятностей» ( An Investigation of the Laws of Thought, on Which are Founded the Mathematical Theories of Logic and Probabilities ).

* * *

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

Число π в 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. Множество алгебраических чисел является счетным. Трансцендентное же число не является корнем многочлена с целыми коэффициентами. Самыми известными трансцендентными числами являются π и е .

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

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