
До начала XX столетия математика удовлетворялась интуитивным представлением алгоритма, ибо считалось, что любая корректно сформулированная математическая проблема должна иметь решение. Если это решение не найдено сейчас, то это только потому, что современное развитие математики не в состоянии справиться с этой задачей. Со временем метод решения обязательно будет найден. А полученный метод всегда можно описать так, чтобы он был понятен большинству.
Положение существенно изменилось в начале XX века, когда жизнь поставила перед математиками такие задачи, существование решений которых вызывало у многих обоснованные сомнения. Доказать отсутствие правил, описывающих способ решения означенных задач, можно только детерминировав само понятие алгоритма — интуитивного представления о нем в данном контексте явно недостаточно. Полное математическое определение алгоритма стало на повестке дня математического сообщества одной из фундаментальных проблем к моменту зарождения простейших средств вычислительной техники, т.е. к началу 30-х годов XX ст.
Начиная с 1935 года, был предположен ряд уточнений понятия алгоритма следующими категориями:
- Определение функции (Алонсо Чёрч, Стивен Клини)
- Общерекурсивные функции (Курт Гёдель, Стивен Клини, Жак Эрбран)
- Рекурсивные функции (Курт Гёдель, Стивен Клини)
- Машина Тьюринга (Алан Тьюринг, Эмиль Пост)
- Марковские алгоритмы (Андрей Марков-ст.)
- Графические схемы (Роза Петер)
Впоследствии оказалось, что все эти уточнения в некотором смысле эквивалентны и каждое из них может быть взято в качестве математического определения понятия алгоритма. Однако в современной математике алгоритмические процессы воспринимаются либо как вычислимые (рекурсивные) функции, либо как машины Тьюринга, либо как алгоритмы, нормализованные по Маркову.
К истории термина «алгоритм»
Алгоритмам и их свойствам посвящено большое число фундаментальных работ, среди которых основной можно считать работу Дональда Эрвина Кнута (Donald Ervin Knuth), в которой он пишет, что само слово «алгоритм» или, как раньше говорили — «алгорифм», представляет большой интерес.

«На первый взгляд может показаться, что кто-то собирался написать слово «логарифм», но случайно поменял местами буквы. В словаре Webster’s New World Dictionary, вышедшем в 1957 г. этого слова еще не было. Там находим только устаревшую форму «algorism» — старинное слово, которое означает «выполнение арифметических действий в помощью арабских цифр», — писал Кнут.
В средние века абакисты считали на абаках (счетных досках), а алгоритмики использовали algorism. В эпоху возрождения это слово оказалось забытым. Одни лингвисты того времени пытались объяснить его значение сочетанием слов «algiros» (больной) и «arithmos» (число), другие не соглашались с таким толкованием и утверждали, что это слово происходит от «King Algor Of Castile».
Наконец, историками математики было установлено истинное происхождение слова «algorism»: оно происходит от имени автора знаменитого персидского учебника по математике Абу Абд Аллах Мухаммед ибн Муса аль-Хорезми, что означает буквально «Отец Абдулы, Муххамед, сын Муссы, уроженец Хорезма». Аль-Хорезми написал знаменитую «Книгу о восстановлении и противопоставлении», которая определила еще одно слово: «алгебра».
Постепенно форма и значение слова «algorism» исказились. Как объясняется в словаре Oxford English Dictionary, это слово «претерпело множество псевдоэтимологических искажений, включая последний вариант «algorithm», где произошла путаница с корнем слова греческого происхождения «arithmetic». Этот переход от «algorism» к «algorithm» кажется вполне закономерным ввиду того, что происхождение рассматриваемого слова было полностью забыто. В старинном немецком математическом словаре Vollständiges mathematisches Lexicon (Leipzig, 1747) дано следующее определение слова algorithmus: «Этот термин включает в себя понятие о четырех типах арифметических операций, а именно: о сложении, умножении, вычитании и делении». Латинское выражение algorithmus infinitesimalis в то время использовалось для определения «способов выполнения действий с бесконечно малыми величинами, открытыми Лейбницем (Leibniz)».
Дональд Кнут утверждает, что «современное значение слова «алгоритм» во многом аналогично таким понятиям, как рецепт, процесс, метод, способ, процедура, программа. Но все-таки слово «algorithm» имеет дополнительный смысловой оттенок. Алгоритм — это не просто последовательность выполнения операций для решения задачи определенного типа».
Алгоритмы и рекурсивные функции
Существенный вклад в теорию алгоритмов уже в наше время внес советский математик Анатолий Иванович Мальцев. Его книга «Алгоритмы и рекурсивные функции» (1965) стала настольной для прикладных математиков, раскрывая природу и сущность алгоритмизации. О том, что она сразу стала библиографической редкостью говорить не приходится. К счастью, монография была переиздана в 1986 г. Ее стоит прочесть тем, кто хочет честно посмотреть в глаза искусственному интеллекту компьютеров.

А.И. Мальцев констатирует интуитивность понятия алгоритма, которое «хотя и нестрогое, но настолько ясное, что практически не было серьезных случаев, когда математики разошлись бы во мнениях относительно того, является ли алгоритмом тот или иной конкретно заданный процесс». Однако, положение изменилось в XX веке, выдвинувшем на первый план такие алгоритмические проблемы, существование положительного решения которых было сомнительным. Действительно, одно дело — доказать существование алгоритма, другое — доказать отсутствие алгоритма. Первое можно сделать путем фактического описания процесса, решающего задачу; в этом случае достаточно и интуитивного понятия алгоритма, чтобы удостовериться в том, что описанный процесс и есть алгоритм. Доказать несуществование алгоритма таким путем невозможно. Для этого нужно точно знать, что такое алгоритм. В 20-х годах XX века задача точного определения понятия алгоритма стала одной из центральных математических проблем. Решение ее было получено в середине 30-х годов того же века в работах Гильберта, Геделя, Черча, Клини, Поста и Тьюринга в двух форматах. Первое решение было основано на понятии рекурсивной функции, второе — на описании точно очерченного класса процессов.
Согласно Мальцеву числовые функции, значения которых можно вычислять посредством некоторого (единого для данной функции) алгоритма, называются вычислимыми функциями. Именно определение А.И. Мальцева дает возможность построить параллель между функциями в функциональных языках программирования и теоретическими аспектами алгоритмов в математике, ибо совокупность вычислимых функций для самых разных пониманий процессов, удовлетворяющая условиям, определенным Мальцевым для алгоритма, оказалась легко описываемой в терминах математики. Эта точно описанная совокупность числовых функций, совпадающая с совокупностью всех вычислимых функций при самом широком до сих пор известном понимании алгоритма, носит название совокупности рекурсивных функций.
Torrent
- Мальцев А.И. // Алгоритмы и рекурсивные функции, 1-е изд. — Москва: «Наука», 1965 — 394 с.
- Мальцев А.И. // Алгоритмы и рекурсивные функции, 2-е изд. — Москва: «Наука», 1986 — 368 с.
Список литературы
- Мальцев А.И. Алгоритмы и рекурсивные функции. — М.: «Наука», 1986. — 367 с.
- Кнут Д.Э. Искусство программирования. Т. 1. Основные алгоритмы / Пер.с агл.: уч. пос., 3-е изд., под общей ред. докт. физ.-мат. наук, проф. Ю.В. Козаченко. — М.: Изд. дом «Вильямс», 2000. — 720 с.
- Кормен Т.Х., Лейзерсон Ч.И., Ривест Р.Л., Штайн К. Алгоритмы: построение и анализ. 2-е изд. — М.: «Вильямс», 2005. — 1290 с.
- Алферова З.В. Теория алгоритмов. — М. : Статистика, 1973. — 164 с.
- Subramaniam V. Programming Scala. Tackle Multicore Complexity on Java Virtual Machine. The Progmatic Programmers. — Pragmatic Bookshelf. — Raleigh, North Carolina, Dallas, Texas, 2008. — 218 p.
- Пирс Б. Типы в языках программирования / Пер. с англ. —М.: «Лямбда пресс» & «Добросвет», 2012. — 655 с.
- Foundational Theories of Classical and Constructive Mathematics. Ed. Giovanni Somma- ruga. — Springer: The Western Ontario Series in Philosophy of Science, 2011. — 316 p.
- Маклейн С. Категории для работающего математика.—М.: ФИЗМАТЛИТ, 2004.— 352 с.
- Лафоре Р. Структуры данных и алгоритмы в Java //Классика Computer Science.— М. : Изд-во «Питер», 2013. — 704 с.
- Гильберт Д., Бернайс П.Основания математики. Логические исчиления и формализация арифметики. — М. : «Наука», 1982. — 550 с.
- Godel K. Uber formal unentscheidbare Siitze der Principia Mathematica und verwandter SystemeI//Monatsheftefurmathematikundphysik.— 1931. — Т. 38, № 1. — С. 173—198.
- Барендрегт АП.Ламбда-исчисление. Его синтаксис и семантика. — М. : Мир, 1985. —606 с.
- Kleene S.C. General recursive functions of natural numberse // Mathematische Annalen.— 1936. — 112. — P. 727—742.
- Успенский В.А. Машина Поста. — М.: Наука, 1979. — C. 89—95.
- Turing A. On computable numbers, with an application to the Entscheidungs problem // Proc. of the London Mathematical Society. Series 2. — 1936-7. — 42. — P. 230—265.
- Хорстман К. Scala для нетерпеливых /Пер. с англ.—M.: Изд-во «ДМК», 2013.— 407 с.
- Марков А.А. Теория алгорифмов // Тр. Математич. ин-та им. В.А. Стеклова. Т. 42. — М.: МАИК «Наука/Интерпериодика», 1954. — 376 с.
- Седжвик Р., Уэйн К. Алгоритмы на Java, 4-е изд. — М.: «И.Д. Вильямс», 2013. — 848 с.
- Рублев В.С. Основы теории алгоримов.— Ярославль: Ярославский гос. ун-т им. П.Е. Демидова, 2005. — 143 с.
- Н.А. Kravtsov, I.A. Prytulyuk A NEW ALGORITHM CLASSIFICATION The author’s classification of algorithms based on the review of famous fundamental and modern works is presented. The author’s classification is different from already known ones due to the involved terms of high order algorithms and context-related algorithms.
Другие источники
- Maltsev, A. (1986), Algoritmy i rekursivnyie funktsii [Algorithms and recursive functions], Nauka, Moscow, Russia.
- Knut, D. (1968), Iskustvo programmirovaniya. Toml. Osnovnyie algoritmy [The Art of Computer Programming. Vol. 1. Fundamental Algorithms], Manual, Third Edition, translated from English by Prof. Kozachenko, Yu.V., Williams, Moscow, Russia.
- Cormen, T.H., Leizerson, Ch.I., Rivest, R.L. and Shtain, K. (1990), Algoritmy:postroyeniye i analiz [Algorithms: structure and analysis], Williams, Moscow, Russia.
- Alferova, Z.V. (1973), Teoriya algoritmov [Algorithmtheory], Statistika, Moscow, Russia.
- Subramaniam, V. (2008), Programming Scala. Tackle multicore complexity on Java virtual machine. The pragmatic programmers, Pragmatic bookshelf, Raleigh, North Carolina, Dallas, Texas, USA.
- Pirs, B. (2012), Tipy v yazykakh programmirovaniya [Types in programming languages], Lambda Press and Dobrosvet, Moscow, Russia.
- Foundational theories of classical and constructive mathematics (2011), Ed. by Giovanni Sommaruga, Springer: The Western Ontario Series in Philosophy of Science, Canada.
- Makleyn, S. (1998), Kategorii dlya rabotayushchego matematika [Categories for the working mathematician], Translated from English, Fizmatlit, Moscow, Russia.
- Lafore, R. (2002), Struktury dannykh i algoritmy v Java [Data structures and algorithms in Java], Piter, Moscow, Russia.
- Gilbert, D. andBernays, P. (1982), Osnovaniya matematiki. Logicheskie ischileniya iforma- lizatsiya arifmetiki [Mathematics bases. Logical calculus and arithmetic formalization], Nauka, Moscow, Russia.
- Gödel, K. (1931), Uber formal unentscheidbare Siitze der Principia Mathematica und verwandter Systeme I, Monatshefte fUr mathematik und physic, Vol. 38, no. 1, pp. 173-198.
- Barendregt, H.P. (1985), Lambda-ischislenie. Yego sintaksis i semantika [The Lambda calculus. Its syntax and semantics], Translated from English, Mir, Moscow, Russia.
- Kleene, S.C. (1936), General recursive functions of natural numbers, Mathematische Annalen, Vol. 112, pp. 727-742.
- Uspenskiy, V. (1979), Mashina Posta [Post-Turing machine], Nauka, Moscow, Russia.
- Turing, A. (1936), On computable numbers, with an application to the Entscheidungs problem, Proc. of the London Mathematical Society, Series 2, Vol. 42, pp. 230-265, available at: http://www.cs.virginia.edu/~robins/Turing_Paper_1936.pdf ( accessed August 2015).
- Khorstman, С. (2012), Skala dlya neterpelivykh [Scala for the impatient], translated from English, DMK, Moscow, Russia.
- Markov, A. (1954), “Algorithm theory”, Trudyi matematich. in-ta im. V. A. Steklova, Vol. 42, MAIK «Nauka/Interperiodika», Moscow, Russia.
- Sedzhvik, R. andUeyn, K. (2011), Algoritmy naJava [Algorithms in Java], Williams, Moscow, Russia.
- Rublev, V. (2005), Osnovyi teorii algorimov [Fundamentals of algorithm theory], P.G. Demidov Yaroslavl State University, Yaroslavl, Russia.
- The Yoda of Silicon Valley // The New York Times