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

* * *

ТЕРМИН «РЕАЛИЗАЦИЯ»

Реализация — это осуществление или воплощение чего-либо. В информатике этот термин означает запись определенного алгоритма на заданном языке программирования.

ТЕРМИН «ПРОГРАММИРОВАНИЕ»

Слово «программировать» (англ, to program ), означающее задание инструкций, которые должен выполнить компьютер, было придумано группой исследователей, работавших над созданием компьютера ENIAC в Институте Мура Пенсильванского университета. В то время использовалось слово «настраивать» ( to set up ), так как программирование ENIAC (изображен на иллюстрации ниже) осуществлялось с помощью соединений и переключателей, то есть путем изменения электрической схемы самого компьютера. Постепенно, по мере того как разделение между аппаратным и программным обеспечением становилось все более явным, стало применяться слово «программирование».

* * *

Древнейшие алгоритмы, которые позволили вавилонянам провозгласить себя первыми математиками, способными решать достаточно сложные задачи, использовались для решения алгебраических уравнений, записывались в общем виде и демонстрировались на конкретных примерах. В них не использовались итерации или условные конструкции вида « если x< 0, то », так как вавилонянам не был известен нуль. Чтобы выразить несколько возможных вариантов, математики Вавилонии повторяли алгоритм необходимое число раз. Прошло много веков, прежде чем Евклид примерно в 300 году до н. э. описал алгоритм вычисления наибольшего общего делителя двух чисел. Этот алгоритм, который сегодня известен как алгоритм Евклида, как правило, реализуется с помощью рекурсии.

* * *

РЕАЛИЗАЦИЯ АЛГОРИТМА ЕВКЛИДА

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

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

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. Языки программирования, с помощью которых стало возможным написание программ, хранящихся в оперативной памяти, позволили сэкономить время и уйти от взаимодействия с аппаратным обеспечением напрямую — именно так осуществлялось программирование первых компьютеров.