Что является характерным для интуитивного понятия алгоритма

Интуитивное понятие алгоритма

Одним из главнейших понятий математики является, как известно, понятие функции. Содержательно функция представляет собой “закон соответствия”, по которому каждому элементу области определения – значению аргумента – сопоставляется какой-то элемент области прибытия – значение функции. При этом, вообще говоря, не требуется, чтобы значение функции можно было каким-либо способом “в самом деле найти” (“построить”, “вычислить” и т.п.) по соответствующему значению аргумента; однако ясно, что для математики и в особенности для ее приложений все же должны быть наиболее интересны те функции, для которых способы нахождения (иначе – “построения” или “вычисления”) их значений существуют.

В трудах Ньютона и Лейбница, в которых впервые появилось понятие функции, равно как и в работах математиков следующих поколений, неявно предполагалось, что значение функции всегда можно так или иначе “найти”, производя над значением аргумента некоторые “действия”, пред
писываемые связанным с этой функцией “аналитическим выражением”. Правда, тогда рассматривались только функции действительной и комплексной переменной; но потом, в XIX сто
летии, было замечено, что даже если ограничиться только такими функциями, их общие свойства никак не связаны с возможностью “вычислять” их значения (более того, с вычислимостью не связаны и те специальные свойства, которые играют основную роль в анализе – непрерывность, дифференцируемость и т.п.). Тогда понятие функции было освобождено от связи с аналитическим выражением и приобрело ту общность, которой мы пользуемся теперь. Но осознание того факта, что не для всех функций можно “вычислить” их значения, не могло, разумеется, уменьшить практического интереса к изучению тех функций, для которых такое вычисление возможно; с теоретической же точки зрения естественно было теперь поставить вопрос о том, чем отличаются “вычислимые” функции от “невычислимых”, т.е. о выработке точного понятия способа вычисления функции.

Интуитивное представление о “вычислительной процедуре” существовало у математиков уже давно, и за этими процедурами был закреплен специальный термин, не отвечавший еще никакому точному понятию, – алгоритм.

Слово “алгоритм” происходит от имени работавшего в IX в. в Багдаде (и писавшего, как все тогдашние мусульманские ученые, по-арабски) математика аль-Хорезми (это имя указывает на происхождение из Хорезма). В латинских переводах его сочинений, получивших распространение в Европе с XII века, имя автора писалось в искаженной форме, чаще всего Algorithmus или Algorismus. По арифметическому трактату аль-Хорезми европейцы впервые познакомились с созданной в Индии позиционной системой счисления, которой мы пользуемся и сейчас. Со временем слово Algorithmus превратилось в название основанной на этой системе арифметики, изданной тогда в виде собрания правил действий над числами. Затем так стали называть любую систему правил, позволяющих чисто механически выполнить любую конкретную операцию некоторого определенного типа. Можно охарактеризовать алгоритм еще и как такую механическую процедуру, которая может применяться к символам некоторого класса (входным символам) и, возможно, выдает для данного входного символа определенный выходной символ.

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

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

Алгоритм задается как предложение формального языка.

Алгоритмический язык – это формализованный язык для однозначной записи алгоритмов.

Пример 2.1. Дифференцирование многочлена

(1) Взять очередной член многочлена; если такового уже не осталось, написать “Конец” и остановиться.

(2) Взять показатель степени переменной данного члена и умножить его на коэффициент, сделав это произведение коэффициентом при новом члене; уменьшить его на 1 и сделать показателем степени при новом члене.

Пример 2.2. Поиск слова в двуязычном (переводном) словаре

(1) Взять первую букву искомого слова и найти тот раздел словаря, первое слово которого начинается этой буквой.

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

(3) Начиная с найденной страницы, просматривать подряд все слова, сравнивая их с искомым словом до тех пор, пока либо будет получено совпадение (“искомое слово найдено”), либо мы дойдем до слова, не начинающегося на три буквы, выделенные на шаге (2) (“искомое слово не найдено”).

(4) Если искомое слово найдено, взять все его эквиваленты; конец.

(5) Если искомое слово не найдено, взять более полный словарь и вернуться к (1).

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

Кроме алгоритмов для вычисления функции, говорят еще об алгоритмах для распознавания свойств и отношений, подразумевая под этим строго определенные “правила” или “процедуры”, позволяющие отвечать на вопросы вроде: “Является ли данное натуральное число простым?”, “Являются ли два данных натуральных числа взаимно простыми?” и т.п. Однако задача распознавания свойства или отношения всегда может быть представлена как задача нахождения, или “вычисления”, истинностного значения некоторого предиката (одноместного и многоместного); поэтому под алгоритмом всегда можно понимать процедуру, позволяющую “находить” или “вычислять” значения некоторой функции.

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

Анализ только что приведенных и любых других примеров алгоритмов показывает, что все они обладают следующими двумя характерными особенностями:

• наличие четкого описания. Алгоритм всегда описывается настолько четко, что на основе этого описания можно действовать чисто механически, не вникая в смысл;

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

Более детальная характеристика понятия “алгоритм” должна включать следующие аспекты (по Хартли Роджерсу):

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

2) имеется механизм (человек, механическое, оптическое и т.п. устройство, электронная машина), воспринимающий и выполняющий инструкции;

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

4) существенно, что все выполняемые процедуры являются дискретными (хотя обрабатываемые ими объекты могут быть по своему характеру непрерывными);

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

Здесь прослеживается аналогия с парой (вычислительная машина, программа), а именно:

а) соответствует программе;

б) соответствует вычислительной машине, работающей по этой программе;

в) соответствует машинной памяти;

г) соответствует дискретной (“цифровой”) природе цифровых вычислительных машин (в отличие от аналоговых);

д) соответствует механичности и жесткой детерминированности порядка выполнения команд программы.

Неформально и схематически алгоритм представлен на рис. 2.1.

Рис. 2.1. Схематическое изображение алгоритма

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

Сказанное сейчас ни в коей мере не может еще претендовать на статус математического определения; мы хотели только подытожить, хотя бы частично, давно существующие в математике интуитивные представления об алгоритме, или “вычислительной процедуре”. Этими интуитивными представлениями математики могли обходиться до тех пор, пока речь шла только об отыскании алгоритмов для решения конкретных “вычислительных” задач и при этом всякий раз нужный алгоритм удавалось найти – потому что когда алгоритм найден, ни у кого из математиков не возникает сомнения, что это действительно алгоритм, т.е. вычислительная процедура. Но со временем возникли некоторые задачи несомненно “вычислительного” характера, все попытки нахождения алгоритмов для которых заводили в тупик, и появилась гипотеза, что, по крайней мере, для части этих задач вообще никаких алгоритмов не существует. Проверка этой гипотезы в каждом случае требует уже строгого определения алгоритма: ведь если мы хотим математически доказать, что чего-то не существует, это “что-то” должно быть определено так, как полагается определять математические понятия.

Именно в связи с проблемой доказательства несуществования алгоритма в 30-е годы нынешнего столетия одновременно несколькими исследователями – К. Гёделем, Э. Постом, А. Тьюрингом – были предприняты усилия дать точное определение соответствующего понятия.

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

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

Источник

Уточнение понятия алгоритма

Лекция 7-8

Элементы теории алгоритмов. Интуитивное понятие алгоритма и его характерные черты. Необходимость уточнения понятия алгоритма.

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

1. Правила выполнения арифметических действий над числами.

2. Правило отыскания наибольшего общего делителя (алгоритм Евклида).

3. Правило извлечения квадратного корня.

4. Правило отыскания решений квадратного уравнения.

5. Правило отыскания производной многочлена n-ой степени.

6. Правило интегрирования рациональной функции.
В каждом из приведенных примеров приходится иметь дело с классом однотипных задач, или, как говорят, с массовой проблемой. Задачи такого класса отличаются друг от друга значениями входящих в них параметров. Так, в задаче отыскания решения квадратного уравнения ах 2 + bх + с = 0 участвует три параметра а, b и с; меняя их, получаем различные задачи одного класса.

В связи со сказанным можно дать следующее определение понятия алгоритма.

Алгоритмом называется общий единообразный, точно определенный способ решения любой задачи из данной массовой проблемы.

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

Отметим характерные черты понятия алгоритма.

2. Детерминированность алгоритма. Система величин, получаемых в какой-то не начальный момент, однозначно определяется системой величин, полученных в предшествующие моменты времени.

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

4. Массовость алгоритма. Начальная система величин может выбираться из некоторого потенциально бесконечного множества.

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

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

Имеется 15 предметов. В игре участвуют двое: начинающий и противник. Каждый игрок по очереди берет один, два или три предмета. Выигрывает тот, кто берет последний предмет. Какой стратегии в игре должен придерживаться начинающий, чтобы выиграть?

Выигрышная стратегия начинающего может быть описана в форме следующей таблицы:

Уточнение понятия алгоритма

В истории математики накопилось много случаев длительных и часто безрезультатных поисков тех или иных алгоритмов. При этом естественно возникало сомнение в существовании алгоритма.

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

В 1900 году на втором международном математическом конгрессе в Париже немецкий математик Давид Гильберт огласил список 23 трудных проблем, на важность решения которых он обращал внимание математической общественности. Среди них была и следующая 10-ая проблема Гильберта: требуется выработать алгоритм, позволяющий для любого диофантова уравнения выяснить, имеет ли оно целочисленное решение.

Рассмотрим всевозможные диофантовы уравнения, т.е. уравнения вида Р = 0, где Р является многочленом

с целочисленными коэффициентами. Такими будут, например, уравнения

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

Для частного случая диофантова уравнения с одним неизвестным давно известен алгоритм, позволяющий найти все его целочисленные решения. Установлено, что если уравнение

с целочисленными коэффициентами имеет целый корень, то он обязательно является делителем a_n. В связи с этим можно предложить такой алгоритм:

2) Вычислить P_n(x> для каждого из делителей числа а_n

3) Если при некотором i из совокупности 1,2. n

Поиски решения десятой проблемы Гильберта привлекли внимание многих математиков и длились около 70 лет. Только в 1968 году молодым математиком Ю. Матиясевичем было доказано, что нет алгоритма, дающего решение поставленной задачи.

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

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

Действительно, в этом случае нужно либо доказать существование алгоритма, либо доказать его отсутствие.

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

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

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

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

И наконец, различные исследователи этой проблемы исходили из разных технических и логических соображений, и вследствие этого было выработано несколько определений алгоритма. Однако со временем выяснилось, что все эти определения равносильны, т.е. определяют одно и то же понятие. Это и есть современное понятие алгоритма.

В подходах к определению понятия алгоритма можно выделить три основных направления.

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

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

Третье направление связано с понятием нормальных алгоритмов, введенным и разработанным российским математиком А. А. Марковым.

Источник

Интуитивное понятие алгоритма

Поможем написать любую работу на аналогичную тему

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

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

2. Массовость: алгоритм должен решать не одну конкретную задачу, а целый класс подобных задач.

3. Элементарность шагов: алгоритм разбивается на этапы, каждый из которых должен быть простым и локальным.

4. Детерминированность: после выполнения очередного этапа однозначно определено, что делать дальше.

5. Результативность: алгоритм должен приводить к решению задачи за конечное число шагов.

1. Нахождение наибольшего общего делителя.

2. Вычисление ранга целочисленной матрицы.

3. Построение ДНФ и КНФ в логике высказываний.

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

Но для того, чтобы доказать, что алгоритм не существует, надо точно знать, что такое алгоритм.

Начиная с 30-х годов XX века, было предложено несколько уточнений понятия алгоритма. К ним относятся:

Источник

Интуитивное представление об алгоритмах

Общее понятие алгоритма

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

Многочисленные и разнообразные алгоритмы окружают нас буквально во всех сферах жизни и деятельности. Многие наши действия доведены до бессознательного автоматизма, мы порой и не осознаем, что они регламентированы определенным алгоритмом — четкой системой инструкций. Например, наши действия при входе в магазин «Универсам» (сдать свою сумку, получить корзину с номером, пройти в торговый зал, заполнить корзину продуктами, оплатить покупку в кассе, предъявить чек контролеру, взять свою сумку, переложить в нее продукты, сдать корзину, покинуть магазин). Второй пример — приготовление манной каши (500 мл молока довести до кипения, при тщательном помешивании засыпать 100 г манной крупы, при помешивании довести до кипения и варить 10 минут). Автоматизм выполнения этих и многих других действий не позволяет нам осознавать их алгоритмическую сущность.

Но есть немало таких действий, выполняя которые, мы тщательно следуем той или иной инструкции. Это главным образом непривычные действия, профессионально не свойственные нам. Например, если вы фотографируете один-два раза в год, то, купив проявитель для пленки, будете весьма тщательно следовать инструкции (алгоритму) по его приготовлению: «Содержимое большого пакета растворить в 350 мл воды при температуре 18— 20 °С. Там же растворить содержимое малого пакета. Объем раствора довести до 500 мл. Раствор профильтровать. Проявлять 3—4 роликовых фотопленки». Второй пример: если вы никогда раньше не пекли торт, то, получив рецепт (алгоритм) его приготовления, постараетесь выполнить в указанной последовательности все его предписания.

Большое количество алгоритмов встречается при изучении математики буквально с первых классов школы. Это прежде всего алгоритмы выполнения четырех арифметических действий над различными числами — натуральными, целыми, дробными, комплексными. Вот пример такого алгоритма: «Чтобы из одной десятичной дроби вычесть другую, надо: 1) уравнять число знаков после запятой в уменьшаемом и вычитаемом; 2) записать вычитаемое под уменьшаемым так, чтобы запятая оказалась под запятой; 3) произвести вычитание так, как вычитают натуральные числа; 4) поставить в полученной разности запятую под запятыми в уменьшаемом и вычитаемом».

1. Выделим слагаемое с наименьшим числом десятичных знаков. Таким слагаемым является число 7,45 (два десятичных знака).

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

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

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

Неформальное понятие алгоритма

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

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

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

Существенной чертой алгоритма является его массовый характер, т. е. возможность применять его к обширному классу начальных данных, возможность достаточно широко эти начальные данные варьировать. Другими словами, каждый алгоритм призван решить ту или иную массовую проблему, т.е. решать класс однотипных задач. Например, задача нахождения наибольшего общего делителя чисел 4 и 6 есть единичная проблема (можно решить ее и без применения алгоритма Евклида), но задача нахождения наибольшего общего делителя произвольных натуральных чисел и — уже проблема массовая. Суть алгоритма Евклида состоит в том, что он приводит к желаемому результату вне зависимости от выбора конкретной пары натуральных чисел, в то время как при решении указанной единичной проблемы можно предложить такой способ, который окажется неприменимым для другой пары натуральных чисел.

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

Говоря о начальных данных для алгоритма, имеют в виду так называемые допустимые начальные данные, т.е. такие начальные данные, которые сформулированы в терминах данного алгоритма. Так, к числу допустимых начальных данных для алгоритма варки манной каши никак не отнесешь элементы множества натуральных чисел, а к числу начальных данных алгоритма Евклида — молоко и манную крупу (или даже комплексные числа).

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

Пример 31.1. Приведем пример бесконечного алгоритмического процесса. Всем известен алгоритм деления десятичных дробей. Числа 5,1 и 3 являются для него допустимыми начальными данными, применение к которым алгоритма деления приводит к искомому результату 1,7. Иная картина возникает для чисел 20 и 3, которые также представляют собой допустимые начальные данные. Для них получается алгоритмический процесс:

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

Пример 31.2. Теперь приведем пример алгоритма, заходящего в тупик, безрезультатно обрывающегося. Вот его предписания.

Пусть натуральные (целые положительные) числа будут допустимыми начальными данными для этого алгоритма. Для числа 6 алгоритмический процесс будет проходить так:

Искомый результат равен 6. Иначе будет протекать алгоритмический процесс для исходного данного 7:

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

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

Отметим в заключение, что сам термин «алгоритм» (или «алгорифм») происходит от имени великого среднеазиатского ученого Мухаммеда аль-Хорезми (787 — ок. 850). В своем трактате, написанном по-арабски, латинская версия которого относится к XII в. и начинается словами «Dixit algorizm», т.е. «Сказал аль-Хорезми», им среди прочего была описана индийская позиционная система чисел и сформулированы правила выполнения четырех арифметических действий над числами в десятичной записи.

Необходимость уточнения понятия алгоритма

Понятие алгоритма формировалось с древнейших времен, но до конца первой трети XX в. математики довольствовались интуитивным представлением об этом объекте. Термин «алгоритм» употреблялся в математике лишь в связи с теми или иными конкретными алгоритмами. Утверждение о существовании алгоритма для решения задач данного типа сопровождалось фактическим его описанием.

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

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

Первые работы по уточнению понятия алгоритма и его изучению, т.е. по теории алгоритмов, были выполнены в 1936–1937 гг. математиками А.Тьюрингом, Э. Постом, Ж.Эрбраном, К.Гёделем, А.А. Марковым, А.Чёрчем. Было выработано несколько определений понятия алгоритма, но впоследствии выяснилось, что все они равносильны между собой, т.е. определяют одно и то же понятие.

Источник