Просмотр кода страницы Алгоритм

{{другие значения|Алгоритм (значения)}}
'''Алгори́тм''' ({{lang-lat|algorithmi}} — от имени среднеазиатского математика [[Аль-Хорезми]]<ref>{{БРЭ|ссылка=https://old.bigenc.ru/mathematics/text/1810305|автор=А. Л. Семёнов|статья=АЛГОРИ́ТМ|том=1|страницы=426|архив=https://web.archive.org/web/20181030090543/https://bigenc.ru/mathematics/text/1810305|архив дата=2018-10-30}}</ref>) — совокупность точно заданных правил решения некоторого класса задач или набор [[Оператор (программирование)|инструкций]], описывающих порядок действий исполнителя для решения определённой задачи. В старой трактовке вместо слова «порядок» использовалось слово «последовательность», но по мере развития [[Параллельный алгоритм|параллельности в работе компьютеров]] слово «последовательность» стали заменять более общим словом «порядок». Независимые инструкции могут выполняться в произвольном порядке, параллельно, если это позволяют используемые исполнители.

Ранее в русском языке писали «алгори'''ф'''м», сейчас такое написание используется редко, но тем не менее имеет место исключение ([[нормальный алгорифм]] [[Марков, Андрей Андреевич (младший)|Маркова]]).

Часто в качестве исполнителя выступает компьютер, но понятие алгоритма необязательно относится к [[Компьютерная программа|компьютерным программам]] — так, например, чётко описанный рецепт приготовления блюда также является алгоритмом, в таком случае исполнителем является человек (а может быть и некоторый механизм, например, ткацкий или токарный станок с [[числовое управление|числовым управлением]]).

Можно выделить алгоритмы ''вычислительные'' (далее речь в основном идёт о них) и ''управляющие''. Вычислительные алгоритмы, по сути, преобразуют некоторые начальные данные в выходные, реализуя вычисление некоторой функции. [[Семантика (программирование)|Семантика]] управляющих алгоритмов существенным образом может отличаться и сводиться к выдаче необходимых управляющих воздействий либо в заданные моменты времени, либо в качестве реакции на внешние события (в этом случае, в отличие от вычислительного алгоритма, управляющий может оставаться корректным при бесконечном выполнении).

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

Частичная формализация понятия алгоритма началась с попыток решения [[Проблема разрешения|проблемы разрешения]] ({{lang-de|Entscheidungsproblem}}), которую сформулировал [[Давид Гильберт]] в [[1928 год]]у. Следующие этапы формализации были необходимы для определения эффективных вычислений<ref>Kleene 1943 in Davis 1965: 274</ref> или «эффективного метода»<ref>Rosser 1939 in Davis 1965: 225</ref>; среди таких формализаций — рекурсивные функции [[Гёдель, Курт|Геделя]] — [[Эрбран, Жак|Эрбрана]] — Клини [[1930]], [[1934]] и [[1935]] гг., [[Лямбда-исчисление|λ-исчисление]] [[Алонзо Чёрч]]а [[1936]] г., «[[Машина Поста|Формулировка 1]]» [[Эмиль Пост|Эмиля Поста]] [[1936 год]]а и [[машина Тьюринга]].

== История термина ==
[[Файл:Image-Al-Kitāb al-muḫtaṣar fī ḥisāb al-ğabr wa-l-muqābala.jpg|thumb|220px|Титульная страница «[[Китаб аль-джебр ва-ль-мукабала|Алгебры]]» [[аль-Хорезми]]]]
[[Файл:1983 CPA 5426 (1).png|thumb|220px|[[Аль-Хорезми]] на советской марке]]
Современное формальное определение вычислительного алгоритма было дано в 30—50-е годы [[XX век]]а в работах [[Тьюринг, Алан Матисон|Тьюринга]], [[Пост, Эмиль Леон|Поста]], [[Чёрч, Алонзо|Чёрча]] ([[тезис Чёрча — Тьюринга]]), [[Винер, Норберт|Н. Винера]], [[Марков, Андрей Андреевич (младший)|А. А. Маркова]].

Само слово «алгоритм» происходит от имени персидского ([[хорезм]]ского и [[мавераннахр]]ского) учёного [[аль-Хорезми]]. Около 825 года он написал сочинение ''[[Китаб аль-джебр валь-мукабала]]'' («Книга о сложении и вычитании»), из оригинального названия которого происходит слово «[[алгебра]]» (аль-джебр — восполнение). В этой книге впервые дал описание придуманной в Индии позиционной десятичной системы счисления. Персидский оригинал книги не сохранился. Аль-Хорезми сформулировал правила вычислений в новой системе и, вероятно, впервые использовал [[0 (цифра)|цифру 0]] для обозначения пропущенной позиции в записи числа (её индийское название арабы перевели как ''as-sifr'' или просто ''sifr'', отсюда такие слова, как «цифра» и «шифр»). Приблизительно в это же время индийские цифры начали применять и другие арабские учёные.

В первой половине XII века книга аль-Хорезми в латинском переводе проникла в Европу. Переводчик, имя которого до нас не дошло, дал ей название ''Algoritmi de numero Indorum'' («Алгоритмы о счёте индийском») — таким образом, латинизированное имя среднеазиатского учёного было вынесено в заглавие книги. Сегодня считается, что слово «алгоритм» попало в европейские языки именно благодаря этому переводу. В течение нескольких следующих столетий появилось множество других трудов, посвящённых всё тому же вопросу — обучению искусству счёта с помощью цифр, и все они имели в названии слово ''algoritmi'' или ''algorismi''.

Про аль-Хорезми позднейшие авторы ничего не знали, но поскольку первый перевод книги начинается словами: «Dixit algorizmi: …» («Аль-Хорезми говорил: …»), всё ещё связывали это слово с именем конкретного человека. Очень распространённой была версия о греческом происхождении книги. В англо-норманнской рукописи XIII века, написанной в стихах, читаем:

<blockquote>Алгоризм был придуман в [[Греция|Греции]].
Это часть [[арифметика|арифметики]].
Придуман он был мастером по имени Алгоризм,
который дал ему своё имя.
И поскольку его звали Алгоризм,

Он назвал свою книгу «Алгоризм».</blockquote>

Около 1250 года английский астроном и математик [[Иоанн Сакробоско]] написал труд по арифметике ''Algorismus vulgaris'', на столетия ставший основным учебником по вычислениям в [[десятичная система счисления|десятичной позиционной системе счисления]] во многих европейских университетах. Во введении Сакробоско назвал автором науки о счёте мудреца по имени Алгус (''Algus''). А в популярной средневековой поэме «[[Роман о Розе]]» (1275—1280) [[Жан де Мен|Жана де Мена]] «греческий философ Алгус» ставится в один ряд с [[Платон]]ом, [[Аристотель|Аристотелем]], [[Евклид]]ом и [[Птолемей|Птолемеем]]! Встречался также вариант написания имени Аргус (''Argus''). И хотя, согласно древнегреческой мифологии, корабль «[[Арго (корабль)|Арго]]» был построен [[Ясон]]ом, именно этому Арго приписывалось строительство корабля.

«Мастер Алгус» (или Аргус) стал в средневековой литературе олицетворением счётного искусства. И в уже упоминавшемся «Романе о розе», и в известной итальянской поэме «Цветок», написанной [[Данте Алигьери|Дуранте]], имеются фрагменты, в которых говорится, что даже «mestre Argus» не сумеет подсчитать, сколько раз ссорятся и мирятся влюблённые. Английский поэт [[Джефри Чосер]] в поэме «[[Чосер, Джеффри#«Французский период»|Книга герцогини]]» ([[1369]] г.) пишет, что даже «славный счётчик Аргус» (noble countour Argu) не сможет счесть чудовищ, явившихся в кошмарных видениях герою.

Однако со временем такие объяснения всё менее занимали математиков, и слово ''algorism'' (или ''algorismus''), неизменно присутствовавшее в названиях математических сочинений, обрело значение способа выполнения арифметических действий посредством арабских цифр, то есть на бумаге, без использования [[Абак (математика)|абака]]. Именно в таком значении оно вошло во многие [[европейские языки]]. Например, с пометкой «устар.» оно присутствует в представительном словаре английского языка ''Webster’s New World Dictionary'', изданном в 1957 году [[Энциклопедический словарь Брокгауза и Ефрона]] предлагает такую трактовку: ''алгорифм'' (до революции использовалось написание ''алгориѳмъ'', через [[фита|фиту]]) производится «от арабского слова „аль-горетм“, то есть корень».

Алгоритм — это искусство счёта с помощью цифр, но поначалу слово «цифра» относилось только к нулю. Знаменитый французский [[труверы|трувер]] [[Куанси, Готье де|Готье де Куанси]] (Gautier de Coincy, 1177—1236) в одном из стихотворений использовал слова ''algorismus-cipher'' (которые означали цифру 0) как метафору для характеристики абсолютно никчёмного человека. Очевидно, понимание такого образа требовало соответствующей подготовки слушателей, а это означает, что новая система счисления уже была им достаточно хорошо известна.

Многие века абак был фактически единственным средством для практичных вычислений, им пользовались и купцы, и менялы, и учёные. Достоинства вычислений на счётной доске разъяснял в своих сочинениях такой выдающийся мыслитель, как [[Сильвестр II (папа римский)|Герберт Аврилакский]] (938—1003), ставший в 999 году [[папа римский|папой римским]] под именем Сильвестра II. Новое с огромным трудом пробивало себе дорогу, и в историю математики вошло упорное противостояние лагерей алгорисмиков и [[абацист]]ов (иногда называемых гербекистами), которые пропагандировали использование для вычислений абака вместо арабских цифр. Интересно, что известный французский математик [[Шюке, Николя|Николя Шюке]] (Nicolas Chuquet, 1445—1488) в реестр налогоплательщиков города [[Лион]]а был вписан как алгорисмик (algoriste). Но прошло не одно столетие, прежде чем новый способ счёта окончательно утвердился, столько времени потребовалось, чтобы выработать общепризнанные обозначения, усовершенствовать и приспособить к записи на бумаге методы вычислений. В Западной Европе учителей арифметики вплоть до XVII века продолжали называть «магистрами абака», как, например, математика [[Тарталья, Никколо|Никколо Тарталью]] (1500—1557).

Итак, сочинения по искусству счёта назывались ''Алгоритмами''. Из многих сотен можно выделить и такие необычные, как написанный в стихах трактат ''Carmen de Algorismo'' (латинское ''carmen'' и означает стихи) Александра де Вилла Деи (Alexander de Villa Dei, ум. 1240) или учебник венского астронома и математика [[Пурбах, Георг|Георга Пурбаха]] (Georg Peurbach, 1423—1461) ''Opus algorismi jocundissimi'' («Веселейшее сочинение по алгоритму»).

Постепенно значение слова расширялось. Учёные начинали применять его не только к сугубо вычислительным, но и к другим математическим процедурам. Например, около 1360 г. французский философ [[Орем, Николай|Николай Орем]] (Nicolaus Oresme, 1323/25-1382) написал математический трактат ''Algorismus proportionum'' («Вычисление пропорций»), в котором впервые использовал степени с дробными показателями и фактически вплотную подошёл к идее логарифмов. Когда же на смену абаку пришёл так называемый счёт на линиях, многочисленные руководства по нему стали называть ''Algorithmus linealis'', то есть ''правила счёта на линиях''.

Можно обратить внимание на то, что первоначальная форма ''algorismi'' спустя какое-то время потеряла последнюю букву, и слово приобрело более удобное для европейского произношения вид ''algorism''. Позднее и оно, в свою очередь, подверглось искажению, скорее всего, связанному со словом ''arithmetic''.

В 1684 году [[Лейбниц, Готфрид Вильгельм|Готфрид Лейбниц]] в сочинении ''Nova Methodvs pro maximis et minimis, itemque tangentibus…'' впервые использовал слово «алгоритм» (''Algorithmo'') в ещё более широком смысле: как систематический способ решения проблем дифференциального исчисления.

В XVIII веке в одном из германских математических словарей, ''Vollstandiges mathematisches Lexicon'' (изданном в [[Лейпциг]]е в 1747 году), термин ''algorithmus'' всё ещё объясняется как понятие о четырёх арифметических операциях. Но такое значение не было единственным, ведь терминология математической науки в те времена ещё только формировалась. В частности, выражение ''algorithmus infinitesimalis'' применялось к способам выполнения действий с бесконечно малыми величинами. Пользовался словом алгоритм и [[Леонард Эйлер]], одна из работ которого так и называется — «Использование нового алгоритма для решения проблемы Пелля» (''De usu novi algorithmi in problemate Pelliano solvendo''). Мы видим, что понимание Эйлером алгоритма как синонима способа решения задачи уже очень близко к современному.

Однако потребовалось ещё почти два столетия, чтобы все старинные значения слова вышли из употребления. Этот процесс можно проследить на примере проникновения слова «алгоритм» в русский язык.

Историки датируют 1691 годом один из списков древнерусского учебника арифметики, известного как «Счётная мудрость». Это сочинение известно во многих вариантах (самые ранние из них почти на сто лет старше) и восходит к ещё более древним рукописям XVI века. По ним можно проследить, как знание арабских цифр и правил действий с ними постепенно распространялось на Руси. Полное название этого учебника — «Сия книга, глаголемая по-еллински и по-гречески арифметика, а по-немецки алгоризма, а по-русски цифирная счётная мудрость».

Таким образом, слово «алгоритм» понималось первыми русскими математиками так же, как и в Западной Европе. Однако его не было ни в знаменитом [[Толковый словарь живого великорусского языка|словаре Даля]], ни спустя сто лет в «[[Словарь Ушакова|Толковом словаре русского языка]]» под редакцией Ушакова (1935). Зато слово «алгорифм» можно найти и в популярном дореволюционном [[Энциклопедический словарь Гранат|Энциклопедическом словаре братьев Гранат]], и в первом издании [[Большая советская энциклопедия|Большой советской энциклопедии]] (БСЭ), изданном в 1926 году. И там, и там оно трактуется одинаково: как правило, по которому выполняется то или иное из четырёх арифметических действий в десятичной системе счисления. Однако к началу XX века для математиков слово «алгоритм» уже означало любой арифметический или алгебраический процесс, выполняемый по строго определённым правилам, и это объяснение также даётся в следующих изданиях БСЭ.

[[Файл:Ada lovelace.jpg|thumb|250px|Баронесса [[Ада Лавлейс]] в 1836/1837 годах написала алгоритм для вычисления [[числа Бернулли|чисел Бернулли]] на [[Разностная машина Чарльза Бэббиджа|разностной машине Бэббиджа]], за что её считают первым [[программист]]ом в истории.]]

Алгоритмы становились предметом всё более пристального внимания учёных, и постепенно это понятие заняло одно из центральных мест в современной математике. Что же касается людей, от математики далёких, то к началу сороковых годов это слово они могли услышать разве что во время учёбы в школе, в сочетании «алгоритм Евклида». Несмотря на это, алгоритм всё ещё воспринимался как термин сугубо специальный, что подтверждается отсутствием соответствующих статей в менее объёмных изданиях. В частности, его нет даже в десятитомной [[Малая советская энциклопедия|Малой советской энциклопедии]] (1957 г.), не говоря уже об однотомных энциклопедических словарях. Но зато спустя десять лет, в третьем издании [[Большая советская энциклопедия|Большой советской энциклопедии]] (1969 год) алгоритм уже характеризуется как одна из основных категорий математики, «не обладающих формальным определением в терминах более простых понятий, и абстрагируемых непосредственно из опыта». Как мы видим, отличие даже от трактовки первым изданием БСЭ разительное! За сорок лет алгоритм превратился в одно из ключевых понятий математики, и признанием этого стало включение слова уже не в энциклопедии, а в словари. Например, оно присутствует в академическом «Словаре русского языка» (1981 г.) именно как термин из области математики.

Одновременно с развитием понятия алгоритма постепенно происходила и его экспансия из чистой математики в другие сферы. И начало ей положило появление компьютеров, благодаря которому слово «алгоритм» вошло в 1985 году во все школьные учебники [[Информатика|информатики]] и обрело новую жизнь. Вообще можно сказать, что его сегодняшняя известность напрямую связана со степенью распространения компьютеров. Например, в третьем томе «Детской энциклопедии» (1959 г.) о вычислительных машинах говорится немало, но они ещё не стали чем-то привычным и воспринимаются скорее как некий атрибут светлого, но достаточно далёкого будущего. Соответственно и алгоритмы ни разу не упоминаются на её страницах. Но уже в начале 70-х гг. прошлого столетия, когда компьютеры перестали быть экзотической диковинкой, слово «алгоритм» стремительно входит в обиход. Это чётко фиксируют энциклопедические издания. В «[[Энциклопедия кибернетики|Энциклопедии кибернетики]]» (1974 год) в статье «Алгоритм» он уже связывается с реализацией на вычислительных машинах, а в «Советской военной энциклопедии» (1976 г.) даже появляется отдельная статья «Алгоритм решения задачи на [[Электронно-вычислительная машина|ЭВМ]]».

За последние полтора-два десятилетия компьютер стал неотъемлемым атрибутом нашей жизни, компьютерная лексика становится всё более привычной. Слово «алгоритм» в наши дни известно, вероятно, каждому. Оно уверенно шагнуло даже в разговорную речь, и сегодня мы нередко встречаем в газетах и слышим в выступлениях политиков выражения вроде «алгоритм поведения», «алгоритм успеха» или даже «алгоритм предательства». Академик Н. Н. Моисеев назвал свою книгу «Алгоритмы развития», а известный врач [[Амосов, Николай Михайлович|Н. М. Амосов]] — «Алгоритм здоровья» и «Алгоритмы разума». А это означает, что слово живёт, обогащаясь всё новыми значениями и смысловыми оттенками.

== Определения алгоритма ==

=== Свойства алгоритмов ===
Различные определения алгоритма в явной или неявной форме содержат следующий ряд общих требований:
* [[Дискретность]] — алгоритм должен представлять процесс решения задачи как упорядоченное выполнение некоторых простых шагов. При этом для выполнения каждого шага алгоритма требуется конечный отрезок времени, то есть преобразование исходных данных в результат осуществляется во времени дискретно.
* [[Детерминированность]] (определённость). В каждый момент времени следующий шаг работы однозначно определяется состоянием системы. Таким образом, алгоритм выдаёт один и тот же результат (ответ) для одних и тех же исходных данных. В современной трактовке у разных реализаций одного и того же алгоритма должен быть изоморфный [[Граф алгоритма|граф]]. С другой стороны, существуют вероятностные алгоритмы, в которых следующий шаг работы зависит от текущего состояния системы и генерируемого случайного числа. Однако при включении метода генерации случайных чисел в список «исходных данных» вероятностный алгоритм становится подвидом обычного.
* Понятность — алгоритм должен включать только те команды, которые доступны исполнителю и входят в его систему команд.
* Завершаемость (конечность) — в более узком понимании алгоритма как математической функции, при правильно заданных начальных данных алгоритм должен завершать работу и выдавать результат за определённое число шагов. [[Дональд Кнут]] называет процедуру, которая удовлетворяет всем свойствам алгоритма, кроме, возможно, конечности, ''методом вычисления'' ({{lang-en|computational method}}){{sfn|Кнут|2006|loc= 1.1. Алгоритмы}}. Однако довольно часто определение алгоритма не включает завершаемость за конечное время<ref>{{Книга|автор=Robert Andrew Wilson, Frank C. Keil|заглавие=The MIT Encyclopedia of the Cognitive Sciences|ссылка=https://books.google.com/books?id=-wt1aZrGXLYC&pg=PA11&|ответственный=|издание=|издательство=MIT Press|год=2001|страницы=11|страниц=1106|isbn=9780262731447|isbn2=|archivedate=2021-11-17|archiveurl=https://web.archive.org/web/20211117090526/https://books.google.com/books?id=-wt1aZrGXLYC&pg=PA11&}}</ref>. В этом случае алгоритм (метод вычисления) определяет {{iw|частичная функция|частичную функцию|en|partial function}}. Для [[Вероятностный алгоритм|вероятностных алгоритмов]] завершаемость как правило означает, что алгоритм выдаёт результат с вероятностью 1 для любых правильно заданных начальных данных (то есть может в некоторых случаях не завершиться, но вероятность этого должна быть равна 0).
* Массовость (универсальность). Алгоритм должен быть применим к разным наборам начальных данных.
* Результативность — завершение алгоритма определёнными результатами.

=== Формальное определение ===
Разнообразные теоретические проблемы математики и ускорение развития физики и техники поставили на повестку дня точное определение понятия алгоритма.

Первые попытки уточнения понятия алгоритма и его исследования осуществляли в первой половине XX века [[Алан Тьюринг]], [[Эмиль Пост]], [[Жак Эрбран]], [[Курт Гедель]], [[Марков, Андрей Андреевич (младший)|А. А. Марков]], [[Алонзо Чёрч]]. Было разработано несколько определений понятия алгоритма, но впоследствии было выяснено, что все они определяют одно и то же понятие (см. [[Тезис Чёрча — Тьюринга]])<ref>(Игошин, с. 317)</ref>

Российский математик, основоположник [[Структурная лингвистика|структурной лингвистики]] в Советском Союзе [[Успенский, Владимир Андреевич|В. А. Успенский]] считал, что понятие алгоритма впервые появилось у Эмиля Бореля в 1912 году, в статье об определённом интеграле. Там он написал о «вычислениях, которые можно реально осуществить», подчеркивая при этом: «Я намеренно оставляю в стороне большую или меньшую практическую деятельность; суть здесь та, что каждая из этих операций осуществима в конечное время при помощи достоверного и недвусмысленного метода»<ref>{{Статья |заглавие=В. А. Успенский: «Математика — это гуманитарная наука» |ссылка=https://elementy.ru/nauchno-populyarnaya_biblioteka/432214/V_A_Uspenskiy_Matematika_eto_gumanitarnaya_nauka |язык=ru |издание=Троицкий вариант |год=2014 |месяц=1 |число=28 |номер=2(146) |страницы=4—6 |archivedate=2018-11-27 |archiveurl=https://web.archive.org/web/20181127234321/https://elementy.ru/nauchno-populyarnaya_biblioteka/432214/V_A_Uspenskiy_Matematika_eto_gumanitarnaya_nauka }}</ref>.

==== Машина Тьюринга ====
{{главная|Машина Тьюринга}}
[[Файл:TuringBeispielDiskretAnimatedGIF.gif|thumb|250px|Схематическая иллюстрация работы машины Тьюринга.]]

Основная идея, лежащая в основе машины Тьюринга, очень проста. Машина Тьюринга — это абстрактная машина (автомат), работающая с лентой отдельных ячеек, в которых записаны символы. Машина также имеет головку для записи и чтения символов из ячеек, которая может двигаться вдоль ленты. На каждом шаге машина считывает символ из ячейки, на которую указывает головка, и, на основе считанного символа и внутреннего состояния, делает следующий шаг. При этом машина может изменить своё состояние, записать другой символ в ячейку или передвинуть головку на одну ячейку вправо или влево.<ref name="gmbm">{{cite web | work = Good Math, Bad Math | url = http://scienceblogs.com/goodmath/2007/02/basics_the_turing_machine_with_1.php | title = Basics: The Turing Machine (with an interpreter!) | date = 2007-02-09 | archive-url = https://web.archive.org/web/20120211065906/http://scienceblogs.com:80/goodmath/2007/02/basics_the_turing_machine_with_1.php | archive-date = 2012-02-11 }}</ref>

На основе исследования этих машин был выдвинут тезис Тьюринга (основная гипотеза алгоритмов):
{{цитата|Некоторый алгоритм для нахождения значений функции, заданной в некотором алфавите, существует тогда и только тогда, когда функция исчисляется по Тьюрингу, то есть когда её можно вычислить на машине Тьюринга.}}

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

==== Рекурсивные функции ====
{{главная|Рекурсивная функция}}
С каждым алгоритмом можно сопоставить функцию, которую он вычисляет. Однако возникает вопрос, можно ли произвольной функции сопоставить машину Тьюринга, а если нет, то для каких функций существует алгоритм? Исследования этих вопросов привели к созданию в 1930-х годах теории рекурсивных функций<ref>(Игошин, раздел 33)</ref>.

Класс вычислимых функций был записан в образ, напоминающий построение некоторой аксиоматической теории на базе системы аксиом. Сначала были выбраны простейшие функции, вычисление которых очевидно. Затем были сформулированы правила (операторы) построения новых функций на основе уже существующих. Необходимый класс функций состоит из всех функций, которые можно получить из простейших применением операторов.

Подобно тезису Тьюринга в теории вычислимых функций была выдвинута гипотеза, которая называется ''[[Тезис Чёрча — Тьюринга|тезис Чёрча]]'':

{{цитата|Числовая функция тогда и только тогда алгоритмически исчисляется, когда она частично рекурсивна.}}

Доказательство того, что класс вычислимых функций совпадает с исчисляемыми по Тьюрингу, происходит в два шага: сначала доказывают вычисление простейших функций на машине Тьюринга, а затем — вычисление функций, полученных в результате применения операторов.

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

==== Нормальный алгоритм (алгорифм) Маркова ====
{{главная|Нормальный алгоритм}}
Нормальный алгоритм (алгорифм в авторском написании) Маркова — это система последовательных применений подстановок, которые реализуют определённые процедуры получения новых слов из базовых, построенных из символов некоторого алфавита. Как и машина Тьюринга, ''нормальные алгоритмы'' не выполняют самих вычислений: они лишь выполняют преобразование слов путём замены букв по заданным правилам<ref>[[Энциклопедия кибернетики]], т. '''2''', c. 90—91.</ref>.

''Нормально вычислимой'' называют функцию, которую можно реализовать нормальным алгоритмом. То есть алгоритмом, который каждое слово из множества допустимых данных функции превращает в её начальные значения<ref>(Игошин, раздел 34)</ref>..

Создатель теории нормальных алгоритмов А. А. Марков выдвинул гипотезу, которая получила название принцип нормализации Маркова:

{{цитата|Для нахождения значений функции, заданной в некотором алфавите, тогда и только тогда существует некоторый алгоритм, когда функция нормально исчисляемая.}}

Подобно тезисам Тьюринга и Черча, принцип нормализации Маркова не может быть доказан математическими средствами.

=== Стохастические алгоритмы ===
Однако приведённое выше формальное определение алгоритма в некоторых случаях может быть слишком строгим. Иногда возникает потребность в использовании [[случайная величина|случайных величин]]<ref name="cohen1996">«Probabilistic algorithms should not be mistaken with methods (which I refuse to call algorithms), which produce a result which has a high probability of being correct. It is essential that an algorithm produces correct results (discounting human or computer errors), even if this happens after a very long time». {{книга
|год=1996
|заглавие=A Course in Computational Algebraic Number Theory
|ссылка=https://archive.org/details/coursecomputatio00cohe_507
|издательство=[[Springer Science+Business Media|Springer-Verlag]]
|страницы=[https://archive.org/details/coursecomputatio00cohe_507/page/n19 2]
|isbn=3-540-55640-0
|язык=en
|автор=Henri Cohen
}}</ref>. Алгоритм, работа которого определяется не только исходными данными, но и значениями, полученными из {{d-l|генератор случайных чисел|генератора случайных чисел}}, называют ''стохастическим'' (или рандомизированным, от {{lang-en|randomized algorithm}})<ref name="mit">{{книга
|автор=Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rives't, Clifford Stein
|год=2001
|заглавие=Introduction to Algorithms
|глава=5.1
|издание=2-е
|страницы=531
|издательство=[[MIT Press]]
|isbn=0-262-03293-7
|язык=en
}}</ref>. <!-- Формально такие алгоритмы нельзя называть алгоритмами, поскольку — почему? — --> Стохастические алгоритмы часто бывают эффективнее детерминированных, а в отдельных случаях — единственным способом решить задачу<ref name="cohen1996" />.

На практике вместо генератора случайных чисел используют [[генератор псевдослучайных чисел]].

Однако следует отличать стохастические алгоритмы и методы, которые дают с высокой вероятностью правильный результат. В отличие от [[Метод#Метод в математике|метода]], алгоритм даёт корректные результаты даже после продолжительной работы.

Некоторые исследователи допускают возможность того, что стохастический алгоритм даст с некоторой заранее известной вероятностью неправильный результат. Тогда стохастические алгоритмы можно разделить на два типа<ref>(Раздел 12, с. 12—22 в Atallah, 2010)</ref>:
* [[Лас-Вегас (алгоритм)|алгоритмы ''типа Лас-Вегас'']] всегда дают корректный результат, но время их работы не определено.
* [[Метод Монте-Карло|алгоритмы ''типа Монте-Карло'']], в отличие от предыдущих, могут давать неправильные результаты с известной вероятностью.

=== Другие формализации ===
Для некоторых задач названные выше формализации могут затруднять поиск решений и осуществление исследований. Для преодоления препятствий были разработаны как модификации «классических» схем, так и созданы новые модели алгоритма, в частности:
* многоленточная и недетерминированная машины Тьюринга;
* регистровая и [[РАМ-машина]] — прототип современных компьютеров и виртуальных машин;
* [[Конечный автомат|конечные]] и [[Клеточный автомат|клеточные автоматы]].

== Виды алгоритмов ==
Виды алгоритмов как логико-математических средств отражают указанные компоненты человеческой деятельности и тенденции, а сами алгоритмы в зависимости от цели, начальных условий задачи, пути её решения. Следует подчеркнуть принципиальную разницу между алгоритмами вычислительного характера, преобразующими некоторые входные данные в выходные (именно их формализацией являются упомянутые выше машины Тьюринга, Поста, РАМ, нормальные алгоритмы Маркова и рекурсивные функции), и интерактивными алгоритмами <!-- называемыми ещё алгоритмами логического управления ? --> (уже у Тьюринга встречается C-машина, от {{lang-en|choice}} — выбор, ожидающая внешнего воздействия, в отличие от классической A-машины, где все начальные данные заданы до начала вычисления и выходные данные недоступны до окончания вычисления). Последние предназначены для взаимодействия с некоторым объектом управления и призваны обеспечить корректную выдачу управляющих воздействий в зависимости от складывающейся ситуации, отражаемой поступающими от объекта управления сигналами<ref>Dina Goldin, Peter Wegner. [ftp://ftp.cs.brown.edu/pub/techreports/04/cs04-14.pdf The origins of the Turing Thesis Myth], CS-04-14, October 2004</ref><ref>{{cite web |url = http://c2.com/cgi/wiki?InteractiveComputationIsMorePowerfulThanNonInteractive |title = Interactive Computation Is More Powerful Than Non Interactive  |archive-url = https://web.archive.org/web/20151119163505/http://c2.com/cgi/wiki?InteractiveComputationIsMorePowerfulThanNonInteractive |archive-date = 2015-11-19 }}, c2.com</ref>. В некоторых случаях алгоритм управления вообще не предусматривает окончания работы (например, поддерживает бесконечный цикл ожидания событий, на которые выдается соответствующая реакция), несмотря на это, являясь полностью правильным.

Можно также выделить алгоритмы:

* '''Механические алгоритмы''', или иначе '''детерминированные''', '''жесткие''' (например, алгоритм работы машины, двигателя и т. п.) — задают определённые действия, обозначая их в единственной и достоверной последовательности, обеспечивая тем самым однозначный требуемый или искомый результат, если выполняются те условия процесса, задачи, для которых разработан алгоритм.
* '''Гибкие алгоритмы''', например, стохастические, то есть вероятностные и эвристические.
* '''Вероятностный''' (стохастический) алгоритм даёт программу решения задачи несколькими путями или способами, приводящими к вероятному достижению результата.
* '''Эвристический алгоритм''' (от греческого слова «[[Эвристика|эврика]]») — алгоритм, использующий различные разумные соображения без строгих обоснований<ref>М. Гэри, Д. Джонсон, Вычислительные машины и труднорешаемые задачи, М.: Мир, 1982, C. 155.</ref>.
* '''Линейный алгоритм''' — набор команд (указаний), выполняемых последовательно во времени друг за другом.
* '''Разветвляющийся алгоритм''' — алгоритм, содержащий хотя бы одно условие, в результате проверки которого может осуществляться разделение на несколько альтернативных ветвей алгоритма.
* '''Циклический алгоритм''' — алгоритм, предусматривающий многократное повторение одного и того же действия (одних и тех же операций). К циклическим алгоритмам сводится большинство методов вычислений, перебора вариантов. Цикл программы — последовательность команд (серия, тело цикла), которая может выполняться многократно.
* '''Вспомогательный''' (''подчинённый'') '''алгоритм''' (''процедура'') — алгоритм, ранее разработанный и целиком используемый при алгоритмизации конкретной задачи. В некоторых случаях при наличии одинаковых последовательностей указаний (команд) для различных данных с целью сокращения записи также выделяют вспомогательный алгоритм. На всех этапах подготовки к алгоритмизации задачи широко используется структурное представление алгоритма.
* '''[[Блок-схема|Структурная блок-схема]], граф-схема алгоритма''' — графическое изображение алгоритма в виде схемы связанных между собой с помощью стрелок (линий перехода) блоков — графических символов, каждый из которых соответствует одному шагу алгоритма. Внутри блока дается описание соответствующего действия. Графическое изображение алгоритма широко используется перед программированием задачи вследствие его наглядности, так как зрительное восприятие обычно облегчает процесс написания программы, её корректировки при возможных ошибках, осмысливание процесса обработки информации. Можно встретить даже такое утверждение: «Внешне алгоритм представляет собой схему — набор прямоугольников и других символов, внутри которых записывается, что вычисляется, что вводится в машину и что выдается на печать и другие средства отображения информации».

== Нумерация алгоритмов ==
Нумерация алгоритмов играет важную роль в их исследовании и анализе<ref>(Игошин, раздел 36)</ref>. Поскольку любой алгоритм можно задать в виде конечного слова (представить в виде конечной последовательности символов некоторого алфавита), а множество всех конечных слов в конечном алфавите [[Счётное множество|счётное]], то множество всех алгоритмов также счётное. Это означает существование взаимно однозначного отображения между множеством натуральных чисел и множеством алгоритмов, то есть возможность присвоить каждому алгоритму номер.

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

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

== Алгоритмически неразрешимые задачи ==
{{main|Алгоритмически неразрешимая задача}}
Формализация понятия алгоритма позволила исследовать существование задач, для которых не существует алгоритмов поиска решений. Впоследствии была доказана невозможность алгоритмического вычисления решений ряда задач, что делает невозможным их решение на любом вычислительном устройстве.

Функцию <math>f</math> называют вычислимой ({{lang-en|computable}}), если существует [[машина Тьюринга]], которая вычисляет значение <math>f</math> для всех элементов множества определения функции. Если такой машины не существует, функцию <math>f</math> называют невычислимой. Функция будет считаться невычислимой, даже если существуют машины Тьюринга, способные вычислить значение для подмножества из всего множества входных данных<ref name="linz">{{книга
|заглавие=An Introduction to Formal Languages and Automata
|издательство=[[Jones & Bartlett Learning|Jones and Bartlett Publishers]]
|год=2000
|isbn=0-7637-1422-4
|язык=en
|автор=Peter Linz
}}</ref>.

Случай, когда результатом вычисления функции <math>f</math> является логическое выражение «истина» или «ложь» (или множество {0, 1}), называют задачей, которая может быть решаемой или нерешаемой, в зависимости от вычислимости функции <math>f</math><ref name="linz" />.

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

Одной из первых задач, для которой была доказана нерешаемость, является [[проблема остановки]]. Формулируется она следующим образом:

{{цитата|Имея описание программы для машины Тьюринга, требуется определить, завершит ли работу программа за конечное время или будет работать бесконечно, получив некоторые входные данные.<ref name="facts2009">{{cite encyclopedia
 | year = 2009
 | title = computability and complexity
 | encyclopedia = Encyclopedia of computer Science and Technology
 | publisher = Facts On File
 | isbn =  978-0-8160-6382-6
 | quote = Given any computer program, can you determine whether the program will halt (end) given any input?
}}</ref>}}

Доказательство неразрешимости проблемы остановки важно тем, что к ней можно свести другие задачи. Например, простую проблему остановки можно свести к задаче остановки на пустой строке (когда нужно определить для заданной машины Тьюринга, остановится ли она, будучи запущенной на пустой строке), доказав тем самым неразрешимость последней.<ref name="linz" />.

== Анализ алгоритмов ==
Вместе с распространением информационных технологий увеличился риск программных сбоев. Одним из способов избежания ошибок в алгоритмах и их реализациях служат доказательства корректности систем математическими средствами.

Использование математического аппарата для анализа алгоритмов и их реализаций называют формальными методами. Формальные методы предусматривают применение формальных спецификаций и, обычно, набора инструментов для синтаксического анализа и доказательства свойств спецификаций. Абстрагирование от деталей реализации позволяет установить свойства системы независимо от её реализации. Кроме того, точность и однозначность математических утверждений позволяет избежать многозначности и неточности естественных языков<ref>(O’Regan, раздел 4.5)</ref>.

По гипотезе Ричарда Мейса, «избежание ошибок лучше устранения ошибок»<ref>(раздел 5.3.6 в Enders, 2003)</ref>. По гипотезе Хоара, «доказательство программ решает проблему корректности, документации и совместимости»<ref>(раздел 5.3.7 в Enders, 2003)</ref>. Доказательство корректности программ позволяет выявлять их свойства по отношению ко всему диапазону входных данных. Для этого понятие корректности было разделено на два типа:
* ''Частичная корректность'' — программа даёт правильный результат для тех случаев, когда она завершается.
* ''Полная корректность'' — программа завершает работу и выдаёт правильный результат для всех элементов из диапазона входных данных.

Во время доказательства корректности сравнивают текст программы со спецификацией желаемого соотношения входных-выходных данных. Для доказательств типа Хоара спецификация имеет вид утверждений, которые называют предусловиями и постусловиями. В совокупности с самой программой их ещё называют [[Тройка Хоара|тройкой Хоара]]. Эти утверждения записывают как
: {P}Q{S}
где ''P'' — это предусловия, должные выполняться перед запуском программы ''Q'', а ''S'' — постусловия, истинные после завершения работы программы.

Формальные методы были успешно применены для широкого круга задач, в частности: разработке электронных схем, искусственного интеллекта, автоматических систем на железной дороге, верификации [[микропроцессор]]ов, спецификации стандартов; спецификации и верификации программ<ref>(O’Regan, с. 119)</ref>.

=== Время работы ===
{{seealso|Класс сложности}}
[[Файл:Нотация Ландау.svg|thumb|300px|Графики функций, приведённых в таблице ниже.]]

Распространённым критерием оценки алгоритмов является время работы и порядок роста продолжительности работы в зависимости от объёма входных данных.<ref name="axo1979">{{книга |заглавие=Построение и анализ вычислительных алгоритмов |оригинал=The Design and Analysis of Computer Algorithms |раздел=1 |издательство=«Мир» |год=1979 |место=М. |язык=ru |автор=[[Ахо, Альфред|А. Ахо]], [[Хопкрофт, Джон|Дж. Хопкрофт]], [[Ульман, Джеффри|Дж. Ульман]]}}</ref>

Для каждой конкретной задачи составляют некоторое число, которое называют её размером. Например, размером задачи вычисления произведения матриц может быть наибольший размер матриц-множителей, а для задач на графах размером может быть количество ребер графа.

Время, которое тратит алгоритм как функция от размера задачи <math>n</math>, называют временной сложностью этого алгоритма ''T''(''n''). Асимптотику поведения этой функции при увеличении размера задачи называют ''асимптотичной временной сложностью,'' а для её обозначения используют [[«O» большое и «o» малое|нотацию «O» большое]]. Например, если алгоритм обрабатывает входные данные размером <math>n</math> за время ''cn''², где ''c'' — некоторая [[Математическая константа|константа]], то говорят, что временная сложность такого алгоритма ''O''(''n''²).

Асимптотическая сложность важна тем, что является характеристикой алгоритма, а не его конкретной реализации: «оптимизацией» операций, без замены алгоритма, можно изменить только мультипликативный коэффициент ''c'', но не асимптотику. Как правило, именно асимптотическая сложность является главным фактором, который определяет размер задач, которые алгоритм способен обработать.

Часто во время разработки алгоритма пытаются уменьшить асимптотическую временную сложность для наихудших случаев. На практике же бывают случаи, когда достаточным является алгоритм, который «обычно» работает быстро.

Грубо говоря, анализ средней асимптотической временной сложности можно разделить на два типа: аналитический и статистический. Аналитический метод даёт более точные результаты, но сложен в использовании на практике. Зато статистический метод позволяет быстрее осуществлять анализ сложных задач<ref>(раздел 11 в Atallah, 2010)</ref>.

В следующей таблице приведены распространённые асимптотические сложности с комментариями<ref>(раздел 1 в Atallah, 2010)</ref>.

{{-}}
{| class="wikitable" border="1"
|-
! Сложность
! Комментарий
! Примеры
|-
| ''O''(1)
| Устойчивое время работы не зависит от размера задачи
| Ожидаемое время поиска в [[Хеш-таблица|хеш-таблице]]
|-
| ''O''(log log ''n'')
| Очень медленный рост необходимого времени
| Ожидаемое время работы интерполирующего поиска ''n'' элементов
|-
| ''O''(log ''n'')
| Логарифмический рост — удвоение размера задачи увеличивает время работы на постоянную величину
| Вычисление ''x''<sup>''n''</sup>; [[Двоичный поиск]] в массиве из ''n'' элементов
|-
| ''O''(''n'')
| Линейный рост — удвоение размера задачи удвоит и необходимое время
| Сложение/вычитание чисел из ''n'' цифр; [[Линейный поиск]] в массиве из ''n'' элементов
|-
| ''O''(''n'' log ''n'')
| Линеаритмичный рост — удвоение размера задачи увеличит необходимое время чуть более, чем вдвое
| [[Сортировка слиянием]] или кучей ''n'' элементов; нижняя граница сортировки сопоставлением ''n'' элементов
|-
| ''O''(''n''²)
| Квадратичный рост — удвоение размера задачи увеличивает необходимое время в четыре раза
| Элементарные [[Алгоритм сортировки|алгоритмы сортировки]]
|-
| ''O''(''n''³)
| Кубичный рост — удвоение размера задачи увеличивает необходимое время в восемь раз
| Обычное умножение матриц
|-
| ''O''(''c''<sup>''n''</sup>)
| Экспоненциальный рост — увеличение размера задачи на 1 приводит к ''c''-кратному увеличению необходимого времени; удвоение размера задачи увеличивает необходимое время в квадрат
| Некоторые [[Задача коммивояжёра|задачи коммивояжёра]], алгоритмы поиска полным перебором
|}

== Наличие исходных данных и некоторого результата ==
Алгоритм — это точно определённая инструкция, последовательно применяя которую к исходным данным, можно получить решение задачи. Для каждого алгоритма есть некоторое множество объектов, допустимых в качестве исходных данных. Например, в алгоритме деления вещественных чисел делимое может быть любым, а делитель не может быть равен нулю.

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

Для разработки алгоритмов и программ используется '''алгоритмизация''' — процесс систематического составления алгоритмов для решения поставленных прикладных задач. Алгоритмизация считается обязательным этапом в процессе разработки программ и решении задач на ЭВМ. Именно для прикладных алгоритмов и программ принципиально важны детерминированность, результативность и массовость, а также правильность результатов решения поставленных задач.

Алгоритм — это понятное и точное предписание исполнителю совершить последовательность действий, направленных на достижение цели.

== Представление алгоритмов ==
Формы записи алгоритма:
* словесная или вербальная: на естественном языке;
* на алгоритмическом языке: [[Язык программирования|языке программирования]] или [[Псевдокод (язык описания алгоритмов)|псевдокоде]];
* в [[Машинный код|машинном коде]] (код процессора ЭВМ);
* в математической нотации (см. выше представленные варианты);
* схематическая:
** графическая (например, [[Блок-схема алгоритма|блок-схемы]] и [[ДРАКОН|ДРАКОН-схемы]]);
** структурограммы ([[Диаграмма Насси — Шнейдермана|диаграммы Насси-Шнейдермана]]).

Обычно сначала (на уровне идеи) алгоритм описывается словами, но по мере приближения к реализации он обретает всё более формальные очертания и формулировку на языке, понятном исполнителю (например, [[машинный код]]).

== Эффективность алгоритмов ==
Хотя в определении алгоритма требуется лишь конечность числа шагов, требуемых для достижения результата, на практике выполнение огромного количество шагов приводит к длительному выполнению программ, также обычно есть другие ограничения (на размер программы, на допустимые действия). В связи с этим вводят такие понятия, как [[сложность алгоритма]] ([[Временная сложность алгоритма|временна́я]], по размеру программы, [[Вычислительная сложность|вычислительная]] и другие).

Для каждой задачи может существовать множество алгоритмов, приводящих к цели. Увеличение эффективности алгоритмов составляет одну из задач [[Информатика|информатики]], начиная с 1940-х годов в связи с этим простроен ряд более эффективных в [[Асимптотическая оценка|асимптотическом смысле]] алгоритмов для традиционных задач (например, {{iw|Алгоритм умножения|алгоритмы быстрого умножения|en|Multiplication algorithm}}, [[алгоритм Чудновского]] для вычисления числа <math> \pi </math>).

== Пример ==
[[Алгоритм Евклида]] — эффективный метод вычисления [[Наибольший общий делитель|наибольшего общего делителя]] (НОД). Назван в честь греческого математика Евклида; один из древнейших алгоритмов, который используют до сих пор<ref name="knuth2">{{книга
|год=1997
|заглавие=[[Искусство программирования|The Art of Computer Programming]], Volume 2: Seminumerical Algorithms
|издание=3rd
|издательство=[[Addison-Wesley|Addison–Wesley]]
|isbn=0201896842
|язык=en
|автор=[[Кнут, Дональд Эрвин|Knuth D.]]
}}</ref>.

Описан в «Началах» Евклида (примерно 300 лет до н. э.), а именно в книгах VII и X. В седьмой книге описан алгоритм для целых чисел, а в десятой — для длин отрезков.

Существует несколько вариантов алгоритма, ниже записанный в [[Псевдокод (язык описания алгоритмов)|псевдокоде]] рекурсивный вариант:

 '''алг''' нод(a, b)
 '''нач'''
     '''если''' b = 0
        '''возврат''' a
     '''иначе'''
        '''возврат''' нод(b, a '''mod''' b)
 '''кон'''

[[Файл:Euclids-algorithm-example-1599-650.gif|thumb|right|350px|Иллюстрация выполнения алгоритма Евклида для вычисления НОД чисел 1599 и 650.]]
НОД чисел 1599 и 650:
{| class="wikitable"
|-
| Шаг 1 || 1599 = 650*2 + 299
|-
| Шаг 2 || 650 = 299*2 + 52
|-
| Шаг 3 || 299 = 52*5 + 39
|-
| Шаг 4 || 52 = 39*1 + 13
|-
| Шаг 5 || 39 = 13*3 + 0
|}
{{clear}}

== См. также ==
* [[Метаалгоритм]]
* [[Аукцион алгоритмов]]
* [[Список алгоритмов]]
* [[Теория алгоритмов]]

== Примечания ==
{{примечания|2}}

== Литература ==
* {{книга |заглавие=Алгоритмы: построение и анализ |издание=3-е |оригинал=Introduction to Algorithms, Third Edition |автор=Томас Х. Кормен, Чарльз И. Лейзерсон, Рональд Л. Ривест, Клиффорд Штайн |страниц=1328 |isbn=978-5-8459-1794-2 |год=2013 |место=М. |издательство=[[Вильямс (издательство)|«Вильямс»]]}}
* {{книга |автор=[[Дональд Кнут]] |заглавие=Искусство программирования |том=1. Основные алгоритмы |оригинал=The Art of Computer Programming, vol. 1. Fundamental Algorithms |ссылка = |издание=3-е изд. |место=М. |издательство=[[Вильямс (издательство)|«Вильямс»]] |год=2006 |страницы=720 |isbn=0-201-89683-4 |ref=Кнут}}
* {{книга |заглавие=Алгоритмы: вводный курс |оригинал=Algorithms Unlocked |автор=Томас Х. Кормен |страниц=208 |isbn=978-5-8459-1868-0 |год=2014 |место=М. |издательство=[[Вильямс (издательство)|«Вильямс»]]}}
* {{книга |автор=Игошин В. И. |заглавие=Математическая логика и теория алгоритмов |место=М. |издание=2-е изд., стер. |издательство=ИЦ «Академия» |год=2008|страниц=448 |isbn=5-7695-1363-2 |ref=Игошин}}

== Ссылки ==
{{Навигация
|Портал       =
|Викисловарь  = алгоритм
|Викиучебник  = Что такое алгоритм
|Викицитатник =
|Викитека     =
|Викивиды     =
|Викиновости  =
|Викисклад    =
|Метавики     =
|Проект       =
}}
* «[[b:Слово «алгоритм»: происхождение и развитие|Слово „алгоритм“: происхождение и развитие]]», В. В. Шилов, [[b:Журнал «Потенциал»|Журнал «Потенциал»]] — источник исторических сведений.
* {{cite web |url = http://www.krugosvet.ru/articles/125/1012581/1012581a1.htm |title = Об алгоритме |deadlink = yes }} в энциклопедии «Кругосвет»
{{Внешние ссылки}}
{{rq|cleanup|wikify}}

[[Категория:Алгоритмы|*]]
[[Категория:Решение задач]]