Мальцев А.И. Алгоритмы и рекурсивные функции

20 Апр 2018

До начала XX столетия математика удовлетворялась интуитивным пред­став­ле­ни­ем алгоритма, ибо считалось, что любая корректно сфор­му­ли­ро­ван­ная математическая проблема должна иметь ре­ше­ние. Если это ре­ше­ние не найдено сейчас, то это только потому, что современное раз­ви­тие ма­те­матики не в состоянии справиться с этой задачей. Со вре­ме­нем ме­тод ре­ше­ния обя­зательно будет найден. А найденный метод все­г­да мож­но опи­сать так, чтобы он был понятен большинству.

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

Начиная с 1935 года, был предположен ряд уточнений понятия алгоритма следующими категориями:

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

К истории термина

Алгоритмам и их свойствам посвящено боль­шое число фундаментальных работ, среди которых основной можно счи­тать работу Д.Э. Кнута, в которой он пишет, что само слово «алгоритм» (al­gorithm) (устаревшее «алгорифм») представляет большой интерес. «На пер­вый взгляд может показаться, что кто-то собирался написать слово «лога­рифм», но случайно переставил первые четыре буквы. В словаре 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)».

Д.Э. Кнут [2] утверждает, что «современное значение слова «алго­ритм» во многом аналогично таким понятиям, как рецепт, процесс, метод, способ, процедура, программа. Но все-таки слово «algorithm» имеет допол­нительный смысловой оттенок. Алгоритм — это не просто последователь­ность выполнения операций для решения задачи определенного типа».

Т. Кормен [3] неформально определяет алгоритм, как «любую кор­ректно определенную вычислительную процедуру, на вход (input) кото­рой подается некая величина или набор величин, и результатом выпол­нения которой является выходная величина (output) или набор значений. Таким образом, алгоритм представляет собой последовательность вычис­лительных шагов, преобразующих входные величины в выходные.

Алгоритм также можно рассматривать как инструмент, предназна­ченный для решения корректно поставленной вычислительной задачи (computational problem). В постановке задачи в общих чертах задаются отношения между входом и выходом. В алгоритме описывается конк­ретная вычислительная процедура, с помощью которой удается добиться указанных отношений. Говорят, что алгоритм корректен (correct), если для каждого ввода результатом его работы является корректный выход. Мы говорим, что корректный алгоритм решает данную вычислительную за­дачу. Если алгоритм некорректный, то для некоторых вводов он может вообще не завершить свою работу или выдать ответ, отличный от ожи­даемого. Правда, некорректные алгоритмы иногда могут оказаться полез­ными, если в них есть возможность контролировать частоту возникнове­ния ошибок».

Следует заметить, что что проверка корректности алгоритма может быть весьма трудоемкой задачей. Например, как проверить корректность алгоритма на всем множестве действительных чисел или корректность факторизации произвольного числа N?

З.В. Алферова [4] под алгоритмом понимает «конечную совокупность точно сформулированных правил решения некоторого класса задач. Алго­ритмы, в соответствии с которыми решение поставленных задач сводится к арифметическим действиям, называются численными алгоритмами, а алгоритмы, в соответствии с которыми решение поставленной задачи сводится к логическим действиям, называются логическими алгоритма­ми». В [4] утверждается, что «алгоритмами в современной математике принято называть конструктивно задаваемые соответствия между сло­вами в абстрактных алфавитах, где абстрактным алфавитом называется любая конечная совокупность объектов, называемых буквами или симво­лами данного алфавита. При этом природа этих объектов совершенно не интересует. Символами абстрактных алфавитов можно считать, напри­мер, буквы алфавита какого-либо языка, цифры, любые значки, рисунки и даже слова конкретного языка. Важно лишь, чтобы рассматриваемый ал­фавит был конечным.

Можно назвать алфавит конечным множеством различных символов. Слово «абстрактный» для краткости будем опускать. Как любое множест­во алфавит задается перечислением его элементов, т.е. символов. Под словом или строкой алфавита понимают любую конечную упорядочен­ную последовательность символов. Наряду со словами положительной длины, состоящими не менее чем из одного символа, в некоторых случаях целесообразно рассматривать также пустые слова, не содержащие ни од­ного символа. Очевидно, что такое определение слова отличается от при­нятого в обычном или естественном языке. При изучении алгоритмов словами в указанном выше смысле следует считать любые сочетания и последовательности символов, в том числе и бессмысленные.

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

Различают однозначные и многозначные алфавитные операторы. Под однозначным алфавитным оператором понимается такой алфавитный опе­ратор, который каждому входному слову ставит в соответствие не более одного выходного слова. С математической точки зрения, однозначный алфавитный оператор является сюръективным отображением».

Следуя утверждениям З.В. Алферовой [4], укажем, что алфавитный оператор, не сопоставляющий некоторому входному слову никакого вы­ходного слова, не определен на этом слове. Такие операторы широко используются в функциональных языках программирования в операциях «сопоставления с образцом» (pattern matching) [5] и в частично определен­ных функциях (partial function) [5, 6].

Совокупность всех слов, на которых алфавитный оператор определен, называется его областью определения или доменом [6]. Совокупность всех слов, которые могут быть результатом выполнения алфавитного оператора, называется областью значений или кодоменом [6].

«С каждым алфавитным оператором связывается интуитивное пред­ставление о его сложности. Наиболее простыми являются алфавитные операторы, осуществляющие посимвольные отображения. Посимвольное отображение состоит в том, что каждый символ входного слова заменяется некоторым символом выходного алфавита. Большое значение имеют так называемые кодирующие отображения. Под кодирующим отображением понимается соответствие, сопоставляющее каждому символу входного алфавита некоторую конечную последовательность символов в выходном алфавите, называемую кодом. Кодирование позволяет сводить изучение произвольных алфавитных отображений к алфавитным отображениям в некотором стандартном алфавите. Наиболее часто в качестве такого стан­дартного алфавита выбирается так называемый двоичный алфавит, сос­тоящий из двух символов, которые обычно отождествляются с цифрами 0 и 1». Так объясняется природа кодирования в работе [4].

С понятием сопряженного алфавитного оператора, а также с природой взаимосвязи сопряженных алфавитных операторов можно более детально ознакомиться в работе [4]. Следует заметить, что предложенный З.В. Ал­феровой алфавитный оператор есть не что иное как уточненная абстрак­ция функтора, а сопряженный алфавитный оператор — уточненная абст­ракция сопряженного функтора в теории категорий [7, 8].

Согласно [4] алфавитные операторы, задаваемые с помощью конечной системы правил, принято называть алгоритмами. Отсюда легко понять, что «всякий алфавитный оператор, который можно фактически задать, является непременно алфавитом. Однако следует иметь в виду одно раз­личие, существующее между понятиями алфавитного оператора и алго­ритма. В понятии алфавитного оператора существенно лишь само соот­ветствие, устанавливаемое между входными и выходными словами, а не способ, которым это соответствие устанавливается. В понятии алгоритма, наоборот, основным является способ задания соответствия, устанавливае­мого алгоритмом». Таким образом, алгоритм — это алфавитный оператор вместе с правилами, определяющими его действия.

В работе [9] дано определение алгоритмов, как «некоторых инстру­ментов оперирования структурами данных, где структурой данных назы­вается способ организации данных в памяти компьютера (или на диске). Примерами структур данных являются массивы, связанные списки, стеки, двоичные деревья, хеш-таблицы и т.п. Очевидно, что такое определение малоинформативное».

Анатолий Иванович Маальцев — основоположник современной теории алгоритмов и рекурсивных функций
Анатолий Иванович Маальцев — основоположник современной теории алгоритмов и рекурсивных функций

А.И. Мальцев [1] констатирует интуитивность понятия алгоритма, которое «хотя и нестрогое, но настолько ясное, что практически не было серьезных случаев, когда математики разошлись бы во мнениях относи­тельно того, является ли алгоритмом тот или иной конкретно заданный процесс». Однако, «...положение существенно изменилось в XX веке, выд

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

В 20-х годах XX века задача точного определения понятия алгоритма стала одной из центральных математических проблем. Решение ее было получено в середине 30-х годов того же века в работах Гильберта, Геделя, Черча, Клини, Поста и Тьюринга в двух форматах. Первое решение было основано на понятии рекурсивной функции, второе — на описании точно очерченного класса процессов».

Согласно [1] «числовые функции, значения которых можно вычислять посредством некоторого (единого для данной функции) алгоритма, назы­ваются вычислимыми функциями. Именно определение А.И. Мальцева дает возможность построить параллель между функциями в функциональ­ных языках программирования и теоретическими аспектами алгоритмов в математике, ибо совокупность вычислимых функций для самых разных пониманий процессов, удовлетворяющая условиям, определенным Маль­цевым для алгоритма, оказалась легко описываемой в терминах математи­ки. Эта точно описанная совокупность числовых функций, совпадающая с совокупностью всех вычислимых функций при самом широком до сих пор известном понимании алгоритма, носит название совокупности рекур­сивных функций».

В работе [1] сказано: «Гильберт и Бернайс [10] рассматривали рекур­сивные определения, отталкиваясь от аксиом арифметики Пеано и выст­раивая свое видение рекурсивной арифметики. Опираясь на идеи Гильберта и Бернайса, Гедель [11] впервые описал класс всех рекурсивных функций как класс всех числовых функций, определимых в некоторой формальной системе. Исходя из других соображений, Черч [12] пришел к тому же классу числовых функций, что и Гедель. Анализ идей, приведших к этому классу функций, позволил Алонзо Черчу первым опубликовать гипотезу о том, что класс рекурсивных функций тождественен классу всюду опреде­ленных вычислимых функций. Эта гипотеза известна как тезис Черча. Так как понятие вычислимой функции точно не определено, то тезис Черча до­казать нельзя.

Учитывая, что не все процессы вычислений конечны, Стив Колл Кли­ни ввел понятие частично рекурсивной функции [13] и высказал гипотезу, что

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

В работе [1] не различаются гипотезы А. Черча и С. Клини. Гипотеза С. Клини, которая является более общей, чем гипотеза А. Черча, так же недоказуема, как и гипотеза А. Черча. «Тезис Черча оказался достаточ­ным, чтобы придать необходимую точность формулировкам алгоритмичес­ких проблем и в ряде случаев сделать возможным доказательство их нераз­решимости» [1]. А.И. Мальцев констатирует, что «точное описание класса частично рекурсивных функций вместе с тезисом Черча — Клини дает одно из возможных решений задачи об уточнении понятия алгоритма».

Э.Л. Пост [14] и А. Тьюринг [15] «независимо друг от друга и почти одновременно с работами Черча и Клини уточнили непосредственно само понятие алгоритма и уже потом, при его помощи точно определили класс вычислимых функций. Основная мысль Поста и Тьюринга заключалась в том, что алгоритмические процессы — это процессы, которые может со­вершать подходяще устроенная «машина». В соответствии с этой мыслью ими были описаны в точных математических терминах узкие классы машин, позволяющих осуществить или имитировать очень сложные алгоритмичес­кие процессы, которые когда-либо описывались математиками» [1].

Свойства алгоритма. Согласно [2] алгоритм обладает такими пятью свойствами: конечность, определенность, точка входа (ввод), точка вы­хода (вывод) и эффективность.

Конечность алгоритма означает, что алгоритм всегда должен закан­чиваться после выполнения конечного числа шагов. Число шагов алго­ритма может быть достаточно большим, но целесообразным. Согласно [4] свойство алгоритма, обеспечивающее получение результата через конеч­ное число шагов, называется результативностью алгоритма. Однако автор [2], дав определение свойства конечности алгоритма, не сказал ни слова о бесконечных алгоритмах. Под бесконечным алгоритмом будем понимать такой алгоритм, реализация которого в виде программы при запуске на компьютере может быть остановлена только посредством выключения (пе­резагрузки) компьютера.

Следует заметить, что «процедура, обладающая всеми характеристи­ками (свойствами) алгоритма, за исключением, возможно, конечности, называется методом вычислений. Метод вычисления, выраженный на язы­ке программирования, называется программой» [2].

Определенность [2] «требует, чтобы каждый шаг алгоритма был точ­но определен. Действия, которые нужно выполнить, должны быть строго и недвусмысленно определены для каждого возможного случая. При опи­сании

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

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

Например, необходимо отсортировать последовательность чисел в один поток или несколько потоков вычислений. Суть задачи от этого не меняется: необходимо отсортировать последовательность. Исходная пос­ледовательность — это определяющие алгоритм исходные данные, а пара­метр «в сколько потоков сортировать» — это контекстные исходные дан­ные. Поскольку алгоритм есть функция, контекстно-зависимые алгорит­мы порождают класс функций в функциональных языках программиро­вания, например Scala, называемый замыканием (closure) [5].

Каждый алгоритм имеет вывод, состоящий из одного или нескольких выходных данных (результатов работы алгоритма). Результаты работы алгоритма тесно связаны с входными данными.

Алгоритм обычно считается эффективным, если все его операторы достаточно просты для того, чтобы их можно было точно выполнить в течение конечного промежутка времени с помощью карандаша и бумаги. Понятие эффективности алгоритма связано с появлением научного нап­равления — анализ алгоритмов [1, 3]. Понятие эффективность алгоритма применимо только к алгоритмам чистых вычислений. Выполнение каж­дого из операторов алгоритма не означает, что с его помощью можно получить результат за приемлемое время для произвольной задачи из класса решаемых им. В первую очередь, это задачи из класса ХР-сложных или экспоненциальной сложности. Данное замечание требует отдельного исследования.

К свойствам алгоритма относят детерминированность, массовость, эквивалентность, область применимости [2,4]. З.В. Алферова определяет: «Два алфавитных оператора считаются равными, если они имеют одну и ту же область определения и сопоставляют любому наперед заданному входному слову из этой области одинаковые выходные слова» [4]. Д. Кнут утверждает, что «два алгоритма считаются равными, если равны соот­ветствующие им алфавитные операторы и совпадает система правил, за­дающих действие этих алгоритмов на выходные слова» [2].

Согласно З.В. Алферовой: «Эквивалентность алгоритмов определяет­ся через совпадение алфавитных операторов алгоритмов, но не совпадение способов их задания (системы правил). Обычно в теории алгоритмов рас­сматривают лишь такие алгоритмы, которым соответствуют однозначные алфавитные операторы. Всякий алгоритм такого рода любому входному слову относит только одно выходное слово. Такие алгоритмы и алфа­витные операторы называют детерминированными.

Массовость алгоритма — свойство алгоритма быть применимым для множества строк. Если алгоритм применим для множества строк, то он обладает свойством массовости.

Из свойства результативности (конечности) вытекает понятие области применимости алгоритма.

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

Теперь эквивалентность алгоритмов может быть определена следующим образом: два алгоритма эквивалентны, если совпадают их области примени­мости и результаты переработки любого слова из этой области.

Различают еще случайные и самоизменяющиеся алгоритмы. Алго­ритм называется случайным, если в системе правил, описывающих алго­ритм, предусматривается возможность случайного выбора тех или иных слов или тех или иных правил. Им соответствуют многозначные алфа­витные операторы». Субъективно понятие применимости требует уточне­ния, а понятие результативности вообще не определено.

«Алгоритм называется самоизменяющимся, если он не только перера­батывает входные слова, но и сам изменяется в процессе такой перера­ботки. Результат действия самоизменяющегося алгоритма на то или иное слово зависит не только от этого слова, но и от истории предыдущей работы алгоритма» [4].

Изучение теории функциональных языков [6, 12] и их практического применения приводит к необходимости формулирования понятия алго­ритма чистых вычислений или чистого алгоритма.

Чистый алгоритм — алгоритм решения конкретной задачи, в ко­тором не существует ни одного шага, который может быть удален без нарушения отображения исходных данных в выходные. Поясним опре­деление. Например, есть алгоритм, который вычисляет некоторое значе­ние в цикле и публикует промежуточные результаты. Шаги публикации промежуточных данных могут быть удалены из алгоритма без ущерба для конечного результата вычислений. Чистые алгоритмы в функциональных языках программирования (например, Scala) представляют в виде чистых функций (pure function) [5]. Шаги алгоритмов, которые могут быть удале­ны без ущерба для вычислений, принято называть сторонний эффект (side effect)[16].

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

Основные формализмы прикладной теории алгоритмов можно разде­лить на два направления, условно называемые «алгебраическим» и «гео­метрическим» [1]. Алгебраическая теория строится в конкретной симво­лике, при которой алгоритмы рассматриваются в виде линейных текстов. В геометрической теории алгоритмы строятся в виде множеств, между ко­торыми вводятся связи, носящие характер отображений или бинарных отношений. При этом значительное место занимает геометрическая ин­терпретация объектов в виде графов, вершины которых задают элементы множества, а ребра — отношения между ними.

Наиболее удобными при коллективной работе являются алгебраичес­кие представления. Поэтому теория категорий [8] играет важную роль. Композиция как основной механизм изучения категорий позволяет пред­ставлять чистые алгоритмы в виде математических категорий.

Алгоритм высшего порядка — это алгоритм, принимающий в качестве входного параметра другой алгоритм. Аналогами таких алгоритмов в функциональных языках программирования, например Scala, являются функции высших порядков (higher-ordered function, HOF)[15, 16]. Следует заметить, что алгоритмом первого порядка является алгоритм, не прини­мающий в качестве параметра другой алгоритм.

В работе [18] дано интуитивное определение алгоритма и сделан акцент на том, что алгоритмы следует всегда рассматривать в совокуп­ности со структурами данных. «Алгоритм можно определить, описав про­цедуру решения задачи на естественном языке или в виде компьютерной программы, которая реализует процедуру», «термин алгоритм применятся в вычислительной технике для описания конечного, детерминированного и эффективного метода решения задачи, который годится для реализации в виде компьютерной программы». Из этих интуитивных определений можно сделать вывод о том, что Р. Седжвик и К. Уэйн [18] выделяют сле­дующие свойства алгоритма: конечность, детерминированность, эффек­тивность и массовость.

Свою систему свойств алгоритмов формирует А.И.Мальцев [1]: «Ал­горитм — это процесс последовательного построения величин, идущий в дискретном времени таким образом, что в начальный момент задается исходная конечная система величин, а в каждый следующий момент сис­тема величин получается по определенному закону (программе) из систе­мы величин, имевшихся в предыдущий момент времени (дискретность алгоритма). При этом система величин, получаемых в какой-то (не на­чальный) момент времени, однозначно определяется системой величин, полученных в предыдущие моменты времени (детерминированность алго­ритма)».

Закон получения последующей системы величин из предшествующей должен быть простым и локальным, что определяет еще одно свойство алгоритма по Мальцеву — элементарность шагов алгоритма. Однако автор [1] не поясняет, что он подразумевает, говоря о «простом и локаль­ном», оставляя это на суд читателя.

Следующее утверждение характеризует направленность алгоритма: «Если способ получения последующей величины из какой-нибудь задан­ной величины не дает результата, то должно быть указанно, что надо счи­тать результатом алгоритма» [1].

Алгоритмы высших порядков. Авторы работы [18] придерживают­ся мнения, что «структуры данных существуют как побочные или ко­нечные продукты алгоритмов, и их изучение необходимо для понимания алгоритмов». Они также говорят о том, что следует выделить в отдельный класс алгоритмы первого порядка и алгоритмы высших порядков. Это вытекает из следующего: «Простые алгоритмы могут потребовать слож­ные структуры данных, и наоборот, сложные алгоритмы могут исполь­зовать простые структуры данных» [18]. Очень важно понимать, что если некоторый алгоритм требует всегда одну и ту же структуру данных, то та­кой алгоритм не является алгоритмом высшего порядка. В таком случае следует говорить о композиции алгоритмов или композиции морфизмов или функторов, если речь идет об алгоритмах вычислимых функций или чистых алгоритмах [8].­


Настольная книга каждого программиста, раскрывающего математическую суть алгоритмизации, написана и издана Анатолием Ивановичем Мальцевым в 1965 году. О том, что она сразу стала библиографической редкостью говорить не приходится. К счастью, монография была переиздана в 1986 г. Рекомендовано к прочтению тем, кто хочет честно посмотреть в глаза искусственному интеллекту компьютеров.


В математике существует большой раздел – рекурсивные (или рекуррентный) функции. Долгое время термин «рекурсия» употреблялся математиками, не будучи чётко определённым. Хотя рекурсивные функции – это вычислимые функции. По сути дела все вычислимые на компьютерах функции – это рекурсивные функции, но разные компьютерные архитектуры по-разному ведут вычислительные процессы. Чем лучше соответствует структура компьютера структуре задач, тем меньше затраты памяти и времени. Так что когда мы говорим о рекурсивных машинах, мы говорим о соответствии структур машины и решаемых задач, а так как задачи бывают разные, то структура машин должна гибко подстраиваться к структурам задач. Математика в настоящее время погружена в программирование, и в программировании рекурсивные операции распространены.

Torrent

Список литературы

1.    Мальцев А.И. Алгоритмы и рекурсивные функции. — М.: «Наука», 1986. — 367 с.

2.    Кнут Д.Э. Искусство программирования. Т. 1. Основные алгоритмы / Пер.с агл.: уч. пос., 3-е изд., под общей ред. докт. физ.-мат. наук, проф. Ю.В. Козаченко. — М.: Изд. дом «Вильямс», 2000. — 720 с.

3.    Кормен Т.Х., Лейзерсон Ч.И., Ривест Р.Л., Штайн К. Алгоритмы: построение и ана­лиз. 2-е изд. — М.: «Вильямс», 2005. — 1290 с.

4.    Алферова З.В. Теория алгоритмов. — М. : Статистика, 1973. — 164 с.

5.    Subramaniam V. Programming Scala. Tackle Multicore Complexity on Java Virtual Ma­chine. The Progmatic Programmers. — Pragmatic Bookshelf. — Raleigh, North Carolina, Dallas, Texas, 2008. — 218 p.

6.    Пирс Б. Типы в языках программирования / Пер. с англ. —М.: «Лямбда пресс» & «Добросвет», 2012. — 655 с.

7.    Foundational Theories of Classical and Constructive Mathematics. Ed. Giovanni Somma- ruga. — Springer: The Western Ontario Series in Philosophy of Science, 2011. — 316 p.

8.    Маклейн С. Категории для работающего математика.—М.: ФИЗМАТЛИТ, 2004.— 352 с.

9.    ЛафореР. Структуры данных и алгоритмы в Java //Классика Computer Science.— М. : Изд-во «Питер», 2013. — 704 с.

10.     Гильберт Д., Бернайс П.Основания математики. Логические исчиления и формали­зация арифметики. — М. : «Наука», 1982. — 550 с.

11.     Godel K. Uber formal unentscheidbare Siitze der Principia Mathematica und verwandter SystemeI//Monatsheftefurmathematikundphysik.— 1931. — Т. 38, № 1. — С. 173—198.

12.     Барендрегт АП.Ламбда-исчисление. Его синтаксис и семантика. — М. : Мир, 1985. —606 с.

13.     Kleene S.C. General recursive functions of natural numberse // Mathematische Annalen.— 1936. — 112. — P. 727—742.

14.                 Успенский В.А. Машина Поста. — М.: Наука, 1979. — C. 89—95.

15.     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. — Last access: August of 2015. — Mode of access: http://www.cs.virginia.edu/~robins/Tu- ring_Paper_ 1936.pdf.

16.                 ХорстманК. Scala для нетерпеливых /Пер. с англ.—M.: Изд-во «ДМК», 2013.— 407 с.

17.     Марков А.А. Теория алгорифмов // Тр. Математич. ин-та им. В.А. Стеклова. Т. 42. — М.: МАИК «Наука/Интерпериодика», 1954. — 376 с.

18.                 Седжвик Р., Уэйн К. Алгоритмы на Java, 4-е изд. — М.: «И.Д. Вильямс», 2013. — 848 с.

19.     РублевВ.С. Основы теории алгоримов.— Ярославль: Ярославский гос. ун-т им. П.Е. Де­мидова, 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 in­volved terms of high order algorithms and context-related algorithms.

Keywords: classification, properties, discreteness, determinism, probability, context dependency.

REFERENCES

1.    Maltsev, A. (1986), Algoritmy i rekursivnyie funktsii [Algorithms and recursive functions], Nauka, Moscow, Russia.

2.    Knut, D. (1968), Iskustvo programmirovaniya. Toml. Osnovnyie algoritmy [The Art of Computer Programming. Vol. 1. Fundamental Algorithms], Manual, Third Edition, trans­lated from English by Prof. Kozachenko, Yu.V., Williams, Moscow, Russia.

3.    Cormen, T.H., Leizerson, Ch.I., Rivest, R.L. and Shtain, K. (1990), Algoritmy:postroyeniye i analiz [Algorithms: structure and analysis], Williams, Moscow, Russia.

4.    Alferova, Z.V. (1973), Teoriya algoritmov [Algorithmtheory], Statistika, Moscow, Russia.

5.    Subramaniam, V. (2008), Programming Scala. Tackle multicore complexity on Java virtual machine. The pragmatic programmers, Pragmatic bookshelf, Raleigh, North Carolina, Dal­las, Texas, USA.

6.    Pirs, B. (2012), Tipy v yazykakh programmirovaniya [Types in programming languages], Lambda Press and Dobrosvet, Moscow, Russia.

7.    Foundational theories of classical and constructive mathematics (2011), Ed. by Giovanni Sommaruga, Springer: The Western Ontario Series in Philosophy of Science, Canada.

8.    Makleyn, S. (1998), Kategorii dlya rabotayushchego matematika [Categories for the work­ing mathematician], Translated from English, Fizmatlit, Moscow, Russia.

9.    Lafore, R. (2002), Struktury dannykh i algoritmy v Java [Data structures and algorithms in Java], Piter, Moscow, Russia.

10.     Gilbert, D. andBernays, P. (1982), Osnovaniya matematiki. Logicheskie ischileniya iforma- lizatsiya arifmetiki [Mathematics bases. Logical calculus and arithmetic formalization], Nauka, Moscow, Russia.

11.     G6del, K. (1931), Uber formal unentscheidbare Siitze der Principia Mathematica und ver­wandter Systeme I, Monatshefte fUr mathematik und physic, Vol. 38, no. 1, pp. 173-198.

12.     Barendregt, H.P. (1985), Lambda-ischislenie. Yego sintaksis i semantika [The Lambda cal­culus. Its syntax and semantics], Translated from English, Mir, Moscow, Russia.

13.     Kleene, S.C. (1936), General recursive functions of natural numbers, Mathematische Anna­len, Vol. 112, pp. 727-742.

14.                Uspenskiy, V. (1979), Mashina Posta [Post-Turing machine], Nauka, Moscow, Russia.

15.     Turing, A. (1936), On computable numbers, with an application to the Entscheidungs prob­lem, 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).

16.     Khorstman, С. (2012), Skala dlya neterpelivykh [Scala for the impatient], translated from English, DMK, Moscow, Russia.

17.     Markov, A. (1954), “Algorithm theory”, Trudyi matematich. in-ta im. V. A. Steklova, Vol. 42, MAIK «Nauka/Interperiodika», Moscow, Russia.

18.     Sedzhvik, R. andUeyn, K. (2011), Algoritmy naJava [Algorithms in Java], Williams, Mos­cow, Russia.

19.     Rublev, V. (2005), Osnovyi teorii algorimov [Fundamentals of algorithm theory], P.G. De­midov Yaroslavl State University, Yaroslavl, Russia.

Теги: