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

• Название: Том 15. От абака к цифровой революции. Алгоритмы и вычисления
• Автор: Бизенц Торра
• Издательство: «Де Агостини»
• Жанр: Математика
• Год: 2014
• ISBN: 978-5-9774-0710-6

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

По сути, компьютерная программа — не более чем алгоритм, составленный на языке, понятном компьютеру. Однако царствование алгоритмов в вычислительной технике — лишь краткий эпизод долгой и интересной истории, которая началась вместе с зарождением вычислений. В этой книге рассказывается история алгоритмов, а также описываются важнейшие особенности вычислений и вычислительной техники, начиная от первых счетных палочек и заканчивая компьютерами, без которых невозможно представить современный мир.

---

gcd (А, 0, А).

gcd (А, В, D)(А > В), (В > 0), R is A mod В, gcd(B, R, D).

gcd (А, В, D)(А < В), (А > 0), R is В mod A, gcd(A, R, D).

В реализации на языке Java также используются вышеизложенные правила. В качестве входных параметров использованы два числа А и В, в качестве результата функция возвращает их наибольший общий делитель. Первая версия алгоритма является рекурсивной, вторая — итеративной.

public static int gcd (int A, int B) {

if (B == 0) {return A;}

else if (A > B) {return gcd(B, A % B);}

else if (A < B) {return gcd(A, В % A);}

return 1;

}

public static int gcdlterative (int A, int B) {

int r = 0;

while (B > 0) {

r = A % B;

A = B;

В = r;

}

return A;

}

* * *

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

С современной точки зрения эти примитивные программы были написаны на машинном языке, поэтому Ада Лавлейс считается первым в истории программистом. Однако понятие программы, хранящейся в памяти вычислительной машины, появилось значительно позже.

Несмотря на все усилия, предпринятые в 1930-е и 1940-е годы, а также написанные в этот период теоретические работы, в особенности те, что были посвящены лямбда-исчислению и машине Тьюринга, развитие алгоритмов началось лишь с появлением первых компьютеров: «Колосса», Mark I, ENIAC, EDSAC и UNIVAC. Языки программирования, с помощью которых стало возможным написание программ, хранящихся в оперативной памяти, позволили сэкономить время и уйти от взаимодействия с аппаратным обеспечением напрямую — именно так осуществлялось программирование первых компьютеров.

Программы для первых компьютеров писались в восьмеричном коде. Среди первых языков программирования, допускавших представление символов, были Short Order Code (1949) Джона Мокли и Sort-Merge Generator Бетти Холбертон. Short Order Code исполнялся на компьютере BINAC и был интерпретируемым языком.

Процедуры, соответствовавшие символам, хранились в памяти компьютера и вызывались системой. Эту же систему унаследовал UNIVAC. Программа, записанная на этом языке, исполнялась в 50 раз медленнее той же программы, записанной на машинном языке.

Sort-Merge Generator, в свою очередь, был приложением, разработанным для UNIVAC, которое осуществляло слияние и перемешивание карточек с входными и выходными операциями.

Бетти Холбертон (на этой фотографии она изображена за работой на ENIAC), создавшая один из первых языков программирования.

Эти первые системы, автоматического программирования (англ, automatic programming systems) всего лишь предоставляли понятные человеку коды операций и инструкции, записанные в символьном виде либо позволяли извлекать подпрограммы из библиотек и вставлять их в требуемый участок программного кода. Некоторые системы допускали интерпретацию операций для чисел с плавающей запятой и операций индексирования (indexing). Как бы то ни было, за исключением компилятора А-2 и алгебраической системы Лейнинга и Цирлера, до 1954 года даже наиболее мощные системы представляли собой всего лишь синтетические машины с кодом, отличающимся от машинного кода.

Эта модель обладала недостатками не только с технической, но и с экономической точки зрения. Оплата труда программистов вычислительного центра превышала стоимость самого компьютера, и этот разрыв неуклонно возрастал по мере того, как стоимость технологий и соответственно стоимость компьютеров снижалась. Кроме того, на программирование и отладку (debugging) тратилось от 25 до 50 % машинного времени. Системы автоматического программирования снижали быстродействие компьютера в 5—10 раз. Продавцы этих систем в худших традициях рынка стали завышать стоимость. Это привело к тому, что использование этих систем оказывалось невыгодным, и отношение к ним было скептическим.

В середине 1954 года в компании IBM под руководством Джона Бэкуса были начаты работы над языком Фортран (FORTRAN — FORmula TRANslation). Целью работ было решение всех вышеперечисленных проблем. При создании компилятора основное внимание уделялось генерации эффективного объектного кода, и эта задача была успешно решена. Качество объектного кода и преобразования, выполняемых для получения эффективных программ, удивили даже самих создателей языка FORTRAN.

Перфокарта с разметкой колонок для языка программирования Фортран.

С появлением языка Фортран появилась возможность записывать математические процедуры на четко определенном языке. Этот язык обеспечивал новый, более высокий уровень абстракции, поэтому программный код мог исполняться на разных компьютерах. Информация сохранялась в памяти и рассматривалась не как последовательность бит, а как целые или вещественные числа. В языке появились первые базовые конструкции императивных языков: условный оператор (IF <условие> <выражение_1_если_условие__истинно> <выражение_2_если_условие_ложно>) и оператор цикла (DO <инструкция> переменная = начальное значение, конечное значение, шаг).

За Фортраном последовали другие языки: Алгол-60 (одним из его создателей был голландский ученый Эдсгер Дейкстра), Кобол и LISP (предшественник функциональных языков программирования). Эти языки предназначались для решения определенных задач. В отличие от этих языков, язык PL/I был создан как язык общего назначения и содержал все нововведения, представленные в более ранних языках, что сделало его громоздким и сложным.

Компьютер Electrologica XI, работавший в период с 1958 по 1965 год, в котором использовался язык Алгол-60.

Авторы языков программирования ставили перед собой менее амбициозные задачи, но созданные ими языки оказались более эффективными. Среди них выделялись Simula 67 и Pascal. Вместо предопределенного полного множества абстракций эти языки обладали гибкими и удобными средствами определения новых произвольных абстракций. Pascal и Алгол-68 позволяли определять новые типы данных на основе предопределенных простых типов и служебных слов (array, record и других). Эти новые типы можно было рассматривать как абстракции, созданные на основе внутренних представлений, и им сопоставлялось множество операций. Эта модель была гибкой, но обладала существенным недостатком. Доступ к представлению предопределенных типов был закрыт, то есть с предопределенными объектами нельзя было работать напрямую (только с помощью операций), однако доступ к структуре пользовательских типов был открыт, и их значения можно было изменять. Причина заключалась в том, что в языке не было различий между двумя уровнями абстракции: уровнем, на котором программист использует тип данных, и уровнем реализации этого типа. Это осложняло чтение программ и исправление ошибок. Когда программы достигали определенных размеров, эта задача становилась невыполнимой.

Решением проблемы стало использование абстрактных типов данных и языков, в которых они поддерживались (Ada, Modula-2 и CLU). В них проводилось различие между этими уровнями абстракции и применялась так называемая инкапсуляция (ограничение доступа к определенным компонентам объектов). На уровне, на котором программист использовал тип, доступ к его внутренней структуре был закрыт. На уровне реализации определялся интерфейс объекта, его внутренняя структура и доступные операции.

Так как программисту были известны операции, доступные для определенных объектов, и их поведение (но не внутреннее представление!), он оперировал терминами абстракции. Любое изменение реализации, которое не приводило к изменению интерфейса, не влияло на модули, где использовался этот интерфейс, так как в них был доступен только сам интерфейс, а не его внутренняя реализация.

Благодаря этим механизмам абстракции программы, написанные на этих языках, стало возможным представлять в терминах объектов. В некоторых языках, например в языке Ада и Modula-2, использование объектов было необязательным, в других — обязательным. В языке CLU программист должен был группировать данные приложения в классы, которые назывались кластерами. Аналогичный принцип использовался в объектно-ориентированных языках, в которых вводилось понятие наследования, позволявшее определять объекты на основе предопределенных объектов.