В Оксфордском словаре указано, что Algorithm – это ошибочное от algorism, который считается синонимом алгебры и арифметики и восходит к IX в. Позднее этим символом обозначались в трудах Евклида правила нахождения общего делителя двух чисел – алгоритм Евклида.
История появления понятия “алгоритм” связана с именем выдающегося узбекского ученого Мухаммеда бен Муса ал-Хорезми (жил в IX в.). Он написал “Арифметический трактат”, по которому европейцы впервые познакомились с десятичной позиционной системой счисления, пришедшей к арабам из Индии. После этого четыре арифметических действия долго называли ал-Хорезми (по латыни Algorithmi). В литературе встречалось “алгоритмус”, “алгорифм”, а в современном варианте произносится как “алгоритм”. Этот термин расширил свое первоначальное значение.
В 1857 в библиотеке Кембриджского университета был найден перевод одной из книг на латинский язык. В ней описаны четыре правила арифметических действий, практически те же, что используются и сейчас. Первые строки этой книги были переведены так: «Сказал Алгоритми. Воздадим должную хвалу Богу, нашему вождю и защитнику». Так имя Аль-Хорезми перешло в Алгоритми, откуда и появилось слово алгоритм. Термин алгоритм употреблялся для обозначения четырех арифметических операций, именно в таком значении он и вошел в некоторые европейские языки.
С 1747 г. вместо слова алгоризм стали употреблять алгорисмус, смысл которого состоял в комбинировании четырёх операций арифметического исчисления - сложения, вычитания, умножения и деления
К 1950 г. алгорисмус стал алгорифмом. Смысл алгорифма чаще всего связывался с алгорифмами Евклида – процессами нахождения наибольшего общего делителя двух многочленнов, наибольшей общей меры двух отрезков и т.п.
На протяжении многих веков понятие алгоритма связывалось с числами и относительно простыми действиями над ними, да и сама математика была, по большей части, наукой о вычислениях, наукой прикладной. Чаще всего алгоритмы представлялись в виде математических формул. Порядок элементарных шагов алгоритма задавался расстановкой скобок, а сами шаги заключались в выполнении арифметических операций и операций отношения (проверки равенства, неравенства и т.д.).
Вплоть до 30 годов понятие алгоритма имело скорее методологическое, чем математическое значение. Под алгоритмом понимали конечную совокупность точно сформулированных правил, которые позволяют решить те или иные классы задач.
Положение существенно изменилось, когда на первый план выдвинулись такие алгоритмические проблемы, решение которых было сомнительным. Действительно, одно дело доказать существование алгоритма, другое — доказать отсутствие алгоритма. Первое можно сделать путем фактического описания процесса, решающего задачу. В этом случае достаточно и интуитивного понятия алгоритма, чтобы удостовериться в том, что описанный процесс есть алгоритм. Доказать несуществование алгоритма таким путем невозможно. Для этого надо точно знать, что такое алгоритм.
В двадцатых годах нашего века задача определения понятия алгоритма стала одной из центральных математических проблем. Решение ее было получено в середине 30-х годов в работах известных математиков Гильберта, Гёделя, Черча, Клини, Поста и Тьюринга в двух формах. Первое решение было основано на понятии особого класса арифметических функций, получивших название рекурсивных функций, второе — на описании точно очерченного класса процессов. Впоследствии в работах Маркова, Калужнина появилось другое толкование теории алгоритмов, поставившее в основу определение алгоритма как особого соответствия между словами в том или ином абстрактном алфавите.
Алгоритм – это точно определенная инструкция, последовательно применяя которую к исходным данным, можно получить решение задачи. Для каждого алгоритма есть некоторое множество объектов, допустимых в качестве исходных данных. Например, в алгоритме деления вещественных чисел делимое может быть любым, а делитель не может быть равен нулю.
К алгоритму предъявляется ряд требований: Определенность, т.е. он должен быть точен, общепонятен, исключать возможность произвольного толкования. Массовость, т.е. чтобы его можно было применить к однотипным задачам. Результативность, т.е. через определенное число шагов алгоритм должен закончиться. Дискретность, т.е. возможность деления задачи на шаги, элементарные операции. Понятность, т.е. ориентация на те команды, которые знает исполнитель. Эффективность. Правильность.
Алгоритм фиксируется разными способами: На естественном языке С помощью специальных схем, графически. На алгоритмическом языке.
Среди математиков популярна притча, ярко иллюстрирующая алгоритмический способ мышления. Вопрос. Имеется плита, спички, водопровод, чайник. Как получить чай? Ответ: 1) из водопровода налить в чайник воду; 2) спичкой зажечь газ; 3) поставить чайник на газ; 4) ждать несколько минут. Вопрос. А если в чайнике уже есть вода и газ уже горит? Ответ. Выключить газ, вылить воду, и мы сведем задачу к предыдущей, решение которой уже есть. Притча имеет, при всей своей нелепости, следующий смысл: выявление закономерностей при решении задачи; сведение задачи к другой, решение которой известно. Возможно, способ будет не самым коротким, но задача будет решена.
