История развития понятия «алгоритм» и его современное понимание и применение в информатике и математике

Содержание

Введение

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

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

Вплоть до 1930 года понятие «алгоритм» оставалось интуитивным и имело скорее методологическое значение, а не математическое. Много ярких примеров раскрыла алгебра и теория чисел. Среди них: «алгоритм Евклида», «алгоритм Гаусса», «алгоритм Штурма» и многие другие.

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

В 1930х годах в работах Гильберта, Черча, Клини, Поста, Тьюринга было определено понятие «алгоритм» в двух формах:

1) на основе понятия рекурсивной функции;

2) на основе описания алгоритмического процесса.

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

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

Стимулом в развитии теории алгоритмов и в изучении алгоритмических моделей послужило применение ЭВМ. Так же ЭВМ послужило самостоятельному изучению алгоритмов с целью их сравнения по рабочим характеристикам (числу действий, расходу памяти), а так же их оптимизации. Алгоритмы стали объектом точного исследования как и те объекты, для работы с которыми они предназначены.

Цель данной работы - показать развитие понятия «алгоритма» в математике и информатике, а также современное понимание понятия «алгоритм».

Задачи:

- изучить историю появления понятия;

- рассмотреть применение алгоритмов в математике;

- рассмотреть применение алгоритмов в информатике;

- рассмотреть свойства алгоритмов;

- рассмотреть машины Поста и Тьюринга.

Объектом исследования в данной работе является развитие, применение и современное понимание понятия «алгоритм».

Предметом исследования является само понятие алгоритма.

1. ИСТОРИЯ РАЗВИТИЯ ПОНЯТИЯ «АЛГОРИТМ» И ЕГО СОВРЕМЕННОЕ ПОНИМАНИЕ

1.1. История развития понятия «алгоритм».

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

Алгоритм одно из самых основных понятий вычислительной математики. Это понятие возникло в связи с поисками общих методов решения однотипных задач задолго до появления ЭВМ.

Еще в III веке до нашей эры греческий математик Евклид изложил правило вычисления наибольшего общего делителя (НОД) двух натуральных чисел. «Алгоритм Евклида» состоит в том, чтобы вычитать из большего числа меньшее, подставляя результат на место большего числа, до тех пор, пока числа не станут равны друг другу. Эти равные числа и будут наибольшим общим делителем их разности и любого из чисел. Идея алгоритма понятна даже на интуитивном уровне и не нуждается в уточнении для применения на практике. Более конкретно «алгоритм Евклида» выглядит следующим образом:

1. Сравнить первое и второе числа. Если они равны, перейти к процедуре 4. Если нет, то перейти к процедуре 2.

2. Если первое число меньше второго, то переставить их. Перейти к процедуре 3.

3. Вычесть из первого числа второе и рассмотреть полученную разность как новое первое число. Перейти к процедуре 1.
4. Считать первое число результатом задачи.

Такой набор правил и является алгоритмом. Следуя ему любой человек может найти НОД.

Это правило в истории развития математики считают первым алгоритмом, хотя само слово «алгоритм» появилось гораздо позднее.

Древнегреческим ученым Эратосфеном во II веке до нашей эры был предложен способ получения простых чисел (точное название «решето Эратосфена»).

В IX веке узбекским математиком Мухаммадом Ал-Хорезми были разработны правила четырех арифметических действий над числами. В Европе эти правила стали называть алгоритмами от латинской формы написания имени автора - Alchorismi или Algorithmi. Переводы арифметического трактата Ал-Хорезми с арабского содержали описание индийской позиционной системы счисления и искусства счета в этой системе. Примером может служить алгоритм сложения «столбиком».

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

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

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

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

В начале ХХ века алгоритм стал объектом математического изучения.

«Общее понятие алгоритма как эффективной вычислительной процедуры и примеры использования такого понятия встречаются в работах француза Э.Бореля (1912 г.) и немца Г.Вейля (1921 г.). Оба они пришли к понятию вычислимой функции (термин «fonction calculable»)» [2, c.161].

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

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

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

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

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

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

Наиболее общий подход к уточнению понятия «алгоритм» было предложено советским ученым Колмогоровым А.Н., которым было дано еще и его «наглядное» представление: «Алгоритм, примененный ко всякому «условию» («начальному состоянию») из некоторого множества («области применимости» алгоритма), дает «решение» («заключительное состояние»). Алгоритмический процесс расчленяется на отдельные шаги заранее ограниченной сложности; каждый шаг состоит в «непосредственной переработке»… (одного) состояния в (другое). Процесс переработки продолжается до тех пор, пока либо не произойдет безрезультатная остановка, либо не появится сигнал о получении «решения». При этом не исключается возможность неограниченного продолжения процесса…» Формулировка по Колмогорову содержит такие существенные моменты, как идея итеративности алгоритмического процесса и идея локальности каждого отдельного шага.

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

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

1.2 Понятие «алгоритм» в математике

Понятие «алгоритм» является одним из основных понятий (категорий) математики, которое не обладает формальным определением. Таким образом, данное понятие можно представить в интуитивном виде. Алгоритмами можно назвать, например, известные из начальной школы правила сложения, вычитания, умножения и деления столбиком.

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

1) указание совокупности возможных исходных данных;

2) правило, по которому процесс признается закончившимся ввиду достижения результата.

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

Понятие «алгоритм» занимает центральное место в современной математике, прежде всего вычислительной.

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

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

Содержательные явления, лежащие в основе образования понятия «алгоритм», издавна занимали важное место в науке. Многие задачи математики, с древнейших времен, заключались в отыскании тех или иных конструктивных методов. Эти поиски, особенно усиливались в связи с созданием удобной символики и осмысления принципиального отсутствия искомых методов в ряде случаев, например, задача о квадратуре круга. Все это явилось мощным фактором развития научных знаний. Осознание невозможности решить задачу прямым вычислением привело к созданию теоретико-множественной концепции в 19 веке, где вопрос о конструктивных методах вообще не возникает. Только лишь в 20 веке оказалось возможным вновь вернуться к вопросам конструктивности. Этот возврат к вопросам конструктивности произошел уже на новом уровне, обогащенном понятием алгоритма. Такое понятие легло в основу особого конструктивного направления в математике.

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

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

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

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

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

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

1) совокупность возможных исходных данных,

2) совокупность возможных результатов,

3) совокупность промежуточных результатов,

4) правило начала,

5) правило непосредственной переработки,

6) правило окончания,

7) правило извлечения результата»[5,с.27].

Алгоритм является предметом изучения такой отрасли математики как теория алгоритмов. В результате изучения понятия «алгоритм» выделены его основные свойства:

- определенность - в любой момент времени исполнитель должен знать, какое действие нужно сделать;

- дискретность - разбиение алгоритма на некоторые действия, которые следуют друг за другом;

- массовость - по одному и тому же алгоритму могут решаться однотипные задачи и причем решаться они могут неоднократно;

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

- результативность означает, что алгоритм всегда должен приводить к результату.

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

1.3 Понятие «алгоритм» в информатике

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

Под алгоритмом в информатике понимается определенная последовательность логических действий для решения поставленной задачи. Кроме того, «Алгоритм - понятное и точное предписание исполнителю выполнить конечную последовательность команд, приводящих от исходных данных к искомому результату» [1, c. 275].

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

program Primer; {вычисление суммы двух чисел}

var

k,m,h: integer;

begin

Writeln('Введите через пробел два числа ');

Readln(m,k);

h := m + k;

Writeln('Сумма чисел равна ',h);

end.

Рассмотренный кусочек кода является алгоритмом. Алгоритм данной программы включает в себя такие действия:

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

- Затем находит их сумму.

- В итоге выводит отчет.

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

1.4 Машина Тьюринга

Данная машина была предложена А. Тьюрингом в 1936 году для формализации понятия «алгоритм». Машина Тьюринга является математической абстракцией, представляющей собой вычислительную машину.

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

Рисунок 1.1 - Схема машины Тьюринга

Управляющее устройство (головка) машины Тьюринга может находится в одном из дискретных состояний состояний: Q={q0, q1, ..., qn}. Читающая и пишущая головка может читать буквы любого заданного алфавита А={a0, а1, ...,аm}, при этом она может эти буквы и стирать и печатать. Каждая ячейка в любой момент времени занята буквой из множества А, часто используется буква а0. В каждый момент времени головка находится над некоторой ячейкой ленты или текущей рабочей ячейкой. Лента может перемещаться по лентопротяжному механизму так, что головка может перемежаться вправо(R) и влево (L), а так же стоять на месте (N). Если головка выходит за левый край ленты, то моментально происходит «аварийная ситуация», то есть происходит машинный останов, когда машина выполняет предписание об остановке.

Работа машины Тьюринга задаётся перечислением элементов множества букв алфавита A, множества состояний Q и набором правил, по которым она работает. Правила имеют такой вид: qiaj→qi1aj1dk. «Другими словами, если головка находится в состоянии qi, а в обозреваемой ячейке записана буква aj, то головка переходит в состояние qi1, в ячейку вместо aj записывается aj1, головка делает движение dk, которое имеет три варианта: влево, вправо и на месте. Для каждой возможной конфигурации имеется ровно одно правило (для недетерминированной машины Тьюринга может быть большее количество правил). Правил нет только для заключительного состояния, попав в которое машина останавливается. Кроме того, необходимо указать конечное и начальное состояния, начальную конфигурацию на ленте и расположение головки машины»[7].

Пример: пускай на ленте имеются символы #, $, 1 и 0. Требуется заменить символы # и $ на нули. Головка в момент запуска над первой буквой слева.

Рисунок 1.3 - Пример задачи 1

Этот же пример можно представить так:

Рисунок 1.4 - Пример задачи 2

В данном примере головка сдвигается до тех пор, пока не окажется над пустым символом. После выполнения этого шага происходит переход в состояние q2 и происходит выполнение данной задачи. # и $ изменяются в 0. После чего, программа обратно переходит в состояние q0 и останавливается.

1.5 Машина Поста

Данная абстрактная машина была предложена Э. Постом в 1937 году. Эта вычислительная машина проста в применении, этим она и отличается от машины Тьюринга.

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

2) С - стереть метку.

3) <- - сдвинуться влево.

4) -> - сдвинуться вправо.

5) m2

- если в ячейке нет метки, то перейти к m2 строке программы,

m1

иначе перейти к m1 строке программы.

6) Стоп - конец программы (стоп).

Рисунок 1.2 - Абстрактная машина Поста

После запуска программы машина Поста имеет несколько возможных вариантов работы:

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

- работа может закончиться командой «Стоп»;

- работа никогда не закончится.

Пример: головка стоит слева над начальной ячейкой. Нужно перейти на следующую пустую ячейку и поставить там метку.

Решение:

1 -> 2

2 M 3

3 Стоп.

Машина Поста также была предложена для формализации понятия алгоритм.

Заключение

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

Можно говорить о том, что понятие «алгоритм» применяется в большинстве наук.

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

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

Цель работы была достигнута. Поставленные задачи были решены.

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

Библиографический список

1. Методика преподавания информатики: учеб. пособие для студ. пед. вузов / М.П. Лапчик, И.Г. Семакин, Е.К. Хеннер; под общей ред.

2. BOREL E. Le calcul des integrales definies // Journal de Mathematiques pures et appliquees. Ser. 6. - V.8, № 2. 1912. - P.159-210.

3. Математическая логика и вычислительная математика // Вестник Академии наук СССР. №8. - с.21-25

4. Википедия - свободная энциклопедия // Алгоритм. -(Рус).

-URL: ru.wikipedia.org/wiki/Алгоритм [дата обращения 9 апреля 2013]

5. Ахо А., Хопкрофт Дж., Ульман Дж. Построение и анализ вычислительных алгоритмов: Пер. с англ.-М.: Мир,1979.

6. Википедия - свободная энциклопедия // Машина Поста. -(Рус). -URL: ru.wikipedia.org/wiki/Машина_Поста [дата обращения 8 апреля 2013]

7. Википедия - свободная энциклопедия // Машина Тьюринга.

-(Рус). -URL: ru.wikipedia.org/wiki/Машина_Тьюринга [дата обращения 8 апреля 2013]

21